Fathom It! icon

Battleship Omnibus

 

On this page you'll find a comprehensive collection of everything related to the Fathom It! / Battleships concept, including board analyses and links to related sites.


"Thanks for providing this resource...it's fun seeing other people's thoughts on a mutually shared interest, especially a puzzle like the Battleship solitaire puzzles."

Peter Duniho (e-mail dated May 2004)

Battleship Variations (VERY interesting!)

Lots of mind-expanding variations on the classic Battleships.

Fathom It! Board Analyses

Here you'll find in-depth analyses of boards found in Fathom It!'s board database.

1999 US/Canadian Puzzle Team Qualifying Test

Puzzles #17 and #18 are 9x9 Battleship puzzles. The solutions are also provided. As a bonus, Matthew Daly provides his analyses of the two puzzles.

The puzzle and solutions for each can be found at:
#17: puzzle / solution / Matthew Daly's analysis
#18: puzzle / solution / Matthew Daly's analysis

The 1999 World Puzzle Championship Test

Includes classic battleship puzzles and 4 variations (e.g., combination of the Battleships and the Minesweeper puzzles).  View the Battleship puzzles here.

The 2000 World Puzzle Championship Test

To see the test, download the Adobe PDF version.

Puzzle #6 is a 10x10 Battleships puzzle.
Puzzle #17 is a very interesting variation using dice pips.
Puzzle #20 is a challenging Digital Battleships variation.

Matthew Daly provides his analyses of the puzzles.

The puzzle and solutions for each can be found at:
#6: puzzle / Matthew Daly's analysis
#17: puzzle / Matthew Daly's analysis
#20: puzzle / Matthew Daly's analysis

The 2001 US/Canadian Qualifying Test

To see the test, download the Adobe PDF version.

Puzzle #8 is a Classic 10x10 Battleships puzzle (Moshe Rubin).
Puzzle #12 is a Digital Battleships puzzle (Moshe Rubin).
Puzzle #19 is a Retrograde Battleships puzzle (Erich Friedman).

The 2002 US/Canada/Finland Team Qualifying Test

Here's the Adobe PDF version. The password to open the document is "wbloF7eldw". It contains three Battleship-type puzzles: a classic (standard) one, a "T It Up" Battleship variant, and a Path Battleship variant.

Analyses of past Battleships columns in "GAMES Magazine" and "World of Puzzles"

For those of you with back issues of GAMES or World of Puzzles, you'll find analyses of previous columns. So pull out those old issues and try your Battleships skills.

Wei-Hwa's Solitaire Battleships Times, and some Battleships Strategies

Wei-Hwa Huang, four-time winner of the World Puzzle Championships, timed himself while solving all 108 Battleships problems in Peter Gordon and Mike Shenks book, "Solitaire Battleships: 108 Challenging Logic Puzzles". His summary makes fascinating reading.

"The Well-Posed Puzzle"

An attempt to analyze a class of puzzles (including Fathom It!-like Battleship puzzles). Here's a quote from the monograph:

    "I'd like to consider a few classes of puzzles that have the feature that there are many puzzles describable in a single framework, but that some of the descriptions don't make sense, or describe puzzles that can't be uniquely solved.

    "I would then like to consider the new puzzle of whether we can know which of the puzzles are uniquely solvable. If we can answer this question, then theoretically, we could crank out hundreds of puzzles."

A monograph entitled "Minesweeper and the "P=NP?" question: a short FAQ"

Within the article, discusses Battleships:

    "One correspondent asked me about battleships. As I understand "battleships", the question concerns whether it is possible to place a collection of "ships" on a square grid avoiding certain squares which have already been tested and found to be vacant. It is clearly in NP, and also contains the bin-packing problem as a special case, so is also NP-complete."

Minesweeper and the P=NP question

An interesting site, even if not directly connected to Fathom It! puzzles. Here's a quote from the :

    What I managed to prove is that the minesweeper game is essentially equivalent in complexity to any of a wide range of known natural and important problems in the literature called NP-complete problems.
Article entitled "Battleships as Decision Problem" (published in ICGA Journal, September 2004) This article, authored by Merlijn Sevenster and published in the September 2004 issue of ICGA (International Computer Games Association) Journal, is a commendable attempt to show that solving Battleship puzzles is NP-hard.  Here's the abstract:

We define the well-known puzzle of Battleships as a decision problem and prove it to be NPcomplete, by means of a parsimonious reduction. By applying Valiant and Vazirani’s (1986) result we immediately obtain that the variant of this problem, viz. promising that there is a unique solution, is NP-complete as well, under randomized reductions. As this finding is in sheer contrast with the general experience of Battleship puzzles being well playable (i.e., effectively solvable), we arrive at a hypothetical explanation for this state of affairs.

