Provided Code:-

import random as rand import math as M class State(object): """The Problem State is an array of Boolean values, which we represent by a nested list. True means a green tile, False a red tile. """ def __init__(self, gridsize, blocks, used, library, grid=None): """ Initialize the State object. gridsize: Integer. The size of a square grid to fill blocks: Dictionary mapping block names to the number still available of that block used: List-of-tuples indicating which blocks have been placed on the grid and where library: Dictionary mapping block names to what they look like. This is NOT copied, but just for reference """ self.N = gridsize # create a copy of the available block counts self.blocks = dict(blocks) # create a copy of current block locations self.used = [x for x in used] # DON'T copy the library, there's no need since # it shouldn't change self.lib = library # store the grid contents to make it easier # to check if pieces can be added later if grid == None: # if no grid is given, make a blank one self.grid = self.make_grid(self.N) else: # if a grid is given, copy it self.grid = [] for row in grid: new_row = [x for x in row] self.grid.append(new_row) def make_grid(self, N): """ creates a list-of-lists-of-strings that represents the grid. We pad it with a border to make the logic for out-of-bounds checks easier. . means empty, * means block, # means border N: integer, the size of the grid """ grid = [] for i in range(N): row = ["."] * N + ["#"] * 3 grid.append(row) for j in range(3): row = ["#"] * (N+3) grid.append(row) return grid def place_block(self, b, row, col): """ places the block b onto the grid at the given row and col location. pre-condition: the placement is legal """ move = (b, row, col) self.blocks[b] -= 1 self.used.append(move) shape = self.lib[b] for y in range(len(shape)): for x in range(len(shape[y])): if shape[y][x] == "*": self.grid[row+y][col+x] = shape[y][x] def remove_block(self, b, row, col): """ remove a block from the grid at location row, col pre-condition: there is a correct block at that location """ move = (b, row, col) self.blocks[b] += 1 self.used.remove(move) shape = self.lib[b] for y in range(len(shape)): for x in range(len(shape[y])): if shape[y][x] == "*": self.grid[row+y][col+x] = "." def legal_move(self, b, row, col): """ returns true if it is legal to place block b at location row, col """ # No block of that type if b not in self.blocks or self.blocks[b]  0: return rand.choice(better) else: return None

Suppose you have an empty NxN grid, and some blocks that each have one of the 6 possible shapes shown above. For convenience, each different shape has a single character that represents it, as shown in the picture. You are allowed to place a block anywhere on the grid, so long as it fully fits and does not cover any portion of another block. You are NOT allowed to rotate the blocks. The goal is to cover as much of the grid as possible with the blocks. The order in which the blocks are placed does not matter, and it does not matter which blocks are used or if there are any blocks left over. Minimizing the number of empty grid spaces is all that counts. Data Files You will be given a series of data files representing Block Tiling problems. Each file represents a single problem. The following is an example that corresponds to the situation in the picture above. The 4 on line 1 specifies N, which is the dimension of the grid. Each subsequent line specifies the availabilty of a certain shape of block. For example, line 2 indicates that one +-shaped block is available, and line 3 indicates that one L-shaped block is available. For this question, you will write the code to apply Local Search to the Block Tiling problem. The following basic Local Search strategies have been provided for you: - Random Guessing: Randomly choose a new state from all possible states. - Random Search: Randomly move to a neighbouring state. - Hill Climbing: Move to the best neighbouring state. - Random Restart Hill Climbing: Repeat Hill Climbing, with random initial positions. These functions are complete and have been tested, and you should be confident that they work. To apply these methods, you will implement a State class and a Problem class, as per the following interface. Problem Class A Problem class has been provided for you in which most of the work relating to the problem specification is already done. You will only need to implement the following methods: - random_state(self): returns a completely random state - neighbors (self, state): returns a list of all neighbors of the given state You should not change any of the other provided methods, but you may add any number of additional helper methods that you wish. Note that defining the neighborhood of a state (i.e. the states that are considered adjacent to a given state) is up to you! There is no single correct answer. This is a design problem, and like all design problems, there are multiple reasonable designs and a great many bad ones. Along with your code, you need to submit a short written paragraph that describes your design. State Class In the State class, you will need to implement the following method: - get_score(self): Returns the fitness score for this state Deciding on how to calculate the fitness score for this problem will likely be quite easy. Recall that this is the score that we are trying to minimize. Include a description of your fitness score in your written document. You should not change any of the other methods in State, but you will likely need to read them in detail to understand how a State is represented so that you can write all of the code you need for this