Sudoku FlowMáy tính giải Sudoku như thế nào
Cập nhật 2026-10-05
Quay lui
Trình giải thử một chữ số hợp lệ vào một ô trống rồi tiếp tục. Nếu không chữ số nào dẫn tới lời giải, nó hoàn tác một lựa chọn trước đó và thử chữ số khác. Chọn trước ô có ít chữ số khả dĩ nhất thường giúp việc tìm kiếm ngắn hơn nhiều.
Nguồn: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Phủ chính xác và Dancing Links
Sudoku có thể được viết lại thành một bài toán phủ chính xác: chọn các cách đặt số sao cho mỗi ô, và mỗi chữ số trong mỗi hàng, cột và khối, đều được phủ đúng một lần. Trong một bài báo từ tháng 11 năm 2000, Donald Knuth mô tả Dancing Links, một cách hiệu quả để chạy Thuật toán X, thuật toán quay lui của ông; khi áp dụng cho mô hình phủ chính xác của Sudoku, nó nhanh chóng tìm ra mọi lời giải của một câu đố.
Nguồn: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Tìm kiếm ngẫu nhiên
Một số chương trình điền lưới một cách ngẫu nhiên rồi xáo trộn các số để giảm số xung đột, bằng các phương pháp như mô phỏng luyện kim hoặc thuật toán di truyền. Chúng đã được nghiên cứu như những cách tiếp cận thay thế; hiệu quả của chúng phụ thuộc vào chương trình và câu đố.
Nguồn: Wikipedia: Sudoku solving algorithms
Trình giải suy nghĩ như con người
Một bộ máy gợi ý có nhiệm vụ khác: không chỉ tìm ra đáp án mà còn chỉ ra bước tiếp theo mà một người có thể làm theo. Bộ máy của ứng dụng chúng tôi thử các kỹ thuật của con người theo một thứ tự cố định, từ dễ nhất, như Đơn ẩn, đến khó nhất, như các chuỗi và tập gần khóa (almost locked sets), và dùng kỹ thuật đầu tiên dẫn tới một chữ số được đặt; các kỹ thuật khó hơn hoạt động bằng cách loại trừ ứng viên trước. Kỹ thuật khó nhất mà nó dùng cho một câu đố quyết định cấp độ của câu đố đó trong ứng dụng.
Nguồn: Mỗi cấp độ khó Sudoku đòi hỏi bạn những gì
