%
% "Sandwich Sudoku" featured by Alex Bellos in The Guardian, 6 May 2019
% https://www.theguardian.com/science/2019/may/06/can-you-solve-it-sandwich-sudoku-a-new-puzzle-goes-viral
%
% Sample ECLiPSe solution by Joachim Schimpf, 2019
% under Creative Commons Attribution 4.0 International License.
%
% All the standard Sudoku rules apply.
% In addition, there is a sum given for each row and each column:
% in each row/column the numbers that are placed *between* the
% numbers 1 and 9 must add up to the corresponding row/column sum.
% 
% ?- solve(1).
%   _  _  _  _  _  _  _  _  _
%   _  _  _  _  _  _  _  _  _
%   _  _  9  _  _  _  _  _  _
%   _  _  _  6  _  _  _  _  _
%   _  _  _  _  1  _  _  _  _
%   _  _  _  _  _  2  _  _  _
%   _  _  _  _  _  _  7  _  _
%   _  _  _  _  _  _  _  _  _
%   _  _  _  _  _  _  _  _  _
% 
%   6  1  2  9  3  8  4  7  5
%   7  8  3  4  5  1  2  6  9
%   4  5  9  2  6  7  8  3  1
%   1  3  8  6  7  5  9  4  2
%   2  7  4  3  1  9  5  8  6
%   5  9  6  8  4  2  3  1  7
%   3  4  5  1  2  6  7  9  8
%   9  2  1  7  8  3  6  5  4
%   8  6  7  5  9  4  1  2  3
% 
% Yes (0.47 cpu)
% 

:- lib(ic).             % for constraints
:- lib(propia).         % for Generalized Propagation


solve(ProblemName) :-
        problem(ProblemName, Board, RSums, CSums),
        print_board(Board),
        sandwich_sudoku(Board, RSums, CSums),
        labeling(Board),
        print_board(Board).


% The problem model
sandwich_sudoku(Board, RSums, CSums) :-
        dim(Board, [N,N]),
        Board :: 1..N,
        NN is integer(sqrt(N)),
        ( multifor([I,J],1,N,NN), param(Board,NN) do
            alldifferent(concat(Board[I..I+NN-1, J..J+NN-1]))
        ),
        ( for(I,1,N), param(Board,RSums,CSums) do
            line(Board[I,*], RSums[I]),     % replaces alldifferent(Board[I,*])
            line(Board[*,I], CSums[I])      % replaces alldifferent(Board[*,I])
        ).


% A problem-specific constraint for the row/column subproblem.
% It combines the all-different and the sum-between-1-and-N condition.
% We use Generalized Propagation to turn a nondeterministic specification
% into a propagation constraint (see lib(propia)'s infers-annotation).
line(Vector, SumExpr) :-
        Sum is SumExpr,
        eval_to_list(Vector, Xs),
        line_automaton_nondet(Xs, Sum) infers ac.


% A nondeterministic predicate that finds all solutions for the
% individual row/column represented by Xs.  It is written in the
% style of an automaton that accepts/generates all valid solutions.
line_automaton_nondet(Xs, Sum) :-
        ( foreach(_,Xs), count(I,1,N), foreach(I,Ints) do true ),
        (
            foreach(X,Xs),
            fromto(1,StateIn,StateOut,3),
            fromto(Ints,Ints1,Ints2,[]),
            fromto(Sum,Sum1,Sum2,0),
            param(N)
        do
            select(X, Ints1, Ints2),
            ( StateIn=1, Sum2=Sum1,
                ( (X=1;X=N) -> StateOut=2
                ; StateOut=1
                )
            ; StateIn=2,
                ( (X=1;X=N) -> Sum1=0, Sum2=Sum1, StateOut=3
                ; Sum1>=X, Sum2 is Sum1-X, StateOut=2
                )
            ; StateIn=3, Sum2=Sum1, StateOut=3
            )
        ).


print_board(Board) :-
        dim(Board, [N,N]),
        ( for(I,1,N), param(Board,N) do
            ( for(J,1,N), param(Board,I) do
                X is Board[I,J],
                ( var(X) -> write("  _") ; printf(" %2d", [X]) )
            ), nl
        ), nl.


% Example data
% These both solve purely by propagation, no backtracking
problem(1, [](
    [](_, _, _, _, _, _, _, _, _),      % initial board
    [](_, _, _, _, _, _, _, _, _),
    [](_, _, 9, _, _, _, _, _, _),
    [](_, _, _, 6, _, _, _, _, _),
    [](_, _, _, _, 1, _, _, _, _),
    [](_, _, _, _, _, 2, _, _, _),
    [](_, _, _, _, _, _, 7, _, _),
    [](_, _, _, _, _, _, _, _, _),
    [](_, _, _, _, _, _, _, _, _)),

    []( 2, 8,26,29, 0,23,15, 2, 4),     % row sums
    [](10,23,23,23,14,12,21, 0, 0)      % column sums
).
problem(2, [](
    [](_, _, _, _, _, _, _, _, 2),
    [](_, 4, _, _, _, _, _, _, _),
    [](_, _, _, _, _, _, _, 6, _),
    [](7, _, 3, _, _, 6, _, _, _),
    [](_, _, _, _, _, _, _, _, _),
    [](_, _, _, 9, _, _, 2, _, 4),
    [](_, 5, _, _, _, _, _, _, _),
    [](_, _, _, _, _, _, _, 8, _),
    [](9, _, _, _, _, _, _, _, _)),

    []( 6, 0,12,11,24, 6, 7,21, 8),
    [](35, 0,35,12,20,19, 0, 0, 0)
).