1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 | % % Nonoram solver using regular and is written in all-MiniZinc. % % This version uses the regular constraint with the following features: % % * Compared to http://www.hakank.org/nonogram_regular.mzn % It calculated all the finite states given a Nonogram pattern, % instead of relying on an external program for doing this. % % * Compared to http://www.hakank.org/nonogram_create_automaton.mzn % It calculates the states as par int (not var int), which % makes it possible to use some optimal regular constraints, % for example the one in Gecode/FlatZinc. % % Warning: the calculation of the states is quite ugly. % % % 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/ include "globals.mzn" ; int : rows; int : row_rule_len; array [1..rows, 1..row_rule_len] of int : row_rules; int : cols; int : col_rule_len; array [1..cols, 1..col_rule_len] of int : col_rules; array [1..rows, 1..cols] of var 1..2: x; solve :: int_search( [x[i,j] | j in 1..cols, i in 1..rows], first_fail, indomain_min, complete) satisfy ; % % The approach is rather simple: % - zero_positions is a set of the positions in the state table where the % state 0 should be, which also correspond to the state of the pattern "0" % - when this have been identified everything else comes to rest % % On the other hand, the calculation of the states is hairy, very hairy. % predicate make_automaton( array [ int ] of var int : x, array [ int ] of int : pattern) = let { int : n = length (pattern), % fix for "zero clues" int : len = max ( length ([pattern[i] | i in 1..n where pattern[i] > 0]) + sum (pattern),1), int : leading_zeros = sum (i in 1..n) ( bool2int (pattern[i] = 0)), set of int : zero_positions = { sum (j in 1..i) (pattern[j]+1) -leading_zeros | i in 1..n where pattern[i] > 0}, array [1..2*len] of 0..len*2: states = if ( length ([pattern[i] | i in 1..n where pattern[i] > 0]) + sum (pattern)) = 0 then [1,1] % fix for "zero clues" else [1, 2] ++ [ if i div 2 in zero_positions then if i mod 2 = 0 then 0 else (i div 2) + 1 endif elseif (i-1) div 2 in zero_positions then if i mod 2 = 0 then (i div 2)+1 else (i div 2)+2 endif else if not( (((i-1) div 2) - 1) in zero_positions) then if i mod 2 = 0 then (i div 2) + 1 else if (i div 2) + 1 in zero_positions then (i div 2) + 2 else 0 endif endif else if i mod 2 = 0 then (i div 2) + 1 else if not((i div 2) + 1 in zero_positions) then 0 else (i div 2) + 2 endif endif endif endif | i in 3..2*(len-1)] ++ [len, 0] endif } in regular( x, len, 2, array2d (1..len, 1..2, states), 1, {len}) % :: domain ; constraint forall (j in 1..cols) ( make_automaton([x[i,j] | i in 1..rows], [col_rules[j,k] | k in 1..col_rule_len]) ) /\ forall (i in 1..rows) ( make_automaton([x[i,j] | j in 1..cols], [row_rules[i,k] | k in 1..row_rule_len]) ) ; output [ if j = 1 then "\n" else "" endif ++ if fix (x[i,j]) = 1 then " " else "#" endif | i in 1..rows, j in 1..cols ] ++ [ "\n" ]; |