Puzzle—Solving the Battleship Puzzle as an Integer Programming Problem

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.