057: Killer Sudoku

% 
% 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
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

% 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
];