I first saw Solitaire Battleships (also known as “Fathom It!”) many years ago about in a puzzle book<\/a>, but it recently became available on Conceptis Puzzles<\/a> too, which was the trigger for this article.<\/p>\n Here’s an online implementation<\/a>, with rules, to explore.<\/p>\n Four years ago, I took on Solitaire Battleships as another puzzle<\/a> to solve.<\/p>\n My approach Solitaire Battleships was a precursor to my very similar approaches to Sudoku<\/a>, Nonograms<\/a> and Kakuro. <\/p>\n Each cell on the grid was represented by an object that maintained a list of possible values it could take (e.g. water, submarine, stern of a vertical battleship), and, when triggered, would compare its list for compatibility with its neighbours, reducing the list until the final solution for that cell was found.<\/p>\n Meanwhile, for each row and column was represented by a Line object which would hold the clue that represented the number of ship segments. When triggered, it would compare its clue to the count of ship objects and unsolved cells. It would detect if the remaining unsolved cells were all ships or all water, and inform the corresponding cells appropriately.<\/p>\n Finally, a Fleet object would track the number of cells that contained, or might contain<\/em> the sterns of each ship type. If the number of definite frigate sterns (for example) equaled the number of frigates in the the fleet, the other “maybe” cells were told that they weren’t frigate sterns. If the number of definite + maybe frigate sterns equalled the number of frigates, the “maybe” cell were told that they definitely were frigate sterns.<\/p>\n Like my half-completed Sudoku solution three years later, my implementation of these simple rules didn’t completely solve any but the simplest of Solitaire Battleship puzzles. I hadn’t implemented back-tracking as I don’t see the point<\/a>.<\/p>\n I had expected this, and I structured the system as an aide to human solving. The human could enter a statement about a particular cell, and the system would reapply the constraints until it could solve no more, and then present the new state of the board, for the human to make the next pronouncement.<\/p>\n Like Sudoku, it was around about this point in the process that I found out that Solitaire Battleships is NP-complete<\/a>. The linked paper discusses how this result appears surprising because solving commercially published Solitaire Battleships doesn’t appear<\/em> to involve guesswork. The authors shows how the puzzles published in newspapers are generated by working backwards from a solution in such a way that simple “human” logic can solve it.<\/p>\n This seems to be a similar result to finding Sudoku is NP-complete<\/a>, which seems somewhat<\/a> controversial<\/a> amongst<\/a> people who point out that they never backtrack in solving the ones that they see.<\/p>\n","protected":false},"excerpt":{"rendered":" My approach Solitaire Battleships was a precursor to my very similar approaches to Sudoku<\/a>, Nonograms<\/a> and Kakuro. <\/p>\n The result seems to be similar to finding Sudoku is NP-complete<\/a>, which seems somewhat<\/a> controversial<\/a> amongst<\/a> people who point out that they never backtrack in solving the ones that they see.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"","footnotes":""},"categories":[33,34],"tags":[263,55,54],"class_list":["post-298","post","type-post","status-publish","format-standard","hentry","category-puzzle-solving","category-software-development","tag-computational-complexity","tag-puzzle","tag-solution"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/298","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=298"}],"version-history":[{"count":0,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/298\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=298"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=298"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=298"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}My Approach<\/h3>\n
The Result<\/h3>\n
NP-Completeness<\/h3>\n