Pecahkan Sudoku dengan Algoritma X

Pada artikel ini, kami mempertimbangkan Knuth "Algorithm X" dan aplikasinya untuk memecahkan sudoku. Keindahan algoritma ini adalah bahwa Sudoku diselesaikan dengan cepat tanpa memprogram teknik solusi tingkat lanjut.

Semuanya dimulai, pada kenyataannya, dengan tugas - tugas dari Project Euler , di mana, untuk mendapatkan jawaban, Anda harus menyelesaikan 50 sudoku. Dan sepertinya dia menerima jawaban untuk itu dengan menulis sebuah program untuk menyelesaikan pencarian yang agak bodoh, tetapi entah bagaimana ada beberapa ketidakpuasan dengan kecepatan solusi. Setelah melihat bagaimana orang normal memecahkan sudoku, saya menemukan bahwa Algoritma X, ditemukan oleh Donald Knut, digunakan untuk ini.

Algoritma X

Algoritma ini memecahkan masalah yang mencakup secara akurat set. Atau, jika Anda suka, ia mengumpulkan "teka-teki diskrit", memiliki informasi tentang bentuk potongan-potongan yang tersedia. Lebih formal:

• Ada banyak s
• Ada satu set himpunan bagian Y dari himpunan ini
• Tugasnya adalah memilih dari Y elemen seperti Y * sehingga setiap elemen dari S terkandung hanya dalam satu set yang termasuk dalam Y *
• Yaitu, penyatuan semua set dalam Y * merupakan (mencakup) set S , dan pada saat yang sama dalam Y * tidak ada set berpotongan berpasangan

Sebagai contoh, pertimbangkan set
S = {1, 2, 3, 4, 5} dan
Y = { A = {1, 2},
B = {2, 3},
C = {1, 5},
D = {1, 4},
E = {5}}
Set B , D, dan E membentuk sampul yang tepat dari himpunan S.

Untuk algoritma X Knuth, himpunan Y direpresentasikan sebagai matriks biner, di mana baris sesuai dengan elemen Y , dan A _{i, j} = 1, jika S _j berada di Y _i . Yaitu untuk contoh di atas:

Algoritma pencarian cakupan yang tepat adalah sebagai berikut:

• Input data: set S dan Y ; Stack set berpotensi termasuk dalam cakupan (awalnya mungkin kosong atau sudah memiliki beberapa elemen)
  
  1. Jika set S kosong, maka penutup yang diinginkan ada di tumpukan.
  2. Jika set Y kosong, penutup tidak ditemukan.
  3. Kami mencari elemen s dalam himpunan S yang termasuk dalam jumlah set minimum dalam Y.
  4. Pilih dari Y semua baris X yang berisi s .
  5. Untuk setiap set X, ulangi 6-9.
  6. Tambahkan X ke tumpukan sebagai elemen cakupan potensial.
  7. Kami membentuk himpunan S ' dan Y' : S ' adalah S dari mana semua elemen yang terkandung dalam X dihapus, Y' adalah himpunan dari Y yang tidak berpotongan dengan X.
  8. Kami memanggil algoritma X untuk S ' , Y' dan Stack .
  9. Jika ditemukan pada langkah 7 bahwa cakupan tidak mungkin, hapus elemen dari atas Stack dan lanjutkan ke X. Jika solusi ditemukan, kami mengembalikannya.
  10. Jika tidak ada solusi untuk X , tugas tidak diselesaikan untuk input ini.

Secara umum, tidak ada yang rumit. Intinya - pencarian yang biasa dilakukan secara mendalam. Ngomong-ngomong, kami mencatat bahwa jika Anda awalnya mengatur stack menjadi nonempty, maka masalahnya dapat dirumuskan sebagai "menemukan cakupan tepat yang mencakup elemen yang sudah ada di stack."

Kehalusannya adalah bahwa dalam praktiknya algoritma ini digunakan untuk masalah di mana set di Y "kecil", yaitu. matriks sangat jarang, karena itu, misalnya, mencari persimpangan antara kolom selama penyimpanan standar dalam bentuk matriks membutuhkan waktu yang lama.
Karenanya, Knut melengkapi algoritme ini dengan mekanisme "tautan menari" . Matriks disajikan dalam bentuk daftar dua dimensi yang ditautkan: untuk setiap baris dalam daftar, hanya nomor kolom yang disimpan, di mana baris ini berisi unit. Daftar ini juga berisi tautan ke elemen berikutnya dan sebelumnya dalam satu baris dan kolom. Organisasi ini memungkinkan Anda untuk menghapus kolom dan baris dari matriks jarang selama O (1) dibandingkan dengan O ( m * n ) saat disimpan dalam array dua dimensi.

