Solitaire Battleship (Tricky/Fun problem)

Decision and strategy, simulations and probability models, card and board games, ...
Post Reply
Javajunkie
Posts: 1
Joined: Tue Jun 01, 2010 8:16 am
Location: Melbourne, Australia

Solitaire Battleship (Tricky/Fun problem)

Post by Javajunkie » Tue Jun 01, 2010 8:21 am

ChallengeProblem.jpg
ChallengeProblem.jpg (35.46 KiB) Viewed 5869 times
Solitaire Battleships is a puzzle related to the two player game of battleships. In the solitaire version a grid is given with row and column totals indicating the number of ship segments that exist in each row and column. A number of hint squares are also revealed. These hint squares will show either:
• Water
• A whole submarine (single unit vessel)
• An end of a vessel
• The middle segment of a vessel (only cruisers in the 7x7 problem (see image))

In a legal battleship configuration, no battleship touches any other battleship, even diagonally.The totality of the input is row and column sums, number of each type of vessel and hints.

Formulate solitaire battleships as both an Integer Programming problem and a constraint programming problem (obviously the IP formulation is also a valid CP formulation so not the same for either).

I have solved a number of LP, IP, and CP problems before in my field of work - but nothing this complicated.


Some helpful links I've been using:
http://www.cs.umbc.edu/courses/671/fall ... mith06.pdf
and

http://www.conceptispuzzles.com/index.a ... techniques

another useful pdf can be found here:
http://www.mathhelpforum.com/math-help/ ... oblem.html

Post Reply