Cached files: 1

Article: "Explain P = NP problem to 10 year old"Excellent set of slides by Geoffrey De Smet explaining why the bin packing problem is so difficult to solve.

Bob Abrahamian's final project for CS 205 (Department of Computer Science, University of Chicago) entitled "Playing Battleship Puzzles" (Link is currently BROKEN, awaiting response from University of Chicago)

Quote from the paper:

    For my final project, I wanted to write a computer program that solved the puzzle "battleship" that appears in GAMES magazine.

The LISP source files can be accessed here and here.

Paper (in PDF format) entitled "Satisfiability Encodings (04)",

There is also an HTML on-line version of the paper.

From Michael L. Littman's course in Numeric Artificial Intelligence at Duke University. Discusses solving Battleship puzzles using satisfiability (SAT) methods.

A description of the Battleships puzzle genre on the Everything2.net website.

The Everything2.net website is a very complex online community with a focus to write, publish and edit a quality database of information, art and humor.

Other Internet sites related to Battleships logical puzzles

You may want to use AltaVista's BabelFish on-line translation service to translate these pages.
Marcelo Inglesias's puzzle blog "Acertijos y pequeños enigmas" carries many delightful Battleship puzzles, both classic and variants (Marcelo admits that Battleship puzzles are his favorites).  To date he has presented the following Battleship variants:

The JuegosDeIngenio.org site carries a guest article of Marcelo's together with an Either/Or Battleships puzzle of his creation.

Here's a picture of Marcelo Inglesias (taken from JuegosDeIngenio.org):

You may want to use AltaVista's BabelFish on-line translation service to translate pages on his site.

Yoogi Logic Software offers "Hexip", a Windows adaptation of Hexagonal Battleships.

I flatter myself that Hexip was inspired, and takes most of its interface and features, from Fathom It!.

By all means, download a copy and play it. The author did a nice job implementing the features. In my opinion, however, the Hexip solver does not relate to the fascinating techniques for solving Hexagonal Battleship puzzles as expounded in Gavin Stark's monumental analysis in September 1999 issue of GAMES Magazine.

Nonetheless, if you enjoy Fathom It!'s Standard Battleship puzzles, you'll enjoy Hexip.

Takahiko Saito's interactive "BtlSez32" Windows program. Takahiko Saito offers his "BtlSez32" Windows program for setting up custom Battleship puzzles and solving them interactively.  His puzzle website offers many types of puzzles, including Battleship puzzles.

Here's a partial list of BtlSez32 features:

  • interactively set up custom Battleship puzzles
  • solve any custom Battleship puzzle
  • undo moves
  • save the board to disk (including the move history, allowing undoing moves when board is resumed)
  • Print board, including print preview

Summary: This is obviously a work of love and a positive step in helping puzzlers enjoy Battleship puzzles.

Dark Chrome Software offers "Battleship Sudoku", a Windows adaptation of Solitaire Battleships. A recent entry into the Solitaire Battleships market, this program has nothing to do with Sudoku but everything to do with Solitaire Battleships.
Constraint Programming and Battleship puzzles Constraint programming is a programming paradigm in which a set of constraints that a solution must meet are specified rather than set of steps to obtain such a solution.  It can be used for solving Battleship puzzles.
LEGUP: Logic Engine for Grid-Using Puzzles

LEGUP (Logic Engine for Grid-Using Puzzles) is an Undergraduate Research Project under Dr. Bram van Heuveln in the department of Cognitive Science. It is under the greater classification of "Visual Logic", as it is a system of logic that is based purely on applying rules to objects visual in nature.

From the LEGUP web site:

Objectives

To research and categorize various grid-based logic puzzles, with the intention of creating a formal system of "grid logic" applicable to various puzzles of different formats. To do this, several well-known logical puzzles will be studied, and the commonalities between them will be used as the framework for a system that can be used to represent them.

The end result of this research will be a single application that will be capable of representing many of these grid-based logical puzzles. This application would utilize a dynamic "grid-based logical engine", with programmable "modules" that allowed the introduction or modification of puzzles on the fly.

Such an application would be very useful in the field of education, as children and adults alike could be taught the basics of formal logic while seemingly playing a game. Through manipulating the objects in the puzzle and attempting to win, users will be constructing logical proofs.

As I understand it, the project hopes to create a logical solver for a host of puzzles including Battleships.  Check out the Battleship PowerPoint file listing numerous rules for solving Battleship puzzles.  To date, all the rules found there are taken from the Fathom It! documentation and solver.  It will be interesting to see if they discover new solving rules.

Cached files: 1 2

