Bridges Puzzle (Hashiwokakero)

Revision as of 14:34, 15 December 2015 by Michael Leuschel (talk | contribs) (Created page with "The [ Hashiwokakero] Puzzle is a logical puzzle where one has to build <b>bridges</b> between islands. The puzzle is also known unde...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

The Hashiwokakero Puzzle is a logical puzzle where one has to build bridges between islands. The puzzle is also known under the name Ai-Ki-Ai. The puzzles can also be played online.

The requirements for this puzzle are as follows:

  • the goal is to build bridges between islands so as to generate a connected graph
  • every island has a number on it, indicating exactly how many bridges should be linked with the island
  • there is an upper bound (MAXBRIDGES) on the number of bridges that can be built-between two islands
  • bridges cannot cross each other

A B model for this puzzle can be found below. The constants and sets of the model are as follows:

  • N are the nodes (islands); we have added a constant ignore where one can stipulate which islands should be ignored in this puzzle
  • nl (number of links) stipulates for each island how many bridges it should be linked with
  • xc, yc are the x- and y-coordinates for every island

A simple puzzle with four islands would be defined as follows, assuming the basic set N is defined as N = {a,b,c,d,e,f,g,h,i,j,k,l,m,n}:

 xc(a)=0 & xc(b)=1 & xc(c)=0 & xc(d) = 1 &
 yc(a)=0 & yc(b)=0 & yc(c)=1 & yc(d) = 1 &
 nl = {a|->2, b|->2, c|->2, d|->2} &
 ignore = {e,f,g,h,i,j,k,l,m,n}

The model then contains the following derived constants:

  • plx,ply: the possible links between islands on the x- and y-axis respectively
  • pl: the possible links both on the x- and y-axis combined
  • cs: the conflict set of links which overlap, i.e., one cannot build bridges on both links (a,b) when the pair (a,b) is in cs
  • connected: the set of links on which at least one bridge was built

The model also sets up the goal constant sol which maps every link in pl to a number indicating how many bridges are built on it. The model also stipulates that the graph set up by connected generates a fully connected graph.