%
% Killer Sudoku in MiniZinc.
%
%   Killer sudoku in Comet.

%   http://en.wikipedia.org/wiki/Killer_Sudoku
%   """
%   Killer sudoku (also killer su doku, sumdoku, sum doku, addoku, or
%   samunamupure) is a puzzle that combines elements of sudoku and kakuro.
%   Despite the name, the simpler killer sudokus can be easier to solve
%   than regular sudokus, depending on the solver's skill at mental arithmetic;
%   the hardest ones, however, can take hours to crack.

%   ...

%   The objective is to fill the grid with numbers from 1 to 9 in a way that
%   the following conditions are met:

%     * Each row, column, and nonet contains each number exactly once.
%     * The sum of all numbers in a cage must match the small number printed
%       in its corner.
%     * No number appears more than once in a cage. (This is the standard rule
%       for killer sudokus, and implies that no cage can include more
%       than 9 cells.)

%   In 'Killer X', an additional rule is that each of the long diagonals
%   contains each number once.
%   """

%   Here we solve the problem from the Wikipedia page, also shown here
%   http://en.wikipedia.org/wiki/File:Killersudoku_color.svg

%   Note, this model is based on the generalized KenKen model:
%   http://www.hakank.org/comet/kenken2.co
%   Killer Sudoku is simpler in that the only mathematical operation is
%   summation.

%   The output is:
%     2 1 5 6 4 7 3 9 8
%     3 6 8 9 5 2 1 7 4
%     7 9 4 3 8 1 6 5 2
%     5 8 6 2 7 4 9 3 1
%     1 4 2 5 9 3 8 6 7
%     9 7 3 8 1 6 4 2 5
%     8 2 1 7 3 9 5 4 6
%     6 5 9 4 2 8 7 1 3
%     4 3 7 1 6 5 2 8 9
%
% Also, see the following model:
%  MiniZinc: http://www.hakank.org/minizinc/killer_sudoku.mzn

% Note: In this current model there is an alternative
% way of representing the hints, namely as segments in the
% segment grid.

%
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@gmail.com
%

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

include "globals.mzn";
int: n = 9;
array[1..n, 1..n] of var 1..9: x;

% For a better view of the problem, see
%  http://en.wikipedia.org/wiki/File:Killersudoku_color.svg
%

%
% segments
%
int: num_segments = 29; % number of segments

array[1..n, 1..n] of int: segments =
array2d(1..n, 1..n,
[
1, 1, 2, 2, 2, 3, 4, 5, 6, % 1
7, 7, 8, 8, 3, 3, 4, 5, 6, % 2
7, 7, 9, 9, 3,10,11,11, 6, % 3
13,14,14, 9,15,10,11,12, 6, % 4
13,16,16,17,15,10,12,12,18, % 5
19,16,20,17,15,21,22,22,18, % 6
19,20,20,17,23,21,21,24,24, % 7
19,25,26,23,23,27,27,24,24, % 8
19,25,26,23,28,28,28,29,29, % 9
]);

array[1..num_segments] of int: segment_sums =
[
3, % 1
15, % 2
22, % 3
4, % 4
16, % 5
15, % 6
25, % 7
17, % 8
9, % 9
8, % 10
20, % 11
17, % 12
6, % 13
14, % 14
17, % 15
13, % 16
20, % 17
12, % 18
27, % 19
6, % 20
20, % 21
6, % 22
10, % 23
14, % 24
8, % 25
16, % 26
15, % 27
13, % 28
17  % 29
];

% solve satisfy;
solve :: int_search([x[i,j] | i,j in 1..n], first_fail, indomain_min, complete) satisfy;

% Standard Sudoku constraints
constraint
% rows and columns
forall(i in 1..n) (
all_different([x[i,j] | j in 1..n]) /\
all_different([x[j,i] | j in 1..n])
)
/\ % blocks
forall(i in 0..2,j in 0..2) (
all_different([x[r,c] | r in i*3+1..i*3+3, c in j*3+1..j*3+3] )
)
;

% Handle the segments
constraint
forall(p in 1..num_segments) (
segment_sums[p] = sum([x[i,j] | i,j in 1..n where segments[i,j] = p])
)
;

output [
if j = 1 then "\n" else " " endif ++
show(x[i,j])
| i,j in 1..n
];