Implementieren Sie einen nicht erratenden Sudoku-Löser

27

Implementieren Sie den kürzesten Sudoku-Löser.

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

Antworten:

 | 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

Regeln:

  1. Angenommen, alle Labyrinthe sind nur durch Logik lösbar.
  2. Alle Eingaben sind 81 Zeichen lang. Fehlende Zeichen sind 0.
  3. Die Lösung als einzelne Zeichenfolge ausgeben.
  4. Das "Gitter" kann nach Belieben intern gespeichert werden.
  5. Die Lösung muss eine nicht erratene Lösung verwenden. (siehe Sudoku Solver )

Beispiel I / O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
quelle
Sie sollten wirklich ein Zeitlimit hinzufügen.
JPvdMerwe
1
@JPvdMerwe: Guter Punkt, aber ein Zeitlimit wäre schwer zu standardisieren.
snmcdonald
1
@gnibbler: Es könnte schon mal gemacht worden sein (aber nicht auf codegolf.se). Ich denke, es wird immer noch Spaß machen, das Problem zu lösen und der Community einen Mehrwert zu verleihen, besonders wenn man es ehrlich angeht.
snmcdonald
2
Ich mag dieses. Ich habe gezögert, eine echte Golflösung zu versuchen, und ich habe darüber nachgedacht, einen Sudoku-Solver zu schreiben (es scheint eine lustige Übung zu sein). Ich denke, es ist etwas, was Leute wie ich, die noch nie zuvor Golf gespielt haben, als Ausgangspunkt nutzen könnten. Und wenn ich eines gefunden habe, könnte ich es dann Golf spielen.
Andy
4
Probleme, die "nur durch Logik lösbar" sind, sind sehr vage. Meinen Sie vielleicht nur die grundlegenden Schritte von a) Schreiben eines Werts in eine Zelle, deren Wert nicht in Zeile, Spalte und Block enthalten ist b) Identifizieren einer Zahl, die nur an einer Stelle in der Zeile und Spalte stehen kann oder blockieren und dort schreiben?
17.

Antworten:

4

RUBIN ( 449 436 Zeichen)

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

Beispiel:

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

Kurze Erklärung:
Board bist ein Array von 81 Arrays, die alle möglichen Werte für jede Zelle enthalten. Das Array in Zeile drei enthält [offset, start_index] für jede Gruppe (Felder, Zeilen, Spalten). Drei Aufgaben werden ausgeführt, während die Gruppen durchlaufen werden.

  1. Der Wert einer Zelle der Größe 1 wird aus dem Rest der Gruppe entfernt.
  2. Wenn ein Zellenpaar die gleichen 2 Werte enthält, werden diese Werte aus dem Rest der Gruppe entfernt.
  3. Die Anzahl der einzelnen Werte wird in gespeichert. dWenn es nur eine Instanz eines Werts gibt, setzen wir die enthaltende Zelle auf diesen Wert und markieren die Zelle, in der sie festgelegt istf

Wiederholen, bis alle Zellen repariert sind.

Ahelly
quelle
Sie können die Klammern weglassen I=*(0..8), um 2 Zeichen zu sparen.
Dogbert
Ich verstehe, sudokusolver.rb:8: unterminated string meets end of filewenn ich damit anfange ruby1.8 sudokusolver.rb 030.... Was mache ich falsch?
Benutzer unbekannt
Die letzte Zeile enthält ein Extra. Nicht sicher, wie das dahin gekommen ist ...
AShelly
2

Prolog - 493 Zeichen

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

Ausgabe:

Eingabe: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Ausgänge: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Eingabe: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Ausgänge: 832591674496387251571264983185746392267953418943812765714638529329175846658429137

MT0
quelle