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:
- Each island must have a specific number of incident bridges equal to its number.
- Bridges cannot cross each other.
- The final network must be a single connected component.
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.
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