% Loeser fuer Sudoku

% Nach http://user.it.uu.se/~justin/sudoku.pl, angepasst fuer Eclipse.
% Benutzt den Constraint-Loeser fuer endliche Domains

% "It took less than 30 minutes (mainly because I don't type that fast)."


:- use_module(library(fd)).
:- use_module(library(lists)).

demo1 :-
% Aus der Zeit vom 13. 10. 2005.
	L=
	[[_,_,8,  _,_,_,  6,_,_],
	 [_,4,_,  9,_,2,  _,5,_],
	 [_,_,_,  6,4,8,  _,_,_],

	 [_,3,9,  _,2,_,  1,7,_],
	 [_,1,_,  _,_,_,  _,3,_],
	 [_,8,5,  _,1,_,  2,6,_],

	 [_,_,_,  2,8,7,  _,_,_],
	 [_,6,_,  1,_,4,  _,8,_],
	 [_,_,2,  _,_,_,  5,_,_]],
	sudoku(L),
	pretty_print(L).



% Expects a list of lists 9 by 9 grid.

sudoku(L) :-
	flatten(L,AllVars),
	AllVars :: 1..9,
	[R1,R2,R3,R4,R5,R6,R7,R8,R9] = L,
% Each row is different.
	alldifferent(R1), alldifferent(R2), alldifferent(R3),
	alldifferent(R4), alldifferent(R5), alldifferent(R6),
	alldifferent(R7), alldifferent(R8), alldifferent(R9),
	transpose(L,TL),
% Each column is different.
	[C1,C2,C3,C4,C5,C6,C7,C8,C9] = TL,
	alldifferent(C1), alldifferent(C2), alldifferent(C3),
	alldifferent(C4), alldifferent(C5), alldifferent(C6),
	alldifferent(C7), alldifferent(C8), alldifferent(C9),
% 3x3 squares, could be more elegant
	[X11,X12,X13,X14,X15,X16,X17,X18,X19] = R1,
	[X21,X22,X23,X24,X25,X26,X27,X28,X29] = R2,
	[X31,X32,X33,X34,X35,X36,X37,X38,X39] = R3,
	[X41,X42,X43,X44,X45,X46,X47,X48,X49] = R4,
	[X51,X52,X53,X54,X55,X56,X57,X58,X59] = R5,
	[X61,X62,X63,X64,X65,X66,X67,X68,X69] = R6,
	[X71,X72,X73,X74,X75,X76,X77,X78,X79] = R7,
	[X81,X82,X83,X84,X85,X86,X87,X88,X89] = R8,
	[X91,X92,X93,X94,X95,X96,X97,X98,X99] = R9,
	alldifferent([X11,X12,X13,X21,X22,X23,X31,X32,X33]),
	alldifferent([X41,X42,X43,X51,X52,X53,X61,X62,X63]),
	alldifferent([X71,X72,X73,X81,X82,X83,X91,X92,X93]),
	alldifferent([X14,X15,X16,X24,X25,X26,X34,X35,X36]),
	alldifferent([X44,X45,X46,X54,X55,X56,X64,X65,X66]),
	alldifferent([X74,X75,X76,X84,X85,X86,X94,X95,X96]),
	alldifferent([X17,X18,X19,X27,X28,X29,X37,X38,X39]),
	alldifferent([X47,X48,X49,X57,X58,X59,X67,X68,X69]),
	alldifferent([X77,X78,X79,X87,X88,X89,X97,X98,X99]),
% Enforce a solution		
	labeling(AllVars).

	
% Transpose a list of lists.

transpose([Word], Cs) :- !,
	R = Word,
	list2columns(R, Cs).
transpose([Word|Words], Cs) :- !,
	transpose(Words, Cs0),
	R=Word,
	put_columns(R, Cs0, Cs).
	
list2columns([], []).
list2columns([X|Xs], [[X]|Zs]) :- list2columns(Xs, Zs).

put_columns([], Cs, Cs).
put_columns([X|Xs], [C|Cs0], [[X|C]|Cs]) :- put_columns(Xs, Cs0, Cs).


/* Pretty Print L */

pretty_print([]).
pretty_print([H|T]) :-
	write(H),nl,
	pretty_print(T).