Tổng quan
Giải Sudoku là quay lui ở dạng dễ đọc nhất. Tìm một ô trống, thử một chữ số không vi phạm luật ngay lập tức, đệ quy, và nếu nhánh đệ quy thất bại thì xóa chữ số đó đi rồi thử số kế tiếp.
Thứ khiến nó kết thúc được là phép cắt tỉa. Tìm kiếm mù sẽ thử 9 chữ số ở mỗi ô trống, với một câu đố điển hình là con số dài năm mươi chữ số. Kiểm tra hàng, cột và ô vuông 3×3 trước khi đệ quy sẽ giết phần áp đảo các nhánh đó ngay tại nút đầu tiên, và phần tìm kiếm còn lại đủ nhỏ để chạy trong vài mili-giây.
Giải Sudoku hoạt động thế nào?
- Quét lưới tìm ô trống kế tiếp. Nếu không còn ô nào, câu đố đã được giải.
- Với mỗi chữ số từ 1 đến 9, kiểm tra xem nó đã xuất hiện trong hàng, cột, hay ô vuông 3×3 của ô đó chưa.
- Nếu chữ số hợp lệ, điền vào rồi đệ quy trên phần lưới còn lại.
- Nếu nhánh đệ quy báo thành công, đẩy kết quả thành công lên trên và dừng.
- Nếu thất bại, xóa chữ số đi — đây chính là bước quay lui — rồi thử ứng viên tiếp theo. Nếu cả chín đều hỏng, báo thất bại về cho nơi gọi.
Khi nào nên dùng?
- Ví dụ dạy quay lui rõ ràng nhất, vì trạng thái, ràng buộc và bước hoàn tác đều nhìn thấy được trên cùng một lưới.
- Cùng bộ khung đó giải được N-Hậu, tô màu đồ thị, ô chữ và các bài phủ chính xác — chỉ phép kiểm tra hợp lệ là khác.
- Các bài thỏa mãn ràng buộc trong xếp lịch và thời khóa biểu, khi một phép gán từng phần phải được hoàn tác nếu dẫn tới ngõ cụt.
- Sinh câu đố chứ không chỉ giải: sinh một lưới đã điền đầy, rồi bỏ dần các gợi ý chừng nào bộ giải vẫn báo có nghiệm duy nhất.
Phân tích độ phức tạp
Trường hợp xấu nhất là O(9^m) với m là số ô trống, vì về nguyên tắc mỗi ô có thể nhận một trong chín chữ số. Cận đó gần như vô nghĩa trong thực tế: phép kiểm tra ràng buộc loại bỏ phần lớn các nhánh trước khi bước vào, và một câu đố hợp lệ được giải nhanh hơn nhiều so với số mũ gợi ý. Bộ nhớ là O(m) cho ngăn xếp đệ quy — bản thân lưới được sửa tại chỗ và khôi phục trên đường quay lên.
Câu hỏi thường gặp
Vì sao lại xóa chữ số thay vì sao chép cả lưới?
Sao chép lưới 81 ô ở mỗi nút sẽ chiếm hết thời gian chạy lẫn bộ nhớ. Ghi vào rồi xóa đi giữ được một lưới duy nhất luôn nhất quán với đường đi hiện tại, và đó là thứ khiến quay lui rẻ.
Thứ tự chọn ô trống có quan trọng không?
Rất quan trọng. Quét theo thứ tự đọc là bản đơn giản; chọn trước ô trống có ít ứng viên hợp lệ nhất — heuristic 'ít lựa chọn còn lại nhất' — thường cắt không gian tìm kiếm đi vài bậc, vì nó buộc mâu thuẫn lộ ra sớm.
Làm sao bộ giải biết một câu đố có nhiều hơn một nghiệm?
Đừng dừng ở nghiệm đầu tiên. Cứ đếm tiếp và dừng khi đạt hai — một câu đố Sudoku đúng chuẩn được định nghĩa là có đúng một nghiệm, và đây chính là phép kiểm tra dùng khi sinh câu đố.