Zaimplementuj Soless Sudoku

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:

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

Przykład I / O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137

— snmcdonald
źródło

Naprawdę powinieneś dodać limit czasu.

— JPvdMerwe,

@JPvdMerwe: Dobrze, ale limit czasu byłby trudny do standaryzacji.

— snmcdonald

@gnibbler: Mogło to być zrobione wcześniej (ale nie na codegolf.se). Myślę, że nadal będzie fajnie rozwiązywać problemy i dodawać wartości społeczności, zwłaszcza jeśli ktoś robi to uczciwie.

— snmcdonald

Ten mi się podoba. Wahałem się, czy wypróbować prawdziwe rozwiązanie do gry w golfa, i zastanawiałem się nad napisaniem solwera Sudoku (wydaje się to zabawnym ćwiczeniem). Myślę, że to coś, co ludzie tacy jak ja, którzy nigdy wcześniej nie grali w golfa, mogliby wykorzystać jako punkt wyjścia. A kiedy już wymyślę taki, mogę go zagrać w golfa.

— Andy

Problemy „rozwiązywalne wyłącznie za pomocą logiki” są bardzo niejasne. Czy masz na myśli być może tylko podstawowe kroki: a) Zapisanie wartości w komórce, dla której jej wartość nie znajduje się w jej wierszu, kolumnie i bloku b) Identyfikacja liczby, która może iść tylko w jednym miejscu w wierszu, kolumnie , czy blokować i pisać tam?

— xnor

Odpowiedzi:

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.

Wartość dowolnej komórki o rozmiarze 1 jest usuwana z reszty grupy.
Jeśli jakakolwiek para komórek zawiera te same 2 wartości, wartości te są usuwane z reszty grupy.
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.

— AShelly
źródło

Możesz pominąć nawiasy I=*(0..8), zapisujesz 2 znaki.

— Dogbert

Rozumiem, sudokusolver.rb:8: unterminated string meets end of filejeśli zacznę ruby1.8 sudokusolver.rb 030.... Co ja robię źle?

— użytkownik nieznany

Wygląda na to, że w ostatnim wierszu jest dodatkowy. Nie jestem pewien, jak to się tam dostało ...

— AShelly

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

— MT0
źródło