alpar@1: /* A solver for the Japanese number-puzzle Hashiwokakero alpar@1: * (http://en.wikipedia.org/wiki/Hashiwokakero) alpar@1: * alpar@1: * Sebastian Nowozin , 13th January 2009 alpar@1: */ alpar@1: alpar@1: param n := 25; alpar@1: set rows := 1..n; alpar@1: set cols := 1..n; alpar@1: param givens{rows, cols}, integer, >= 0, <= 8, default 0; alpar@1: alpar@1: /* Set of vertices as (row,col) coordinates */ alpar@1: set V := { (i,j) in { rows, cols }: givens[i,j] != 0 }; alpar@1: alpar@1: /* Set of feasible horizontal edges from (i,j) to (k,l) rightwards */ alpar@1: set Eh := { (i,j,k,l) in { V, V }: alpar@1: i = k and j < l and # Same row and left to right alpar@1: card({ (s,t) in V: s = i and t > j and t < l }) = 0 # No vertex inbetween alpar@1: }; alpar@1: alpar@1: /* Set of feasible vertical edges from (i,j) to (k,l) downwards */ alpar@1: set Ev := { (i,j,k,l) in { V, V }: alpar@1: j = l and i < k and # Same column and top to bottom alpar@1: card({ (s,t) in V: t = j and s > i and s < k }) = 0 # No vertex inbetween alpar@1: }; alpar@1: alpar@1: set E := Eh union Ev; alpar@1: alpar@1: /* Indicators: use edge once/twice */ alpar@1: var xe1{E}, binary; alpar@1: var xe2{E}, binary; alpar@1: alpar@1: /* Constraint: Do not use edge or do use once or do use twice */ alpar@1: s.t. edge_sel{(i,j,k,l) in E}: alpar@1: xe1[i,j,k,l] + xe2[i,j,k,l] <= 1; alpar@1: alpar@1: /* Constraint: There must be as many edges used as the node value */ alpar@1: s.t. satisfy_vertex_demand{(s,t) in V}: alpar@1: sum{(i,j,k,l) in E: (i = s and j = t) or (k = s and l = t)} alpar@1: (xe1[i,j,k,l] + 2.0*xe2[i,j,k,l]) = givens[s,t]; alpar@1: alpar@1: /* Constraint: No crossings */ alpar@1: s.t. no_crossing1{(i,j,k,l) in Eh, (s,t,u,v) in Ev: alpar@1: s < i and u > i and j < t and l > t}: alpar@1: xe1[i,j,k,l] + xe1[s,t,u,v] <= 1; alpar@1: s.t. no_crossing2{(i,j,k,l) in Eh, (s,t,u,v) in Ev: alpar@1: s < i and u > i and j < t and l > t}: alpar@1: xe1[i,j,k,l] + xe2[s,t,u,v] <= 1; alpar@1: s.t. no_crossing3{(i,j,k,l) in Eh, (s,t,u,v) in Ev: alpar@1: s < i and u > i and j < t and l > t}: alpar@1: xe2[i,j,k,l] + xe1[s,t,u,v] <= 1; alpar@1: s.t. no_crossing4{(i,j,k,l) in Eh, (s,t,u,v) in Ev: alpar@1: s < i and u > i and j < t and l > t}: alpar@1: xe2[i,j,k,l] + xe2[s,t,u,v] <= 1; alpar@1: alpar@1: alpar@1: /* Model connectivity by auxiliary network flow problem: alpar@1: * One vertex becomes a target node and all other vertices send a unit flow alpar@1: * to it. The edge selection variables xe1/xe2 are VUB constraints and alpar@1: * therefore xe1/xe2 select the feasible graph for the max-flow problems. alpar@1: */ alpar@1: set node_target := { (s,t) in V: alpar@1: card({ (i,j) in V: i < s or (i = s and j < t) }) = 0}; alpar@1: set node_sources := { (s,t) in V: (s,t) not in node_target }; alpar@1: alpar@1: var flow_forward{ E }, >= 0; alpar@1: var flow_backward{ E }, >= 0; alpar@1: s.t. flow_conservation{ (s,t) in node_target, (p,q) in V }: alpar@1: /* All incoming flows */ alpar@1: - sum{(i,j,k,l) in E: k = p and l = q} flow_forward[i,j,k,l] alpar@1: - sum{(i,j,k,l) in E: i = p and j = q} flow_backward[i,j,k,l] alpar@1: /* All outgoing flows */ alpar@1: + sum{(i,j,k,l) in E: k = p and l = q} flow_backward[i,j,k,l] alpar@1: + sum{(i,j,k,l) in E: i = p and j = q} flow_forward[i,j,k,l] alpar@1: = 0 + (if (p = s and q = t) then card(node_sources) else -1); alpar@1: alpar@1: /* Variable-Upper-Bound (VUB) constraints: xe1/xe2 bound the flows. alpar@1: */ alpar@1: s.t. connectivity_vub1{(i,j,k,l) in E}: alpar@1: flow_forward[i,j,k,l] <= card(node_sources)*(xe1[i,j,k,l] + xe2[i,j,k,l]); alpar@1: s.t. connectivity_vub2{(i,j,k,l) in E}: alpar@1: flow_backward[i,j,k,l] <= card(node_sources)*(xe1[i,j,k,l] + xe2[i,j,k,l]); alpar@1: alpar@1: /* A feasible solution is enough alpar@1: */ alpar@1: minimize cost: 0; alpar@1: alpar@1: solve; alpar@1: alpar@1: /* Output solution graphically */ alpar@1: printf "\nSolution:\n"; alpar@1: for { row in rows } { alpar@1: for { col in cols } { alpar@1: /* First print this cell information: givens or space */ alpar@1: printf{0..0: givens[row,col] != 0} "%d", givens[row,col]; alpar@1: printf{0..0: givens[row,col] = 0 and alpar@1: card({(i,j,k,l) in Eh: i = row and col >= j and col < l and alpar@1: xe1[i,j,k,l] = 1}) = 1} "-"; alpar@1: printf{0..0: givens[row,col] = 0 and alpar@1: card({(i,j,k,l) in Eh: i = row and col >= j and col < l and alpar@1: xe2[i,j,k,l] = 1}) = 1} "="; alpar@1: printf{0..0: givens[row,col] = 0 alpar@1: and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and alpar@1: xe1[i,j,k,l] = 1}) = 1} "|"; alpar@1: printf{0..0: givens[row,col] = 0 alpar@1: and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and alpar@1: xe2[i,j,k,l] = 1}) = 1} '"'; alpar@1: printf{0..0: givens[row,col] = 0 alpar@1: and card({(i,j,k,l) in Eh: i = row and col >= j and col < l and alpar@1: (xe1[i,j,k,l] = 1 or xe2[i,j,k,l] = 1)}) = 0 alpar@1: and card({(i,j,k,l) in Ev: j = col and row >= i and row < k and alpar@1: (xe1[i,j,k,l] = 1 or xe2[i,j,k,l] = 1)}) = 0} " "; alpar@1: alpar@1: /* Now print any edges */ alpar@1: printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and xe1[i,j,k,l] = 1} "-"; alpar@1: printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and xe2[i,j,k,l] = 1} "="; alpar@1: alpar@1: printf{(i,j,k,l) in Eh: i = row and col >= j and col < l and alpar@1: xe1[i,j,k,l] = 0 and xe2[i,j,k,l] = 0} " "; alpar@1: printf{0..0: card({(i,j,k,l) in Eh: i = row and col >= j and col < l}) = 0} " "; alpar@1: } alpar@1: printf "\n"; alpar@1: for { col in cols } { alpar@1: printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and xe1[i,j,k,l] = 1} "|"; alpar@1: printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and xe2[i,j,k,l] = 1} '"'; alpar@1: printf{(i,j,k,l) in Ev: j = col and row >= i and row < k and alpar@1: xe1[i,j,k,l] = 0 and xe2[i,j,k,l] = 0} " "; alpar@1: /* No vertical edges: skip also a field */ alpar@1: printf{0..0: card({(i,j,k,l) in Ev: j = col and row >= i and row < k}) = 0} " "; alpar@1: printf " "; alpar@1: } alpar@1: printf "\n"; alpar@1: } alpar@1: alpar@1: data; alpar@1: alpar@1: /* This is a difficult 25x25 Hashiwokakero. alpar@1: */ alpar@1: 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 alpar@1: 25 := alpar@1: 1 2 . 2 . 2 . . 2 . 2 . . 2 . . . . 2 . 2 . 2 . 2 . alpar@1: 2 . 1 . . . . 2 . . . 4 . . 5 . 2 . . 1 . 2 . 2 . 1 alpar@1: 3 2 . . 5 . 4 . . 3 . . . . . 1 . . 4 . 5 . 1 . 1 . alpar@1: 4 . . . . . . . . . . . 1 . 3 . . 1 . . . . . . . . alpar@1: 5 2 . . 6 . 6 . . 8 . 5 . 2 . . 3 . 5 . 7 . . 2 . . alpar@1: 6 . 1 . . . . . . . . . 1 . . 2 . . . . . 1 . . . 3 alpar@1: 7 2 . . . . 5 . . 6 . 4 . . 2 . . . 2 . 5 . 4 . 2 . alpar@1: 8 . 2 . 2 . . . . . . . . . . . 3 . . 3 . . . 1 . 2 alpar@1: 9 . . . . . . . . . . 4 . 2 . 2 . . 1 . . . 3 . 1 . alpar@1: 10 2 . 3 . . 6 . . 2 . . . . . . . . . . 3 . . . . . alpar@1: 11 . . . . 1 . . 2 . . 5 . . 1 . 4 . 3 . . . . 2 . 4 alpar@1: 12 . . 2 . . 1 . . . . . . 5 . 4 . . . . 4 . 3 . . . alpar@1: 13 2 . . . 3 . 1 . . . . . . . . 3 . . 5 . 5 . . 2 . alpar@1: 14 . . . . . 2 . 5 . . 7 . 5 . 3 . 1 . . 1 . . 1 . 4 alpar@1: 15 2 . 5 . 3 . . . . 1 . 2 . 1 . . . . 2 . 4 . . 2 . alpar@1: 16 . . . . . 1 . . . . . . . . . . 2 . . 2 . 1 . . 3 alpar@1: 17 2 . 6 . 6 . . 2 . . 2 . 2 . 5 . . . . . 2 . . . . alpar@1: 18 . . . . . 1 . . . 3 . . . . . 1 . . 1 . . 4 . 3 . alpar@1: 19 . . 4 . 5 . . 2 . . . 2 . . 6 . 6 . . 3 . . . . 3 alpar@1: 20 2 . . . . . . . . . 2 . . 1 . . . . . . 1 . . 1 . alpar@1: 21 . . 3 . . 3 . 5 . 5 . . 4 . 6 . 7 . . 4 . 6 . . 4 alpar@1: 22 2 . . . 3 . 5 . 2 . 1 . . . . . . . . . . . . . . alpar@1: 23 . . . . . . . . . 1 . . . . . . 3 . 2 . . 5 . . 5 alpar@1: 24 2 . 3 . 3 . 5 . 4 . 3 . 3 . 4 . . 2 . 2 . . . 1 . alpar@1: 25 . 1 . 2 . 2 . . . 2 . 2 . . . 2 . . . . 2 . 2 . 2 alpar@1: ; alpar@1: alpar@1: end;