Benchmark Instances and Branch-and-Cut Algorithm for the Hashiwokakero Puzzle

Leandro C. Coelho, Gilbert Laporte, Arinei Lindbeck, Thibaut VidalarXiv 2019 · arXiv

Abstract

Hashiwokakero (Hashi) is a popular Japanese logic puzzle proven to be NP-complete. This paper presents the first robust mathematical framework and exact algorithm for solving large-scale Hashi puzzles. By formulating the puzzle as an integer linear program (ILP) and employing a branch-and-cut algorithm enhanced by a novel "weak connectivity" constraint, the authors demonstrate the ability to solve complex puzzles with up to 400 islands in under 40 seconds on average.

Introduction: The Hashiwokakero Challenge

Hashiwokakero, commonly known as "Hashi" or "Bridges," involves connecting a set of "islands" (numbered circles) on a grid using horizontal or vertical bridges. The objective is to satisfy three main conditions:

  1. Each island must have a specific number of incident bridges equal to its number.
  2. Bridges cannot cross each other.
  3. The final network must be a single connected component.
A typical Hashi puzzle and its completed solution showing single and double bridges.

Despite its simple rules, Hashi is computationally difficult. Proven to be NP-complete in 2009, the search space for solutions grows exponentially with the number of islands. Prior research lacked standardized benchmarks and efficient exact solvers for large-scale instances.

Methodology: Integer Linear Programming and Branch-and-Cut

The authors approach Hashi as a graph theory problem, modeling it using Integer Linear Programming (ILP). The model utilizes integer variables ($x_{ij}$) to represent the number of bridges (0, 1, or 2) and binary variables ($y_{ij}$) to indicate the presence of any bridge between two islands.

Connectivity Constraints

The connectivity requirement is the most challenging to model. Instead of pre-loading thousands of subtour elimination constraints, the authors utilize a Branch-and-Cut algorithm. This approach solves a relaxed version of the problem and dynamically introduces "strong connectivity" constraints only when a disconnected solution is found.

Illustration of a Hashi puzzle, intermediate steps showing the dynamic introduction of connectivity constraints, and the final completed solution.

The "Weak Connectivity" Innovation

A significant contribution of this work is the introduction of the "weak connectivity constraint." Recognizing that any valid solution must at least contain a spanning tree, the authors added a global constraint requiring the total number of bridges to be at least $n-1$ (where $n$ is the number of islands). This simple bound effectively prunes the search space, reducing the reliance on computationally expensive "strong" connectivity checks.

Benchmarking and Datasets

To evaluate their algorithm, the authors developed a Hashi puzzle generator and created a dataset of 1,440 instances. These instances vary by size (100 to 400 islands), connectivity (cycle density), and double-bridge density. This dataset serves as a public baseline for future research in the field.

Results and Insights

The branch-and-cut algorithm proved highly efficient, solving 100-island puzzles almost instantaneously and 400-island puzzles in an average of 36.94 seconds.

Key findings include:

  • Impact of Weak Connectivity: Without this constraint, average CPU time increased by 24%, and the number of required "strong" cuts rose by 70%.
  • Complexity Drivers: The number of islands ($n$) and the density of double-bridges ($\beta$) are the primary factors influencing puzzle difficulty.
  • NP-Completeness: The authors demonstrated that Hashi remains hard even without the connectivity rule, proving that the combination of degree and non-crossing constraints is sufficient for NP-completeness.

Conclusion

This research provides a powerful tool for solving large-scale Hashi puzzles and establishes a rigorous framework for future algorithmic development. While the current generator does not guarantee unique solutions—a common requirement for commercial puzzles—the ILP framework demonstrates remarkable scalability and efficiency for this class of logic puzzles.

Summary updated

Abstract

Hashiwokakero, or simply Hashi, is a Japanese single-player puzzle played on a rectangular grid with no standard size. Some cells of the grid contain a circle, called island, with a number inside it ranging from one to eight. The remaining positions of the grid are empty. The player must connect all of the islands by drawing a series of horizontal or vertical bridges between them, respecting a series of rules: the number of bridges incident to an island equals the number indicated in the circle, at most two bridges are incident to any side of an island, bridges cannot cross each other or pass through islands, and each island must eventually be reachable from any other island. In this paper, we present some complexity results and relationships between Hashi and well-known graph theory problems. We give a formulation of the problem by means of an integer linear mathematical programming model, and apply a branch-and-cut algorithm to solve the model in which connectivity constraints are dynamically generated. We also develop a puzzle generator. Our experiments on 1440 Hashi puzzles show that the algorithm can consistently solve hard puzzles with up to 400 islands.
BibTeX
@misc{coelho2019benchmark,
  author = {Leandro C. Coelho and Gilbert Laporte and Arinei Lindbeck and Thibaut Vidal},
  title = {{Benchmark Instances and Branch-and-Cut Algorithm for the Hashiwokakero Puzzle}},
  year = {2019},
  eprint = {1905.00973},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.00973},
}
Figure