Berapa jumlah minimum petunjuk yang dapat dimiliki Sudoku?
Terakhir diperbarui
Sudoku yang valid - yang memiliki tepat satu solusi - membutuhkan setidaknya 17 digit yang diberikan. Ini adalah hasil matematika yang terbukti. Teka-teki dengan 16 petunjuk atau kurang memiliki banyak solusi atau tidak sama sekali.
Bukti 2012
Pada tahun 2012, Gary McGuire, Bastian Tugemann, dan Gilles Civario di University College Dublin menerbitkan bukti bahwa tidak ada Sudoku 16-petunjuk yang valid. Pekerjaan mereka terutama bersifat komputasional: mereka mencari seluruh ruang kemungkinan grid 16-petunjuk dan memverifikasi bahwa tidak ada yang menghasilkan solusi unik. Pencarian tersebut membutuhkan sekitar 7 juta jam-inti komputasi.
Sebelum ini, diyakini secara luas bahwa 17 adalah minimum dan ribuan teka-teki 17-petunjuk telah ditemukan secara eksperimental. Tim McGuire memberikan bukti ketat pertama bahwa 16 tidak mungkin.
Seperti Apa Tampilan Teka-teki 17-Clue
Teka-teki dengan 17 petunjuk sangat jarang - 17 digit yang diberikan dalam 81 sel, menyisakan 64 kosong. Mereka termasuk teka-teki tersulit untuk dipecahkan dan biasanya memerlukan teknik lanjutan. Menemukan teka-teki 17 petunjuk yang valid sendiri memerlukan upaya komputasi selama puluhan tahun. Pada saat penulisan ini, lebih dari 49.000 teka-teki Sudoku 17 petunjuk yang pada dasarnya berbeda telah diketahui.
Apa Artinya Ini untuk Desain Teka-teki
Teka-teki yang diterbitkan yang ditujukan untuk pemecah manusia jarang turun di bawah 22 petunjuk. Teka-teki tingkat Expert dan Master biasanya menggunakan 22-27 digit yang diberikan, sementara teka-teki Mudah menggunakan 36-45. Minimum 17-petunjuk adalah batas teoretis - Dalam praktiknya, kemampuan pemecahan dengan teknik yang baik dan jalur pemecahan yang menyenangkan jauh lebih penting daripada jumlah petunjuk saja.