% Author: Karthik Nadig
% Copyright © 2012
% Instructions:
% Type start to test out a few puzzles
% ?- start.
start:-
	write('Easy Puzzle: '),nl,
	EasyPuzzle=[
		[_,_,_,6,_,5,8,_,_],
		[6,_,_,_,_,1,3,_,4],
		[5,_,_,8,_,9,_,7,_],
		[8,3,9,_,_,_,_,_,_],
		[7,_,4,5,_,8,6,_,3],
		[_,_,_,_,_,_,4,8,7],
		[_,6,_,1,_,7,_,_,8],
		[9,_,1,4,_,_,_,_,5],
		[_,_,3,9,_,6,_,_,_]
	       ],
	solve(EasyPuzzle),write(EasyPuzzle),nl,
	write('Medium Puzzle: '),nl,
	MediumPuzzle =[
		[_,_,_,1,_,_,_,3,_],
		[_,3,1,_,_,8,9,4,5],
		[_,_,2,_,9,_,1,_,_],
		[_,_,_,_,_,4,_,_,_],
		[_,9,5,_,3,_,2,7,_],
		[_,_,_,7,_,_,_,_,_],
		[_,_,3,_,6,_,5,_,_],
		[1,7,6,5,_,_,3,8,_],
		[_,5,_,_,_,9,_,_,_]
	       ],
	solve(MediumPuzzle),write(MediumPuzzle),nl,
	write('Hard Puzzle:'),nl,
	HardPuzzle=[
	    [3,_,_,_,2,_,7,5,4],
		[_,_,1,9,_,5,_,_,8],
		[2,_,_,_,3,_,_,_,_],
		[5,3,_,_,_,_,1,_,_],
		[_,_,_,_,_,_,_,_,_],
		[_,_,2,_,_,_,_,4,5],
		[_,_,_,_,8,_,_,_,6],
		[7,_,_,1,_,9,4,_,_],
		[8,4,5,_,6,_,_,_,3]
	       ],
	solve(HardPuzzle),write(HardPuzzle),nl,
	write('Evil Puzzle:'),nl,
	EvilPuzzle=[
	    [_,_,_,9,1,_,_,_,_],
		[_,_,_,_,_,5,_,7,_],
		[_,6,5,_,_,3,_,_,4],
		[2,_,_,_,_,_,3,8,_],
		[_,1,_,6,_,4,_,9,_],
		[_,5,6,_,_,_,_,_,1],
		[9,_,_,2,_,_,8,5,_],
		[_,2,_,1,_,_,_,_,_],
		[_,_,_,_,3,7,_,_,_]
	       ],
	solve(EvilPuzzle),write(EvilPuzzle),nl.

% allUnique(+List).
% checks if each member in the list is unique
allUnique(X):-
	nonvar(X),
	X=[].
allUnique([H|T]):-
	\+member(H,T),
	allUnique(T).

% member1(?Element,+List).
% Accepts element and a list and finds a position
% for the element in the list.
member1(B, [C|A]) :-
	nonvar(C),!,
        member1(A, B, C).
member1(B, [C|A]) :-
	var(C),!,
        member1(B,A).
member1(_, A, A).
member1([C|A], B, _) :-
	nonvar(C),!,
        member1(A, B, C).
member1([C|A], B, _) :-
	var(C),!,
	member1(B,A).

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

% getNext(+List1,+List2,+List3,-Element).
% Finds a element thats fits into the three lists
getNext(L1,L2,L3,A):-
	between(1,9,A),
	\+member(A,L1),
	\+member(A,L2),
	\+member(A,L3).

% solve(+Puzzle).
% Accepts a list of 9 elements where each element
% of the list is a list of 9 integers between 1 and 9.
solve(Puzzle):-
	Puzzle=[
		[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]
	       ],
getNext([A2,A3,A4,A5,A6,A7,A8,A9],[B1,C1,D1,E1,F1,G1,H1,I1],[A2,A3,B1,B2,B3,C1,C2,C3],A1),
getNext([A1,A3,A4,A5,A6,A7,A8,A9],[B2,C2,D2,E2,F2,G2,H2,I2],[A1,A3,B1,B2,B3,C1,C2,C3],A2),
getNext([A1,A2,A4,A5,A6,A7,A8,A9],[B3,C3,D3,E3,F3,G3,H3,I3],[A1,A2,B1,B2,B3,C1,C2,C3],A3),
getNext([A1,A2,A3,A5,A6,A7,A8,A9],[B4,C4,D4,E4,F4,G4,H4,I4],[A5,A6,B4,B5,B6,C4,C5,C6],A4),
getNext([A1,A2,A3,A4,A6,A7,A8,A9],[B5,C5,D5,E5,F5,G5,H5,I5],[A4,A6,B4,B5,B6,C4,C5,C6],A5),
getNext([A1,A2,A3,A4,A5,A7,A8,A9],[B6,C6,D6,E6,F6,G6,H6,I6],[A4,A5,B4,B5,B6,C4,C5,C6],A6),
getNext([A1,A2,A3,A4,A5,A6,A8,A9],[B7,C7,D7,E7,F7,G7,H7,I7],[A8,A9,B7,B8,B9,C7,C8,C9],A7),
getNext([A1,A2,A3,A4,A5,A6,A7,A9],[B8,C8,D8,E8,F8,G8,H8,I8],[A7,A9,B7,B8,B9,C7,C8,C9],A8),
getNext([A1,A2,A3,A4,A5,A6,A7,A8],[B9,C9,D9,E9,F9,G9,H9,I9],[A7,A8,B7,B8,B9,C7,C8,C9],A9),

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

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


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

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

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

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

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

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

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

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