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