Sudoku algorithmus

Mario Sandler

Hab den Thread nicht gelesen, aber wenn ich den code da oben so sehe
(überfliege) drängt sich mir eine Frage auf.

Hast du schonmal was von 2-Dimensionalen Arrays und for-Schleifen gehört?

glinux

Hallo Leute!

Ich bin Informatik Student und musste in meinem ersten Semester einen Sudoku Löser programmieren. Außerdem habe ich ein paar andere Lösungen gesehen. Daraus kann ich folgern, dass eine der schnellsten und kürzesten Lösungen die sog. Tiefensuche darstellt. Dabei wird aus der Sudoku Matrix ein Baum gebildet, in dem für jedes Eingabefeld alle Möglichen Zahlen in einer Baumstruktur berechnet werden. Wenn es nun (mindestens) ein Weg vom 1 Eingabefeld bis zum Letzten gibt (das ist die Tiefensuche), dann wurde eine Lösung gefunden, ansonsten wird der nächste Baumzweig ausprobiert usw. Damit können auch die mehrdeutigen Sudokus und mit jedem Schwierigkeitsgrad gelöst werden. Die Tiefensuche an sich ist am besten durch eine rekursive fkt. zu lösen. Dabei wird zwar teilweise recht viel Speicher verbraten, dafür passt der Algorithmus auf eine Seite und ist außerdem brutal schnell.

Übrigens funktionieren die meisten Online Löser auf diese weise. Bei eindeutigen Lösungen ist die Peformance im millisikunden bereich. Bei Matrizen mit meheren Lösungen und ungünstiger belegung kann der Code schon mal 30 Sekunden arbeiten. Dies kann bei den Online Lösern teilweise zur 100% Serverauslastung führen, wenn er dies nicht abfängt. Dafür gibt es aber auch zahlreiche Verbesserungen, wie bspw. zuerst die Felder betrachten, bei denen die wenigsten Möglichkeiten existieren.

Bei weiterem Interesse kann ich den Quellcode gerne posten. Aber da fehlt dann irgend wo die Motivation, oder?

mfg,
Alexej

ERROR

hab da mal vor geraumer zeit in prolog was gemacht. löst einfache sudokus(rein durch logik, kein probieren)

aber nachdem ich dann festgstellt habe, dass es funktioniert, hab ich dann nicht weiter gemacht und weitere stratgien eingebaut ... motivationsverlust

n([1,2,3,4,5,6,7,8,9]).

differenz_(X,[A|[]],B):-delete(X,A,B).
differenz_(X,[_|_],X).

diff_(X,[A1|[]],B):-differenz_(X,A1,B).
diff_(X,[A1|A],B):-differenz_(X,A1,X1),diff_(X1,A,B).

diff([A,B,C,D,E,F,G,H,I],[X1,X2,X3,X4,X5,X6,X7,X8,X9]):-

diff_(A,[B,C,D,E,F,G,H,I],X1),
diff_(B,[A,C,D,E,F,G,H,I],X2),
diff_(C,[A,B,D,E,F,G,H,I],X3),
diff_(D,[A,B,C,E,F,G,H,I],X4),
diff_(E,[A,B,C,D,F,G,H,I],X5),
diff_(F,[A,B,C,D,E,G,H,I],X6),
diff_(G,[A,B,C,D,E,F,H,I],X7),
diff_(H,[A,B,C,D,E,F,G,I],X8),
diff_(I,[A,B,C,D,E,F,G,H],X9).

