Số lượng gợi ý tối thiểu mà một Sudoku có thể có là bao nhiêu?
Cập nhật lần cuối
Một Sudoku hợp lệ - Một Sudoku có chính xác một lời giải - Yêu cầu ít nhất 17 chữ số cho trước. Đây là một kết quả toán học đã được chứng minh. Bất kỳ câu đố nào có 16 manh mối trở xuống đều có nhiều lời giải hoặc không có lời giải nào.
Chứng minh năm 2012
Vào năm 2012, Gary McGuire, Bastian Tugemann và Gilles Civario tại University College Dublin đã công bố một chứng minh rằng không có Sudoku 16 manh mối hợp lệ nào tồn tại. Công trình của họ chủ yếu là tính toán: họ đã tìm kiếm toàn bộ không gian của các lưới 16 manh mối có thể và xác minh rằng không có lưới nào tạo ra một giải pháp duy nhất. Cuộc tìm kiếm yêu cầu khoảng 7 triệu giờ lõi tính toán.
Trước đó, người ta tin rộng rãi rằng 17 là tối thiểu và hàng nghìn câu đố 17 manh mối đã được tìm thấy bằng thực nghiệm. Nhóm của McGuire đã cung cấp chứng minh chặt chẽ đầu tiên rằng 16 là không thể.
Câu đố 17 gợi ý trông như thế nào
Các câu đố 17 manh mối cực kỳ thưa thớt - 17 chữ số cho trước trong 81 ô, để lại 64 ô trống. Chúng là một trong những câu đố khó nhất để giải và thường yêu cầu các kỹ thuật nâng cao. Việc tìm ra các câu đố 17 manh mối hợp lệ tự nó đã đòi hỏi nhiều thập kỷ nỗ lực tính toán. Tính đến thời điểm viết bài, hơn 49.000 câu đố Sudoku 17 manh mối khác nhau về cơ bản đã được biết đến.
Điều này có nghĩa gì cho Thiết kế Câu đố
Các câu đố được xuất bản nhắm vào người giải hiếm khi có dưới 22 manh mối. Các câu đố độ khó Chuyên gia và Bậc thầy thường sử dụng 22-27 chữ số cho sẵn, trong khi các câu đố Dễ sử dụng 36-45. Mức tối thiểu 17 manh mối là một giới hạn lý thuyết - Trong thực tế, khả năng giải được với kỹ thuật tốt và một đường dẫn giải thú vị quan trọng hơn nhiều so với số lượng manh mối đơn thuần.