% Autor: Wiebke Petersen
% Sudoku Solver: simple generate and test approach
% Heavily based on ideas of Christof Rumpf
% Datum: 27.04.2017

% Tasks:
% 1) This solver is very slow, but it can be heavily improved by setting one cut, but where?
% 2) Write a predicate print_board/1 that takes a board and prints it
% 3) Write a predicate solve_game/1 that takes a game by its number,
%    prints the board of the game, solves it and prints the solution.


:- consult(sudoku_boards).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Main predicates

play(M,M):- length(M,81), !.    % matrix completed - problem solved
play(M,Solution):-
        choose_some_value(RCV,M), % make a temporary decision
        consistent(RCV,M,NewM), % if consistent, NewM appears
        play(NewM,Solution).    % matrix enhanced with new element

choose_some_value((R,C,V),M):-
        numbers(N),
        member(R,N),
        member(C,N),
        \+ member((R,C,_),M),    % make sure that the field is empty
        member(V,N).

consistent((R,C,V),M,[(R,C,V)|M]):-
        row_consistent((R,V),M),
        col_consistent((C,V),M),
        block_consistent((R,C,V),M).

row_consistent((R,V),M):-
        \+ member((R,_,V),M).

col_consistent((C,V),M):-
        \+ member((_,C,V),M).

block_consistent((R,C,V),M):-
        block_values((R,C),M,Values),
        \+ member(V,Values).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Auxiliary predicates

block_values((R,C),M,Values):-
        interval(R,RInt),
        interval(C,CInt),
        findall(V,(member(R,RInt),member(C,CInt),member((R,C,V),M)),Values).

interval(I,Int):-
        numbers(N),
        findall(Z,(member(Z,N),(I-1)//3 =:= (Z-1)//3),Int).

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