Assignment 3: CSP Battleship
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 (https://en.wikipedia.org/wiki/Battleship_(game)) . 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).
Copyright By PowCoder代写 加微信 powcoder
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:
Submarines (1×1) Destroyers (1×2) Cruisers (1×3) 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).
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) (https://en.wikipedia.org/wiki/Battleship_(puzzle)) . You can play games of battleship solitaire for free at https://lukerissacher.com/battleships (https://lukerissacher.com/battleships) .
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.
Performing GAC on such constraints will be too expensive. Try not to use table constraints over large numbers of variables.
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 puzzle1.txt output1.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:
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
Mark Breakdown
As stated earlier, the majority of your marks will come from correctness and performance, in that we measure how many puzzles you are able to solve within the time provided.
Marking Scheme Component Weight
Heuristic file 10%
As shown in this table, 10% of your mark for this assignment is earned through the implementation of additional heuristics or techniques that you add to your CSP solver. These are meant to be part of your solution and described in a file called heuristics.pdf , which you will submit on Markus along with your battle.py file. This mark is assigned separately from your correctness mark (i.e. you can get full marks for your heuristics even if you don’t get full correctness marks).
Correctness (puzzles solved)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com