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
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.
Download the PDF
Click below to download the PDF of this paper. If you do not have Adobe Reader, click here to download the latest version.
Supplementary Material
Citation Information
Meuffels, W. J. M., D. de Hertog. 2010. Puzzle—Solving the Battleship puzzle as an integer programming problem. INFORMS Trans. Ed. 10(3) 156-162.
DOI: 10.1287/ited.1100.0047