Bạn đã thấy trò chơi Sudoku? không nghi ngờ gì nữa, vì ngày nay, nó phổ biến trên các báo và tạp chí. Trông nó như thế này:
Nhiệm vụ của bạn là điền vào trong các ô bỏ trống với những chữ số từ 1-9 theo cách như vậy mỗi hàng, cột và khối 3x3 chứa mỗi con số chính xác một lần. Trong một trò chơi thích hợp, các đầu mối bắt đầu như vậy để đảm bảo có 1 và chỉ một cách để hoàn thành hình vuông.
Trò chơi này đặc biệt chỉ có 17 đầu mối bắt đầu. Nó đã từ lâu được tin rằng 17 là số lượng tối thiểu cho bất kỳ 1 trò chơi thích hợp. Nhà toán học Gordon Royle duy trì một cơ sở dữ liệu trực tuyến hiện có gần 50.000 câu đố với 17 đầu mối bắt đầu (trong thực tế, các câu đố trên được chuyển thể từ một trong những câu đố trong danh sách đó). Tuy nhiên, mặc dù tìm kiếm bằng máy tính, người ta vẫn không tìm thấy ví dụ cho 1 trò chơi với 16 hoặc ít hơn những đầu mối.
Vấn đề là tìm kiếm máy tính đầy đủ dường như không thể. Đơn giản bởi có quá nhiều khả năng để xem xét. Ngay cả bằng cách sử dụng các phần cứng hiện đại nhất, và sử dụng các kỹ thuật tìm kiếm hiệu quả nhất được biết đến, hàng trăm hàng ngàn năm mới được yêu cầu.
Tương tự, Toán học thuần túy cũng hỗ trợ được rất ít. Nó rất dễ dàng để thấy rằng bảy đầu mối là không đủ. Với bảy đầu mối bắt đầu sẽ có ít nhất hai chữ số mà không được xuất hiện khi bắt đầu trò chơi. Để cụ thể, chúng ta hãy nói rằng đã có không có số 1 hoặc 2 trong bảng bắt đầu. Khi đó, trong bất kỳ cách hoàn thành nào, chỉ cần thay các ô 1 bởi 2 và các ô 2 bởi 1, ta sẽ tạo ra một lời giải thứ hai hợp lệ để câu đố. Tuy nhiên, sau khi quan sát này, ta đã không biết làm thế nào để tiếp tục. Ngay cả một lập luận đơn giản là chứng minh sự bất cập của tám đầu mối đã được khẳng định là rất khó
Giải pháp của McGuire đòi hỏi một sự kết hợp của toán học và khoa học máy tính. Để giảm thời gian cần thiết cho một tìm kiếm đầy đủ, ông đưa ra ý tưởng về một "tập hợp không thể tránh khỏi" (Hãy xét các ô được tô đậm)
Bây giờ tưởng tượng ra một câu đố bắt đầu có hình vuông này cho một giải pháp. Bạn có thể thấy lý do tại sao chúng ta sẽ cần phải có ít nhất một đầu mối bắt đầu từ một trong những “tế bào” được tô đậm? Lý do là nếu không như vậy, sau đó ta sẽ có thể chuyển đổi các chữ số trong các ô để tạo ra một giải pháp thứ hai cho cùng một câu đố. Trong thực tế, đặc biệt Sudoku vuông, có rất nhiều bộ tương tự như "bộ không thể tránh khỏi", nói chung một số hình vuông sẽ có nhiều hơn những cái khác, và các loại khác nhau. Một phần của giải pháp McGuire liên quan đến việc tìm kiếm một bộ sưu tập lớn của một số "các bộ không thể tránh khỏi" trong mỗi hình vuông Sudoku được xem xét.
Tìm kiếm các "bộ không thể tránh khỏi" cho phép giảm đáng kể kích thước của không gian phải được tìm kiếm. Thay vì tìm kiếm thông qua tất cả các tập hợp con 16 đầu mối của một Sudoku vuông, sự tìm kiếm tuyệt vọng thực sự cho một câu đố thích hợp, chúng tôi chỉ cần xem xét tập hợp của 16 đầu mối bắt đầu có chứa ít nhất một “tế bào” từ mỗi “bộ không thể tránh khỏi” được biết đến. Tìm kiếm những bộ cụ thể của các đầu mối bắt đầu là 1 ví dụ cụ thể của 1 vấn đề tổng quát hơn, đó là thuật toán để giải quyết các vấn đề tập hợp đánh một lượng hợp lý "vấn đề tập hợp đánh." số lần. Giải quyết vấn đề tối thiểu đầu mối cho Sudoku là một ứng dụng của thuật toán mới này.
Tất nhiên, thận trọng là cần thiết cho đến khi các nhà nghiên cứu có thời gian để kiểm tra kỹ các lập luận của McGuire. Nó là một trong những sự “tàn bạo” của toán học nhằm cẩn thận tránh những lỗi tinh tế của các nghiên cứu viên. Chúng ta chắc chắn có thể nói, mặc dù, rằng các kỹ thuật đang được sử dụng ở đây là rất chính đáng và thú vị. Họ cũng có thể là hữu ích cho việc đánh bóng "đầu mối tối thiểu" các vấn đề trong Sudoku. Ví dụ, nếu chúng tôi yêu cầu rằng các đầu mối bắt đầu được đặt đối xứng, sau đó 18 đầu mối là nhỏ nhất được biết đến (như được hiển thị bên dưới bên trái, câu đố lấy từ Taking Sudoku Seriously). Mặt khác, Sudoku X, trong đó các 2 chính đường chéo tham gia các hàng, cột và các khối là khu vực hợp lệ Sudoku, các tối thiểu hiện nay là 12 (xem bên dưới phải; câu đố phù hợp từ một bộ sưu tập trực tuyến Ruud của 12-đầu mối Sudoku X).
Sodoku X
Bài báo của McGuire minh họa hai trong số những thực tế của toán học hiện đại. Đầu tiên là vai trò nổi bật của máy tính. Ngày nay nó là ngày càng khó khăn để xác định câu đố nên được xem như các vấn đề toán học, và thực sự là vấn đề cho các nhà khoa học máy tính.
Tuy nhiên, thứ hai là tốc độ phát hiện toán học. Chúng ta đã học được của công việc McGuire như chúng ta đã đi đến một hội nghị toán học mà chúng tôi đã tổ chức một phiên họp về các câu đố Sudoku. Một người trong chúng ta đã có một cuộc nói chuyện chuẩn bị, trong đó vấn đề này được mô tả là chưa được giải quyết. Nó rất thú vị để có thể sử dụng hội nghị để báo cáo về sự phát triển này. Cuốn sách về toán học của Sudoku của chúng ta đã chỉ ra trong một vài tuần, nhưng nó có thể đã bị lỗi thời, ít nhất là đối với một vấn đề này.
Hoàng Ngọc Thế dịch từ http://blog.oup.com
Bài viết đã được chỉnh sửa nội dung bởi Ban Biên Tập: 10-03-2012 - 00:33
