%	GNU Prolog code to solve sudoku puzzels
%	written by Niels & Andreas


:- dynamic(counter/1).
:- initialization(go).	%gnu prolog

go :-
	argument_value(1, File), %gnu prolog
	%File = 'sudoku.txt',           % the file to read from, file should have 9 lines, each 9 charaters
        start(File).                    % 0 or spaces should be used for unknown values


start(File) :-
	%statistics(cputime,Cpu),	% gnu prolog
	cpu_time(Cpu),			% swi-prolog
        write(trying_file(File)),nl,
        see(File),                      % open file

        (       readall(List),nl,       % read the file into the List
                write('list after reading: '),nl,
                pretty_sudo_print(List),nl,     % print to see if reading went ok
		 X = 1,!,
		(	inc(1,Inc,1000),
              		retractall(counter(_)),
			assertz(counter(X)),
			%write(test(Inc,List)),nl,
			solve(List,X)
			;
                	true
		)
	),
        seen,
        write('cpu time taken: '),
	cpu_time(CpuNew),		% gnu prolog
	%statistics(cputime,CpuNew),	%for swi-prolog
        CpuUsed is CpuNew - Cpu,
        write(CpuUsed),nl,                              % close the file
	halt.	% gnu prolog

% predicate to count from Start to Max	(yeah, it's from KRPL.pl :D)
%inc(Start, Next, Max)
inc(X,X,_).

inc(X,Xnew,Max) :-
	X < Max,
	Xtemp is X + 1,
	inc(Xtemp,Xnew,Max).
	
solve(List,C) :-                        %solve List max C times
        correct_whole(List),fill_numbers_in(List),
        retract(counter(X)),
        Xnew is X -1,
        Numb is C - X +1,
        write('number '),write(Numb),write(' found: '),
	%write(List),
	pretty_sudo_print(List),
	nl,
        assertz(counter(Xnew)),
        (       Xnew < 1,!,
                write('solving completed: '),write(C),write(' solutions found.... there might be more out there ... '),
		fail
		;
		true
        ),
        fail.


solve(List,_) :-
	write(not_able_to_solve(List)), nl.
	
correct_whole(List) :-		% check the file which was read for mistakes already existing
	control_hori(List),
	control_verti(List),
	control_regio(List).
	
% check if all rows have no double items
control_hori([]).	
control_hori([H|T]) :-
	all_different(H),
	control_hori(T).
	
% check if all columns have no double items	
control_verti([[],[],[],[],[],[],[],[],[]]).	
control_verti([[A|TA],[B|TB],[C|TC],[D|TD],[E|TE],[F|TF],[G|TG],[H|TH],[I|TI]]) :-
	all_different([A,B,C,D,E,F,G,H,I]),
	control_verti([TA,TB,TC,TD,TE,TF,TG,TH,TI]).

% check if every 3x3 area has no double items
control_regio([]).
control_regio([A,B,C|T]) :-
	control_regio_row([A,B,C]),
	control_regio(T).
	
control_regio_row([[],[],[]]).
control_regio_row([[A,B,C|TA],[D,E,F|TB],[G,H,I|TC]]) :-
	all_different([A,B,C,D,E,F,G,H,I]),
	control_regio_row([TA,TB,TC]).

	

correct_part(List,X,Y) :-	% control a part of the sudoku with locations X and Y
	control_part_verti(List,Y),
	control_part_regio(List,X,Y),!.

	
control_part_verti([[A|_],[B|_],[C|_],[D|_],[E|_],[F|_],[G|_],[H|_],[I|_]],1) :-	%right column found
	!,
	all_different([A,B,C,D,E,F,G,H,I]).

control_part_verti([[_|TA],[_|TB],[_|TC],[_|TD],[_|TE],[_|TF],[_|TG],[_|TH],[_|TI]],Y) :-	
	Ynew is Y -1,
	control_part_verti([TA,TB,TC,TD,TE,TF,TG,TH,TI],Ynew).		%check next column
	
	
control_part_regio(List,X,Y) :-	
	Xnew is (X -1)// 3,	% make the 9x9 to a 3x3
	Ynew is (Y -1)// 3,
	control_part_regio_area(List,Xnew,Ynew).

control_part_regio_area([Row1,Row2,Row3|_],0,Y) :-
	!,control_part_regio_row([Row1,Row2,Row3],Y).	% rows where the 3x3 area is are found

control_part_regio_area([_,_,_|List],X,Y) :-	
	Xnew is X -1,
	control_part_regio_area(List,Xnew,Y).	% try next rows
	

control_part_regio_row([[A,B,C|_],[D,E,F|_],[G,H,I|_]],0) :-	% 3x3 area found
	!,all_different([A,B,C,D,E,F,G,H,I]).		
	
control_part_regio_row([[_,_,_|TA],[_,_,_|TB],[_,_,_|TC]],Y) :-
	Ynew is Y -1,
	control_part_regio_row([TA,TB,TC],Ynew).	%check next columns	
		
	

all_different([]) :- !.		% an empty list has no double items :)