Sangat menarik bahwa Ali Assaf menawarkan alternatif untuk mekanisme link menari menggunakan daftar asosiatif, yang memungkinkan Anda untuk mengimplementasikan algoritma X dalam beberapa lusin baris dalam bahasa tingkat tinggi.

Idenya adalah untuk menyimpan kolom dan baris matriks dalam daftar asosiatif. Di kolom, kami menyimpan indeks baris, di persimpangan dengan yang ada elemen bukan nol, di baris, masing-masing, indeks kolom. Selain itu, kami akan menyimpan indeks dalam baris secara berurutan, dalam sebuah array, kami mencatat bahwa dalam algoritma Knuth, pada dasarnya tidak perlu memodifikasi baris, oleh karena itu optimasi untuk menghapus elemen dari suatu baris dengan cepat tidak diperlukan. Tetapi kolom akan diatur dalam bentuk set, karena ketika menghapus baris dari sebuah matriks, perlu untuk menghapus pengidentifikasi dari semua kolom (dan ketika menghapusnya dari semua kolom, baris tersebut menghilang "dengan sendirinya").

Pertimbangkan penerapan algoritma pada Julia.
Matriks dari contoh sekarang akan terlihat seperti ini:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

Agar algoritme berfungsi, Anda memerlukan fungsi yang mengeluarkan garis dari matriks yang bersinggungan dengan yang diberikan, dan fungsi yang mengembalikan garis-garis ini ke tempatnya.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

Agar kedua fungsi ini berfungsi sebagaimana mestinya, hanya diperlukan penyimpanan elemen dalam baris matriks yang diperlukan. Dalam fungsi extract_intersects!() , Pada setiap iterasi dari loop luar, baris-baris yang bersinggungan dengan base_row tetapi tidak mengandung elemen yang dilihat pada iterasi sebelumnya dihapus dari matriks. Ini memastikan bahwa ketika kita menyisipkan kolom di restore_intersects!() Dalam urutan terbalik, di loop terdalam pada saat panggilan push!(columns[col], added_row) extract_intersects!() elemen dari kolom akan dikembalikan ke tempat asalnya.

Sekarang algoritma X sendiri:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

Sudoku

Ada algoritma, masalahnya kecil - untuk menghadirkan Sudoku sebagai tugas untuk menemukan cakupan yang tepat.

Kami merumuskan persyaratan yang harus dipenuhi oleh sudoku yang terpecahkan:

1. Di setiap sel ada angka dari 1 hingga 9 (atau hingga n ² jika kuadrat dari ukuran yang berbeda dipecahkan).
2. Di setiap baris, setiap angka muncul satu kali.
3. Di setiap kolom, setiap angka muncul satu kali.
4. Di setiap kuadran, setiap angka muncul sekali.

Masing-masing persyaratan ini harus dipenuhi tepat 1 kali, yaitu mereka membentuk himpunan yang perlu ditutup. Ia memiliki elemen persis 4 n ² (kolom dalam matriks).

Subhimpunan yang kami anggap dibentuk dengan mengganti nomor tertentu dalam sel tertentu. Misalnya, angka 9 di persimpangan 1 baris dan 4 kolom "mencakup" subset "dalam sel (1,4) adalah angka, di 1 baris ada angka 9, dalam 4 kolom ada angka 9, di 2 kuadran ada angka 9" (menyiratkan yang biasa Sudoku 9 × 9).

Setelah itu, algoritme solusi ditulis sepele.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

Mari kita periksa beberapa contoh:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

Tampaknya berfungsi, dan kecepatannya dapat diterima.

Perlu dicatat bahwa tidak ada teknik khusus untuk Sudoku (seperti, misalnya, di sini atau di sini ) tidak diletakkan dalam algoritma, kecuali untuk representasi spesifik dari set dan elemen penutup yang diinginkan.