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.