Terapkan pemecah Sudoku terpendek menggunakan menebak. Karena saya telah menerima beberapa permintaan, saya telah menambahkan ini sebagai pertanyaan alternatif bagi mereka yang ingin menerapkan solver sudoku brute force.
Teka-teki Sudoku:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 3 | 1 |
B| 6 | | 5
C| 5 | | 9 8 3
-+-----------------------
D| 8 | 6 | 3 2
E| | 5 |
F| 9 3 | 8 | 6
-+-----------------------
G| 7 1 4 | | 9
H| 2 | | 8
I| | 4 | 3
Menjawab:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7
Aturan:
- Asumsikan semua labirin hanya dapat dipecahkan oleh logika.
- Semua input akan terdiri dari 81 karakter. Karakter yang hilang adalah 0.
- Keluarkan solusi sebagai string tunggal.
- "Grid" dapat disimpan secara internal sesuai keinginan Anda.
- Solusinya harus menggunakan solusi menebak brute force.
- Solusi harus diselesaikan dalam batas waktu yang wajar.
Contoh I / O:
>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
code-golf
game
puzzle-solver
sudoku
snmcdonald
sumber
sumber
Jawaban:
k (72 byte)
Penghargaan untuk ini diberikan kepada Arthur Whitney, pencipta bahasa k.
sumber
Python, 188 byte
Ini adalah versi yang lebih pendek dari pengajuan kemenangan saya untuk CodeSprint Sudoku , dimodifikasi untuk input baris perintah dan bukan stdin (sesuai OP):
Jika Anda menggunakan Python 2,
'%d'%5**18
bisa diganti dengan`5**18`
untuk menyimpan 3 byte.Untuk membuatnya berjalan lebih cepat, Anda dapat mengganti
'%d'%5**18
dengan permutasi apa pun dengan'123456789'
biaya 1 byte.Jika Anda ingin menerima input pada stdin, Anda dapat menggantinya
import sys;f(sys.argv[1])
denganf(raw_input())
, membawanya ke 177 byte .EDIT: Berikut ini tautan ke langkah-langkah yang lebih rinci.
sumber
Python, 197 karakter
sumber
Jawab dalam D:
Dengan input sampel, diperlukan 0,033 pada Phenom II X6 1090T saya ketika dikompilasi dengan
dmd -w
(yaitu tanpa optimasi), dan dibutuhkan 0,011s saat dikompilasi dengandmd -w -O -inline -release
(yaitu dengan optimasi).sumber
J, 103
perkiraan jangka waktu: O (trilyun miliar tahun)
sumber
Perl, 120 byte
Oh, saya ingat bermain golf pada tahun 2008 ... Dan ternyata berhenti bekerja di perl 5.12 karena pengaturan implisit dari @_ oleh split dihapus kemudian. Jadi hanya coba ini pada perl yang cukup lama.
Jalankan dengan input pada STDIN:
sudoku.pl
:sumber
Perl, 235 karakter
Ini adalah versi golf dari sesuatu yang saya posting bertahun-tahun yang lalu ke milis Fun With Perl : sebuah regexp penyelesaian sudoku.
Pada dasarnya, itu input input menjadi 81 baris, masing-masing berisi semua angka yang bisa terjadi di kotak yang sesuai. Itu kemudian membangun regexp untuk mencocokkan satu nomor dari setiap baris, menggunakan backreferences dan pernyataan lookahead negatif untuk menolak solusi yang melanggar batasan baris, kolom atau wilayah. Kemudian cocok dengan string terhadap regexp, membiarkan mesin regexp Perl melakukan kerja keras uji coba dan mundur.
Yang mengherankan, dimungkinkan untuk membuat regexp tunggal yang berfungsi untuk input apa pun, seperti yang dilakukan oleh program asli saya. Sayangnya, ini cukup lambat, jadi saya mendasarkan kode golf di sini pada versi hardcoded-givens ( ditemukan kemudian di utas FWP ), yang mengubah regexp untuk menolak awal setiap solusi yang diketahuinya akan melanggar batasan. Ini membuatnya cukup cepat untuk sudokus tingkat sedang hingga mudah, meskipun yang sulit masih bisa membutuhkan waktu yang agak lama untuk diselesaikan.
Jalankan kode dengan
perl -M5.010
untuk mengaktifkan fitur Perl 5.10+say
. Input harus diberikan pada input standar, dan solusinya akan dicetak ke output standar; contoh:sumber
Naskah kopi 1-liner
solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0
Ini adalah versi yang lebih besar dengan penggunaan sampel :
sumber
solve
, menghapus banyak spasi putih (saya tahu ini penting, tetapi di banyak tempat itu bisa dihapus), menggunakan simbol bukan kata-kata (seperti!=
bukannyaisnt
), menggunakan lekukan alih-alihthen
kata kunci, ganti[0...9]
dengan[0..8]
.Clojure - 480 byte
Ukurannya meledak, tetapi setidaknya itu angka yang cukup. Saya pikir itu bisa ditingkatkan banyak dengan hanya menggunakan 1D-vektor. Bagaimanapun, test case membutuhkan waktu kurang dari empat detik di laptop saya. Saya pikir akan lebih tepat untuk mendefinisikan suatu fungsi, karena ini adalah bahasa fungsional.
Contoh:
Versi yang sedikit ungolfed (dan lebih cantik):
sumber
PowerShell ,
244242218215 byteCobalah online!
Script menemukan semua solusi untuk sudoku.
Belum dibuka:
Kasus uji:
sumber
D (322 karakter)
Untuk setiap kotak yang belum terpecahkan, ia membangun larik opsi yang tersedia dan kemudian memutarnya.
dengan spasi putih:
sumber
Perl (195 karakter)
Semua penghargaan diberikan kepada pencipta di sini , dan penjelasannya dapat ditemukan di sana juga.
sumber
J, 94 byte
Bekerja dengan cara yang persis sama dengan versi K, yaitu dengan BFS (sehingga akan menampilkan semua solusi). Ini mencetak spasi antara digit output, tetapi begitu juga program K. Saya tidak menghitung "s =:" karena ini hanya penamaan fungsi (seperti saya tidak akan menghitung nama file dalam bahasa lain).
sumber