Battleship (puzzle)

The Battleship puzzle (sometimes called Solitaire Battleships or Battleship Solitaire) is a logic puzzle based on the Battleship guessing game. It and its many variants often appear in puzzle contests, such as the WPC, and puzzle magazines, such as "Games" magazine.

The puzzle is played in a grid of squares in which ships of different sizes are hidden. Numbers alongside the grid indicate how many squares in a row or column are occupied by part of a ship.

Description

An armada of battleships is located in a square grid of 10×10 small squares. There is one battleship of four squares, two cruisers of three squares, three destroyers of two squares, and four submarines of one square. Each ship occupies a number of contiguous squares on the grid, arranged either horizontally or vertically. The boats are placed so that no boat touches any other boat, not even diagonally.

The goal of the puzzle is to discover where the ships are located. To solve it, one is given various clues. The clues are of two forms. Firstly, one can be told, for particular squares in the grid, whether each square contains a submarine, a longer ship (and whether it is the north, south, east, west, or middle of a ship), or water (meaning no ship). Secondly, one can be told, for a row or column of the grid, how many squares are occupied by ships.

Variants have included using larger or smaller grids (with comparable increases in the size of the armada to be found), as well as using a hexagonal grid.

Battleship is an NP-complete problem. [Sevenster, M. 2004, ' [http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf Battleships as Decision Problem] ', "ICGA Journal" [Electronic] , Vol. 27, No. 3, pp.142-149. ISSN 1389-6911. Accessed: September 5 2007]

History

The solitaire version of Battleship was invented in Argentina in 1982 under the name Batalla Naval, with the first published puzzles appearing in 1982 in the Spanish magazine Humor & Juegos. Battlehip was created by Jaime Poniachik, founder of Humor & Juegos, and Eduardo Abel Gimenez, Jorge Varlotta, and Daniel Samoilovich, who were editors of the magazine.

After 1982, no more Battleship puzzles were published until five years later in 1987, when Battleship puzzles were published in Juegos Para Gente De Mente, a renamed version of Humor & Juegos. The publishing company of Juegos Para Gente de Mente regularly publishes Battleship puzzles in its monthly magazine Enigmas Lógicos.

Battleship made its international debut at the first World Puzzle Championship in New York in 1992 and was an instant success. It was published in Games magazine in 1993.

Since the World Puzzle Championship in 1993, many variants of Battleship have been developed. [http://www.conceptispuzzles.com/index.aspx?uri=puzzle/battleships/history]

References

External links

* [http://www.mountainvistasoft.com/omnibus.htm The Battleship Omnibus] - Extensive information on variants, competitions, and strategies.