/*
 * Prolog-Programm zum Loesen von Sudoku-Raetseln
 *
 * Autor: Kristof Hamann
 * Datum: 7. Mai 2006
 *
 * Diese Regeln finden Loesungen fuer Sudoku-Raetsel. Dabei koennen komplett
 * unterspezifizierte, teilspezifizierte oder vollstaendig spezifizierte
 * Aufrufe erfolgen. Dadurch koennen ALLE moeglichen Sudoku-Felder erzeugt
 * werden, ein Raetsel geloest oder ein vorliegendes Feld verifiziert werden.
 *
 * Beispiel-Eingaben siehe Kommentar ueber der Regel sudoku/3
 *
 * Es wird dabei nicht die Holzhammer-Methode benutzt, deren Implementierung
 * in Prolog simpel waere. Statt dessen wird in dieser Implementierung mit
 * Hilfs-Listen gearbeitet, die direkt beim Finden von Belegungen fuer die
 * Felder nicht erlaubte Kombinationen ausschliessen. Daher ist der Code
 * auf den ersten Blick etwas unuebersichtlich.
 */

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

drin(X, [X | _]).
drin(X, [_ | Tail]) :- drin(X, Tail).


zeile([Feld1,  Feld2,  Feld3],
	Used,  [Feld1, Feld2, Feld3 | Used],
	UsedZ, [Feld1, Feld2, Feld3 | UsedZ],
	US1, [Feld1 | US1],
	US2, [Feld2 | US2],
	US3, [Feld3 | US3]
	) :-
	zahl(Feld1),   zahl(Feld2),   zahl(Feld3),
	\+ drin(Feld1, Used),
	\+ drin(Feld1, UsedZ),
	\+ drin(Feld1, US1),
	\+ drin(Feld2, [Feld1 | Used]),
	\+ drin(Feld2, [Feld1 | UsedZ]),
	\+ drin(Feld2, US2),
	\+ drin(Feld3, [Feld1, Feld2 | Used]),
	\+ drin(Feld3, [Feld1, Feld2 | UsedZ]),
	\+ drin(Feld3, US3).

block([Zeile1, Zeile2, Zeile3], UZ1, UZ2, UZ3, UZ1o, UZ2o, UZ3o,
	US1, US2, US3, XS1, XS2, XS3) :-
	zeile(Zeile1, [], U1, UZ1, UZ1o,  US1, VS1, US2, VS2, US3, VS3),
	zeile(Zeile2, U1, U2, UZ2, UZ2o,  VS1, WS1, VS2, WS2, VS3, WS3),
	zeile(Zeile3, U2, _,  UZ3, UZ3o,  WS1, XS1, WS2, XS2, WS3, XS3).

reihe([Block1, Block2, Block3],
	US1, US2, US3, US4, US5, US6, US7, US8, US9,
	VS1, VS2, VS3, VS4, VS5, VS6, VS7, VS8, VS9
	) :-
	block(Block1, [], [], [], U1, U2, U3,  US1,US2,US3, VS1,VS2,VS3),
	block(Block2, U1, U2, U3, V1, V2, V3,  US4,US5,US6, VS4,VS5,VS6),
	block(Block3, V1, V2, V3, _,  _,  _,   US7,US8,US9, VS7,VS8,VS9).


/* Beispiel-Eingabe:

A=[[_,_,_],[_,_,_],[_,_,_]],
B=[[_,_,_],[_,_,_],[_,_,_]],
C=[[_,_,_],[_,_,_],[_,_,_]],
D=[[_,_,_],[_,_,_],[_,_,_]],
E=[[_,_,_],[_,_,_],[_,_,_]],
F=[[_,_,_],[_,_,_],[_,_,_]],
G=[[_,_,_],[_,_,_],[_,_,_]],
H=[[_,_,_],[_,_,_],[_,_,_]],
I=[[_,_,_],[_,_,_],[_,_,_]],
sudoku([[A,B,C], [D,E,F], [G,H,I]]).


A=[[_,1,_],[7,_,_],[_,_,_]],
B=[[_,9,6],[_,5,_],[_,_,2]],
C=[[3,_,8],[9,_,_],[_,_,_]],
D=[[_,_,3],[8,9,_],[_,_,_]],
E=[[_,_,4],[7,_,5],[9,_,_]],
F=[[_,_,_],[_,3,6],[4,_,_]],
G=[[_,_,_],[_,_,6],[2,_,7]],
H=[[5,_,_],[_,5,_],[3,4,_]],
I=[[_,_,_],[_,_,1],[_,8,_]],
sudoku([[A,B,C], [D,E,F], [G,H,I]]).

*/

sudoku([Reihe1, Reihe2, Reihe3]) :-
	reihe(Reihe1, [],[],[],[],[],[],[],[],[], U1,U2,U3,U4,U5,U6,U7,U8,U9),
	reihe(Reihe2, U1,U2,U3,U4,U5,U6,U7,U8,U9, V1,V2,V3,V4,V5,V6,V7,V8,V9),
	reihe(Reihe3, V1,V2,V3,V4,V5,V6,V7,V8,V9, _, _, _, _, _, _, _, _, _).