The first step I took in approaching this challenge is by making a function that pre-processes the given board by simplifying it. Once the board is read and turned into an object via a board class, my knowledge of how the board works is utilized to my advantage by placing water where I know there must be some; take for example the rows and columns that have a zero indicating the number of ship parts in them, I can replace the column/row with water, or the hints, I know the diagonal entries next to them must also be water. Another clever thing I do to make this process easier is to create my own type of ship part (a pseudo part 'p') which does not imply anything about the type of ship or its orientation. Once the board has been completely determined in terms of pseudo parts, I call a function to reconstruct the board with the actual specific ship parts based on their orientation and length. By doing so, I can avoid iterating through the board and having to account for all the different types of ship parts and only focus on whether or not it meets the constraints. Lastly, the backtracking function assigns a value (a pseudo ship part or water) to the cell (the variable) and then checks whether or not all the necessary constraints are met in the board. If at any point a constraint is not met then the function returns to the most recently accepted board and tries a different assignment. This process keeps taking place and making assignments that pass all the constraints until there are no more variables/cells to be assigned a value, thus finding a solution to the board. The passConstraints function calls all the constraints that must be checked before any permanent assignment and determines if they are all met is called within the backtracking function after every new assignment.

Input & Output:

Input: A text file with a representation of the starting board. Note that there are hints with some ship parts.

• The first line represents the row constraints as a string of N numbers. 

• The second line represents the column constraints as a string of N numbers.

• The third line describes the number of each type of ship.

  • The four numbers represent the number of submarines (1x1), destroyers (1x2), cruisers (1x3) and battleships (1x4) in that order.

• The remaining lines represent an N by N grid with the initial layout of the puzzle. For each cell, there are eight possible characters.

  • • ‘0’ (zero) represents no hint for that square.

    • ‘S’ represents a submarine,

    • ‘.’ (period) represents water.

    • ‘<’ represents the left end of a horizontal ship,

    • ‘>’ represents the right end of a horizontal ship,

    • ‘^’ represents the top end of a vertical ship, 

    • ‘v’ (lower-cased letter v) represents the bottom end of a vertical ship.

    • ‘M’ represents a middle segment of a ship (horizontal or vertical).

Output: A text file with the solution to the puzzle - the ships uncovered.