Pelajari kode ini dengan hati-hati dan temukan cara cerdas menggunakan rekursi untuk memecahkan teka-teki sudoku yang rumit itu.
Sudoku adalah teka-teki angka populer yang terdiri dari kotak berukuran 9x9 dengan angka dari 1 hingga 9. Teka-teki tersebut mencakup kombinasi angka dan beberapa ruang kosong, yang harus Anda isi.
Saat mengisi ruang kosong, setiap baris, kolom, dan subkisi 3x3 harus berisi semua digit dari 1 hingga 9.
Skrip Python sederhana dapat membantu memecahkan teka-teki Sudoku untuk Anda. Itu dapat menganalisis semua ruang kosong di papan Sudoku, dan menemukan nomor yang memungkinkan untuk diisi di setiap ruang kosong.
Cara Membuat dan Menampilkan Papan Sudoku
Di dalam skrip Python, Anda perlu menggunakan daftar larik untuk menyimpan nilai teka-teki Sudoku yang belum terpecahkan.
Kode yang digunakan dalam proyek ini tersedia di sini repo GitHub di bawah lisensi MIT.
- Di dalam skrip Python baru bernama sudoku.py, simpan semua nilai untuk kisi 9x9. Setiap baris dan kolom mewakili sembilan angka di sepanjang dan di bawah teka-teki Sudoku. Tambahkan 0 untuk mewakili ruang yang perlu dipecahkan:
papan = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
] - Di dalam fungsi baru bernama print_board, menggunakan for loop untuk memproses setiap baris dalam kisi:
defprint_board(papan):
untuk baris di dalam jangkauan(9): - Untuk memisahkan setiap baris menjadi sepertiga, periksa apakah baris tersebut habis dibagi tiga, dan tambahkan baris:
jika baris % 3 == 0Dan baris != 0:
mencetak("- - - - - - - - - - - - - - ") - Dalam setiap baris, lewati setiap kolom. Anda juga dapat membagi kolom menjadi tiga dengan memeriksa apakah kolom dapat dibagi tiga:
untuk kol di dalam jangkauan(9):
jika col % 3 == 0Dan kol != 0:
mencetak(" | ", akhir="") - Cetak nilai angka yang disimpan di grid. Jika kolom adalah kolom terakhir untuk baris tersebut, tambahkan garis pemisah, sehingga baris berikutnya muncul di baris baru:
jika kol == 8:
cetak (papan[baris][kolom])
kalau tidak:
cetak (str (papan[baris][kolom]) + " ", akhir="") - Panggil fungsi untuk mencetak papan:
print_board (papan) - Di baris perintah, navigasikan ke folder tempat Anda menyimpan skrip python, misalnya:
cd Desktop - Gunakan perintah python untuk menjalankan skrip Sudoku Anda. Lihat teka-teki yang tercetak di layar:
python sudoku.py
Cara Mengidentifikasi Ruang Kosong untuk Diselesaikan
Anda dapat melintasi daftar untuk menemukan ruang yang terdiri dari 0s. Ini menentukan ruang mana yang perlu dipecahkan.
- Dalam fungsi baru yang disebut find_empty(), lewati setiap baris dan kolom di papan tulis:
deffind_empty(papan):
untuk baris di dalam jangkauan(9):
untuk kol di dalam jangkauan(9): - Jika nilai sel saat ini adalah 0, kembalikan posisi sel kosong saat ini:
jika papan[baris][kolom] == 0:
kembali (baris, kolom) - Jika skrip mencapai akhir fungsi, itu berarti skrip tidak dapat menemukan sel apa pun dengan nilai 0. Dalam hal ini, jangan kembalikan apa pun:
kembaliTidak ada - Dalam fungsi baru bernama solve(), gunakan fungsi find untuk menemukan ruang kosong pertama di papan tulis:
defmenyelesaikan(papan):
temukan = temukan_kosong (papan) - Fungsi find_empty() mengembalikan posisi sel dalam format tuple, misalnya (0, 2). Simpan nilai-nilai ini secara terpisah ke dalam baris Dan kol variabel. Jika tidak, kembalikan true untuk menandakan bahwa tidak ada ruang kosong yang tersisa untuk dipecahkan:
jikabukan menemukan:
kembaliBENAR
kalau tidak:
baris, col = temukan
Cara Memecahkan Puzzle untuk Setiap Baris, Kolom, dan Kisi 3x3
Sekarang Anda dapat mengidentifikasi ruang kosong pertama untuk dipecahkan, Anda perlu mencoba dan menemukan nomor yang sesuai untuk mengisi ruang itu dan memecahkan teka-teki.
Menggunakan rekursi, panggil fungsi solve() di dalam dirinya sendiri untuk mencoba setiap kemungkinan kombinasi nilai untuk semua ruang lainnya juga.
- Di dalam fungsi solve(), setelah menemukan ruang kosong pertama, ulangi setiap angka dari 1 hingga 9. Angka-angka ini mewakili kemungkinan angka yang dapat mengisi ruang yang belum terpecahkan:
untuk nomor di dalam jangkauan(1, 10): - Masukkan papan, nomor yang mungkin, dan posisi sel kosong ke dalam fungsi baru. Fungsi baru akan mengembalikan nilai true jika angka tersebut adalah angka valid yang dapat menyelesaikan ruang kosong tersebut. Jika valid, tetapkan nomor itu ke sel di papan tulis:
jika is_valid (papan, num, (baris, kolom)):
papan[baris][kolom] = bil - Buat fungsi is_valid(), dengan parameter yang cocok:
defadalah benar(papan, nomor, pos): - Gunakan fungsi untuk memeriksa apakah menempatkan nomor pada posisi tersebut melanggar aturan permainan Sudoku. Pertama, periksa apakah nomor tersebut sudah ada di baris atau kolom sel:
untuk kol di dalam jangkauan(9):
jika papan[pos[0]][kolom] == jumlah Dan pos[1] != col:
kembaliPALSUuntuk baris di dalam jangkauan(9):
jika papan[baris][pos[1]] == jumlah Dan pos[0] != baris:
kembaliPALSU - Dapatkan kisi 3x3 tempat sel itu berada. Anda dapat melakukannya dengan membagi posisi sel dengan tiga:
kotak_baris = pos[0] // 3
kotak_kolom = pos[1] // 3 - Untuk setiap baris dan kolom dalam kisi 3x3 tersebut, periksa apakah nomornya sudah ada. Jika ya, kembalikan salah:
untuk baris di dalam rentang (baris_kotak*3, kotak_baris*3 + 3):
untuk kol di dalam rentang (kotak_kolom*3, kotak_kolom*3 + 3):
jika papan[baris][kolom] == num Dan (baris, kolom) != pos:
kembaliPALSU - Jika skrip mencapai akhir fungsi, berarti tidak ada aturan Sudoku yang gagal. Kembali benar:
kembaliBENAR - Fungsi is_valid() hanya memeriksa apakah penempatan nomor valid, tetapi itu tidak berarti itu adalah jawaban yang benar untuk solusi keseluruhan. Di dalam fungsi solve(), panggil lagi fungsi solve() dengan papan yang diperbarui. Fungsi solve() dapat mencapai keadaan di mana ia tidak dapat lagi menggunakan angka apa pun untuk mengisi spasi apa pun. Dalam hal ini, seluruh fungsi mengembalikan salah, mengatur ulang sel tertentu itu kembali ke 0, dan mundur. Fungsi solve() hanya mengembalikan nilai true jika skrip dapat mengisi semua spasi:
untuk nomor di dalam jangkauan(1, 10):
jika is_valid (papan, num, (baris, kolom)):
papan[baris][kolom] = bil
jika memecahkan (papan):
kembaliBENAR
papan[baris][kolom] = 0kembaliPALSU - Untuk mulai memecahkan teka-teki, panggil fungsi solve() dengan papan aslinya, di bagian bawah skrip, setelah mendeklarasikan fungsi solve():
memecahkan (papan) - Cetak hasil akhir:
mencetak("Terselesaikan:")
print_board (papan) - Pada baris perintah, gunakan perintah python untuk menjalankan ulang skrip. Lihat teka-teki yang dipecahkan yang tercetak di layar:
python sudoku.py
Membuat Game Menggunakan Python
Sudoku hanyalah salah satu dari banyak permainan yang dapat Anda buat dan selesaikan menggunakan Python. Anda dapat menggunakan Python untuk membuat berbagai permainan lain, seperti permainan kata campur aduk, permainan petualangan berbasis teks, atau permainan warna, dan masih banyak lagi.