Jumlah minimum petunjuk untuk menentukan sepenuhnya sudoku?

Kita tahu dari makalah ini bahwa tidak ada puzzle yang dapat dipecahkan dimulai dengan 16 atau lebih sedikit petunjuk, tetapi itu menyiratkan bahwa ada sebuah puzzle yang dapat dipecahkan dari 17 petunjuk. Apakah semua teka-teki sudoku yang valid dapat ditentukan dalam 17 petunjuk? Jika tidak, berapakah jumlah minimum petunjuk yang sepenuhnya dapat menentukan setiap puzzle yang valid? Secara lebih formal, apakah ada teka-teki sudoku yang valid (atau, saya kira itu akan menjadi serangkaian teka-teki) yang tidak dapat dipecahkan secara unik hanya dari 17 petunjuk? Jika demikian, lalu berapa jumlah minimum petunjuk, , sehingga setiap teka-teki sudoku yang valid dapat secara unik ditentukan dalam C atau lebih sedikit petunjuk?$C$$C$

Karena mengubah dua baris dalam satu blok tunggal dari sudoku yang valid dan selesai, menghasilkan sudoku lain yang lengkap dan sah, Anda dapat mengambil papan apa saja yang sudah selesai (81 petunjuk) dan menghapus dua baris pertama (81-18 = 63 petunjuk), yang akan memberi Anda sudoku tidak lengkap dengan dua solusi. Perhatikan bahwa meskipun Anda menghapus semua kecuali satu dari 18 angka di sana, solusinya langsung ditentukan secara unik (karena tidak ada nomor yang diulang dalam kolom yang sama).

Operasi lain yang menghasilkan sudoku lengkap lainnya adalah menerapkan permutasi . Jika Anda mengambil permutasi yang merupakan transposisi (memungkinkan dua elemen, menjaga yang lainnya tetap), sekali lagi, seperti sebelumnya, Anda dapat menghapus semua tampilan dari kedua elemen tersebut dan Anda memiliki sudoku yang tidak lengkap dengan dua solusi yang mungkin dan 63 petunjuk. Sekali lagi, jika Anda tidak menghapus semua 18 angka, solusinya akan unik.$\{1,\ldots,9\}$

Dari enam operasi elemen yang menghasilkan sudoku lengkap (lihat di sini ), keduanya adalah yang dapat melibatkan jumlah elemen paling sedikit, jadi saya akan mengatakan adalah batas atas untuk apa yang Anda cari. Saya tahu ini tidak persis menjawab pertanyaan Anda, tetapi gagasan umum untuk menghapus set posisi yang menghasilkan dua solusi berbeda mungkin merupakan titik awal yang baik.$C=63$

Itu paling sedikit petunjuk yang diperlukan untuk tepat Sudoku adalah 17, tetapi tidak semua selesai grid dapat dikurangi dengan 17 petunjuk yang tepat Sudoku. Sekitar 49.000 Sudokus unik (tidak setara) dengan 17 petunjuk telah ditemukan. (Sudoku yang tepat hanya memiliki satu solusi).

Itu paling petunjuk dalam minimal Sudoku diyakini 40 (dua diketahui eksis), tetapi belum terbukti apakah ini maksimal. (minimal berarti jika ada petunjuk yang dihapus, Sudoku akan memiliki lebih dari satu solusi, dan karena itu bukan Sudoku yang tepat)

(Informasi ini dari Wikipedia, di mana pernyataan ini direferensikan dengan baik).

Sudoku ini memiliki 77 petunjuk namun memiliki beberapa solusi (2). Anda dapat menggunakan 7-4 di baris atas dan 4-7 di baris lainnya atau menggunakan 4-7 di atas dan 7-4 di bawah. Teka-teki Sudoku khusus ini membutuhkan 78 petunjuk untuk memiliki solusi yang unik.