% sudoku(Puzzle) :- solve the given Sudoku puzzle and print the problem statement as well as the solution to the standard output (list-of-integers, partially instantiated) 
 
sudoku(Puzzle) :-  
   printPuzzle(Puzzle),		% prints the given puzzle as it is
   nl,						% 'nl' prints a new line. 
   connect(Spots),			% creates the Sudoku map
   flag(counter,_,0),		% map 'counter' => 0. 
   init(Puzzle,Spots),
   solve(Spots),
   printPuzzle(Puzzle),
   flag(counter,N,N+1),		% if: 'counter' => N, map 'counter' => N+1. 
   fail.
sudoku(_) :-				% when will we get here?
   flag(counter,N,N),		% retrieve N. 
   nl, printCounter(N).

printPuzzle([]). 
printPuzzle(Xs) :- nl,
   printBand(Xs,Xs1),
   write('--------+---------+--------'), nl,
   printBand(Xs1,Xs2),
   write('--------+---------+--------'), nl,
   printBand(Xs2,_).
 
printBand(Xs,Xs3) :-
   printRow(Xs,Xs1), nl,
   write('        |         |'), nl,
   printRow(Xs1,Xs2), nl, 
   write('        |         |'), nl,
   printRow(Xs2,Xs3), nl.

printRow(Xs,Xs3) :-
   printTriplet(Xs,Xs1), write(' | '),
   printTriplet(Xs1,Xs2), write(' | '),
   printTriplet(Xs2,Xs3).
 
printTriplet(Xs,Xs3) :-
   printElement(Xs,Xs1), write('  '),
   printElement(Xs1,Xs2), write('  '),
   printElement(Xs2,Xs3).
 
printElement([X|Xs],Xs) :- var(X), !, write('.').
printElement([X|Xs],Xs) :- write(X). 
 
printCounter(0) :- !, write('No solution'), nl.
printCounter(1) :- !, write('1 solution'), nl.
printCounter(K) :- write(K), write(' solutions'), nl.

% The most difficult part of the problem solution is to prepare the list of spot/4 terms representing the spots in the puzzle. We have to make sure that every spot "knows" its row column, and square. In other words, all the spots in a row access the same list in order to check whether a new number can be placed in the row. The same is true for the columns and the squares.  
 
% connect(Spots) :- Spots = [spot(_,R1,C1,S1),spot(_,R1,C2,S1),.....]. 
 
connect(Spots) :-
   length(Spots,81),
   connectRows(Spots),
   connectCols(Spots),
   connectSquares(Spots).

% Question 1a
% skip(List,N,List1) :- skip the first N elements from a List and return the rest of the list in List1. If the List is too short, then succeed and return [] as rest.

skip([],_,[]) :- !.
skip(Xs,0,Xs) :- !.
skip([_|Xs],N,List1) :- 
	M is N-1, 
	skip(Xs,M,List1).

% Question 1b
% connectRow(Spots,R,K) :- the first K elements of Spots are in the same row R.

connectRow(_,_,0) :- !.
connectRow([spot(_,R,_,_)|Rest],R,K) :-
	J is K-1,
	connectRow(Rest,R,J).

% Question 1c
% connectRows(Spots) :- connect the spots of all rows in the list Spots.

connectRows([]).
connectRows(Spots) :- 
	connectRow(Spots,_,9),
	skip(Spots,9,Rest), 
	connectRows(Rest).

% Question 1d
% connectCol(Spots,C) :- connect the first spot in Spots with the other spots in its column C.

connectCol([],_).
connectCol([spot(_,_,C,_)|Rest],C) :-
	skip(Rest,8,Rest1),
	connectCol(Rest1,C).

% Question 1e
% connectCols(Spots) :- connect the spots of the same column.

connectCols(Spots) :- connectCols(Spots,9).

% connectCols(Spots,K) :- connect K more columns (0<=K<=9).

connectCols(_,0) :- !.
connectCols(Spots,K) :-
	J is K-1,
	skip(Spots,J,Rest),
	connectCol(Rest,_),
	connectCols(Spots,J).

