Apakah bilangan petunjuk minimum yang boleh dimiliki oleh Sudoku?
Kemas kini terakhir
Sudoku yang sah - Satu dengan tepat satu penyelesaian - Memerlukan sekurang-kurangnya 17 digit yang diberi. Ini adalah hasil matematik yang terbukti. Mana-mana teka-teki dengan 16 atau kurang petunjuk sama ada mempunyai pelbagai penyelesaian atau tiada langsung.
Bukti 2012
Pada tahun 2012, Gary McGuire, Bastian Tugemann, dan Gilles Civario di University College Dublin menerbitkan bukti bahawa tiada Sudoku 16-clue yang sah wujud. Kerja mereka terutamanya pengiraan: mereka mencari seluruh ruang grid 16-clue yang mungkin dan mengesahkan bahawa tiada satu pun menghasilkan penyelesaian unik. Carian tersebut memerlukan kira-kira 7 juta core-hours pengiraan.
Sebelum ini, dipercayai secara meluas bahawa 17 adalah minimum dan ribuan teka-teki 17-clue telah ditemui secara eksperimen. Pasukan McGuire menyediakan bukti teliti pertama bahawa 16 adalah mustahil.
Rupa Bentuk Teka-teki 17-Clue
17-clue puzzles adalah extremely sparse - 17 given digits dalam 81 cells, meninggalkan 64 empty. Ia adalah antara hardest puzzles untuk diselesaikan dan typically memerlukan advanced techniques. Mencari valid 17-clue puzzles itself memerlukan decades of computational effort. Setakat masa penulisan ini, lebih 49,000 essentially different 17-clue Sudoku puzzles diketahui.
Apa Maknanya untuk Reka Bentuk Teka-teki
Teka-teki yang diterbitkan untuk penyelesai manusia jarang pergi ke bawah 22 clues. Expert dan Master difficulty puzzles biasanya menggunakan 22-27 given digits, manakala Easy puzzles menggunakan 36-45. Minimum 17-clue adalah batas teori - Dalam amalan, kebolehselesaian dengan teknik yang baik dan laluan penyelesaian yang menyeronokkan jauh lebih penting daripada jumlah clue sahaja.