Bách khoa toàn thư Sudoku · Toán học và máy tính

Toán học của Sudoku

Cập nhật 2026-10-05

Một hình vuông Latin có thêm khối

Trong một hình vuông Latin, mỗi ký hiệu xuất hiện một lần ở mỗi hàng và mỗi cột. Một Sudoku đã hoàn thành là một hình vuông Latin cỡ 9 có thêm một điều kiện: mỗi khối trong chín khối 3×3 cũng chứa mọi chữ số, mỗi số một lần.

Nguồn: Wikipedia: Latin square

Có bao nhiêu lưới

Năm 2005, Bertram Felgenhauer và Frazer Jarvis đã đếm số lưới 9×9 hoàn chỉnh: có 6.670.903.752.021.072.936.960 lưới, khoảng 6,67 × 10²¹. Nhiều lưới trong số đó thực chất là cùng một lưới được ngụy trang. Nếu coi hai lưới là một khi có thể biến lưới này thành lưới kia bằng cách đặt lại nhãn các chữ số, xoay hoặc lật, hoặc sắp xếp lại hàng và cột theo những cách giữ cho lưới hợp lệ, thì còn lại 5.472.730.538 lưới khác biệt về bản chất, một con số do Ed Russell và Frazer Jarvis tính ra.

Nguồn: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Mức tối thiểu 17 manh mối

Không có Sudoku 9×9 tiêu chuẩn nào với 16 số cho sẵn trở xuống có đúng một lời giải. Gary McGuire, Bastian Tugemann và Gilles Civario đã chứng minh điều này bằng một cuộc tìm kiếm vét cạn trên máy tính và công bố kết quả vào tháng 1 năm 2012. Mười bảy là mức tối thiểu, không phải sự bảo đảm: nhiều lưới có 17 số cho sẵn vẫn có nhiều hơn một lời giải.

Nguồn: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku như bài toán tô màu đồ thị

Vẽ một điểm cho mỗi ô trong 81 ô và nối hai điểm bất cứ khi nào hai ô tương ứng cùng chung một hàng, một cột hoặc một khối. Đồ thị Sudoku này có 810 đường nối, và mỗi điểm có đúng 20 điểm kề. Giải câu đố nghĩa là mở rộng các màu đã được cố định bởi số cho sẵn sao cho hai điểm được nối với nhau không bao giờ cùng màu. Cần ít nhất chín màu, vì mỗi hàng, cột và khối là một nhóm chín điểm đều được nối với nhau, và bất kỳ lưới hoàn chỉnh nào cũng cho thấy chín màu là đủ.

Nguồn: Wikipedia: Sudoku graph

Khó trong trường hợp tổng quát, nhanh với lưới 9×9

Với các lưới Sudoku có thể lớn lên không giới hạn (n²×n² với các khối n×n), việc xác định một lưới đã điền một phần có thể hoàn thành được hay không là bài toán NP-đầy đủ, một kết quả được Takayuki Yato và Takahiro Seta công bố năm 2003. Các chương trình máy tính hiệu quả thường giải những câu đố 9×9 thông thường trong chưa đến một giây, dù thời gian còn phụ thuộc vào chương trình, máy tính và câu đố.

Nguồn: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Xem thêm

Nguồn

Tất cả bài viết →