Zaimplementuj najkrótszy solver Sudoku.

Sudoku Puzzle:

 | 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

Odpowiedź:

 | 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

Zasady:

1. Załóżmy, że wszystkie labirynty można rozwiązać tylko za pomocą logiki.
2. Wszystkie dane wejściowe będą miały 81 znaków. Brakujące znaki będą wynosić 0.
3. Wyjście rozwiązania jako pojedynczy ciąg.
4. „Siatka” może być przechowywana wewnętrznie, jak chcesz.
5. Rozwiązanie musi wykorzystywać rozwiązanie nie wymagające zgadywania. (patrz Sudoku Solver )

Przykład I / O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137

RUBY ( 449436 znaków)

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*''

Przykład:

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

szybkie wyjaśnienie:
Tablica bto tablica 81 tablic zawierających wszystkie możliwe wartości dla każdej komórki. Tablica w wierszu trzecim zawiera [przesunięcie, indeks_początkowy] dla każdej grupy (pola, wiersze, kolumny). Podczas iteracji w grupach wykonywane są trzy zadania.

1. Wartość dowolnej komórki o rozmiarze 1 jest usuwana z reszty grupy.
2. Jeśli jakakolwiek para komórek zawiera te same 2 wartości, wartości te są usuwane z reszty grupy.
3. Liczba każdej wartości jest przechowywana w d- jeśli jest tylko 1 instancja wartości, ustawiamy zawierającą komórkę na tę wartość i zaznaczamy komórkę ustaloną wf

Powtarzaj, aż wszystkie komórki zostaną naprawione.

Prolog - 493 znaków

:-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).

Wydajność:

Wprowadzanie: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Wyjścia: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Wprowadzanie: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Wyjścia: 832591674496387251571264983185746392267953418943812765714638529329175846658429137