%n(N),diff([[5],[3],[4],[6],N,[8],[9],[1],[2]],[A,B,C,D,E,F,G,H,I]).
%n(N),diff([[5],[3],[4],[6],N,[8],[9],[1],[2]],[_,_,_,_,E,_,_,_,_]).
%n(N),diff_all([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],[1],[4],[2],[3]],[[4],[2],[6],[8],[5],[3],[7],[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).

sudoku_([[[A1|[]],[A2|[]],[A3|[]],[A4|[]],[A5|[]],[A6|[]],[A7|[]],[A8|[]],[A9|[]]],
         [[B1|[]],[B2|[]],[B3|[]],[B4|[]],[B5|[]],[B6|[]],[B7|[]],[B8|[]],[B9|[]]],
         [[C1|[]],[C2|[]],[C3|[]],[C4|[]],[C5|[]],[C6|[]],[C7|[]],[C8|[]],[C9|[]]],
         [[D1|[]],[D2|[]],[D3|[]],[D4|[]],[D5|[]],[D6|[]],[D7|[]],[D8|[]],[D9|[]]],
         [[E1|[]],[E2|[]],[E3|[]],[E4|[]],[E5|[]],[E6|[]],[E7|[]],[E8|[]],[E9|[]]],
         [[F1|[]],[F2|[]],[F3|[]],[F4|[]],[F5|[]],[F6|[]],[F7|[]],[F8|[]],[F9|[]]],
         [[G1|[]],[G2|[]],[G3|[]],[G4|[]],[G5|[]],[G6|[]],[G7|[]],[G8|[]],[G9|[]]],
         [[H1|[]],[H2|[]],[H3|[]],[H4|[]],[H5|[]],[H6|[]],[H7|[]],[H8|[]],[H9|[]]],
         [[I1|[]],[I2|[]],[I3|[]],[I4|[]],[I5|[]],[I6|[]],[I7|[]],[I8|[]],[I9|[]]]],

        [[A1,A2,A3,A4,A5,A6,A7,A8,A9],
         [B1,B2,B3,B4,B5,B6,B7,B8,B9],
         [C1,C2,C3,C4,C5,C6,C7,C8,C9],
         [D1,D2,D3,D4,D5,D6,D7,D8,D9],
         [E1,E2,E3,E4,E5,E6,E7,E8,E9],
         [F1,F2,F3,F4,F5,F6,F7,F8,F9],
         [G1,G2,G3,G4,G5,G6,G7,G8,G9],
         [H1,H2,H3,H4,H5,H6,H7,H8,H9],
         [I1,I2,I3,I4,I5,I6,I7,I8,I9]]).

sudoku_([[A1,A2,A3,A4,A5,A6,A7,A8,A9],
         [B1,B2,B3,B4,B5,B6,B7,B8,B9],
         [C1,C2,C3,C4,C5,C6,C7,C8,C9],
         [D1,D2,D3,D4,D5,D6,D7,D8,D9],
         [E1,E2,E3,E4,E5,E6,E7,E8,E9],
         [F1,F2,F3,F4,F5,F6,F7,F8,F9],
         [G1,G2,G3,G4,G5,G6,G7,G8,G9],
         [H1,H2,H3,H4,H5,H6,H7,H8,H9],
         [I1,I2,I3,I4,I5,I6,I7,I8,I9]],

        [[ZA1,ZA2,ZA3,ZA4,ZA5,ZA6,ZA7,ZA8,ZA9],
         [ZB1,ZB2,ZB3,ZB4,ZB5,ZB6,ZB7,ZB8,ZB9],
         [ZC1,ZC2,ZC3,ZC4,ZC5,ZC6,ZC7,ZC8,ZC9],
         [ZD1,ZD2,ZD3,ZD4,ZD5,ZD6,ZD7,ZD8,ZD9],
         [ZE1,ZE2,ZE3,ZE4,ZE5,ZE6,ZE7,ZE8,ZE9],
         [ZF1,ZF2,ZF3,ZF4,ZF5,ZF6,ZF7,ZF8,ZF9],
         [ZG1,ZG2,ZG3,ZG4,ZG5,ZG6,ZG7,ZG8,ZG9],
         [ZH1,ZH2,ZH3,ZH4,ZH5,ZH6,ZH7,ZH8,ZH9],
         [ZI1,ZI2,ZI3,ZI4,ZI5,ZI6,ZI7,ZI8,ZI9]]):-write(go),

%Zeilen
diff([A1,A2,A3,A4,A5,A6,A7,A8,A9],[XA1,XA2,XA3,XA4,XA5,XA6,XA7,XA8,XA9]),
diff([B1,B2,B3,B4,B5,B6,B7,B8,B9],[XB1,XB2,XB3,XB4,XB5,XB6,XB7,XB8,XB9]),
diff([C1,C2,C3,C4,C5,C6,C7,C8,C9],[XC1,XC2,XC3,XC4,XC5,XC6,XC7,XC8,XC9]),
diff([D1,D2,D3,D4,D5,D6,D7,D8,D9],[XD1,XD2,XD3,XD4,XD5,XD6,XD7,XD8,XD9]),
diff([E1,E2,E3,E4,E5,E6,E7,E8,E9],[XE1,XE2,XE3,XE4,XE5,XE6,XE7,XE8,XE9]),
diff([F1,F2,F3,F4,F5,F6,F7,F8,F9],[XF1,XF2,XF3,XF4,XF5,XF6,XF7,XF8,XF9]),
diff([G1,G2,G3,G4,G5,G6,G7,G8,G9],[XG1,XG2,XG3,XG4,XG5,XG6,XG7,XG8,XG9]),
diff([H1,H2,H3,H4,H5,H6,H7,H8,H9],[XH1,XH2,XH3,XH4,XH5,XH6,XH7,XH8,XH9]),
diff([I1,I2,I3,I4,I5,I6,I7,I8,I9],[XI1,XI2,XI3,XI4,XI5,XI6,XI7,XI8,XI9]),

%Spalten
diff([XA1,XB1,XC1,XD1,XE1,XF1,XG1,XH1,XI1],[YA1,YB1,YC1,YD1,YE1,YF1,YG1,YH1,YI1]),
diff([XA2,XB2,XC2,XD2,XE2,XF2,XG2,XH2,XI2],[YA2,YB2,YC2,YD2,YE2,YF2,YG2,YH2,YI2]),
diff([XA3,XB3,XC3,XD3,XE3,XF3,XG3,XH3,XI3],[YA3,YB3,YC3,YD3,YE3,YF3,YG3,YH3,YI3]),
diff([XA4,XB4,XC4,XD4,XE4,XF4,XG4,XH4,XI4],[YA4,YB4,YC4,YD4,YE4,YF4,YG4,YH4,YI4]),
diff([XA5,XB5,XC5,XD5,XE5,XF5,XG5,XH5,XI5],[YA5,YB5,YC5,YD5,YE5,YF5,YG5,YH5,YI5]),
diff([XA6,XB6,XC6,XD6,XE6,XF6,XG6,XH6,XI6],[YA6,YB6,YC6,YD6,YE6,YF6,YG6,YH6,YI6]),
diff([XA7,XB7,XC7,XD7,XE7,XF7,XG7,XH7,XI7],[YA7,YB7,YC7,YD7,YE7,YF7,YG7,YH7,YI7]),
diff([XA8,XB8,XC8,XD8,XE8,XF8,XG8,XH8,XI8],[YA8,YB8,YC8,YD8,YE8,YF8,YG8,YH8,YI8]),
diff([XA9,XB9,XC9,XD9,XE9,XF9,XG9,XH9,XI9],[YA9,YB9,YC9,YD9,YE9,YF9,YG9,YH9,YI9]),

%Quadrat
diff([YA1,YB1,YC1,YA2,YB2,YC2,YA3,YB3,YC3],[UA1,UB1,UC1,UA2,UB2,UC2,UA3,UB3,UC3]),
diff([YA4,YB4,YC4,YA5,YB5,YC5,YA6,YB6,YC6],[UA4,UB4,UC4,UA5,UB5,UC5,UA6,UB6,UC6]),
diff([YA7,YB7,YC7,YA8,YB8,YC8,YA9,YB9,YC9],[UA7,UB7,UC7,UA8,UB8,UC8,UA9,UB9,UC9]),
diff([YD1,YE1,YF1,YD2,YE2,YF2,YD3,YE3,YF3],[UD1,UE1,UF1,UD2,UE2,UF2,UD3,UE3,UF3]),
diff([YD4,YE4,YF4,YD5,YE5,YF5,YD6,YE6,YF6],[UD4,UE4,UF4,UD5,UE5,UF5,UD6,UE6,UF6]),
diff([YD7,YE7,YF7,YD8,YE8,YF8,YD9,YE9,YF9],[UD7,UE7,UF7,UD8,UE8,UF8,UD9,UE9,UF9]),
diff([YG1,YH1,YI1,YG2,YH2,YI2,YG3,YH3,YI3],[UG1,UH1,UI1,UG2,UH2,UI2,UG3,UH3,UI3]),
diff([YG4,YH4,YI4,YG5,YH5,YI5,YG6,YH6,YI6],[UG4,UH4,UI4,UG5,UH5,UI5,UG6,UH6,UI6]),
diff([YG7,YH7,YI7,YG8,YH8,YI8,YG9,YH9,YI9],[UG7,UH7,UI7,UG8,UH8,UI8,UG9,UH9,UI9]),

sudoku_([[UA1,UA2,UA3,UA4,UA5,UA6,UA7,UA8,UA9],
         [UB1,UB2,UB3,UB4,UB5,UB6,UB7,UB8,UB9],
         [UC1,UC2,UC3,UC4,UC5,UC6,UC7,UC8,UC9],
         [UD1,UD2,UD3,UD4,UD5,UD6,UD7,UD8,UD9],
         [UE1,UE2,UE3,UE4,UE5,UE6,UE7,UE8,UE9],
         [UF1,UF2,UF3,UF4,UF5,UF6,UF7,UF8,UF9],
         [UG1,UG2,UG3,UG4,UG5,UG6,UG7,UG8,UG9],
         [UH1,UH2,UH3,UH4,UH5,UH6,UH7,UH8,UH9],
         [UI1,UI2,UI3,UI4,UI5,UI6,UI7,UI8,UI9]],

        [[ZA1,ZA2,ZA3,ZA4,ZA5,ZA6,ZA7,ZA8,ZA9],
         [ZB1,ZB2,ZB3,ZB4,ZB5,ZB6,ZB7,ZB8,ZB9],
         [ZC1,ZC2,ZC3,ZC4,ZC5,ZC6,ZC7,ZC8,ZC9],
         [ZD1,ZD2,ZD3,ZD4,ZD5,ZD6,ZD7,ZD8,ZD9],
         [ZE1,ZE2,ZE3,ZE4,ZE5,ZE6,ZE7,ZE8,ZE9],
         [ZF1,ZF2,ZF3,ZF4,ZF5,ZF6,ZF7,ZF8,ZF9],
         [ZG1,ZG2,ZG3,ZG4,ZG5,ZG6,ZG7,ZG8,ZG9],
         [ZH1,ZH2,ZH3,ZH4,ZH5,ZH6,ZH7,ZH8,ZH9],
         [ZI1,ZI2,ZI3,ZI4,ZI5,ZI6,ZI7,ZI8,ZI9]]).

%n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],[1],[4],[2],[3]],[[4],[2],[6],[8],[5],[3],[7],[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).
%n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],[1],[4],[2],[3]],[[4],N,[6],[8],[5],[3],N,[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).
%n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],[2],[3]],[[4],N,[6],[8],[5],N,N,[9],[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).
%n(N),sudoku_([[[5],[3],[4],[6],[7],[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],[4],[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],N,[3]],[[4],N,[6],[8],[5],N,N,N,[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],[7],[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).
%n(N),sudoku_([[[5],[3],[4],[6],N,[8],[9],N,[2]],[[6],[7],N,[1],[9],[5],[3],N,[8]],[[1],N,[8],[3],[4],[2],[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],N,[3]],[[4],N,[6],[8],[5],N,N,N,[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],N,[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).
%n(N),sudoku_([[[5],[3],[4],[6],N,[8],N,N,[2]],[[6],[7],N,[1],[9],N,[3],N,[8]],[[1],N,[8],[3],[4],N,[5],[6],[7]],[[8],[5],[9],[7],[6],N,[4],N,[3]],[[4],N,[6],[8],[5],N,N,N,[1]],[[7],[1],[3],[9],[2],[4],[8],[5],[6]],[N,[6],[1],[5],[3],N,[2],[8],[4]],[[2],[8],[7],[4],N,[9],[6],[3],[5]],[[3],[4],[5],[2],[8],[6],[1],[7],[9]]],[A,B,C,D,E,F,G,H,I]).
%n(N),sudoku_([[[5],[3],N,N,[7],N,N,N,N],[[6],N,N,[1],[9],[5],N,N,N],[N,[9],[8],N,N,N,N,[6],N],[[8],N,N,N,[6],N,N,N,[3]],[[4],N,N,[8],N,[3],N,N,[1]],[[7],N,N,N,[2],N,N,N,[6]],[N,[6],N,N,N,N,[2],[8],N],[N,N,N,[4],[1],[9],N,N,[5]],[N,N,N,N,[8],N,N,[7],[9]]],[A,B,C,D,E,F,G,H,I]).

programmiert für swi-prolog

viel spaß damit

error

ps: die mit % auskommentierten aufrufe unten kann man zum testen nutzen ... sollten funktionieren(ohne garantie

EDIT: es könnte endlosrekursion auftreten( glaub ich ... ist ne weile her , wenn es kein einfaches rätsel ist ... das ganze war nur zum rumspielen mit prolog gedacht ...

Hi Alexej,
mich würde der Code interessieren. Wäre Dir für posten dankbar, bzw. um anderen nicht den Spaß zu nehmen, gerne an uw(ät)dipbach.de - ist schone korrekt ohne e.

Gruß,
Uwe

Entenwickler

Schwere Sudokus sind so aufgebaut, dass du verausdenken musst:
„Wenn ich hier eine 5 mache, muss ich dort eine 3 machen, dann muss die 3 dort hin, und das geht nicht -> keine 5 einsetzen, sondern die andere Möglichkeit“

Genau das kannst du am PC nur doch probieren simulieren. Ich würde es so versuchen, dass der sichere Algrithmus solange arbeiten darf, bis er nicht mehr weiter weiß, dann wird probiert (Backtracing).

Phoemuex

glinux schrieb:

Übrigens funktionieren die meisten Online Löser auf diese weise. Bei eindeutigen Lösungen ist die Peformance im millisikunden bereich. Bei Matrizen mit meheren Lösungen und ungünstiger belegung kann der Code schon mal 30 Sekunden arbeiten.

Entschuldige, aber das hört sich nicht nach einer optimalen Lösung an... Ich habe einen Sudoku-Solver in Python (interpretiert) geschrieben und der löst auf meinem Athlon 3000+ JEDES Feld, das ich bisher probiert habe in unter 3 Sekunden. Und ich habe auch ein KOMPLETT leeres Feld probiert ^^ ne ungünstigere Belegung geht ja wohl nicht mehr.

Vorgegangen wird nach dem logischen Ausschlussprinzip und wenn man damit nicht mehr weiter kommt, wird Backtracking hinzugenommen.

Bei Interesse kann ich den Code mal posten, ich hab das Ganze auch in C++, da allerdings ohne GUI

An dem Generator für Sudokus arbeite ich gerade noch, der ist allerdings etwas langsamer, d.h. es kann bis zu 10 Sekunden dauern

Felix

Hallo zusammen,

das Grundprinzip zum Lösen ist recht einfach.
Du speicherst dir für jede Zelle, die möglichen Zahlen.
Du initialiesierst jede Zell mit allen Zahlen.
Jetzt fängst du an die vorgegebenen Zahlen einzutragen.
Wenn du eine Zahl einträgst, löschst du diese Zahl in deinem Quadrat,
Zeile und Spalte für die übrigen Felder, zudem marikierst du dir dieses
Feld als gelöst. Wenn du jetzt alle vorgegebenen Zahlen eingetragen hast.
Läufst du das Spielfeld durch und sucht, ob in einer Zelle (die nicht als
gelöst markiert ist) nur noch ein Wert möglich ist oder diese Zahl in allen
anderen Zellen der Zeile / Spalte / Quadrat ausgeschlossen ist. Irgendwas wirst
du in der Regel finden. Die kannst du dann wie am Anfang eintragen.
Irgendwann wirst du möglicherweise den Fall haben, dass du irgendwann mit
diesen Mitteln nicht weiterkommst. Wenn du so weit bist, kannst du dann ja
mal wieder schreiben.

Dann mußt du etwa so etwas weiter eingrenzen:
Bsp.: (2,3,4,5) , (2,3,4,5), (1,4,5), (4,5) , (1,5)
Das kannst du auf (2,3) (2,3), (1,4,5), (4,5), (1,5) reduzieren

Da mußt du für alle Teilmengen von Zahlen, alle Felder suchen, in denen sie
vorhanden sind. Falls die Anzahl der gefundenen Felder gleich der Größe der Menge ist, kannst du die restlichen Zahlen in den Feldern löschen.
(Natürlich wieder für alle Zeilen Spalten, Quadrate)
Im Prinzip ist das ne Veralgemeinerung der oberen Verfahren.

Ob du damit alle eindeutigen SuDokus lösen kannst, weiß ich nicht, aber
ziemlich viele.

Gruß,
SuDokuSolver

PS: Ich hoffe ich, ich hab nix vergessen

Warum sollte man einen schlauen Algo schreiben, wenn man es mit probieren in wenigen ms hin bekommt?

Bei einfachen

groovemaster

Toniiii schrieb:

Warum sollte man einen schlauen Algo schreiben, wenn man es mit probieren in wenigen ms hin bekommt?

So ein Algorithmus muss sich ja nicht immer auf das typische 9x9 Sudoku beziehen. Du kannst das Spielfeld fast beliebig vergrössern. Dann werden aus Millisekunden mal ganz schnell Sekunden oder Minuten.