Battleship (puzzle)

From Wikipedia, the free encyclopedia

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.

[edit] 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. ^[1]

[edit] References

^ Sevenster, M. 2004, 'Battleships as Decision Problem', ICGA Journal [Electronic], Vol. 27, No. 3, pp.142-149. ISSN 1389-6911. Accessed: September 5, 2007