Bridges AKA Hashi is now available for iPhone/iPad

Bridges AKA Hashi

This Java applet generates Hashi boards and provides an interface to allow the user to fill in the generated boards. It includes real-time validation of the user's progress towards solving the puzzle. A specification can be found below explaining how this applet generates boards and describing how the iPhone version will provide three difficulty levels as well as the different board sizes offered by this applet.

Rules

  • Each island is connected to one or more islands
  • Islands are connected with either one or two bridges
  • The number written on each bridge is the total number of bridges it has in all directions
  • Bridges can only be orthogonal (horizontal or vertical)
  • Bridges may not cross eachother
  • Add a bridge by left-clicking on an island and dragging to the island to connect to
  • Remove a bridge by right-clicking on an island and dragging to the island where the bridge ends
  • It must be possible to travel from any island to any other island
  • The game is won when all islands have been given their required number of bridges
Your browser understands the <APPLET> tag but isn't running the applet, for some reason. Your browser is ignoring the <APPLET> tag!

Java Source Code

Complete source (zipped, 6kb)

This applet was created using the BlueJ IDE - a Java development environment designed for use in educational establishments to teach object-oriented programming.

Specification

Parameters for the Board

The board will be a user-defined width and height. The board will contain islands which are all connected by bridges, i.e. it wil be possible to travel from any island to any other island by following a route consisting solely of islands and bridges. The density of these islands across the board will depend on the difficulty level. The average number of bridges per island will be higher on the hardest difficulty level than on other levels.

Representing the Board

The board is stored as a 2-D array of integers. The width and height of the array are the width and height chosen by the user for the board size. Each element in the array holds the number of bridges linked to the island in that square (or zero if there is not an island in that square).

Generating the Board

A random starting square is chosen by picking two psuedo-random numbers to use as co-ordinates. The x-co-ordinate will be between zero and (the width of the board minus one); the y-co-ordinate will be between zero and (the height of the board minus one) since the first element of an array is element zero in Java.

From this island (and every subsequently created island) exactly one attempt will be made to add bridges in each orthogonal (i.e. horizontal or vertical) direction. An attempt to add a bridge will fail if:

  • the next square in that direction is occupied by another bridge;
  • travelling two squares in that direction would go over the edge of the board (this only results in failure if the board has a defined edge on that axis, so does not affect all directions on a cylinder or torus);
  • (easy and normal only) another island would be reached by travelling less than four squares in that direction. On the "hard" difficulty bridges may be created which join the current island with an existing island, resulting in a higher average number of bridges per island than the lower difficulty levels.
During the generation of the board a record will be kept of which squares are not empty (i.e. conatin an island or bridge). For each island created a record wil be kept of which directions attempts have been made to add bridges in to ensure that for each island each direction is tried exactly once. These records will be discarded once the board has been generated.

The length of the bridge will depend on the difficulty level. Each bridge must be a minimum of one square long. Once it has been determined that the bridge can be this minimum length it will be extended one square at a time until any of the following occur:

  • the edge of the board is reached
  • (easy and normal only) extending the bridge would make it adjacent to an existing island
  • a psudeo-random number generator determines that the bridge should not be extended any further. The chance of this occurring depends on the difficulty level. A random number between zero and n is calculated using Java's Math.random() function. If the number equals zero then the bridge will not be extended any further. The higher the difficulty level, the lower the value of n. This will result in a greater density of islands on higher difficulty levels.
Once the length of the bridge has been determined a random number between one and two will be calculated. Based on its value either one of two bridges will be created between the current island and an island whose distance from the current one is (the length of the bridge plus one) squares. If this island does not exist then it will be created and attempts will be made to travel in all orthogonal directions from it. If it does exist then attempts will continue from the current island. Once attempts to travel in all four directions have been attempts will resume from the previous island to be created. This process is repeated until attempts have been made in all four directions from the starting island. Internally, the program will maintain a "stack" of islands to attempt to add bridges to. The first island on the stack will be the randomly-located starting island. Each element on the stack will hold the location of that island and a list of directions that attempts to add bridges have already been made in (the DirectionsTest.java class). The following psuedo-code snippet illustrates this:
LinkedList<DirectionsTested> islandsUnderConstruction =
    new LinkedList<DirectionsTested>(); islandsUnderConstruction.add(new DirectionsTested()); while(!islandsUnderConstruction.isEmpty()) { // Get the last element on the stack DirectionsTested currentIsland = islandsUnderConstruction.getLast(); // Pick a random untried direction for it int chosenDirection = currentIsland.randomUntriedDirection(); if (chosenDirection == DirectionsTested.NONE) { islandsUnderConstruction.removeLast(); continue; } // Attempt to add an island in this direction if(<can add a bridge in this direction>) { // add it to the board ... // add it to the stack if(<adding new island>) { islandsUnderConstruction.add(<the new island>); } } }

Known Bugs in Java Applet

  • Number of required bridges text is not drawn in the vertical centre for board sizes 5 x 5 and 30 x 30
  • If there is more than one possible solution then the game only accepts the one created when the puzzle was generated

Planned Enhancements for iPhone Version

  • Different background colours for islands based on their number of outstanding bridges
  • Animations/sounds to indicated when an island has been given the correct number of bridges
  • Three difficulty levels, as described in the specification above