I'm new to Minizinc, and I want to solve the following problem.
I have a given matrix of 6x6 cells. Rows are numbered from 1..6, columns from A..B. All cells shall be filled with digits from 1..9 by certain rules:
The most headache for me when constructing the model in Minzinc is the "contradictionary" constraints:
How can this realized?
Thanks in advance and best regards. Guenther
I got curious how to model this problem in a concise way with Clingo ASP as an alternative to minizinc. It’s not Constraint Programming, but is related and quite declarative, so it may give you some ideas:
(actually, minizinc supports the related solver via flatzingo as well.)
% Define rows and columns
row(1..6).
col(a;b;c;d;e;f).
% Define digits
digit(1..9).
% Each cell has exactly one digit
1 { value(R, C, D) : digit(D) } 1 :- row(R), col(C).
% Each digit appears exactly 4 times in the grid
:- digit(D), #count { R, C : value(R, C, D) } != 4.
% No two adjacent cells in a row or column can have the same digit
:- value(R1, C, D), value(R2, C, D), R1 = R2 - 1.
:- value(R, C1, D), value(R, C2, D), adjacent_col(C1, C2).
% Define adjacency in columns
adjacent_col(a, b). adjacent_col(b, c). adjacent_col(c, d).
adjacent_col(d, e). adjacent_col(e, f).
adjacent_col(X, Y) :- adjacent_col(Y, X).
% Row uniqueness with exceptions
:- row(R), digit(D), #count { C : value(R, C, D) } > 1, not allowed_repeat(R, D).
% Column uniqueness with exceptions
:- col(C), digit(D), #count { R : value(R, C, D) } > 1, not allowed_repeat(C, D).
% Define exceptions for uniqueness constraints
allowed_repeat(2, 6).
allowed_repeat(3, 3).
allowed_repeat(4, 5).
allowed_repeat(5, 7).
allowed_repeat(6, 8).
allowed_repeat(b, 3).
allowed_repeat(d, 8).
allowed_repeat(f, 9).
% Enforce the exact count for the exceptions
:- #count { C : value(2, C, 6) } != 2.
:- #count { C : value(3, C, 3) } != 2.
:- #count { C : value(4, C, 5) } != 2.
:- #count { C : value(5, C, 7) } != 3.
:- #count { C : value(6, C, 8) } != 2.
:- #count { R : value(R, b, 3) } != 2.
:- #count { R : value(R, d, 8) } != 2.
:- #count { R : value(R, f, 9) } != 2.
% Sum constraints row 1, col E
:- #sum { D : value(1, C, D), col(C) } < 38.
:- #sum { D : value(R, e, D), row(R) } != 21.
% Forbidden digits in specific rows and columns
:- value(2, C, 1).
:- value(4, C, 4).
:- value(5, C, 2).
:- value(6, C, 3).
:- value(R, c, 2).
% Column B only has even digits except for two "3"
:- value(R, b, D), D != 2, D != 4, D != 6, D != 8, D != 3.
% Column A must be an ascending or descending sequence
% (in conjunction w/ all different)
:- value(R1, a, D1), value(R2, a, D2), R2 = R1 + 1,
D2 != D1 + 1, D2 != D1 - 1.
#show value/3.
Output: (copy and paste the code to run it online)
clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
Answer: 1
value(6,a,8) value(5,a,7) value(4,a,6) value(3,a,5) value(2,a,4) value(1,a,3) value(3,b,3) value(5,b,3) value(4,e,1) value(6,e,2) value(3,e,3) value(5,e,4) value(1,e,5) value(2,e,6) value(1,c,6) value(1,d,7) value(1,b,8) value(1,f,9) value(6,f,9) value(2,d,8) value(6,d,8) value(5,c,7) value(5,f,7) value(4,c,5) value(4,f,5) value(2,b,6) value(4,b,2) value(6,b,4) value(6,c,1) value(3,c,4) value(2,c,9) value(5,d,1) value(3,d,2) value(4,d,9) value(3,f,1) value(2,f,2)
SATISFIABLE
Models : 1+
Calls : 1
Time : 0.158s (Solving: 0.02s 1st Model: 0.02s Unsat: 0.00s)
CPU Time : 0.000s
The unique solution as a matrix:
R\C | A | B | C | D | E | F |
---|---|---|---|---|---|---|
1 | 3 | 8 | 6 | 7 | 5 | 9 |
2 | 4 | 6 | 9 | 8 | 6 | 2 |
3 | 5 | 3 | 4 | 2 | 3 | 1 |
4 | 6 | 2 | 5 | 9 | 1 | 5 |
5 | 7 | 3 | 7 | 1 | 4 | 7 |
6 | 8 | 4 | 1 | 8 | 2 | 9 |
Update:
I added the other solution from OP to the model to verify in both directions:
value(1,a,3). value(1,b,6). value(1,c,7). value(1,d,8). value(1,e,5). value(1,f,9).
value(2,a,4). value(2,b,8). value(2,c,6). value(2,d,9). value(2,e,6). value(2,f,2).
value(3,a,5). value(3,b,3). value(3,c,4). value(3,d,1). value(3,e,3). value(3,f,9).
value(4,a,6). value(4,b,2). value(4,c,5). value(4,d,2). value(4,e,1). value(4,f,5).
value(5,a,7). value(5,b,3). value(5,c,1). value(5,d,7). value(5,e,4). value(5,f,7).
value(6,a,8). value(6,b,4). value(6,c,9). value(6,d,8). value(6,e,2). value(6,f,1).
… and this is the output:
clingo version 5.7.2 (6bd7584d)
Reading from stdin
Solving...
UNSATISFIABLE
Models : 0
Calls : 1
Time : 0.099s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.000s
Hint:
Have a look at row 4!