Hashiwokakero is a type of logic puzzle

Logic puzzle

A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...

 published by Nikoli

Nikoli

Nikoli Co., Ltd. is a Japanese publisher that specializes in games and, especially, logic puzzles. Nikoli is also the nickname of a quarterly magazine issued by the company...

. It has also been published in English under the name Bridges or Chopsticks (an understandably mistaken translation; the hashi of the title, 橋, means bridge; hashi written with another character, 箸, means chopsticks). It has also appeared in The Times

The Times

The Times is a British daily national newspaper, first published in London in 1785 under the title The Daily Universal Register . The Times and its sister paper The Sunday Times are published by Times Newspapers Limited, a subsidiary since 1981 of News International...

under the name Hashi. In France

France

The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...

, Denmark

Denmark

Denmark is a Scandinavian country in Northern Europe. The countries of Denmark and Greenland, as well as the Faroe Islands, constitute the Kingdom of Denmark . It is the southernmost of the Nordic countries, southwest of Sweden and south of Norway, and bordered to the south by Germany. Denmark...

, the Netherlands

Netherlands

The Netherlands is a constituent country of the Kingdom of the Netherlands, located mainly in North-West Europe and with several islands in the Caribbean. Mainland Netherlands borders the North Sea to the north and west, Belgium to the south, and Germany to the east, and shares maritime borders...

, and Belgium

Belgium

Belgium , officially the Kingdom of Belgium, is a federal state in Western Europe. It is a founding member of the European Union and hosts the EU's headquarters, and those of several other major international organisations such as NATO.Belgium is also a member of, or affiliated to, many...

 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 perpendicular
  Perpendicular
  In geometry, two lines or planes are considered perpendicular to each other if they form congruent adjacent angles . The term may be used as a noun or adjective...
  
  ly.
• 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

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. Obviously, 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 islands whose bridge quota has been reached. In addition to reducing mistakes, this can also help locate potential "short circuits": keeping in mind that all islands must be connected by one network of bridges, a bridge that would create a closed network that no further bridges could be added to can only be permitted if it immediately yields the solution to the complete puzzle. The simplest example of this is two islands showing '1' aligned with each other; unless they are the only two islands in the puzzle, they cannot be connected by a bridge, as that would complete a network that cannot be added to, and would therefore force those two islands to be unreachable by any others.

There is a solution using integer linear programming in the MathProg examples included in GLPK.

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).