Bridges game

I’ve spent a few morning train trips lately making another puzzle game:

It’s based on Hashiwokakero. The puzzles used to appear in Salient, when I was at VUW.

The initial state of the game is a board with numbered vertices on it. The player’s task is to draw “bridges” between vertices, so that each vertex of value N has exactly N bridges connecting to it. You can have up to two bridges between any pair, but bridges cannot cross. And all vertices should be connected into a single component.

The board is generated as a tree. It starts as a single seed vertex. Then, a random existing vertex, a random angle, and a random distance from the vertex are chosen; if it is possible to build a bridge to a new vertex there, it is added to a tree. Finally after enough vertices have been added or it is impossible to add new ones, all the bridges are erased, leaving disconnected vertices.

Possible bridges under the current mouse position are highlighted. The player clicks to add a bridge or to erase bridges (if two already exist there). The build direction alternates between horizontal and vertical, so multiple clicks may be required to build the intended bridge.

There is no AI player yet. When playing the game we invent and test strategies and rules. It is hard not to think of how they could be implemented in a computer. As with the previous network puzzle, there are local rules, global rules, and non-deterministic rules.

Local rules only require knowledge from within a finite radius: regardless of how complicated the board is, there is a simple algorithm to determine whether it is safe to apply a rule to a given point. In the network game, local rules were heuristics applied at the cell level, e.g. “if there is a corner edge in this cell, and one side is necessary, then the opposite side is impossible.” In this game, there are several local rules applied when I play: “two 2-vertices cannot have a double bridge between them” and “a 6/7/8-vertex with a 1-vertex neighbour must have bridges to its other vertices.” Information about local rules can lead to a global solution, because local areas can overlap. The solution to a local area can provide information useful in solving its neighbours.

Global rules are harder, but are sometimes needed to solve a game. In the network game, there was additional information in the form of liveness and deadness. These relied in an assumption of acyclic connectedness for the whole puzzle. If a cell has exactly one live neighbour, then it must connect to it. The cell then becomes live to its neighbours.

A non-deterministic strategy amounts to: making a guess, and seeing if it leads to a contradiction; if it does, undo the guess and try something else. This applies recursively. This algorithm can be tricky to implement in imperative languages, but it is also easy to abstract. It relies in having a) a variety of possible guesses it can make, and b) tests for whether the game is solved and/or a guess is proved incorrect. Given these it can attempt a brute force trial-and-error solution to the puzzle.

It was fun and easy to make. As usual, I’ve implemented the 90% to get it functional and run out of ideas for the 10% extra required to make it fun to play! The source is on Google Code.