Download
%
% Crossfigure problem in MiniZinc.
%
% CSPLib problem 21
% http://www.csplib.org/Problems/prob021
% """
% Crossfigures are the numerical equivalent of crosswords. You have a grid and some
% clues with numerical answers to place on this grid. Clues come in several different
% forms (for example: Across 1. 25 across times two, 2. five dozen, 5. a square number,
% 10. prime, 14. 29 across times 21 down ...).
% """
%
% Also, see
% http://en.wikipedia.org/wiki/Cross-figure
%
% William Y. Sit: "On Crossnumber Puzzles and The Lucas-Bonaccio Farm 1998
% http://scisun.sci.ccny.cuny.edu/~wyscc/CrossNumber.pdf
%
% Bill Williams: Crossnumber Puzzle, The Little Pigley Farm
% http://jig.joelpomerantz.com/fun/dogsmead.html
%
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%
% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
%
% This model was inspired by the ECLiPSe model written by Warwick Harvey:
% http://www.csplib.org/Problems/prob021/models
%
%
% Data from
% http://thinks.com/crosswords/xfig.htm.
%
% This problem is 001 from http://thinks.com/crosswords/xfig.htm
% ("X" is the blackbox and is fixed to the value of 0)
%
% 1 2 3 4 5 6 7 8 9
% ---------------------------
% 1 2 _ 3 X 4 _ 5 6 % 1
% 7 _ X 8 _ _ X 9 _ % 2
% _ X 10 _ X 11 12 X _ % 3
% 13 14 _ _ X 15 _ 16 _ % 4
% X _ X X X X X _ X % 5
% 17 _ 18 19 X 20 21 _ 22 % 6
% _ X 23 _ X 24 _ X _ % 7
% 25 26 X 27 _ _ X 28 _ % 8
% 29 _ _ _ X 30 _ _ _ % 9
%
% The answer is
% 1608 9183
% 60 201 42
% 3 72 14 1
% 5360 2866
% 3 4
% 4556 1156
% 9 67 16 8
% 68 804 48
% 1008 7332
% Solutions:
% MiniZinc and Gecode/fz solves the problem in about 8 seconds.
% ECLiPSe/ic: 35 seconds
% MiniZinc/fdmip in 14 seconds.
%
int: n = 9;
array[1..n, 1..n] of var 0..9: M;
set of int: D = 0..9999; % the max length of the numbers in this problem is 4
var D: A1;
var D: A4;
var D: A7;
var D: A8;
var D: A9;
var D: A10;
var D: A11;
var D: A13;
var D: A15;
var D: A17;
var D: A20;
var D: A23;
var D: A24;
var D: A25;
var D: A27;
var D: A28;
var D: A29;
var D: A30;
var D: D1;
var D: D2;
var D: D3;
var D: D4;
var D: D5;
var D: D6;
var D: D10;
var D: D12;
var D: D14;
var D: D16;
var D: D17;
var D: D18;
var D: D19;
var D: D20;
var D: D21;
var D: D22;
var D: D26;
var D: D28;
%
% across(Matrix, Across, Len, Row, Col)
% Constrains 'Across' to be equal to the number represented by the
% 'Len' digits starting at position (Row, Col) of the array 'Matrix'
% and proceeding across.
%
predicate across(array[int, int] of var D: Matrix, var D: Across, int: Len, int: Row, int: Col) =
let {
array[1..Len] of var D: tmp
}
in
toNum10(tmp, Across)
/\
forall(i in 0..Len-1) (
Matrix[Row,Col+i] = tmp[i+1]
)
;
%
% down(Matrix, Down, Len, Row, Col):
% Constrains 'Down' to be equal to the number represented by the
% 'Len' digits starting at position (Row, Col) of the array 'Matrix'
% and proceeding down.
%
predicate down(array[int,int] of var D: Matrix, var D: Down, int: Len, int: Row, int: Col) =
let {
array[1..Len] of var D: tmp
}
in
toNum10(tmp, Down)
/\
forall(i in 0..Len-1) (
Matrix[Row+i,Col] = tmp[i+1]
)
;
%
% converts a number <-> array
%
predicate toNum10(array[int] of var D: a, var D: n) =
let { int: len = length(a) }
in
n = sum(i in 1..len) (
ceil(pow(10.0, int2float(len-i))) * a[i]
)
/\ forall(i in 1..len) (a[i] >= 0)
;
%
% x is a square
%
predicate square(var D: x) =
exists(y in D) (
y*y = x
)
;
%
% very simple primality test
%
predicate is_prime(var int: x) =
forall(i in 2..ceil(sqrt(9999.0))) (
(i < x) -> (x mod i > 0)
)
;
solve :: int_search(
[M[i,j] | i,j in 1..n] ++
[A1,A4,A7,A8,A9,A10,A11,A13,A15,A17,A20,A23,A24,A25,A27,A28,A29,A30,
D1,D2,D3,D4,D5,D6,D10,D12,D14,D16,D17,D18,D19,D20,D21,D22,D26,D28],
occurrence,
indomain_min,
complete
)
satisfy;
constraint
% Set up the constraints between the matrix elements and the
% clue numbers.
across(M, A1, 4, 1, 1) /\
across(M, A4, 4, 1, 6) /\
across(M, A7, 2, 2, 1) /\
across(M, A8, 3, 2, 4) /\
across(M, A9, 2, 2, 8) /\
across(M, A10, 2, 3, 3) /\
across(M, A11, 2, 3, 6) /\
across(M, A13, 4, 4, 1) /\
across(M, A15, 4, 4, 6) /\
across(M, A17, 4, 6, 1) /\
across(M, A20, 4, 6, 6) /\
across(M, A23, 2, 7, 3) /\
across(M, A24, 2, 7, 6) /\
across(M, A25, 2, 8, 1) /\
across(M, A27, 3, 8, 4) /\
across(M, A28, 2, 8, 8) /\
across(M, A29, 4, 9, 1) /\
across(M, A30, 4, 9, 6) /\
down(M, D1, 4, 1, 1) /\
down(M, D2, 2, 1, 2) /\
down(M, D3, 4, 1, 4) /\
down(M, D4, 4, 1, 6) /\
down(M, D5, 2, 1, 8) /\
down(M, D6, 4, 1, 9) /\
down(M, D10, 2, 3, 3) /\
down(M, D12, 2, 3, 7) /\
down(M, D14, 3, 4, 2) /\
down(M, D16, 3, 4, 8) /\
down(M, D17, 4, 6, 1) /\
down(M, D18, 2, 6, 3) /\
down(M, D19, 4, 6, 4) /\
down(M, D20, 4, 6, 6) /\
down(M, D21, 2, 6, 7) /\
down(M, D22, 4, 6, 9) /\
down(M, D26, 2, 8, 2) /\
down(M, D28, 2, 8, 8) /\
% Set up the clue constraints.
% Across
% 1 27 across times two
% 4 4 down plus seventy-one
% 7 18 down plus four
% 8 6 down divided by sixteen
% 9 2 down minus eighteen
% 10 Dozen in six gross
% 11 5 down minus seventy
% 13 26 down times 23 across
% 15 6 down minus 350
% 17 25 across times 23 across
% 20 A square number
% 23 A prime number
% 24 A square number
% 25 20 across divided by seventeen
% 27 6 down divided by four
% 28 Four dozen
% 29 Seven gross
% 30 22 down plus 450
A1 = 2 * A27 /\
A4 = D4 + 71 /\
A7 = D18 + 4 /\
A8 = D6 div 16 /\
A9 = D2 - 18 /\
A10 = 6 * 144 div 12 /\
A11 = D5 - 70 /\
A13 = D26 * A23 /\
A15 = D6 - 350 /\
A17 = A25 * A23 /\
square(A20) /\
is_prime(A23) /\
square(A24) /\
A25 = A20 div 17 /\
A27 = D6 div 4 /\
A28 = 4 * 12 /\
A29 = 7 * 144 /\
A30 = D22 + 450 /\
% Down
%
% 1 1 across plus twenty-seven
% 2 Five dozen
% 3 30 across plus 888
% 4 Two times 17 across
% 5 29 across divided by twelve
% 6 28 across times 23 across
% 10 10 across plus four
% 12 Three times 24 across
% 14 13 across divided by sixteen
% 16 28 down times fifteen
% 17 13 across minus 399
% 18 29 across divided by eighteen
% 19 22 down minus ninety-four
% 20 20 across minus nine
% 21 25 across minus fifty-two
% 22 20 down times six
% 26 Five times 24 across
% 28 21 down plus twenty-seven
D1 = A1 + 27 /\
D2 = 5 * 12 /\
D3 = A30 + 888 /\
D4 = 2 * A17 /\
D5 = A29 div 12 /\
D6 = A28 * A23 /\
D10 = A10 + 4 /\
D12 = A24 * 3 /\
D14 = A13 div 16 /\
D16 = 15 * D28 /\
D17 = A13 - 399 /\
D18 = A29 div 18 /\
D19 = D22 - 94 /\
D20 = A20 - 9 /\
D21 = A25 - 52 /\
D22 = 6 * D20 /\
D26 = 5 * A24 /\
D28 = D21 + 27
% Fix the blackboxes
/\
M[1,5] = 0 /\
M[2,3] = 0 /\
M[2,7] = 0 /\
M[3,2] = 0 /\
M[3,5] = 0 /\
M[3,8] = 0 /\
M[4,5] = 0 /\
M[5,1] = 0 /\
M[5,3] = 0 /\
M[5,4] = 0 /\
M[5,5] = 0 /\
M[5,6] = 0 /\
M[5,7] = 0 /\
M[5,9] = 0 /\
M[6,5] = 0 /\
M[7,2] = 0 /\
M[7,5] = 0 /\
M[7,8] = 0 /\
M[8,3] = 0 /\
M[8,7] = 0 /\
M[9,5] = 0
;
output [
show([A1,A4,A7,A8,A9,A10,A11,A13,A15,A17,A20,A23,A24,A25,A27,A28,A29,A30,
D1,D2,D3,D4,D5,D6,D10,D12,D14,D16,D17,D18,D19,D20,D21,D22,D26,D28]), "\n",
] ++
[
if j = 1 then "\n" else " " endif ++
show(M[i,j])
| i,j in 1..n
] ++ ["\n"];
This work is licensed under a Creative Commons Attribution 4.0 International License.