C battleship program

CSCI-1200 Data Structures — Spring 2018 Homework 6 — Battleship Recursion

In this homework we will solve ship placement puzzles inspired by the pencil & paper “Battleship” game that was later made into a board game by Milton Bradley and then a puzzle that is a regular feature in Games magazine. You can read more about the history of the game and see examples here:

https://en.wikipedia.org/wiki/Battleship_(game)

https://en.wikipedia.org/wiki/Battleship_(puzzle)

This is a popular game with lots of material available online. You may not search for, study, or use any code related to the Battleship game or puzzle. Please carefully read the entire assignment and study the examples before beginning your implementation.

Battleship Puzzles - How to Play

Your program will accept one or two command line arguments. The first argument is the name of a battleship puzzle board file similar to the file shown below. This sample file begins with the dimensions of the board, in this case 4 rows and 5 columns. Next, we give the number of cells in each row and each column that are occupied by a ship. The other cells in the row are open water. Then, we have a simple list of the ships that must be placed on that board. All ships are 1 cell wide, but each ship type has a different length (# of cells): submarine = 1, destroyer = 2, cruiser = 3, battleship = 4, carrier = 5, cargo = 6, and tanker = 7.

board 4 5

rows 4 0 2 1

cols 1 2 1 2 1

cruiser

destroyer

submarine

submarine

4

1 2 1 2 1

1

2

0

Your task is to place the ships on the board satisfying the counts for each row. One important rule in placing the ships is that no two ships may occupy adjacent cells (including the diagonal). The sample puzzle above actually has two solutions. The diagram and sample output below show one of the solutions. Can you manually find the other?

Solution:

cruiser 0 0 horizontal

submarine 0 4

submarine 2 1

destroyer 2 3 vertical

+-----+

| o|4

| |0

| o ^ |2

| v |1

+-----+

12121

1

2

0

4

1 2 1 2 1

Output Formatting

To ensure full credit on the homework server, please format your solution exactly as shown above. The solution must begin with the keyword “Solution:”, followed by a line for each ship beginning with the ship type, the row and column of the upperleftmost cell occupied by the ship, and for non-submarine ships the orientation of the ship (“horizontal” or “vertical”). The ships may be listed in any order. After the ship

https://en.wikipedia.org/wiki/Battleship_(game)
https://en.wikipedia.org/wiki/Battleship_(puzzle)
placement details, you should make an ASCII art diagram of the solved board (this will help in debugging). However, this will be graded by the TAs not the automated grading on the homework server, so you may format your ASCII art diagram somewhat differently than the sample above.

If the optional second argument find_all_solutions is not specified, your program should output to std::cout any single valid solution to the puzzle. If the optional argument find_all_solutions is speci- fied, your program should output all valid, unique solutions (in any order) and then also print at the bottom the number of solutions found, e.g., “Found 2 solution(s)”. If the puzzle has no solutions, your program should print “No solutions”. When searching for all solutions, make sure you do not double count or du- plicate the same solution. For example, if a puzzle has two submarines, swapping the submarines does not make a “new” solution.

Puzzles with Cell Constraints

Some input puzzle files have one or more additional constraints placed on some of the cells. These will be listed in the input file after the ships. Here is an example:

board 4 5

rows 4 0 2 1

cols 1 2 1 2 1

cruiser

destroyer

submarine

submarine

constraint 0 2 <

1

2

0

4

1 2 1 2 1

Each constraint line begins with the keyword “constraint”, then the row and column, then one of 7 characters: ’o’ to represent a submarine; ’<’ or ’>’, to represent the left or right cells of a horizontal ship (length ≥ 2); ’^’, or ’v’, to represent the top or bottom cells of a vertical ship (length ≥ 2); ’X’ to represent a middle cell (not either end) of a ship with length ≥ 3; or ’_’ to represent open water. Your task is to limit the output to solutions that match these constraints.

Puzzles with Unknown Sums and/or Unknown Ship Types

The final twist for this assignment is that the input file may have some unspecified row and/or column sums (listed as ’?’) and/or some ships of unspecified type (listed as “unknown”), which may be any length from 1 to 7 cells. Here is an example input: