%%% Updated November 6, 2012
%%% Tested in BProlog


dati(0, [ 
5,3,8, _,_,_, _,_,_,
1,_,_, _,_,_, _,_,8,
6,7,4, 8,2,_, _,1,5,
%
_,_,_, _,7,_, _,_,9,
4,_,_, _,9,_, _,_,2,
2,_,_, _,6,_, _,_,_,
%
8,1,_, _,5,3, 2,9,7,
_,_,_, _,_,_, _,_,1,
_,_,_, _,_,_, _,_,3
]).


dati(1, [ 
_,3,1, 9,_,4, 5,2,_,
_,_,_, _,3,_, _,_,_,
_,_,_, _,5,_, _,_,_,
_,_,9, 2,7,3, 8,_,_,
_,8,_, _,_,_, _,9,_,
_,5,_, _,_,_, _,1,_,
_,7,_, _,_,_, _,6,_,
_,2,_, _,6,_, _,8,_,
6,_,_, _,4,_, _,_,9
]).

dati(2, [ 
_,6,_, _,_,_, _,9,_,
9,4,_, _,6,_, _,7,8,
_,_,_, _,9,_, _,_,_,
%
_,9,_, _,_,_, _,8,_,
6,7,_, _,8,_, _,1,4,
_,_,_, _,5,_, _,_,_,
%
_,5,_, _,_,_, _,4,_,
8,1,_, _,7,_, _,2,5,
_,_,_, 9,1,5, _,_,_
]).

dati(3,[
_,_,_, _,_,_, _,_,6,
_,_,9, 7,_,5, _,8,_,
2,_,_, _,_,_, 4,_,_,
_,7,_, _,9,_, _,_,_,
_,3,_, _,_,_, _,5,_,
_,_,_, _,8,_, _,1,_,
_,_,8, _,_,_, _,_,2,
_,5,_, 3,_,1, 6,_,_,
6,_,_, _,_,_, _,_,_
]).


sudoku(I,Cells) :-
   dati(I,Cells), %%% see example above
   N = 9, M = 81,
   length(Cells,M),
   domain(Cells,1,N),
   row_constraints(Cells,N),
   column_constraints(Cells,N),
   square_constraints(Cells,N),
   statistics(runtime,_),
   labeling([ff],Cells),
   statistics(runtime,[_,T]),
   write('Soluzione trovata in: '),
   write(T),write('ms'),nl,
   write(N,N,Cells).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
row_constraints([],_).
row_constraints(Cells,N) :-
   extract(N,Cells,Row,Rest),
   all_different(Row),
   row_constraints(Rest,N).
   
column_constraints(Cells,N):- 
   column_constraints(Cells,1,N).
column_constraints(_,M,N) :-
   M > N, !.
column_constraints(Cells,M,N) :-
   column(Cells,M,N,Col),
   all_different(Col),
   M1 is M + 1,
   column_constraints(Cells,M1,N).

square_constraints(Cells,N):-
   M is integer(sqrt(N)),
   square_constraints(Cells,0,N,M).
   
square_constraints(_,N,N,_):-!.
square_constraints(Cells,I,N,M):-
   square(Cells,I,M,N),
   I1 is I + 1,
   square_constraints(Cells,I1,N,M).
  
square(Cells,I,M,N) :-
   Start is (I//M)*(N*M) + (I mod M)*M, 
   extract(Start,Cells,_,MyCells),
   pick_square(MyCells,0,M,N,Square),
   all_different(Square).

pick_square( _,M,M,_,[]):-!.
pick_square(Cells,I,M,N,Square):-
   extract(M,Cells,Sq,_),
   (extract(N,Cells,_,Rest), !;
    true),
   I1 is I + 1,
   pick_square(Rest,I1,M,N,Uare),
   append(Sq,Uare,Square).

%%% AUX
         
column([],_,_,[]).
column(Code,M,N,[A|R]) :-
   element(M,Code,A),
   extract(N,Code,_,RestCode),
   column(RestCode,M,N,R).

extract(N,Code,First,Last) :-
  length(First,N),
  append(First,Last,Code).
   
%%%%%%% PRINT RESULT:
write(_,_,[]) :- !.
write(0,N,Code) :-
   !,nl, write(N,N,Code).
write(M,N,[A|Code]) :-
   M1 is M -1,
   write(A),write(' '),
   write(M1,N,Code).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
