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