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

% Tasks:
% 1) Make the program independent of the board size.
%    Allow for all fields with row_length=col_lenght=n^2
% 2) Make the program more 'intelligent'. For example,
%    a) solve first all deterministic fields that is fields
%       for which only one value is possible.
%    b) do not generate candidates that are inconsistent
%       in the row/column/block.
% 3) Write a predicate that generates all solutions of a board.
% 4) Write a predicate that solves all loaded games, adds all solutions
%    to a knowledge base
%    (idea: 'game(N,M), for all M with play(M,MS), assert(solutions:solution(N,MS)').
%    Take the time and print basic information about each board to the screen:
%    - number of solutions
%    - time it took to find all
%    - average time per solution.

:- consult(sudoku_boards).

solve_game(N):-
        statistics(walltime,_),
        game(N,B),
        print_board(B),
        play(B,NewB),
        print_board(NewB),
        statistics(walltime,[_,T]),
        write(time:T),nl.       % T is the time difference in msec


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).

block_values((R,C),M,Values):-
        interval(R,RInt),
        interval(C,CInt),
        findall(V,(member(R1,RInt),member(C1,CInt),member((R1,C1,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]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% print board

print_board(B):- nl, print_board(B,1,1).

print_board(_,10,_):- nl,nl,!. % board is done
print_board(B,R,10):-    % row is done
        nl,
        R1 is R+1,
        print_board(B,R1,1). % repeat with next row

print_board(B,R,C):-
        member((R,C,V),B),!, % field is filled
        write(V),tab(1),     % print value
        C1 is C+1,
        print_board(B,R,C1). % go to next field

print_board(B,R,C):-
        write("_"),tab(1),   % print empty field
        C1 is C+1,
        print_board(B,R,C1). % go to next field