Sudoku in Prolog

klausi

Hallo!

Mir war grad langweilig, also habe ich mir ein kleines programm in prolog geschrieben, dass mir ein beliebiges sudoku-rätsel löst.

jetzt rechnet der swi-prolog interpreter schon seit einer halben stunde und ist immer noch nicht fertig. ich weiß, es gibt sehr viele mögliche kombinationen, aber dass die berechnung so lange dauert .... bin enttäuscht von prolog.

es kann natürlich sein, dass ich da etwas in meinem prog vergessen/übersehn/falsch gemacht habe.

Code

%Mögliche Werte die ein Kastl annehmen kann
bereich(1).
bereich(2).
bereich(3).
bereich(4).
bereich(5).
bereich(6).
bereich(7).
bereich(8).
bereich(9).


%Berechnung einer Zeile, Spalte oder Kästchens
einheit(X1,X2,X3,X4,X5,X6,X7,X8,X9) :- bereich(X1), bereich(X2), bereich(X3), bereich(X4), 
	bereich(X5), bereich(X6), bereich(X7), bereich(X8), bereich(X9), 
	X1 =\= X2, X1 =\= X3, X1 =\= X4, X1 =\= X5, X1 =\= X6, X1 =\= X7, X1 =\= X8, X1 =\= X9,
	X2 =\= X3, X2 =\= X4, X2 =\= X5, X2 =\= X6, X2 =\= X7, X2 =\= X8, X2 =\= X9,
	X3 =\= X4, X3 =\= X5, X3 =\= X6, X3 =\= X7, X3 =\= X8, X3 =\= X9,
	X4 =\= X5, X4 =\= X6, X4 =\= X7, X4 =\= X8, X4 =\= X9,
	X5 =\= X6, X5 =\= X7, X5 =\= X8, X5 =\= X9,
	X6 =\= X7, X6 =\= X8, X6 =\= X9,
	X7 =\= X8, X7 =\= X9,
	X8 =\= X9.


sudoku(	X11,X12,X13,X14,X15,X16,X17,X18,X19,
	X21,X22,X23,X24,X25,X26,X27,X28,X29,
	X31,X32,X33,X34,X35,X36,X37,X38,X39,
	X41,X42,X43,X44,X45,X46,X47,X48,X49,
	X51,X52,X53,X54,X55,X56,X57,X58,X59,
	X61,X62,X63,X64,X65,X66,X67,X68,X69,
	X71,X72,X73,X74,X75,X76,X77,X78,X79,
	X81,X82,X83,X84,X85,X86,X87,X88,X89,
	X91,X92,X93,X94,X95,X96,X97,X98,X99) :-
	%zeilen
	einheit(X11,X12,X13,X14,X15,X16,X17,X18,X19),
	einheit(X21,X22,X23,X24,X25,X26,X27,X28,X29),
	einheit(X31,X32,X33,X34,X35,X36,X37,X38,X39),
	einheit(X41,X42,X43,X44,X45,X46,X47,X48,X49),
	einheit(X51,X52,X53,X54,X55,X56,X57,X58,X59),
	einheit(X61,X62,X63,X64,X65,X66,X67,X68,X69),
	einheit(X71,X72,X73,X74,X75,X76,X77,X78,X79),
	einheit(X81,X82,X83,X84,X85,X86,X87,X88,X89),
	einheit(X91,X92,X93,X94,X95,X96,X97,X98,X99),
	%spalten
	einheit(X11,X21,X31,X41,X51,X61,X71,X81,X91),
	einheit(X12,X22,X32,X42,X52,X62,X72,X82,X92),
	einheit(X13,X23,X33,X43,X53,X63,X73,X83,X93),
	einheit(X14,X24,X34,X44,X54,X64,X74,X84,X94),
	einheit(X15,X25,X35,X45,X55,X65,X75,X85,X95),
	einheit(X16,X26,X36,X46,X56,X66,X76,X86,X96),
	einheit(X17,X27,X37,X47,X57,X67,X77,X87,X97),
	einheit(X18,X28,X38,X48,X58,X68,X78,X88,X98),
	einheit(X19,X29,X39,X49,X59,X69,X79,X89,X99),
	%kästchen
	einheit(X11,X12,X13,X21,X22,X23,X31,X32,X33),
	einheit(X14,X15,X16,X24,X25,X26,X34,X35,X36),
	einheit(X17,X18,X19,X27,X28,X29,X37,X38,X39),
	einheit(X41,X42,X43,X51,X52,X53,X61,X62,X63),
	einheit(X44,X45,X46,X54,X55,X56,X64,X65,X66),
	einheit(X47,X48,X49,X57,X58,X59,X67,X68,X69),
	einheit(X71,X72,X73,X81,X82,X83,X91,X92,X93),
	einheit(X74,X75,X76,X84,X85,X86,X94,X95,X96),
	einheit(X77,X78,X79,X87,X88,X89,X97,X98,X99).

Alles anzeigen

Testfall:

Code

