Abstract
Integer programming refers to the task of assigning integer values to variables in order to optimize a linear function while satisfying a set of linear constraints. A particular subset of integer programming, 0-1 integer programming, restricts all variables to having a value of one or zero, where a value of one represents when an affirmative decision is made, and a value of zero represents when a non-affirmative decision is made. This subset of integer programming is particularly useful for solving puzzles, which (by nature) revolve around two decisions---whether to place/include something or not. In this report, we use 0-1 integer programming to formulate and solve a version of the Battleship puzzle, which is a pencil-and-paper adaptation of the classic two-person game. Furthermore, we introduce an objective function that allows us to check whether or not a given puzzle has a unique solution
Advisor
Pierce, Pam
Department
Mathematics
Recommended Citation
Koenig, William, "A Discussion of Integer Programming and its Application to the Battleship Puzzle" (2018). Senior Independent Study Theses. Paper 12838.
https://openworks.wooster.edu/independentstudy/12838
Disciplines
Applied Mathematics | Mathematics
Keywords
Linear Programming, Integer Programming, Battleship Puzzle, Solitaire Battleships, Optimization
Publication Date
2018
Degree Granted
Bachelor of Arts
Document Type
Senior Independent Study Thesis
© Copyright 2018 William Koenig