sudoku(Matrix) :-
    all_different_rows(Matrix),
    transpose(Matrix, MatrixT),
    all_different_rows(MatrixT),
    submatrix(Matrix, 0, 0, 3, 3, M00), all_different_elements(M00),
    submatrix(Matrix, 3, 0, 3, 3, M30), all_different_elements(M30),
    submatrix(Matrix, 6, 0, 3, 3, M60), all_different_elements(M60),
    submatrix(Matrix, 0, 3, 3, 3, M03), all_different_elements(M03),
    submatrix(Matrix, 3, 3, 3, 3, M33), all_different_elements(M33),
    submatrix(Matrix, 6, 3, 3, 3, M63), all_different_elements(M63),
    submatrix(Matrix, 0, 6, 3, 3, M06), all_different_elements(M06),
    submatrix(Matrix, 3, 6, 3, 3, M36), all_different_elements(M36),
    submatrix(Matrix, 6, 6, 3, 3, M66), all_different_elements(M66), !,
    all_sudoku_numbers(Matrix, 2).

all_different_elements(M) :-
    flatten(M, M1),
    all_different(M1).

flatten([], []).
flatten([[]|Xs], Ys) :-
    flatten(Xs, Ys).
flatten([[X|Xs]|X1s], [X|Ys]) :-
    flatten([Xs|X1s], Ys).

submatrix(_, _, _, 0, _, []).
submatrix(_, _, _, _, 0, []).
submatrix([M|Ms], 0, C1, Rows, Cols, [M1|SM]) :- Cols > 0, Rows > 0,
    sublist(M, C1, Cols, M1),
    Rows1 is Rows - 1,
    submatrix(Ms, 0, C1, Rows1, Cols, SM).
submatrix(M, R1, C1, Rows, Cols, SM) :- R1 > 0, Rows > 0, Cols > 0,
    sublist(M, R1, Rows, M1),
    submatrix(M1, 0, C1, Rows, Cols, SM).

sublist(_, _, 0, []).
sublist([X|Xs], 0, N, [X|Ys]) :- N > 0,
    N1 is N - 1,
    sublist(Xs, 0, N1, Ys).
sublist([_|L], N, M, SL) :- N > 0, M > 0,
    N1 is N - 1,
    sublist(L, N1, M, SL).

all_sudoku_numbers(X, 0) :- member(X, [1, 2, 3, 4, 5, 6, 7, 8, 9]).
all_sudoku_numbers([], N) :- N > 0.
all_sudoku_numbers([X|Xs], N) :- N > 0,
    N1 is N - 1,
    all_sudoku_numbers(X, N1),
    all_sudoku_numbers(Xs, N).

all_different_rows(List) :-
    maplist(all_different, List).

all_different([]).
all_different([_]).
all_different([X|Xs]) :-
    all_different(X, Xs),
    all_different(Xs).
all_different(_, []).
all_different(X, [X1|Xs]) :-
    dif(X, X1),
    all_different(X, Xs).

transpose([[]|_], []).
transpose(Matrix, Transposed) :-
    Matrix = [[_|_]|_],
    cut_heads(Matrix, T, M1),
    transpose(M1, T1),
    Transposed = [T|T1].

cut_heads([], [], []).
cut_heads([[H|T]|Rest], [H|Heads], [T|Tails]) :-
    cut_heads(Rest, Heads, Tails).

write_sudoku(M) :-
	maplist(writeln, M).
writeln(X) :- write(X), nl.