Description
Overview
In this assignment you will be creating a CSP solver for the domain of Battleship
Solitaire puzzles. This will require you to encode these puzzles as a constraint
satisfaction problem (CSP), implement the CSP solver, and use that to solve the
puzzles we provide.
Background
Battleship Solitaire (which also goes by other names) is a game played on a square
NxN grid that contains ships of different sizes and sections of open water, similar to
the Battleship board game Links to an external site.. Unlike the board game (which is
meant to be played against another player), Battleship Solitaire shows the number of
occupied squares in each row and column, from which you’re meant to determine the
location of each ship (see Figure 1, at right).
To aid with this, these puzzles observe the following rules:
1. There are four types of ships in these puzzles, each of which occupies a
specific number of squares:
o Submarines (1×1)
o Destroyers (1×2)
o Cruisers (1×3)
o Battleships (1×4)
2. Ships can be oriented vertically or horizontally, but not diagonally. For
example, the battleship can either be a 1×4 rectangle or a 4×1 rectangle,
depending on the orientation.
3. The number of ships for each type is provided as part of the puzzle (see
Figure 2, at right).
4. Ships are not allowed to touch each other, even diagonally. This means that
each ship must be surrounded by at least one square of water on all sides
and corners.
5. In addition to being provided with the number of occupied squares in each
column and row, some puzzles also reveal the contents of certain squares,
showing whether they contain water or some piece of a ship. Where a ship
piece is revealed, it will indicate whether it is a middle or end portion of a ship,
and in the case of the end portion it will show what the orientation of that
piece is (i.e. what direction the rest of the ship can be found).
o In the case where a submarine is revealed, it will simple show the
entire ship.
For more information or for the rules of battleship solitaire, please
consult https://en.wikipedia.org/wiki/Battleship_(puzzle) Links to an external site..
You can play games of battleship solitaire for free
at https://lukerissacher.com/battleships Links to an external site..
What you need to do
In order to solve these puzzles, you need to choose variables for this problem and
define a domain for each variable. You then need to define enough constraints over the
variables that would sufficiently capture the rules of Battleship Solitaire.
Remember to choose constraints wisely such that when solving you will be able to
prune domains of variables efficiently and shrink the search space. There are a few tips
we recommend to accomplish this:
• Design your variables in a way that makes it easy to check the constraints.
• Avoid variables that require an exponential number of values.
o Performing GAC on such constraints will be too expensive.
• Try not to use table constraints over large numbers of variables.
o Table constraints over two or three variables are fine: performing
GAC on table constraints with large numbers of variables becomes
very expensive.
You then need to implement a CSP solver. The implementation details are up to you,
but it would be advisable to follow the concepts used in this course. Try using forward
checking and general arc consistency, along with a backtracking search, and see which
works better.
Evaluation
Your submission will be marked primarily for correctness and performance. We will test
your solution on grids that range from 6×6 to 10×10 with a unique solution. Your solver
needs to find this unique solution (correctness) within the time allotted (~5 minutes per
puzzle). There is a small portion of your assignment mark allocated for the explanation
of any heuristics that you used.
Input Format
Your program should be named battle.py and take in two arguments from the
command line: the names of the input and output files. The following command should
run your program on the puzzle in puzzle1.txt, storing the output in output1.txt:
python3 battle.py puzzle.txt
The input file will represent an NxN puzzle and be formatted as follows:
• On the first line will be the puzzle’s row constraints written as a string of N
numbers (note that row constraints are usually written to the left or the right of
each row when viewing examples of these puzzle).
• On the second line will be the puzzle’s column constraints written as a
string of N numbers (note that column constraints are usually written on top or
bottom of each column when viewing examples of these puzzle).
• On the third line will be 1-4 numbers, representing the number of submarines,
destroyers, cruisers and battleships, in that order. Some of the smaller
puzzles are too small to contain larger ships, so if there are less than 4
numbers in this row you can assume that no ships of that size exist in this
puzzle.
The remaining lines will represent the starting layout of the puzzle, which indicates any
starting values you have to work with. Each line will represent a row of the Battleship
Solitaire grid as a string of characters, with each character representing a single square
in that row. There are 8 possible characters for this section of the input file:
• ‘0’ (zero) represents no hint for that square
• ‘S’ represents a submarine,
• ‘W’ represents water
• ‘L’ represents the left end of a horizontal ship,
• ‘R’ represents the right end of a horizontal ship,
• ‘T’ represents the top end of a vertical ship,
• ‘B’ represents the bottom end of a vertical ship, and
• ‘M’ represents a middle segment of a ship (horizontal or vertical).
Therefore, an NxN puzzle will have its initial grid represented by N lines, each of which
is N characters long.
An example of an input file would be:
211222
140212
321
000000
0000S0
000000
000000
00000W
000000
The above input file corresponds to the puzzle below (in typical print form).
As stated above, your main program should take two command-line arguments: one for
the input file and one for the output file:
python3 battle.py
