% Sudoku solver v CLP, pro libovolně velké sudoku
% (c) 2014 Vladimír Štill
% BSD2 licenced

:- use_module(library(clpfd)).

% vyres sudoku o delce hrany N^2 (tj. N je pocet poctvercu v sudoku)
% sudoku(3, X) generuje reseni standartiniho 9*9 sudoku
sudoku(N, X) :-
    N2 is N * N,
    length(X, N2),
    sub_length(X, N2),
    flatten(X, FX), % ins & label potrebuje seznam promennych, ne seznam seznamu
    FX ins 1..N2,
    sub_different(X),
    cols_different(N2, X),
    squares_diff(N, X),
    label(FX).

sub_length([], _) :- !.
sub_length([X|XS], N) :- length(X, N), sub_length(XS, N).

sub_different([]) :- !.
sub_different([X|XS]) :- all_different(X), sub_different(XS).

cols_different(0, _) :- !.
cols_different(N, XS) :-
    pick_nth(N, XS, ES),
    all_different(ES),
    N1 is N - 1,
    cols_different(N1, XS).

pick_nth(_, [], []) :- !.
pick_nth(N, [X|XS], [E|ES]) :- nth1(N, X, E), pick_nth(N, XS, ES).

squares_diff(N, Rows) :- squares_diff2(N, N, N, Rows).

squares_diff2(0, _SY, _, _) :- !.
squares_diff2(SX, 0, N, Rows) :-
    !,
    SX1 is SX - 1,
    squares_diff2(SX1, N, N, Rows).
squares_diff2(SX, SY, N, Rows) :-
    square(SX, SY, N, N, N, Rows, Square),
    all_different(Square),
    SY1 is SY - 1,
    squares_diff2(SX, SY1, N, Rows).

square(_, _, 0, _Yi, _, _, []) :- !.
square(SX, SY, Xi, 0, N, Rows, XS) :-
    !,
    Xi1 is Xi - 1,
    square(SX, SY, Xi1, N, N, Rows, XS).
square(SX, SY, Xi, Yi, N, Rows, [X|XS]) :-
    Xix is N * (SX - 1) + Xi,
    Yix is N * (SY - 1) + Yi,
    nth1(Xix, Rows, Row),
    nth1(Yix, Row, X),
    Yi1 is Yi - 1,
    square(SX, SY, Xi, Yi1, N, Rows, XS).