Sudoku Solver
Papan sudoku adalah kisi 9 × 9 yang dibagi menjadi sembilan kotak 3 × 3. Pada papan yang sudah terpecahkan, setiap baris, setiap kolom, dan setiap kotak memuat setiap digit dari 1 sampai 9 tepat satu kali.
Teka-teki diberikan sebagai 9 string, satu untuk setiap baris dari atas; . menandakan sel kosong. Isi setiap sel kosong dan kembalikan papan yang sudah terpecahkan dalam bentuk yang sama. Papan ini memiliki tepat satu solusi.
Fungsi
- boardstring-array
- 9 baris teka-teki, satu titik di setiap sel kosong
- Mengembalikanstring-array
- 9 baris pada papan yang telah diselesaikan
Batasan
boardberisi 9 string dengan panjang 9.- Setiap karakter adalah
.atau salah satu digit dari1sampai9. - Digit yang diberikan tidak pernah berulang dalam baris, kolom, atau kotak.
- Papan ini memiliki tepat satu solusi.
Contoh
- Input
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Output
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Penjelasan
- Baris paling atas
9.7.....6sudah berisi 9, 7, dan 6, jadi enam sel kosongnya diisi dengan 1, 2, 3, 4, 5, dan 8. Kolom dan kotak menentukan posisi masing-masing angka, dan baris tersebut menjadi957214386.
Pertanyaan lanjutan
Dalam Sudoku Killer, kandang yang terdiri dari beberapa sel juga harus memiliki jumlah sesuai dengan angka yang diberikan. Bagaimana kamu akan menambahkan aturan itu ke dalam pencarian dan menggunakannya untuk memangkas cabang lebih awal?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Catat digit yang sudah ada di setiap baris, setiap kolom, dan setiap kotak 3 × 3. Dengan begitu, kamu bisa mengetahui dalam O(1) apakah suatu digit cocok untuk sel kosong.
Isi sel yang kosong satu per satu. Coba setiap digit yang cocok untuk sel tersebut, lanjutkan ke sel berikutnya, lalu hapus digit itu jika bagian papan lainnya tidak dapat diselesaikan dengan digit tersebut.
Urutan sel penting. Selanjutnya, isi sel kosong yang memiliki paling sedikit digit tersisa: sel dengan satu pilihan tidak memerlukan percabangan, dan sel tanpa pilihan langsung memberi tahu kamu untuk kembali.
Solusi
Selesaikan dengan backtracking: tempatkan digit yang sesuai, lanjutkan, lalu batalkan penempatannya saat papan tidak dapat diselesaikan. Urutan sel menentukan kecepatannya. Pada papan yang sulit, urutan membaca dapat mengunjungi ratusan juta papan parsial; mengisi sel dengan pilihan paling sedikit terlebih dahulu hanya membutuhkan sekitar seratus.
Backtracking dalam urutan pembacaan
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Isi sel kosong sesuai urutan baca, masing-masing dengan digit terkecil yang cocok. Saat tidak ada lagi digit yang bisa dimasukkan ke sebuah sel, kembali ke sel sebelumnya dan coba digit berikutnya. Setiap kombinasi yang mematuhi aturan dicoba satu per satu, sehingga pencarian menemukan solusi.
Tiga tabel membuat setiap pengujian kecocokan berjalan dalam O(1): rowUsed[r][d], colUsed[c][d] dan boxUsed[b][d], dengan kotak b = (r / 3) * 3 + c / 3. Menempatkan digit akan mengatur tiga entri, dan menghapusnya akan mengosongkan entri tersebut.
Urutan tetap ini adalah titik lemahnya: pencarian bisa mengisi seluruh baris dengan digit yang cocok secara lokal, lalu baru mengetahui bahwa banyak sel tidak menyisakan ruang. Papan yang baris-baris atasnya hampir tidak memiliki petunjuk, dengan digit tinggi sebagai jawabannya, membuat pencarian melewati lebih dari 300 juta papan parsial.
Algoritma
- Baca papan ke dalam grid dengan 0 untuk sel kosong, isi
rowUsed,colUsed, danboxUsed, lalu daftarkan sel kosong sesuai urutan baca. backtrack(k): jikaksama dengan jumlah sel kosong, kembalikan true.- Untuk setiap digit
ddari 1 sampai 9 yang belum digunakan pada baris, kolom, dan kotak selk, tempatkan digit tersebut, tandai, lalu kembalikan true jikabacktrack(k+1)mengembalikan true; jika tidak, hapus tandanya. - Jika tidak ada digit yang cocok, kosongkan sel dan kembalikan false. Panggil
backtrack(0)dan ubah grid kembali menjadi string.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Isi sel yang paling kosong terlebih dahulu
Intuisi
Solusi tidak bergantung pada urutan pengisian, jadi pilih urutan yang menjaga pencarian tetap kecil: pada setiap langkah, isi sel kosong yang memungkinkan digit paling sedikit. Sel yang hanya memungkinkan satu digit sudah pasti dan tidak menambahkan cabang. Sel yang tidak memungkinkan digit apa pun langsung dipilih, sehingga papan yang salah segera diketahui.
Untuk menghitung digit yang memungkinkan dengan cepat bagi 81 sel pada setiap langkah, simpan setiap baris, kolom, dan kotak sebagai bitmask: bit d dari rows[r] disetel saat digit d berada di baris r. Sel memungkinkan ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, dengan 0x3FE mempertahankan bit 1 hingga 9, dan jumlahnya adalah banyaknya bit yang disetel. Menempatkan d menyetel bit d dalam tiga mask; operasi xor eksklusif menghapusnya.
Algoritma
- Buat kisi dan mask
rows,cols, danboxesdari digit yang diberikan. backtrack(): pindai semua sel, hitung digit yang boleh digunakan untuk setiap sel kosong, lalu pilih sel pertama dengan jumlah paling sedikit. Jika tidak ada sel kosong, kembalikan true.- Untuk setiap digit yang boleh digunakan di sel tersebut, tempatkan digit itu, atur bitnya di ketiga mask, lalu kembalikan true jika
backtrack()mengembalikan true. Jika tidak, hapus bit-bit tersebut. - Jika tidak ada digit yang cocok, kosongkan sel tersebut dan kembalikan false. Panggil
backtrack()dan ubah kisi kembali menjadi string.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Jebakan dan kasus tepi
- Lupa menghapus digit dari catatan baris, kolom, dan kotak saat kamu membatalkannya. Sel-sel berikutnya akan menganggap digit itu sudah digunakan, sehingga pencarian tidak menemukan solusi.
- Menggunakan
r / 3 + c / 3untuk kotak. Sel(0, 4)dan(4, 0)sama-sama menghasilkan 1, sehingga dua kotak berbagi satu catatan dan papan tidak akan pernah bisa diisi. Gunakan(r / 3) * 3 + c / 3dengan pembagian bilangan bulat. - Tidak berhenti pada solusi pertama. Langkah-langkah pembatalan kemudian mengosongkan papan lagi sebelum kamu membacanya.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu algoritma backtracking untuk menyelesaikan sudoku?
Eksponensial dalam kasus terburuk, O(9^m) untuk m sel kosong, karena setiap sel dapat bercabang menjadi hingga 9 digit. Pada teka-teki nyata, aturan baris, kolom, dan kotak memangkas sebagian besar cabang, dan mengisi sel yang paling kosong terlebih dahulu memangkas sebagian besar sisanya.
Bagaimana cara memeriksa bahwa Sudoku memiliki tepat satu solusi?
Jalankan pencarian backtracking yang sama, tetapi hitung solusi dan berhenti saat jumlahnya mencapai 2. Jumlah 1 berarti teka-teki hanya memiliki satu solusi, sedangkan 0 berarti tidak memiliki solusi. Generator teka-teki menjalankan pemeriksaan ini setelah menghapus setiap petunjuk.
Apakah ada cara yang lebih cepat untuk menyelesaikan sudoku daripada backtracking?
Kebanyakan pemecah cepat tetap menggunakan backtracking, tetapi membuat lebih banyak deduksi sebelum setiap tebakan. Propagasi kendala mengisi setiap sel yang hanya memiliki satu pilihan dan setiap digit yang hanya cocok pada satu sel di baris, kolom, atau kotaknya, lalu mengulangi prosesnya. Sudoku juga dapat dinyatakan sebagai masalah exact cover dan diselesaikan dengan Algorithm X dari Knuth.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def solveSudoku(board):
# Tulis kodemu di siniTes #1
Argumen
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Output yang diharapkan
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]