%%%%%%%%%%%%%%%%
%              %
%  Sudoku CSP  %
%              %
%%%%%%%%%%%%%%%%

:- set_prolog_flag(toplevel_print_options,
                   [quoted(true), portray(true), max_depth(0)]).

:- use_module(constraints).


generateVars(Board) :-
    retractall(vars(_)),
    enum(1, 9, Ls),
    generateVars(Board, Ls, 0, V),
    asserta(vars(V)).

enum(N, N, [N]) :- !.
enum(K, N, [K|L]) :-
    K1 is K+1,
    enum(K1, N, L).

generateVars([], _, _, []).
generateVars([[]|Board], Ls, I, Vars) :- !,
    generateVars(Board, Ls, I, Vars).
generateVars([[B|Bs]|Board], Ls, I, [x(I):VI | Vars]) :-
    ( var(B) -> VI = Ls;
      VI = [B] ),
    I1 is I + 1,
    generateVars([Bs|Board], Ls, I1, Vars).



consistent((x(_), VI), (x(_), VJ)) :-
    VI =\= VJ, !.
consistent((x(I), _), (x(J), _)) :-
    I mod 9 =\= J mod 9,
    I // 9 =\= J // 9,
    notSameSquare(I, J).

notSameSquare(I, J) :-
    SI is ((I mod 9) // 3) + 3 * ((I // 9) // 3),
    SJ is ((J mod 9) // 3) + 3 * ((J // 9) // 3),
    SI =\= SJ.


printBoard([]) :- nl.
printBoard([[]|Board]) :- !, nl,
    printBoard(Board).
printBoard([[B|Bs]|Board]) :-
    ( var(B) -> write('  .');
      write('  '), write(B) ),
    printBoard([Bs|Board]).


solToBoard(Sol, Board) :-
    solToBoard(Sol, 0, Board).
solToBoard([], _, []) :- !.
solToBoard(Sol, 9, [[]|Board]) :- !,
    solToBoard(Sol, 0, Board).
solToBoard([(_,B)|Sol], N, [[B|Bs]|Board]) :-
    N1 is N+1,
    solToBoard(Sol, N1, [Bs|Board]).


% Solve sudoku problem N
sudoku(N) :-
    problem(N, Board),
    nl, printBoard(Board),
    generateVars(Board),
    solve(Sol),
    solToBoard(Sol, BoardSol),
    nl, printBoard(BoardSol).

solve(Sol) :-
    nodeConsistFF(Sol).



%----------------------------------------------------------------------
% Samples Sudoku problems
%----------------------------------------------------------------------

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


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

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

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

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

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


% Problems 7-10 are harder, taken from
% http://www2.ic-net.or.jp/~takaken/auto/guest/bbs46.html
problem(7, [ [_, 9, 8, _, _, _, _, _, _],
             [_, _, _, _, 7, _, _, _, _],
             [_, _, _, _, 1, 5, _, _, _],
             [1, _, _, _, _, _, _, _, _],
             [_, _, _, 2, _, _, _, _, 9],
             [_, _, _, 9, _, 6, _, 8, 2],
             [_, _, _, _, _, _, _, 3, _],
             [5, _, 1, _, _, _, _, _, _],
             [_, _, _, 4, _, _, _, 2, _]  ]).

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

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

problem(10, [ [1, _, 4, _, _, _, _, _, _],
              [_, _, 2, 7, 4, _, _, _, _],
              [_, _, _, 5, _, _, _, _, _],
              [_, 3, _, _, _, _, _, _, _],
              [7, 5, _, _, _, _, _, _, _],
              [_, _, _, _, _, 9, 6, _, _],
              [_, 4, _, _, _, 6, _, _, _],
              [_, _, _, _, _, _, _, 7, 1],
              [_, _, _, _, _, 1, _, 3, _]  ]).