% Question 1f
% connectTriplet(Spots,S) :- connect the next three spots in the Spots list with the square S.

connectTriplet([spot(_,_,_,S),spot(_,_,_,S),spot(_,_,_,S)|_],S).

% Question 1g
% connectSq(Spots,S) :- connect the spots of square S. In the Spots list each square is composed of three spot-triplets which are separated by 6 spots.

connectSq(Spots,S) :-
	connectTriplet(Spots,S),
	skip(Spots,9,Rest),
	connectTriplet(Rest,S),
	skip(Rest,9,Rest1),
	connectTriplet(Rest1,S).

% Question 1h
% connectBand(Spots) :- connec the next band (of three squares).

connectBand(Spots) :-
	connectSq(Spots,_),
	skip(Spots,3,Rest),
	connectSq(Rest,_),
	skip(Rest,3,Rest1),
	connectSq(Rest1,_).
	
% Question 1i
% connectSquares(Spots) :- connect all three bands. The nine squares are arranged in three horizontal bands, three squares in each band.

connectSquares(Spots) :-
	connectBand(Spots),
	skip(Spots,27,Rest),
	connectBand(Rest),
	skip(Rest,27,Rest1),
	connectBand(Rest1).
 
% insert(X,L) :- X can be inserted into the list without conflict, i.e. X is not yet in the list, when insert/2 is called. Otherwise the predicate fails. 
 
insert(X,L) :- var(L), !, L = [X|_]. % if L is yet undefined, make it with X
insert(X,[X|_]) :- fail, !. % if found, then fail
insert(X,[Y|Ys]) :- nonvar(X), X=\=Y, insert(X,Ys). % look for X in Ys


% Question 1j
% If X is not instantiated in the given puzzle (X is a variable), create a link between the variable in the puzzle and the corresponding variable in the spot. Otherwise copy the given number from the puzzle into the spot and insert it into the spot's correct row, column, and square, if this is legal.

initSpot(X,spot(X,_,_,_)) :- var(X), !. % if X is undefined, just makes up a spot... on the spot.
initSpot(X,spot(X,R,C,S)) :- integer(X), insert(X,R), insert(X,C), insert(X,S). % if X is an integer, make sure it's ok to insert it in each on of its lists.


% Question 1k
% init(Puzzle,Spots) :- initialize the Spots list on the basis of the problem statement (Puzzle) and link the Puzzle list to the Spots list.

init([Puz|Rest1],[Spot|Rest2]) :- initSpot(Puz,Spot), init(Rest1,Rest2).
init([],[]).


% Question 1l
% bind(Spot) :- bind the data field in Spot to an available non-conflicting digit. 

bind(spot(X,_,_,_)) :- nonvar(X), !. % if x is defined, ok.
bind(spot(X,R,C,S)) :- var(X), between(1,9,X), insert(X,R), insert(X,C), insert(X,S). % if x is undefined, need to find a number between 1 and 9 that will be ok to insert into spot.


% Question 1m
% solve(Spots) :- solve the problem using backtracking

solve([]) :- !.
solve([Spot|Spots]) :- bind(Spot), solve(Spots).



test(N) :- puzzle(N,P), sudoku(P).

puzzle(1,P) :- P = [_,_,4,8,_,_,_,1,7, 6,7,_,9,_,_,_,_,_, 5,_,8,_,3,_,_,_,4,3,_,_,7,4,_,1,_,_, _,6,9,_,_,_,7,8,_, _,_,1,_,6,9,_,_,5,1,_,_,_,8,_,3,_,6, _,_,_,_,_,6,_,9,1, 2,4,_,_,_,1,5,_,_].

puzzle(2,P) :- P = [3,_,_,_,7,1,_,_,_, _,5,_,_,_,_,1,8,_, _,4,_,8,_,_,_,_,_,_,_,6,2,_,_,3,_,_, _,_,1,_,5,_,8,_,_, _,_,3,_,_,8,2,_,_,_,_,_,_,_,3,_,4,_, _,6,4,_,_,_,_,7,_, _,_,_,9,6,_,_,_,1]. 
 
