Results 1 to 2 of 2

Math Help - Solitaire Battleship (Tricky/Fun problem)

  1. #1
    Newbie
    Joined
    Aug 2009
    From
    Melbourne
    Posts
    11

    Solitaire Battleship (Tricky/Fun problem)

    Came across this problem and I can't figure it out. Wanted to see if anyone else could.

    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.

    I'm trying to 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/f...es/smith06.pdf

    and

    Battleships techniques

    and the attached pdf file.
    Hope you have better luck than I. I'm .
    Attached Thumbnails Attached Thumbnails Solitaire Battleship (Tricky/Fun problem)-challengeproblem.jpg  
    Attached Files Attached Files
    Last edited by JavaJunkie; June 3rd 2010 at 03:04 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2009
    From
    Melbourne
    Posts
    11
    I still haven't been able to solve this one. But, I am making a little progress with the IP version.....


    So we can let X_{i,j} = 1 or 0 where 0 denotes a water square and 1 denoting a battleship of some kind for all i, j \in N where N= 1,2,...,7.

    X_{i,j} is our decision variable.

    Let A[n] be the number of ship parts in row n.
    Let B[n] be the number of ship parts in column n.

    Subject to constraints:

    (1) X_{1,4} = 0 (see picture)

    (2)  X_{7,5} = 1 (see picture)

    (3) \sum_j^N X_{i,j} = A(i) \ \ \forall i \in N i.e. for each row, the sum of all values in each row must equal the number of ship parts in row i.

    (4) \sum_j^N X_{j,i} = B(i) \ \ \forall i \in N i.e. Same as above but for columns.


    Now I can solve this model, but I still need to model two more things:

    (a) I need to somehow include the ship types and ensure the right number of ship types are included in the solution and;

    (b) Ensure that no battleship touches any other battleship, even diagonally.

    Can anyone please help me add these into the model?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Clock Solitaire
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 18th 2010, 05:08 AM
  2. Battleship Problem
    Posted in the Business Math Forum
    Replies: 2
    Last Post: December 3rd 2008, 10:42 PM
  3. Replies: 6
    Last Post: March 30th 2008, 10:39 AM
  4. Solitaire problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: September 26th 2007, 05:13 AM
  5. tricky problem please HELP
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 27th 2006, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum