Hashiwokakero (Hashi, Bridges)

Description

Hashiwokakero is a single player game played on a rectangular grid in which each cell is either empty or it contains a vertex, called island, labelled with an integer between 1 and 8. The player can draw bridges, i.e., horizontal or vertical edges between islands. Bridges cannot intersect any other vertex except their endpoints, nor can they intersect any other bridge. At most one bridge (whether single or double) can be built between the same (unordered) pair of islands. In other words the resulting graph drawing must be a plane graph. Moreover, each bridge can be either single or double. The goal is that of drawing a suitable set of bridges so that:

• All islands are directly or indirectly connected (i.e., the resulting graph is connected).
• The label on each island is equal to the number of its incident single bridges plus twice the number of its incident double bridges.

The figure shows a solved instance of Hashiwokakero. The gray grid is often omitted.

Computational complexity

The problem of deciding whether an instance of Hashiwokakero admits a solution is NP-Complete [1].

A branch-and-cut algorithm for solving Hashiwokakero instances is given in [2].

References

[1] D. Andersson, “Hashiwokakero is NP-complete”, Information Processing Letters, 2009.

[2] L. C. Coelho, G. Laporte, A. Lindbeck, T. Vidal, “Benchmark Instances and Branch-and-Cut Algorithm for the Hashiwokakero Puzzle”, arXiv preprint, 2019.

@misc{cog:hashiwokakero,
    author = "{CoG contributors}",
    title  = "{Hashiwokakero (Hashi, Bridges) --- Complexity of Games}",
    year   = "2024",
    url    = "https://www.isnphard.com/i/hashiwokakero/",
    note   = "[Online; accessed 2024-04-13]"
}