Sudoku là một trò chơi đại chúng rất thông dụng được các báo, tạp chí trên toàn thế giới đăng tải hàng ngày. Sudoku cũng đã hiện diện trên bán tuần báo Việt Luận, Sydney, Australia và  trong trang nhà “Đọc Vui và Suy Nghĩ”  (https://docvui-suynghi.net/) từ lâu.

Khung Sudoku tiêu chuẩn kích thước 9×9 gồm có 81 ô chia ra thành 9 hàng, 9 cột, 9 khối 3×3 với 3 dãy khối ngang và 3 dãy khối dọc. Mục đích của trò chơi Sudoku tiêu chuẩn là điền các con số trong khoảng 1 đến 9 vào các ô trống trong 81 ô của khung Sudoku sao cho mỗi hàng, mỗi cột và mỗi khối của khung đều có chứa tất cả các con số từ 1 đến 9.

Trò chơi Sudoku tiêu chuẩn bắt đầu với một khung với 81 ô vuông (hay chữ nhật), trên đó có một số ô đã được điền số gọi là các ô hướng dẩn (clues).

Một cách tương đối, độ khó của khung Sudoku tuỳ thuộc phần lớn ở số ô hướng dẩn.   Để ý rằng độ khó của khung Sudoku cũng tuỳ thuộc ở sự phân phối cũng như trị của các ô hướng dẩn.

Thông thường, khung Sudoku được xem là “dễ”  khi số ô hướng dẩn lớn hơn hay bằng 27, tức là bổ đồng mỗi khung có 3 hay nhiều hơn 3 ô hướng dẩn. Khung Sudoku được xem là “khó” khi số ô hướng dẩn ở vào khoảng từ 22 đến 27, đượcxem là “thử thách” khi số ô hướng dẩn nhỏ hơn 22.

Có nhiều Sudoku thật khó, chỉ có 17 ô hướng dẩn như khung Sudoku sau đây (Khung nầy có nhiều lời giải):

Người ta chưa thấy ai tìm được một khung Sudoku chỉ có 16 ô hướng dẩn. Nhà toán học Ái nhỉ lan Gary McGuire ở đại học Dublin, Ireland, đã quyết định đi tìm một khung như vậy.

Phương pháp của ông đơn giản như sau:

Ông tính ra tất cả các lời giải khả hữu của một khung Sudoku. Số nầy lớn kinh khủng:

                             6,670,903, 752, 021, 072, 936, 960

Sau khi loại bỏ những trường hợp đối xứng giữa các khối và hoán vị giữa các hàng và các cột, số đó rút gọn lại còn:

5,472,730,538

Sau đó, ông thảo một chương trình điện toán để xét từng lời giải và tìm xem có lời giải nào có thể tạo thành một khung Sudoku với 16 ô hướng dẩn không? Chương trình tìm những vùng nhỏ trên khung Sudoku bắt buộc phải cần một ô hướng dẩn. Chương trình được sửa đổi nhiều lần để làm cho chạy nhanh hơn, cho đến khi ông vừa ý.

Sau cùng, ông chia những sự tính toán ra làm nhiều công việc nhỏ và gởi đến siêu máy tính của đại học Dublin. Sau một năm với 7 triệu giờ CPU, tất cả công việc tính toán mới hoàn thành! Và kết quả là ông không tìm được một khung Sudoku nào với 16 ô hướng dẩn!  

Không thể có khung Sudoku với số  ô hướng dẩn nhỏ hơn 17.

Đó là kết luận của nhà toán học Gary McGuire trong buổi hội thảo toán học ở Boston ngày 7 tháng Giêng năm 2012 vừa qua. Các nhà toán học khác cũng đồng ý là phương pháp chứng minh của McGuire là hợp lý và là một bước tiến quan trọng trong lãnh vực toán học Sudoku.

Trở lại khung Sudoku với 17 ô hướng dẩn trong bài, Costas Palmer nói rằng khung có 9,734 lời giải, mà 2 lời giải đầu như sau:

Tất cả các lời giải có thể tìm thấy trong: http://www.nfactorial.co.uk/sols.txt

Thuận Hoà