This dissertation compares Cell-based and Ship-based Integer Linear Programming formulations for solving the NP-Complete Battleship Solitaire puzzle. A Python and Gurobi benchmark across grids up to 30×30 isolates matrix density, not search-tree depth, as the dominant performance factor.