sudoku.pl

這是個prolog程式

%solve([]/[]/[]/[], Solution).
%sudoku([4,2,0,0]/[0,1,0,2]/[0,0,1,0]/[1,0,0,4], Solution).

sudoku(Problem, Sol) :-
	solve([]/[]/[]/[],Sol),
	match([Problem], Sol).

match([[X11,X12,X13,X14]/[X21,X22,X23,X24]/[X31,X32,X33,X34]/[X41,X42,X43,X44]], [[Y11,Y12,Y13,Y14]/[Y21,Y22,Y23,Y24]/[Y31,Y32,Y33,Y34]/[Y41,Y42,Y43,Y44]]):-
	(X11 =:= 0;X11 =:= Y11),
	(X12 =:= 0;X12 =:= Y12),
	(X13 =:= 0;X13 =:= Y13),
	(X14 =:= 0;X14 =:= Y14),
	(X21 =:= 0;X21 =:= Y21),
	(X22 =:= 0;X22 =:= Y22),
	(X23 =:= 0;X23 =:= Y23),
	(X24 =:= 0;X24 =:= Y24),
	(X31 =:= 0;X31 =:= Y31),
	(X32 =:= 0;X32 =:= Y32),
	(X33 =:= 0;X33 =:= Y33),
	(X34 =:= 0;X34 =:= Y34),
	(X41 =:= 0;X41 =:= Y41),
	(X42 =:= 0;X42 =:= Y42),
	(X43 =:= 0;X43 =:= Y43),
	(X44 =:= 0;X44 =:= Y44).

goal([_,_,_,_]/[_,_,_,_]/[_,_,_,_]/[_,_,_,_]).

solve(Node,Solution):-
	depthfirst([],Node,Solution).

depthfirst(Path,Node,[Node]):-
	goal(Node).

depthfirst(Path,Node,Sol):-
	break(Node,Node1),
	not(member(Node1,Path)),
	depthfirst([Node|Path],Node1,Sol).

break(R1/R2/R3/R4, Nr1/Nr2/Nr3/Nr4):-	%put each number like eight queen
	s(R1,Nr1),
	s(R2,Nr2),
	s(R3,Nr3),
	s(R4,Nr4),
	column(R1,R2,R3,R4).				%each column checks no numbers put the same place

s(Queens, [Queen|Queens]):-
	member(Queen, [1,2,3,4]),
	count(Queens, N),					%count how many queens (N)
	N1 is N + 1,
	not(attacks(Queen, Queens, N1)).	%new queen X coordinate is N+1

attacks(Y, Others, X):-
	member(Y1, Others),
	position(Y1, Others, X1),			%queen at Y1 that its position is X1
	(Y1 = Y;							%Y1 is equal Y then queen attack
	blockone(X, Y, X1, Y1);				%same number in block appears twice then attack
	blocktwo(X, Y, X1, Y1);
	blockthree(X, Y, X1, Y1);
	blockfour(X, Y, X1, Y1)).

position(Target,[A|L], P):-				%get position X
	member(Target, [A]),
	count([A|L], P)
	;
	position(Target, L, P).

blockone(X, Y, X1, Y1):-				%coordinate X[1,2] Y[1,2]
	member(X, [1,2]),
	member(Y, [1,2]),
	member(X1, [1,2]),
	member(Y1, [1,2]).

blocktwo(X, Y, X1, Y1):-				%coordinate X[3,4] Y[1,2]
	member(X, [3,4]),
	member(Y, [1,2]),
	member(X1, [3,4]),
	member(Y1, [1,2]).

blockthree(X, Y, X1, Y1):-				%coordinate X[1,2] Y[3,4]
	member(X, [1,2]),
	member(Y, [3,4]),
	member(X1, [1,2]),
	member(Y1, [3,4]).

blockfour(X, Y, X1, Y1):-				%coordinate X[3,4] Y[3,4]
	member(X, [3,4]),
	member(Y, [3,4]),
	member(X1, [3,4]),
	member(Y1, [3,4]).

column([],[],[],[]).
column([F1 | L1],[F2 | L2],[F3 | L3],[F4 | L4]):-
	not(member(F2, [F1])),
	not(member(F3, [F1,F2])),
	not(member(F4, [F1,F2,F3])),
	column(L1,L2,L3,L4).

count([],0).
count([_|L], N):-
	count(L, N1),
	N is N1 + 1 .

member(X, [X|_]).
member(X, [Y|L]):-
	member(X, L).