• Special Pages
• User

Help

Bridges Puzzle (Hashiwokakero)

(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.