puzzle(3,P) :- P = [1,7,_,_,_,9,_,_,4, _,_,_,_,_,_,7,_,_, 5,_,_,3,_,_,2,_,_,_,8,_,_,_,_,5,3,6, _,_,_,_,8,_,_,_,_, 6,9,1,_,_,_,_,8,_,_,_,7,_,_,4,_,_,2, _,_,2,_,_,_,_,_,_, 3,_,_,5,_,_,_,7,1]. 
 
% an example with many solutions 
puzzle(4,P) :- P = [1,_,_,_,_,9,_,_,4, _,_,_,_,_,_,7,_,_, 5,_,_,3,_,_,2,_,_,_,8,_,_,_,_,5,_,6, _,_,_,_,8,_,_,_,_, 6,9,1,_,_,_,_,8,_,_,_,7,_,_,4,_,_,2, _,_,2,_,_,_,_,_,_, 3,_,_,5,_,_,_,7,1]. 
 
puzzle(5,P) :- P = [_,6,5,_,_,_,7,2,_, 3,_,7,_,_,_,1,_,8, 2,9,_,_,1,_,_,3,4,_,_,_,5,_,7,_,_,_, _,_,1,_,_,_,8,_,_, _,_,_,2,_,1,_,_,_,8,1,_,_,2,_,_,5,7, 7,_,2,_,_,_,9,_,1, _,5,4,_,_,_,6,8,_].

puzzle(6,P) :- P = [5,_,2,_,_,3,_,_,_, 4,6,_,_,7,_,9,_,_, _,_,3,4,_,_,_,_,_,9,5,_,_,6,_,_,_,_, _,4,_,_,_,_,_,9,_, _,_,_,_,9,_,_,1,7,_,_,_,_,_,7,2,_,_, _,_,9,_,4,_,_,3,5, _,_,_,3,_,_,7,_,6].

puzzle(7,P) :- P = [6,_,_,_,9,2,3,5,8,
		    _,9,8,_,6,7,_,_,_,
		    _,_,_,_,_,_,_,9,_,
		    _,3,_,6,8,_,_,2,1,
		    _,_,_,_,_,_,_,_,_,
		    1,5,_,_,2,4,_,7,_,		   
		    _,7,_,_,_,_,_,_,_,
		    _,_,_,4,7,_,2,8,_,
		    8,6,2,3,5,_,_,_,4].

puzzle(8,P) :- P = [_,_,9,_,_,_,5,7,_,
		    _,5,8,9,_,_,_,_,1,
		    2,3,_,7,5,_,9,_,_,
		    6,_,2,_,3,_,_,_,_,
		    _,1,7,_,9,_,2,8,_,
		    _,_,_,_,6,_,3,_,7,		   
		    _,_,3,_,4,1,_,9,5,
		    9,_,_,_,_,3,1,6,_,
		    _,4,6,_,_,_,8,_,_].

% an example with an error in the problem statement (5 appears 
% twice in the top left square) 
puzzle(e1,P) :- P = [5,_,2,_,_,3,_,_,_, 4,6,5,_,7,_,9,_,_, _,_,3,4,_,_,_,_,_,9,5,_,_,6,_,_,_,_, _,4,_,_,_,_,_,9,_, _,_,_,_,9,_,_,1,7,_,_,_,_,_,7,2,_,_, _,_,9,_,4,_,_,3,5, _,_,_,3,_,_,7,_,6].
 
% another example with an error in the problem statement (garbage 
% in the first row 
puzzle(e2,P) :- P = [x,_,2,_,_,3,_,_,_, 4,6,_,_,7,_,9,_,_, _,_,3,4,_,_,_,_,_,9,5,_,_,6,_,_,_,_, _,4,_,_,_,_,_,9,_, _,_,_,_,9,_,_,1,7,_,_,_,_,_,7,2,_,_, _,_,9,_,4,_,_,3,5, _,_,_,3,_,_,7,_,6].