all_different([H|T]) :-
	(	var(H)		% if H is a Var, don't let it match with other items in the list 
		;
		\+ membervar(H,T)	% else, make sure H is not in T
	),!,
	all_different(T).	%check rest of list
	
	
membervar(H,[Var|T]) :-
	var(Var),!,	% don't match Var with H
	membervar(H,T).	% check if H is in T
	
membervar(H,[H|_]) :- !.

membervar(H,[_|T]) :-
	!,membervar(H,T).
	

fill_numbers_in(List) :-
	findanVar(H,List,0,X,Y,Sublist),	%find an var
	difference([1,2,3,4,5,6,7,8,9],Sublist,Choices),
	!,
	member(H,Choices),		% find available number for that row
	correct_part(List,X,Y),
	fill_numbers_in(List).		%check if it is correct

fill_numbers_in(_).	%there are no vars to fill in anymore.
	

% give difference bewteen List and another list, all items which are in 1st but not in 2nd
difference(List,[],List) :- !.

difference(List,[H|Sublist],Difference) :-
	var(H),!,difference(List,Sublist,Difference),!.
	
difference(List,[H|Sublist],Difference) :-
	remove(H,List,Newlist),
	difference(Newlist,Sublist,Difference),!.

% remove item from the list
remove(H,[H|T],T) :- !.	%there is always max one time H in the list
remove(_,[],[]).
remove(H,[V|T],[V|NewT]) :-
	remove(H,T,NewT).
	
findanVar(V,[Row|_],X,Xend,Yend,Row) :-	
	Xnew is X +1,
	findaVar(V,Row,Xnew,1,Xend,Yend).	% find a Var inside this row

findanVar(V,[_|Rest],X,Xend,Yend,Sublist) :-	
	Xnew is X +1,
	findanVar(V,Rest,Xnew,Xend,Yend,Sublist).	%loop thru all horizontal rows
	

findaVar(V,[V|_],X,Y,X,Y) :-	%lovely.. :]
	var(V),!.
	
findaVar(V,[_|T],X,Y,Xend,Yend) :-
	Ynew is Y + 1,
	findaVar(V,T,X,Ynew,Xend,Yend),!.
	
	
% to read from the file
readall(List) :-
	List = [_,_,_,_,_,_,_,_,_],
	readrows(List),!.

readall(_) :-
	write('reading failed :/'),!,fail.	
	
readrows([]).
readrows([H|T]) :-
	readrow(H),
	readrows(T).

%read one row
readrow(Var) :-
	Var = [_,_,_,_,_,_,_,_,_],
	readchars(Var).

readchars([]) :- 
	get0(Y),
	(Y == 10 ; Y == 13; Y == -1),!.

	
readchars([H|T]) :-
	get0(Y),
	(((Y == 10 ; Y == 13),!,readchars([H|T]));
	(	(Y == 32;Y == 48),!;
		(Y > 48,Y < 58,!,H is Y - 48)
	),
	readchars(T)).

	
% pretty printing \0/		
pretty_sudo_print([]).
pretty_sudo_print([A,B,C|T]) :-
	nl,printsudorow(A),
	printsudorow(B),	
	printsudorow(C),	
	pretty_sudo_print(T).

printsudorow([]) :- nl.
printsudorow([A,B,C|T]) :-
	writerepv(A),tab(1),
	writerepv(B),tab(1),
	writerepv(C),tab(3),
	printsudorow(T).	
	
writerepv(X) :-
	var(X),!,write(' ').
	
writerepv(X) :-
	write(X).
	