sudoku(	2,X12,X13,X14,X15,7,X17,X18,4,
	X21,7,X23,5,X25,X26,9,X28,X29,
	8,5,X33,X34,3,X36,X37,7,1,
	X41,6,X43,X44,X45,3,7,X48,X49,
	X51,9,7,6,X55,1,X57,X58,X59,
	3,4,X63,X64,X65,X66,6,X68,5,
	X71,X72,X73,9,1,X76,4,X78,X79,
	X81,2,X83,X84,X85,X86,X87,6,X89,
	6,X92,5,2,8,4,X97,X98,X99).

bitte um anregungen!

Plantschkuh!

Es ist in Prolog zwar relativ straight forward, sowas zu formulieren, aber wenn der Suchraum exponentiell ist, dann wird der Interpreter auch exponentiell lang suchen...
Was extrem ineffizient ist, ist daß dein Programm (sehr oft) alle möglichen Kombinationen der Ziffern 1 bis 9 aufzählt und erst dann auf Ungleichheit testet. Besser ist sicher, zuerst mit dif/2 alle Constraints zuzusichern und erst dann die Variablen mit Werten zu belegen. dif/2 unterscheidet sich von =\= und anderen Ungleichheitsprädikaten darin, daß die Argumente noch nicht instanziiert sein müssen; wenn irgendwann später mal beide bekannt sind, wird erst verglichen. Damit schließt man schon während der Aufzählung möglichst früh ungünstige Konstellationen aus.

Hier ist dein Code mit entsprechenden Modifikationen:

Code

zahl(1). zahl(2). zahl(3).
zahl(4). zahl(5). zahl(6).
zahl(7). zahl(8). zahl(9).


unterschiedlich(A,B,C,D,E,F,G,H,I) :-
    dif(A,B), dif(A,C), dif(A,D), dif(A,E), dif(A,F), dif(A,G), dif(A,H), dif(A,I),
              dif(B,C), dif(B,D), dif(B,E), dif(B,F), dif(B,G), dif(B,H), dif(B,I),
                        dif(C,D), dif(C,E), dif(C,F), dif(C,G), dif(C,H), dif(C,I),
                                  dif(D,E), dif(D,F), dif(D,G), dif(D,H), dif(D,I),
                                            dif(E,F), dif(E,G), dif(E,H), dif(E,I),
                                                      dif(F,G), dif(F,H), dif(F,I),
                                                                dif(G,H), dif(G,I),
                                                                          dif(H,I).
zahlen(A,B,C,D,E,F,G,H,I) :-
    zahl(A), zahl(B), zahl(C),
    zahl(D), zahl(E), zahl(F),
    zahl(G), zahl(H), zahl(I).


sudoku( X11,X12,X13,X14,X15,X16,X17,X18,X19,
        X21,X22,X23,X24,X25,X26,X27,X28,X29,
        X31,X32,X33,X34,X35,X36,X37,X38,X39,
        X41,X42,X43,X44,X45,X46,X47,X48,X49,
        X51,X52,X53,X54,X55,X56,X57,X58,X59,
        X61,X62,X63,X64,X65,X66,X67,X68,X69,
        X71,X72,X73,X74,X75,X76,X77,X78,X79,
        X81,X82,X83,X84,X85,X86,X87,X88,X89,
        X91,X92,X93,X94,X95,X96,X97,X98,X99) :-
        % zeilen
        unterschiedlich(X11,X12,X13,X14,X15,X16,X17,X18,X19),
        unterschiedlich(X21,X22,X23,X24,X25,X26,X27,X28,X29),
        unterschiedlich(X31,X32,X33,X34,X35,X36,X37,X38,X39),
        unterschiedlich(X41,X42,X43,X44,X45,X46,X47,X48,X49),
        unterschiedlich(X51,X52,X53,X54,X55,X56,X57,X58,X59),
        unterschiedlich(X61,X62,X63,X64,X65,X66,X67,X68,X69),
        unterschiedlich(X71,X72,X73,X74,X75,X76,X77,X78,X79),
        unterschiedlich(X81,X82,X83,X84,X85,X86,X87,X88,X89),
        unterschiedlich(X91,X92,X93,X94,X95,X96,X97,X98,X99),
        % spalten
        unterschiedlich(X11,X21,X31,X41,X51,X61,X71,X81,X91),
        unterschiedlich(X12,X22,X32,X42,X52,X62,X72,X82,X92),
        unterschiedlich(X13,X23,X33,X43,X53,X63,X73,X83,X93),
        unterschiedlich(X14,X24,X34,X44,X54,X64,X74,X84,X94),
        unterschiedlich(X15,X25,X35,X45,X55,X65,X75,X85,X95),
        unterschiedlich(X16,X26,X36,X46,X56,X66,X76,X86,X96),
        unterschiedlich(X17,X27,X37,X47,X57,X67,X77,X87,X97),
        unterschiedlich(X18,X28,X38,X48,X58,X68,X78,X88,X98),
        unterschiedlich(X19,X29,X39,X49,X59,X69,X79,X89,X99),
        % kaestchen
        unterschiedlich(X11,X12,X13,X21,X22,X23,X31,X32,X33),
        unterschiedlich(X14,X15,X16,X24,X25,X26,X34,X35,X36),
        unterschiedlich(X17,X18,X19,X27,X28,X29,X37,X38,X39),
        unterschiedlich(X41,X42,X43,X51,X52,X53,X61,X62,X63),
        unterschiedlich(X44,X45,X46,X54,X55,X56,X64,X65,X66),
        unterschiedlich(X47,X48,X49,X57,X58,X59,X67,X68,X69),
        unterschiedlich(X71,X72,X73,X81,X82,X83,X91,X92,X93),
        unterschiedlich(X74,X75,X76,X84,X85,X86,X94,X95,X96),
        unterschiedlich(X77,X78,X79,X87,X88,X89,X97,X98,X99),
        % alles zahlen
        zahlen(X11,X12,X13,X14,X15,X16,X17,X18,X19),
        zahlen(X21,X22,X23,X24,X25,X26,X27,X28,X29),
        zahlen(X31,X32,X33,X34,X35,X36,X37,X38,X39),
        zahlen(X41,X42,X43,X44,X45,X46,X47,X48,X49),
        zahlen(X51,X52,X53,X54,X55,X56,X57,X58,X59),
        zahlen(X61,X62,X63,X64,X65,X66,X67,X68,X69),
        zahlen(X71,X72,X73,X74,X75,X76,X77,X78,X79),
        zahlen(X81,X82,X83,X84,X85,X86,X87,X88,X89),
        zahlen(X91,X92,X93,X94,X95,X96,X97,X98,X99).

