constraintsminizinc

Minzinc Constraint Question - Sudoku similar


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:

  1. All 9 digits occur excatly 4 times in the matrix.
  2. Direct neighbours in row or column cannot have the same value.
  3. All cells in a row and all cells in a column shall have different values.
  4. There are some exceptions from (3): a) Row 2 has two "6". b) Row 3 has two "3". c) Row 4 has two "5". d) Row 5 has three "7". e) Row 6 has two "8". f) Column B has two "3". g) Column D has two "8". h) Column F has two "9".
  5. The sum of all digits of row 1 is >= 38.
  6. The sum of all digits of column E is = 21.
  7. Row 2 does not contain a "1".
  8. Row 4 does not contain a "4".
  9. Row 5 does not contain a "2".
  10. Row 6 does not contain a "3".
  11. Column C does not contain a "2".
  12. Column B has only even digits, except for the two "3".
  13. Column A has a ascending or descending sequence, e.g. "234567" or "987654".

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


Solution

  • 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!