Hashiwokakero (橋をかけろ Hashi o kakero; lit. "build bridges!") is a type of logic puzzle published by Nikoli. It has also been published in English under the name Bridges or Chopsticks (based on a mistranslation: the hashi of the title, 橋, means bridge; hashi written with another character, 箸, means chopsticks). It has also appeared in The Times under the name Hashi. In France, Denmark, the Netherlands, and Belgium it is published under the name Ai-Ki-Ai.

Rules

Hashiwokakero is played on a rectangular grid with no standard size, although the grid itself is not usually drawn. Some cells start out with (usually encircled) numbers from 1 to 8 inclusive; these are the "islands". The rest of the cells are empty.

The goal is to connect all of the islands by drawing a series of bridges between the islands. The bridges must follow certain criteria:

  • They must begin and end at distinct islands, travelling a straight line in between.
  • They must not cross any other bridges or islands.
  • They may only run orthogonally (i.e. they may not run diagonally).
  • At most two bridges connect a pair of islands.
  • The number of bridges connected to each island must match the number on that island.
  • The bridges must connect the islands into a single connected group.

Solution methods

thumb|right|200px|Moderately difficult Hashiwokakero puzzle ([[Media:Bridges-answer.png|solution)]]

Solving a Hashiwokakero puzzle is a matter of procedural force: having determined where a bridge must be placed, placing it there can eliminate other possible places for bridges, forcing the placement of another bridge, and so on.

An island showing '3' in a corner, '5' along the outside edge, or '7' anywhere must have at least one bridge radiating from it in each valid direction, for if one direction did not have a bridge, even if all other directions sported two bridges, not enough will have been placed. A '4' in a corner, '6' along the border, or '8' anywhere must have two bridges in each direction. This can be generalized as added bridges obstruct routes: a '3' that can only be travelled from vertically must have at least one bridge each for up and down, for example.

It is common practice to cross off or fill in islands whose bridge quota has been reached. There is a solution using integer linear programming in the MathProg examples included in GLPK. A library of puzzles counting up to 400 islands as well as integer linear programming results are also reported.

History

Hashiwokakero first appeared in Puzzle Communication Nikoli in issue #31 (September 1990), although an earlier form of the puzzle appeared in issue #28 (December 1989).

See also

  • List of Nikoli puzzle types

References

  • Nikoli's English page on Hashiwokakero