"Problem solving in ID-logic with aggregates: some experiments" (Authors: Van Nuffelen, Bert; Denecker, Marc)

In this paper the authors attempt to design an expressive logic, suitable for declarative knowledge representation.  One of the experimental problems they use in testing their work is Solitaire Battleships.  The authors define the problem in declarative terms.

Quoting the abstract from the paper: 

The goal of the LP+ project at the K.U.Leuven is to design an expressive logic, suitable for declarative knowledge representation, and to develop intelligent systems based on Logic Programming technology for solving computational problems using the declarative specifications. The ID-logic is an integration of typed classical logic and a definition logic. Different abductive solvers for this language are being developed. This paper is a report of the integration of high order aggregates into ID-logic and the consequences on the solver SLDNFA.

The paper can be accessed here or here.

Constraint Programming Models for Solitaire Battleships
Barbara M. Smith
Cork Constraint Computation Centre, University College Cork, Ireland
Quoting the abstract from the paper:

The Solitaire Battleships puzzle is described, and a range of constraint programming models are presented. The aim in building these models was to solve difficult instances of the puzzle from CSPLib, without resorting to searching for the solution. These are instances that existing rule-based software for Solitaire Battleships, Fathom It!, cannot solve. The puzzle is quite a challenge to model successfully using CP; a basic model is presented that requires some search even for easy instances. The search effort is much reduced by using regular constraints, at the expense of an increase in run-time. Finally, some of the CSPLib instances have been successfully solved without search, by using shaving. Since Fathom It! already does something very like shaving, this seems a promising route to solving a greater range of instances.

The paper can be accessed here or here.

Puzzle-Solving the Battleship Puzzle as an Integer Programming Problem

W. J. M. Meuffels
Tilburg University, 5000 LE Tilburg, The Netherlands, and ORTEC, 2800 AL Gouda, The Netherlands, ineke.meuffels@ortec.com

D. den Hertog
Tilburg University, 5000 LE Tilburg, The Netherlands, d.denHertog@uvt.nl
Quoting the paper's abstract:

One’s aim in solving logical puzzles is to find the solution by making use of several clues and restrictions. In this paper, we solve a logical puzzle, the Battleship puzzle, by integer programming. Moreover, two integer programming models (i.e., a cell-based model and a ship-based model) for the Battleship puzzle are compared based on their complexity and solution times. The ship-based model requires more preprocessing work before running the integer program than the cell-based model, but strongly outperforms the latter one. Finally, the models are used to check if a puzzle contains redundant information and to create a puzzle with a unique solution.

The paper can be access here, and sample code (written in the AIMMS programming language) can be downloaded from here (material is cached here)
Discussion about "false" NxN Battleship puzzles (from the now defunct bbcmindgames.com puzzle forums) A question I've considered over the years is" are "false" 10x10 Battleship puzzles considered 10x10 puzzles?  A "false 10x10" puzzle is a Battleship puzzle that has 10 rows and 10 columns, but where one or more rows/columns could be removed without changing the puzzle.

Here's an example:

Notice the two rows and one column with zero counts on the extremities of the board.  This puzzle has 10 rows and columns but is really an 8x9 puzzle:

The thread contains the question and several replies.

Niels Roest (member of the Dutch team at the World Puzzle Championship) wearing a Battleship T-shirt. I came across this photo while perusing a page on the Japanese Puzzle Championship site.  The page highlighted the backs of several contestants' T-shirts, including Niels Roest's Battleship-themed T-shirt sponsored by Puzzlesport worn at the 15th WPC in Borovets, Bulgaria.
The CYBIRD Group (Japan) advertised playing Battleship puzzles on cell-phones back in 2001. The Japanese mobile-phone company CYBIRD advertised a service for solving Battleship puzzles on mobile phones back in 2001.  Here's the page in Japanese and the same page translated into English.

Note that the puzzle above is identical to the puzzle on the front cover of Sekaibunka's "Battleships #1" puzzle book:

How to handcraft your own Battleship puzzles (Mike Selinker's and Thomas Snyder's "PuzzleCraft #48: Battleships" column in GAMES Magazine, February 2009).Tom Selinker has a wonderful ongoing series of articles in GAMES Magazine entitled "PuzzleCraft", describing how to create your own homespun versions of popular puzzles including crosswords (#5 - #7), quote boxes (#9), logic puzzles (#10 - #11), diagramless crosswords (#14), Sudoku (#18), Kakuro (#27), Solitaire Hangman (#31), and many more.  In the February 2009 issue he tackles the task of creating Battleship puzzles by hand.

Here is a set of four handcrafted Battleship puzzles, and here is a detailed explanation of how to create Battleship puzzles.


This page last modified on: 27 April 2012