Anda mengira sudoku biasa itu sulit, sekarang coba Killer Sudoku !
Dalam permainan Killer Sudoku, Anda tidak diberi nomor sama sekali. Sebagai gantinya, Anda diberikan wilayah yang dikatakan menambahkan hingga jumlah tertentu. Pertimbangkan contoh berikut, dari Wikipedia:
Dan solusinya:
Program yang Anda tulis akan mengambil format yang terdiri dari urutan 81 huruf yang mewakili wilayah, diikuti oleh urutan angka. Kemudian setiap angka dalam urutan mewakili jumlah angka di masing-masing daerah surat, mulai dari "A", "B", dll.
Ini kemudian akan menampilkan urutan 81 digit yang mewakili solusi.
Sebagai contoh, contoh puzzle di atas akan memiliki input berikut:
AABBBCDEFGGHHCCDEFGGIICJKKFLMMINJKOFLPPQNJOORSPTQNUVVRSTTQWUUXXSYZWWaaXXSYZWbbbcc
3 15 22 4 16 15 25 17 9 8 20 6 14 17 17 13 20 12 27 6 20 6 10 14 8 16 15 13 17
Dan output yang dihasilkan adalah:
215647398368952174794381652586274931142593867973816425821739546659428713437165289
Anda dapat mengasumsikan bahwa input tersebut valid, dan bahwa wilayah akan selalu muncul dalam urutan oleh A, B, ..., Y, Z, a, b, ..., z.
(Kode terpendek yang berfungsi akan menang.)
sumber
Jawaban:
R - 378 karakter
Asumsi
378 karakter:
Dibutuhkan sekitar satu jam pada PC sederhana saya untuk mencapai solusi yang diharapkan, setelah 2.964.690 iterasi.
De-golf:
sumber
GolfScript, 138 karakter
Ini adalah solver pembunuh sudoku di GolfScript. Ia mengharapkan input pada STDIN dalam dua baris seperti yang diberikan dalam contoh di atas.
Harap dicatat: Karena deskripsi puzzle tidak membatasi waktu eksekusi, saya lebih suka ukuran kode kecil daripada kecepatan. Kode ini menguji semua konfigurasi jaringan 9 ^ 81 untuk solusi yang mungkin memakan waktu lama di komputer yang lambat ;-)
sumber
AABBCADEFFDDGGGG
6 7 4 8 2 3 10
Ruby, 970 karakter
Kode ruby di atas berlawanan dengan langganan GolfScript saya. Ini cukup panjang (dan belum sepenuhnya golf), tetapi dioptimalkan untuk kecepatan. Sudoku pembunuh yang diberikan di atas diselesaikan dalam waktu kurang dari satu detik (dengan versi java asli saya hanya beberapa mili detik). Solver itu sendiri adalah implementasi dasar dari algoritma DLX Knuth.
Input harus diberikan sebagai dua baris pada STDIN. Contoh ( online ):
sumber