Portal de Periódicos da CAPES

Puzzle —Solving the Battleship Puzzle as an Integer Programming Problem

2010; Institute for Operations Research and the Management Sciences; Volume: 10; Issue: 3 Linguagem: Inglês

10.1287/ited.1100.0047

1532-0545

W.J.M. Meuffels, Dick den Hertog,

AI-based Problem Solving and Planning

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.