Berapa jumlah minimum bit yang diperlukan untuk menyimpan puzzle sudoku?

Catatan: Ini tentang puzzle sudoku 9x9 standar. Solusinya hanya harus mendukung teka-teki hukum yang diselesaikan . Jadi solusi tidak perlu mendukung sel kosong dan dapat mengandalkan properti dari teka-teki sudoku yang terpecahkan.

Saya bertanya-tanya tentang hal ini, tetapi saya tidak dapat menemukan jawaban yang puas. Solusi naif akan menggunakan satu byte untuk setiap sel (81 sel), dengan total 648 bit. Solusi yang lebih canggih akan menyimpan seluruh teka-teki sudoku dalam angka basis-9 (satu digit per sel) dan membutuhkan bit.$\lceil\log_2(9^{81}))\rceil = 257$

Tetapi masih bisa ditingkatkan, misalnya, jika Anda tahu 8 dari 9 angka dalam subgrid 3x3 Anda dapat dengan mudah menyimpulkan yang ke-9. Anda dapat melanjutkan pemikiran ini ke titik di mana pertanyaan ini bermuara pada Berapa jumlah sudokus terpecahkan yang unik? Sekarang Anda dapat menggunakan tabel pencarian besar yang memetakan setiap nomor biner ke teka-teki sudoku, tetapi itu tidak akan menjadi solusi yang dapat digunakan.

Jadi, pertanyaan saya:

Tanpa menggunakan tabel pencarian, berapakah jumlah bit minimum yang diperlukan untuk menyimpan puzzle sudoku dan dengan algoritma apa?

Sepanjang baris yang sama dengan jawaban ratchet freak, jika Anda mengisi sel-sel non-bintang di matriks berikut, kotak 3x3 sekaligus, selalu memilih kotak berikutnya untuk diisi menjadi kotak yang berbagi baris atau kolom dengan kotak yang Anda Sudah diisi, Anda mendapatkan pola seperti berikut untuk jumlah pilihan per langkah (mengisi kotak tengah atas pertama, kotak kanan atas berikutnya, dll).

Di setiap kotak 3x3 setelah yang pertama, setelah Anda mengisi satu baris atau kolom kotak, tiga dari enam digit yang tersisa dilokalkan ke satu baris. Pilih lokasi mereka terlebih dahulu, lalu isi tiga sel yang tersisa. (Jadi urutan aktual sel mana yang akan diisi mungkin bervariasi tergantung pada apa yang sudah Anda ketahui, tetapi jumlah pilihan tidak pernah lebih dari apa yang saya tunjukkan.)

Setelah Anda mengisi sel-sel ini, semua bintang ditentukan.

* * * 9 8 7 6 5 4
* * * 6 5 4 3 3 2
* * * 3 2 1 3 2 1

6 5 4 * * * 6 3 3
3 3 2 * * * 5 3 2
3 2 1 * * * 4 2 1

6 3 3 6 5 4 * * *
5 3 2 3 3 2 * * *
4 2 1 3 2 1 * * *

Jika saya menghitung dengan benar, ini menghasilkan 87 bit. Ada beberapa penghematan tambahan yang bisa didapat di blok 3x3 terakhir, per komentar oleh Peter Shor: setiap nilai dilokalkan ke satu dari empat sel, dan setiap baris mengandung setidaknya satu sel dengan hanya empat nilai yang mungkin, jadi tentu saja faktor-faktor di dalamnya blok harus dimulai dengan 4 bukan 6, tapi saya tidak mengerti faktor yang tersisa dalam jawaban Shor.

terjadi dengan jawaban @ peter berikut daftar kemungkinan terburuk untuk setiap sel saat Anda mengisinya mulai dari kiri atas

9   8   7       6   5   4       3   2   1
6   5   4       6   5   4       3   2   1
3   2   1       3   2   1       3   2   1

6   6   3       6   5   4       3   2   1
5   5   2       5   5   3       3   2   1
4   4   1       4   2   1       3   2   1

3   3   3       3   3   3       1   1   1
2   2   2       2   2   2       1   1   1
1   1   1       1   1   1       1   1   1

ini membuat untuk 4.24559E + 29 kemungkinan atau 99 bit

