Menerapkan Soloku Non-Guessing Sudoku

27

Terapkan pemecah Sudoku terpendek.

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:

  1. Asumsikan semua labirin hanya dapat dipecahkan oleh logika.
  2. Semua input akan terdiri dari 81 karakter. Karakter yang hilang adalah 0.
  3. Keluarkan solusi sebagai string tunggal.
  4. "Grid" dapat disimpan secara internal sesuai keinginan Anda.
  5. Solusinya harus menggunakan solusi yang tidak dapat ditebak. (lihat Sudoku Solver )

Contoh I / O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
sumber
Anda harus benar-benar menambahkan batas waktu.
JPvdMerwe
1
@ JPPMerwe: Poin bagus, tapi batas waktu akan sulit untuk distandarisasi.
snmcdonald
1
@gnibbler: Mungkin sudah pernah dilakukan sebelumnya (tetapi tidak pada codegolf.se). Saya pikir itu akan tetap menyenangkan untuk diselesaikan dan juga menambah nilai bagi masyarakat, terutama jika seseorang melakukannya dengan jujur.
snmcdonald
2
Saya suka yang ini. Saya ragu-ragu untuk mencoba solusi golf yang sebenarnya, dan saya sudah berpikir tentang menulis pemecah Sudoku (sepertinya latihan yang menyenangkan). Saya pikir itu sesuatu yang orang seperti saya, yang belum pernah main golf sebelumnya, bisa gunakan sebagai titik awal. Dan begitu saya datang dengan satu, saya mungkin akan golf itu.
Andy
4
Masalah "dipecahkan oleh logika saja" sangat kabur. Maksud Anda, mungkin, hanya menggunakan langkah-langkah dasar a) Menulis nilai dalam sel yang nilainya tidak dalam baris, kolom, dan bloknya b) Mengidentifikasi angka yang hanya bisa masuk di satu tempat di baris, kolomnya , atau memblokir, dan menulisnya di sana?
xnor

Jawaban:

4

RUBY ( 449 436 karakter)

I=*(0..8)
b=$*[0].split('').map{|v|v<'1'?I.map{|d|d+1}:[v.to_i]};f=b.map{|c|!c[1]}
[[z=I.map{|v|v%3+v/3*9},z.map{|v|v*3}],[x=I.map{|v|v*9},I],[I,x]
].map{|s,t|t.map{|i|d=[a=0]*10;s.map{|j|c=b[i+j];c.map{|v|d[v]+=1if !f[i+j]}
v,r=*c;s.map{|k|b[i+k].delete(v)if j!=k}if !r 
s[(a+=1)..8].map{|k|s.map{|l|b[i+l]-=c if l!=k&&l!=j}if c.size==2&&c==b[i+k]}}
v=d.index 1;f[i+k=s.find{|j|b[i+j].index v}]=b[i+k]=[v]if v}}while f.index(!1)
p b*''

Contoh:

C:\golf>soduku2.rb 030001000006000050500000983080006302000050000903800060714000009020000800000400030
"832591674496387251571264983185746392267953418943812765714638529329175846658429137"

penjelasan cepat:
Papan badalah array 81 array yang memegang semua nilai yang mungkin untuk setiap sel. Array pada baris tiga menampung [offset, start_index] untuk setiap grup (kotak, baris, kolom). Tiga tugas dilakukan saat iterasi melalui grup.

  1. Nilai sel apa pun ukuran 1 dihapus dari sisa grup.
  2. Jika pasangan sel mana pun mengandung 2 nilai yang sama, nilai-nilai ini dihapus dari sisa grup.
  3. Hitungan setiap nilai disimpan di d- jika hanya ada 1 instance dari nilai, kami mengatur sel yang berisi nilai tersebut, dan menandai sel yang diperbaiki dif

Ulangi sampai semua sel diperbaiki.

ASHelly
sumber
Anda dapat menghilangkan tanda kurung I=*(0..8), akan menghemat 2 karakter.
Dogbert
Saya mengerti sudokusolver.rb:8: unterminated string meets end of filejika saya memulainya ruby1.8 sudokusolver.rb 030.... Apa yang saya lakukan salah?
pengguna tidak diketahui
Sepertinya ada tambahan 'di baris terakhir. Tidak yakin bagaimana itu sampai di sana ...
AShelly
2

Prolog - 493 Karakter

:-use_module(library(clpfd)).
a(X):-all_distinct(X).
b([],[],[]).
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-a([A,B,C,D,E,F,G,H,I]),b(X,Y,Z).
c([A,B,C,D,E,F,G,H,I|X])-->[[A,B,C,D,E,F,G,H,I]],c(X).
c([])-->[].
l(X,Y):-length(X,Y).
m(X,Y):-maplist(X,Y).
n(L,M):-l(M,L).
o(48,_).
o(I,O):-O is I-48.
:-l(L,81),see(user),m(get,L),seen,maplist(o,L,M),phrase(c(M),R),l(R,9),m(n(9),R),append(R,V),V ins 1..9,m(a,R),transpose(R,X),m(a,X),R=[A,B,C,D,E,F,G,H,I],b(A,B,C),b(D,E,F),b(G,H,I),flatten(R,O),m(write,O).

Keluaran:

Memasukkan: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Keluaran: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Memasukkan: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Keluaran: 832591674496387251571264983185746392267953418943812765714638529329175846658429137

MT0
sumber