% Create a generic sudoku reader

valid([]).
valid([Head|Tail]) :-
    fd_all_different(Head),
    valid(Tail).

sudoku(Board, X, Y, Solution) :-
    Solution = Board,
    Max is X * Y,
    fd_domain(Solution, 1, Max),
    board(X, Y, Board),
    rows(Board, Max, Rows),
    cols(Board, Max, Cols),
    boxes(Board, X, Y, Boxes),
    valid(Rows),
    valid(Cols),
    valid(Boxes).

board(X, Y, Board) :-
    % Y * X boxes of size X * Y
    Size is (Y * X) * (X * Y),
    board(Size, Board).
board(1, [_]).
board(Size, [_|Board]) :- SmallerSize is Size - 1, board(SmallerSize, Board).

sublist(Start, Length, Input, Output) :- End is Start + Length - 1, sublist(Start, End, 1, Input, Output).
sublist(Start, End, Pos, [Head|TailIn], [Head|TailOut]) :- Pos >= Start, Pos =< End, NextPos is Pos + 1, sublist(Start, End, NextPos, TailIn, TailOut).
sublist(Start, End, Pos, [_|TailIn], Output) :- Pos < Start, NextPos is Pos + 1, sublist(Start, End, NextPos, TailIn, Output).
sublist(_, End, Pos, _, []) :- Pos > End.

rows(Board, RowLength, Rows) :- rows(Board, RowLength, 1, Rows).
rows(Board, RowLength, RowNum, [NewRow|Rows]) :- RowNum =< RowLength, NextRowNum is RowNum + 1,
    Start is ((RowNum - 1) * RowLength) + 1, sublist(Start, RowLength, Board, NewRow),
    rows(Board, RowLength, NextRowNum, Rows).
rows(_, RowLength, RowNum, []) :- RowNum > RowLength.

nth_from_list(Start, N, Input, Output) :- nth_from_list(N, Start, 1, Input, Output).
nth_from_list(N, Next, Pos, [Head|TailIn], [Head|TailOut]) :- Pos == Next, NewNext is Next + N, NewPos is Pos + 1,
    nth_from_list(N, NewNext, NewPos, TailIn, TailOut).
nth_from_list(N, Next, Pos, [_|TailIn], Output) :- Pos < Next, NewPos is Pos + 1, nth_from_list(N, Next, NewPos, TailIn, Output).
nth_from_list(_, _, _, [], []).

cols(Board, ColLength, Cols) :- cols(Board, ColLength, 1, Cols).
cols(Board, ColLength, ColNum, [NewCol|Cols]) :- ColNum =< ColLength, NextColNum is ColNum + 1,
    nth_from_list(ColNum, ColLength, Board, NewCol),
    cols(Board, ColLength, NextColNum, Cols).
cols(_, ColLength, ColNum, []) :- ColNum > ColLength.

in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY) :-
    PosX >= BoxX * MaxBoxWidth, PosX < (BoxX + 1) * MaxBoxWidth,
    PosY >= BoxY * MaxBoxHeight, PosY < (BoxY + 1) * MaxBoxHeight.

box(_, _, _, MaxBoxWidth, MaxBoxHeight, _, PosY, []) :- PosY >= MaxBoxWidth * MaxBoxHeight.
box([Head|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, [Head|Box]) :-
    in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY),
    PosX < (MaxBoxWidth * MaxBoxHeight) - 1, NextX is PosX + 1,
    box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, PosY, Box).
box([Head|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, [Head|Box]) :-
    in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY), 
    PosX >= (MaxBoxWidth * MaxBoxHeight) - 1, NextX is 0, NextY is PosY + 1,
    box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, NextY, Box).
box([_|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, Box) :- 
    \+ in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY), PosX < (MaxBoxWidth * MaxBoxHeight) - 1, NextX is PosX + 1, box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, PosY, Box).
box([_|Tail], BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY, Box) :- 
    \+ in_box(BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, PosX, PosY), PosX >= (MaxBoxWidth * MaxBoxHeight) - 1, NextX is 0, NextY is PosY + 1, box(Tail, BoxX, BoxY, MaxBoxWidth, MaxBoxHeight, NextX, NextY, Box).

boxes(Board, BoxWidth, BoxHeight, Boxes) :- boxes(Board, BoxWidth, BoxHeight, 0, 0, Boxes).
boxes(_, MaxBoxY, MaxBoxX, BoxX, BoxY, []) :- BoxY >= MaxBoxY.
boxes(Board, MaxBoxY, MaxBoxX, BoxX, BoxY, [Box|Boxes]) :- BoxX < (MaxBoxX - 1), BoxY < MaxBoxY, box(Board, BoxX, BoxY, MaxBoxY, MaxBoxX, 0, 0, Box), NextX is BoxX + 1,  boxes(Board, MaxBoxY, MaxBoxX, NextX, BoxY, Boxes).
boxes(Board, MaxBoxY, MaxBoxX, BoxX, BoxY, [Box|Boxes]) :- BoxX >= (MaxBoxX - 1), BoxY < MaxBoxY, box(Board, BoxX, BoxY, MaxBoxY, MaxBoxX, 0, 0, Box), NextY is BoxY + 1, boxes(Board, MaxBoxY, MaxBoxX, 0, NextY, Boxes).