sunting: lupa bahwa kotak terakhir sepenuhnya ditentukan oleh semua yang lain

Anda tidak perlu tabel pencarian lengkap untuk mencapai kompresibilitas optimal. Saya percaya bahwa komputer modern yang menggunakan tabel look-up yang sangat masuk akal dapat menghitung jumlah Sudokus yang dibatasi , yaitu Sudokus dengan beberapa digit yang sudah ada. Menggunakan ini, inilah cara Anda menyandikan (decoding mirip).

$d_1$$N_1$$d_1$$d_2$$N_2$$d_1$$d_2$$N = \sum_i N_i$

$72.4$

Sunting: Halaman Wikipedia tentang matematika Sudoku membantu kami mengklarifikasi gambar. Juga membantu adalah tabel yang disusun oleh Ed Russell .

Ternyata jika Anda hanya mempertimbangkan tiga baris teratas, maka pada dasarnya hanya ada 44 konfigurasi yang berbeda untuk dipertimbangkan. Dalam tabel, Anda dapat menemukan jumlah total konfigurasi yang setara dengan yang diberikan (dengan asumsi bahwa baris teratas adalah 123456789), dan jumlah total penyelesaian masing-masing. Diberikan Sudoku, berikut ini cara menghitung angka ordinalnya:

1. Normalisasikan konfigurasi sehingga baris teratasnya adalah 123456789.
2. Cari tahu dari 44 konfigurasi berbeda yang dimiliki. Artikel Wikipedia memberikan algoritma untuk itu. Tabel ini mencantumkan jumlah kelas ekivalensi untuk setiap konfigurasi, serta jumlah penyelesaian.
3. Tentukan nomor urut konfigurasi dari tiga baris teratas di dalam kelas ekivalennya. Ini dapat dilakukan dengan dua cara: baik menggunakan daftar semua kelas kesetaraan (ada total 36288 di semua kelas kesetaraan), atau dengan menemukan cara untuk dengan cepat menyebutkan semuanya.
4. Normalisasi baris yang tersisa dengan mengurutkan baris 4-6 dan 7-9 dengan kolom pertama mereka, dan kemudian mengurutkan dua blok baris ini dengan cara yang sewenang-wenang. Ini mengurangi jumlah penyelesaian dengan faktor 72.
5. $2^{20}$
6. $i$$j$$k$$C_i,D_i$$C_i + jD_i + k$$9! \cdot 72$

Prosedur ini dapat dibalik, dan akan menghasilkan Sudoku dari nomor urut. Perhatikan bahwa pencacahan Sudoku telah dikurangi menjadi beberapa menit (pada tahun 2006; lihat halaman pembicaraan artikel Wikipedia) atau kurang, jadi saya berharap bahwa pada komputer modern pendekatan ini akan sangat praktis dan membutuhkan waktu beberapa detik atau kurang.

Berikut ini adalah algoritma yang saya duga akan menghasilkan pengkodean yang cukup bagus. Anda telah menyelesaikan sudoku yang ingin Anda kompres, dan katakanlah Anda telah menyandikan beberapa selnya, jadi ada sebagian sudoku (tidak harus dengan solusi unik) dengan beberapa sel terisi.

Gunakan algoritma tetap untuk menghitung berapa banyak angka yang dapat ditempatkan ke setiap sel kosong. Temukan sel pertama secara leksikografis ke mana jumlah terkecil dari nomor yang berbeda dapat ditempatkan, dan mengkodekan salah satu dari angka-angka ini masuk ke dalamnya (jadi jika sel hanya dapat berisi 3, 7, atau 9, 3 dikodekan oleh "0 ", 7 oleh" 1 "dan 9 oleh" 2 "). Encode urutan yang dihasilkan dengan menggunakan pengkodean aritmatika (yang memperhitungkan jumlah angka yang mungkin dimiliki sel).

Saya tidak tahu berapa lama urutan biner yang dihasilkan, tetapi saya menduga itu cukup singkat, terutama jika algoritma Anda untuk menghitung berapa banyak angka yang dapat ditempatkan ke dalam sel cukup canggih.

Jika Anda memiliki algoritme yang baik yang memperkirakan probabilitas setiap sel yang berisi angka tertentu, Anda bisa melakukannya lebih baik lagi.

