1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/examples/hashi.mod Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,168 @@
1.4 +/* A solver for the Japanese number-puzzle Hashiwokakero
1.5 + * (http://en.wikipedia.org/wiki/Hashiwokakero)
1.6 + *
1.7 + * Sebastian Nowozin <nowozin@gmail.com>, 13th January 2009
1.8 + */
1.9 +
1.10 +param n := 25;
1.11 +set rows := 1..n;
1.12 +set cols := 1..n;
1.13 +param givens{rows, cols}, integer, >= 0, <= 8, default 0;
1.14 +
1.15 +/* Set of vertices as (row,col) coordinates */
1.16 +set V := { (i,j) in { rows, cols }: givens[i,j] != 0 };
1.17 +
1.18 +/* Set of feasible horizontal edges from (i,j) to (k,l) rightwards */
1.19 +set Eh := { (i,j,k,l) in { V, V }:
1.20 + i = k and j < l and # Same row and left to right
1.21 + card({ (s,t) in V: s = i and t > j and t < l }) = 0 # No vertex inbetween
1.22 + };
1.23 +
1.24 +/* Set of feasible vertical edges from (i,j) to (k,l) downwards */
1.25 +set Ev := { (i,j,k,l) in { V, V }:
1.26 + j = l and i < k and # Same column and top to bottom
1.27 + card({ (s,t) in V: t = j and s > i and s < k }) = 0 # No vertex inbetween
1.28 + };
1.29 +
1.30 +set E := Eh union Ev;
1.31 +
1.32 +/* Indicators: use edge once/twice */
1.33 +var xe1{E}, binary;
1.34 +var xe2{E}, binary;
1.35 +
1.36 +/* Constraint: Do not use edge or do use once or do use twice */
1.37 +s.t. edge_sel{(i,j,k,l) in E}:
1.38 + xe1[i,j,k,l] + xe2[i,j,k,l] <= 1;
1.39 +
1.40 +/* Constraint: There must be as many edges used as the node value */
1.41 +s.t. satisfy_vertex_demand{(s,t) in V}:
1.42 + sum{(i,j,k,l) in E: (i = s and j = t) or (k = s and l = t)}
1.43 + (xe1[i,j,k,l] + 2.0*xe2[i,j,k,l]) = givens[s,t];
1.44 +
1.45 +/* Constraint: No crossings */
1.46 +s.t. no_crossing1{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
1.47 + s < i and u > i and j < t and l > t}:
1.48 + xe1[i,j,k,l] + xe1[s,t,u,v] <= 1;
1.49 +s.t. no_crossing2{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
1.50 + s < i and u > i and j < t and l > t}:
1.51 + xe1[i,j,k,l] + xe2[s,t,u,v] <= 1;
1.52 +s.t. no_crossing3{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
1.53 + s < i and u > i and j < t and l > t}:
1.54 + xe2[i,j,k,l] + xe1[s,t,u,v] <= 1;
1.55 +s.t. no_crossing4{(i,j,k,l) in Eh, (s,t,u,v) in Ev:
1.56 + s < i and u > i and j < t and l > t}:
1.57 + xe2[i,j,k,l] + xe2[s,t,u,v] <= 1;
1.58 +
1.59 +
1.60 +/* Model connectivity by auxiliary network flow problem:
1.61 + * One vertex becomes a target node and all other vertices send a unit flow
1.62 + * to it. The edge selection variables xe1/xe2 are VUB constraints and
1.63 + * therefore xe1/xe2 select the feasible graph for the max-flow problems.
1.64 + */
1.65 +set node_target := { (s,t) in V:
1.66 + card({ (i,j) in V: i < s or (i = s and j < t) }) = 0};
1.67 +set node_sources := { (s,t) in V: (s,t) not in node_target };
1.68 +
1.69 +var flow_forward{ E }, >= 0;
1.70 +var flow_backward{ E }, >= 0;
1.71 +s.t. flow_conservation{ (s,t) in node_target, (p,q) in V }:
1.72 + /* All incoming flows */
1.73 + - sum{(i,j,k,l) in E: k = p and l = q} flow_forward[i,j,k,l]
1.74 + - sum{(i,j,k,l) in E: i = p and j = q} flow_backward[i,j,k,l]
1.75 + /* All outgoing flows */
1.76 + + sum{(i,j,k,l) in E: k = p and l = q} flow_backward[i,j,k,l]
1.77 + + sum{(i,j,k,l) in E: i = p and j = q} flow_forward[i,j,k,l]
1.78 + = 0 + (if (p = s and q = t) then card(node_sources) else -1);
1.79 +
1.80 +/* Variable-Upper-Bound (VUB) constraints: xe1/xe2 bound the flows.
1.81 + */
1.82 +s.t. connectivity_vub1{(i,j,k,l) in E}:
1.83 + flow_forward[i,j,k,l] <= card(node_sources)*(xe1[i,j,k,l] + xe2[i,j,k,l]);
1.84 +s.t. connectivity_vub2{(i,j,k,l) in E}:
1.85 + flow_backward[i,j,k,l] <= card(node_sources)*(xe1[i,j,k,l] + xe2[i,j,k,l]);
1.86 +
1.87 +/* A feasible solution is enough
1.88 + */
1.89 +minimize cost: 0;
1.90 +
1.91 +solve;
1.92 +
1.93 +/* Output solution graphically */
1.94 +printf "\nSolution:\n";
1.95 +for { row in rows } {
1.96 + for { col in cols } {
1.97 + /* First print this cell information: givens or space */
1.98 + printf{0..0: givens[row,col] != 0} "%d", givens[row,col];
1.99 + printf{0..0: givens[row,col] = 0 and
1.100 + card({(i,j,k,l) in Eh: i = row and col >= j and col < l and
1.101 + xe1[i,j,k,l] = 1}) = 1} "-";
1.102 + printf{0..0: givens[row,col] = 0 and
1.103 + card({(i,j,k,l) in Eh: i = row and col >= j and col < l and
1.104 + xe2[i,j,k,l] = 1}) = 1} "=";
1.105 + printf{0..0: givens[row,col] = 0
1.106 + and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and
1.107 + xe1[i,j,k,l] = 1}) = 1} "|";
1.108 + printf{0..0: givens[row,col] = 0
1.109 + and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and
1.110 + xe2[i,j,k,l] = 1}) = 1} '"';
1.111 + printf{0..0: givens[row,col] = 0
1.112 + and card({(i,j,k,l) in Eh: i = row and col >= j and col < l and
1.113 + (xe1[i,j,k,l] = 1 or xe2[i,j,k,l] = 1)}) = 0
1.114 + and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and
1.115 + (xe1[i,j,k,l] = 1 or xe2[i,j,k,l] = 1)}) = 0} " ";
1.116 +
1.117 + /* Now print any edges */
1.118 + printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and xe1[i,j,k,l] = 1} "-";
1.119 + printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and xe2[i,j,k,l] = 1} "=";
1.120 +
1.121 + printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and
1.122 + xe1[i,j,k,l] = 0 and xe2[i,j,k,l] = 0} " ";
1.123 + printf{0..0: card({(i,j,k,l) in Eh: i = row and col >= j and col < l}) = 0} " ";
1.124 + }
1.125 + printf "\n";
1.126 + for { col in cols } {
1.127 + printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and xe1[i,j,k,l] = 1} "|";
1.128 + printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and xe2[i,j,k,l] = 1} '"';
1.129 + printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and
1.130 + xe1[i,j,k,l] = 0 and xe2[i,j,k,l] = 0} " ";
1.131 + /* No vertical edges: skip also a field */
1.132 + printf{0..0: card({(i,j,k,l) in Ev: j = col and row >= i and row < k}) = 0} " ";
1.133 + printf " ";
1.134 + }
1.135 + printf "\n";
1.136 +}
1.137 +
1.138 +data;
1.139 +
1.140 +/* This is a difficult 25x25 Hashiwokakero.
1.141 + */
1.142 +param givens : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1.143 +25 :=
1.144 + 1 2 . 2 . 2 . . 2 . 2 . . 2 . . . . 2 . 2 . 2 . 2 .
1.145 + 2 . 1 . . . . 2 . . . 4 . . 5 . 2 . . 1 . 2 . 2 . 1
1.146 + 3 2 . . 5 . 4 . . 3 . . . . . 1 . . 4 . 5 . 1 . 1 .
1.147 + 4 . . . . . . . . . . . 1 . 3 . . 1 . . . . . . . .
1.148 + 5 2 . . 6 . 6 . . 8 . 5 . 2 . . 3 . 5 . 7 . . 2 . .
1.149 + 6 . 1 . . . . . . . . . 1 . . 2 . . . . . 1 . . . 3
1.150 + 7 2 . . . . 5 . . 6 . 4 . . 2 . . . 2 . 5 . 4 . 2 .
1.151 + 8 . 2 . 2 . . . . . . . . . . . 3 . . 3 . . . 1 . 2
1.152 + 9 . . . . . . . . . . 4 . 2 . 2 . . 1 . . . 3 . 1 .
1.153 + 10 2 . 3 . . 6 . . 2 . . . . . . . . . . 3 . . . . .
1.154 + 11 . . . . 1 . . 2 . . 5 . . 1 . 4 . 3 . . . . 2 . 4
1.155 + 12 . . 2 . . 1 . . . . . . 5 . 4 . . . . 4 . 3 . . .
1.156 + 13 2 . . . 3 . 1 . . . . . . . . 3 . . 5 . 5 . . 2 .
1.157 + 14 . . . . . 2 . 5 . . 7 . 5 . 3 . 1 . . 1 . . 1 . 4
1.158 + 15 2 . 5 . 3 . . . . 1 . 2 . 1 . . . . 2 . 4 . . 2 .
1.159 + 16 . . . . . 1 . . . . . . . . . . 2 . . 2 . 1 . . 3
1.160 + 17 2 . 6 . 6 . . 2 . . 2 . 2 . 5 . . . . . 2 . . . .
1.161 + 18 . . . . . 1 . . . 3 . . . . . 1 . . 1 . . 4 . 3 .
1.162 + 19 . . 4 . 5 . . 2 . . . 2 . . 6 . 6 . . 3 . . . . 3
1.163 + 20 2 . . . . . . . . . 2 . . 1 . . . . . . 1 . . 1 .
1.164 + 21 . . 3 . . 3 . 5 . 5 . . 4 . 6 . 7 . . 4 . 6 . . 4
1.165 + 22 2 . . . 3 . 5 . 2 . 1 . . . . . . . . . . . . . .
1.166 + 23 . . . . . . . . . 1 . . . . . . 3 . 2 . . 5 . . 5
1.167 + 24 2 . 3 . 3 . 5 . 4 . 3 . 3 . 4 . . 2 . 2 . . . 1 .
1.168 + 25 . 1 . 2 . 2 . . . 2 . 2 . . . 2 . . . . 2 . 2 . 2
1.169 + ;
1.170 +
1.171 +end;