Alles anzeigen

Das ist mit deinem Testfall ziemlich schnell: 429,041 inferences, 0.34 CPU in 0.38 seconds (89% CPU, 1261885 Lips)
Ob auch das Ergebnis stimmt, kann wer anderer überprüfen

Hübscher wäre das ganze übrigens mit Listen, aber was soll's. Und auch mit Constraints, siehe 11.8 im SWI-Manual.

klausi

thx, sehr elegant mit dif/2.

hatte zuerst probleme mit dif in meiner swi-prolog version (die schon komplett veraltet ist, aber noch immer in den repositories von ubuntu ist). habs jetzt per ssh im inflab ausprobiert, funktioniert wunderbar:thumb:
der respekt vor prolog ist wiederhergestellt

P.S.: Plantschkuh muss ich jetzt respekt oder angst vor dir haben, weil du mir mit einer vollwertigen lösung binnen einer stunde aufwartest?:zwinker:

rul0r

definitiv angst

Plantschkuh!

Zitat von klausi

Plantschkuh muss ich jetzt respekt oder angst vor dir haben, weil du mir mit einer vollwertigen lösung binnen einer stunde aufwartest?:zwinker:

Mir ist beides recht Naja, viel war echt nicht zu machen, der größte Teil des Codes stammt von dir. Ich hab nur ein paar Sachen umbenannt und die Vergleiche nach vorne gezogen.
Außerdem hätte ich gerade total fleißig eine Präsentation ausarbeiten sollen, also hatte ich viel Zeit für sowas...

Spockman

Zitat von klausi

Mir war grad langweilig, also habe ich mir ein kleines programm in prolog geschrieben, dass mir ein beliebiges sudoku-rätsel löst.

Verwend den FD-Constraint-Solver von SWI (library(bounds)). Tipp: all_different/1 Constraint, bzw. all_distinct/1 aus library(clp_distinct). Du findest eine effiziente Loesung in einem alten Thread hier: http://www.informatik-forum.at/showthread.php?t=38825

klausi

stimmt, googeln hätte auch geholfen.
aber es ist doch auch mal witzig das rad selbst zu erfinden

EDIT: außerdem war mir ja langweilig

JohnFoo

Grad' hab ich beim Frühstück eben an diese Aufgabe gedacht. Muss ich gleich mal testen ..

shebang

hab sowas auch schon vor längerer zeit in javascript gemacht: http://stud4.tuwien.ac.at/~e0325694/sudoku-solver.html

Adok

Und ich in C: http://www.students.meduniwien.ac.at/~n0102122/miscellaneous/sudoku.zip

maddinatone

[edit]
*ack - wo is denn mein text hin ?*

Plantschkuh!

In der einen Datei kannst du deine Instanzen definieren:

Code

sudokuinstanz([[1,2,3,_,_,9,7,8,4], ...]).

oder

Code

sudokuinstanz(1,2,3,_,_,9,7,8,4, ...).

Und in der anderen Datei in deinem Sudoku-Prädikat diese sudokuinstanz als Ziel (am Anfang) einfügen.

maddinatone

Zitat von Plantschkuh!

...diese sudokuinstanz als Ziel (am Anfang) einfügen.

Hmm...also ich stehe noch ziemlich am Anfang mit dem guten Prolog, googlen nach "Prolog Ziel" ergab nichts was mir unmittelbar weiterhilft...oder meinst Du damit das "consult(raetsel.pl)." ?

Bin da etwas ratlos, vielen Dank schonmal !

de Maddin...

Jetzt mitmachen!