Hi, I\'m currently having a lot of trouble creating the program described in the

Question

Hi, I'm currently having a lot of trouble creating the program described in the assignment below (written in c++). I've already done all the easy stuff, as in parsing/reading the given file, creating a class for the tiles of the board, etc. The one thing that I can't solve is the recursive concept of the program. How am I supposed to implement a recursive function that solves the board while keeping track of which attempts failed under which conditions and which conditions to delete in what order when something fails. It's hard to explain like this, so I'd just read the file that I posted below. This question is already asked on Chegg, but the answer is wildly wrong, considering it answers how to make a standard battleship game between you and a computer, and not how to solve a battleship puzzle. Any insight and help would be highly appreciated!

On a side note, the format of the input file is the same format as that of the text next to the images of the battleship puzzle board. It first states the dimensions of the board, what numbers are above each row, what numbers are next to each column, and how many of each ship there are. As stated below, recursion is a big must in this assignment, and it can't be implemented in a trivial way. I would also greatly appreciate an emphasis on explaining how it all works rather than just a response filled with code (like the other one was) since I would like to understand how it all works and be able to learn from the answer.

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 eramples 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, carrier5, cargo- 6, and tanker 7. 4 board 4 5 rows 4 0 2 1 cols 1 2 1 21 cruiser destroyer submarine submarine 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 4 0 lo 12121 Output Formatting To ensuref 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 cel 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

Explanation / Answer