Setiap komentar dan kritik diterima

$69.96$$171.72$

1.) Menyimpan puzzle berarti menyimpan solusi (informasi secara teoritis).

$t(\alpha)\alpha^{2}$$t(\alpha)$$\alpha$$t(3) ~= 2.44444$$3$

$P$$\alpha^{4}$$t(\alpha)\alpha^{2}$

$M$$\beta \times \alpha^{4}$$\beta \ge 2t(\alpha)\alpha^{2}$$2t(\alpha)\alpha^{2}$$\{0,\pm 1\}$$\beta = kt(\alpha)\alpha^{2}$$k$

$V = MP$$\beta$$|\alpha^{2}|$$M$$\{0,\pm 1\}$

$V$$\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$

$\alpha = 3$$t(\alpha) ~= 3$$2kt(\alpha)\alpha^{2}\log{\alpha} = 69.96k$$85.86k$$k=2$$139.92$$171.72bits$

$MP$

$A.)$$k$$2$$t(\alpha)-1$

$B.)$$t(\alpha)$$t(\alpha)$$k$$t(\alpha)$${}^{\alpha^{4}}C_{t(\alpha)\alpha^{2}}$${}^{\alpha^{4}-(3\alpha^{2} - 1)}C_{t(\alpha)\alpha^{2}-3t(\alpha)}$

$t(\alpha)\alpha^{2}$

$C.)$$k$

$D.)$ $V$$V$$O(\sqrt(V_{max})) = O(\sqrt{|\alpha^{2}|})$$2$$\beta\log{\alpha^{2}} = 2kt(\alpha)\alpha^{2}\log{\alpha}$

$2k$$2$$A.)$$B.)$$C.)$$D.)$$89$$73$

Ini untuk melaporkan implementasi pengkodean sudoku yang lengkap (mirip dengan saran oleh Zurui Wang 9/14/11).

Inputnya adalah baris teratas dan 3 digit pertama dari baris kedua. Ini dikurangi menjadi 1-9! dan 1-120 dan digabungkan menjadi <= 4.4x10 ^ 7. Ini digunakan sebagai givens untuk menghitung secara leksikografis semua sukokus parsial dari 30 digit hingga urutan yang cocok. Kemudian penghitungan akhir hingga seluruh 81 digit dilakukan dengan cara yang sama. 3 sekuens ini disimpan sebagai bilangan bulat 32-bit dari maks 26 bit, sehingga dapat dikompresi lebih lanjut. Seluruh proses memakan waktu sekitar 3 menit, dengan 30 digit pertama menghabiskan sebagian besar waktu. Penguraiannya mirip - kecuali pencocokan jumlah alih-alih sudokus.

Segera hadir - Revisi mencakup 3 digit pertama baris kedua dalam enumerasi 30 digit penyelesaian (kode 32-bit kedua), perbandingan dengan enumerasi Jarvis (Jscott, 3/1615)

Saya akan pergi dengan analisis sederhana berikut:

Setiap nilai dapat disimpan dalam 4 bit (berkisar 1-9, tiga bit ini bahkan memungkinkan untuk 0-16)

$9 \times 9 = 81$

$8 \times 8$

Saya kira saya bisa menguranginya menjadi:

$b = \lceil \log_2(v) \rceil (n-1)$

dimana

$v$

$n$

Sunting: Neo Style: Saya tahu Lateks.

Angka itu berbeda untuk setiap Sudoku. Salah satu aturan untuk Sudoku adalah memiliki satu solusi.

Jadi jika Anda melihat contoh, itu adalah jumlah minimum data yang harus Anda simpan.

Jika Anda bekerja dari sisi yang berlawanan, Anda dapat menghapus digit demi digit dan menjalankan solver pada hasilnya untuk melihat apakah masih memiliki satu solusi. Jika demikian, Anda dapat menghapus digit lainnya. Jika tidak, Anda harus mengembalikan digit ini dan coba yang lain. Jika Anda tidak bisa, Anda telah menemukan minimum.

Karena sebagian besar teka-teki mulai kosong, enkode panjang run mungkin akan menghasilkan hasil yang baik.