import random class Puzzle: # grid grid = None populated_grid = None row_totals = None column_totals = None n = 10 m = 10 empty = "-" node = "o" # ships battleship_size = 4 cruiser_size = 3 destroyer_size = 2 submarine_size = 1 ships = None def __init__(self, n, m, battleships, cruisers, destroyers, submarines, genType): self.n = n self.m = m self.battleships = battleships self.cruisers = cruisers self.destroyers = destroyers self.submarines = submarines self.grid = [[self.empty for i in range(m)] for j in range(n)] self.populated_grid = [[self.empty for i in range(m)] for j in range(n)] self.row_totals = [0 for i in range(m)] self.column_totals = [0 for i in range(n)] self.build_ship_list() if genType == 0: self.generate() else: self.randomly_generate() self.set_totals() self.copy_grid() self.erase_grid() def build_ship_list(self): # build list of ships to be placed self.ships = [] for i in range (0, self.battleships): self.ships.append(self.battleship_size) for i in range (0, self.cruisers): self.ships.append(self.cruiser_size) for i in range (0, self.destroyers): self.ships.append(self.destroyer_size) for i in range (0, self.submarines): self.ships.append(self.submarine_size) def generate(self): # Place ships, forcing a yes instance while(True): for i in range(len(self.ships)): placed = False size = self.ships[i] cells = self.get_empty_cells() for j in range (0, len(cells)): row = cells[j][0] col = cells[j][1] orien = random.randint(0,1) adjacent = self.adjacent_nodes(row,col,size,orien) if adjacent == False: placed = self.place_ship(row,col,size,orien) if placed == False: adjacent = self.adjacent_nodes(row,col,size,1-orien) if adjacent == False: placed = self.place_ship(row,col,size,1-orien) if placed == True: break if placed == False: break if i == (len(self.ships)-1) and placed == True: return else: self.erase_grid() def randomly_generate(self): # Place ships randomly within grid # High probability of no instance while(True): for i in range(len(self.ships)): placed = False size = self.ships[i] cells = self.get_empty_cells() for j in range (0, len(cells)): row = cells[j][0] col = cells[j][1] orien = random.randint(0,1) placed = self.place_ship(row,col,size,orien) if placed == False: placed = self.place_ship(row,col,size,1-orien) if placed == True: break if placed == False: break if i == (len(self.ships)-1) and placed == True: return else: self.erase_grid() def get_empty_cells(self): # Return a list of all empty cells cells = [] for i in range(0, self.m): for j in range(0,self.n): if self.grid[i][j] == self.empty: cells.append([i,j]) random.shuffle(cells) return cells def place_ship(self,row,col,size,orien): # Check that placement is within bounds of grid # and that ship won't overlap existing nodes try: if orien == 0: for j in range(col, col + size): if self.grid[row][j] != self.empty: return False for j in range(col, col + size): self.grid[row][j] = self.node else: for i in range(row, row + size): if self.grid[i][col] != self.empty: return False for i in range(row, row + size): self.grid[i][col] = self.node except IndexError: return False return True def remove_ship(self,row,col,size,orien): # Set nodes to empty if orien == 0: for j in range(col,col+size): self.grid[row][j] = self.empty else: for i in range(row,row+size): self.grid[i][col] = self.empty def set_totals(self): # Assign row and column totals accordingly for i in range(0, self.m): self.row_totals[i] = self.get_row_total(i) for j in range(0, self.n): self.column_totals[j] = self.get_column_total(j) def get_row_total(self,row): # Calculate current number of nodes in row total = 0 for i in range(0,self.n): if self.grid[row][i] != self.empty: total += 1 return total def get_column_total(self,col): # Calculate current number of nodes in column total = 0 for i in range(0,self.m): if self.grid[i][col] != self.empty: total += 1 return total def erase_grid(self): # Must be called prior to solving for i in range(0, self.m): for j in range(0,self.n): self.grid[i][j] = self.empty def copy_grid(self): # After generation, use this to store # the generated solution in populated_grid for i in range(0, self.m): for j in range(0,self.n): self.populated_grid[i][j] = self.grid[i][j] def get_node(self,row,col): # Check if node is empty or not # Avoid L[-1] if row < 0 or col < 0: return self.empty try: value = self.grid[row][col] except IndexError: value = self.empty return value def adjacent_nodes(self,row,col,size,orien): # Returns True if there are adjacent nodes, # False otherwise if orien == 0: if self.get_node(row,col+size) != self.empty: return True if self.get_node(row,col-1) != self.empty: return True for j in range(-1,size+1): if self.get_node(row+1,col+j) != self.empty: return True if self.get_node(row-1,col+j) != self.empty: return True else: if self.get_node(row+size,col) != self.empty: return True if self.get_node(row-1,col) != self.empty: return True for i in range(-1,size+1): if self.get_node(row+i,col+1) != self.empty: return True if self.get_node(row+i,col-1) != self.empty: return True return False def empty_nodes(self,row,col,size,orien): # Check if nodes are empty try: if orien == 0: for j in range(col, col + size): if self.grid[row][j] != self.empty: return False else: for i in range(row, row + size): if self.grid[i][col] != self.empty: return False except IndexError: return False return True def respects_indicators(self): # Check that the current placement of nodes # respects all row/column indicators for i in range(0, self.m): if self.get_row_total(i) != self.row_totals[i]: return False for j in range(0, self.n): if self.get_column_total(j) != self.column_totals[j]: return False return True def print_alg_solution(self): # Output current solution column_totals = [" ", " "] for j in range(0, self.n): column_totals.append(str(self.column_totals[j])) column_totals.append(" ") print(''.join(column_totals)) for i in range(0,self.m): strList = [] strList.append(str(self.row_totals[i])) strList.append(" ") for j in range(0,self.n): strList.append(self.grid[i][j]) strList.append(" ") print(''.join(strList)) print('n: '+ str(self.n) + ' m: ' + str(self.m) + ' ' + 'battleships: ' + str(self.battleships) + ' ' + 'cruisers: ' + str(self.cruisers) + ' ' + 'destroyers: ' + str(self.destroyers) + ' ' + 'submarines: ' + str(self.submarines) + ' ') def print_solution(self): # Output solution given in instance generation column_totals = [" ", " "] for j in range(0, self.n): column_totals.append(str(self.column_totals[j])) column_totals.append(" ") print(''.join(column_totals)) for i in range(0,self.m): strList = [] strList.append(str(self.row_totals[i])) strList.append(" ") for j in range(0,self.n): strList.append(self.populated_grid[i][j]) strList.append(" ") print(''.join(strList)) print('n: '+ str(self.n) + ' m: ' + str(self.m) + ' ' + 'battleships: ' + str(self.battleships) + ' ' + 'cruisers: ' + str(self.cruisers) + ' ' + 'destroyers: ' + str(self.destroyers) + ' ' + 'submarines: ' + str(self.submarines) + ' ') def print_solution_to_file(self): # Print solution given in instance generation to file f = open('instances.txt', 'a') column_totals = [" ", " "] for j in range(0, self.n): column_totals.append(str(self.column_totals[j])) column_totals.append(" ") f.write(''.join(column_totals) + ' ') for i in range(0,self.m): strList = [] strList.append(str(self.row_totals[i])) strList.append(" ") for j in range(0,self.n): strList.append(self.populated_grid[i][j]) strList.append(" ") f.write(''.join(strList) + ' ') f.write('n: '+ str(self.n) + ' m: ' + str(self.m) + ' ' + 'battleships: ' + str(self.battleships) + ' ' + 'cruisers: ' + str(self.cruisers) + ' ' + 'destroyers: ' + str(self.destroyers) + ' ' + 'submarines: ' + str(self.submarines) + ' ') f.close()

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.