PLEASE USE PYTHON, THANK YOU!

You will represent a given state for a sudoku puzzle as a list of nine lists. Each of the 9 sub-lists will contain 9 elements, and will represent a single row in the puzzle. Empty cells will be indicated by storing a value of 0 in the location representing that cell. As an example, the list displayed on the left below would represent the puzzle displayed on the right. . | 8 1. 1 . 36 1 9 7 . . | 2 . +- puzzle = [ [8, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 3, 6, 0, 0, 0, 0, 0], [0, 7, 0, 0, 9, 0, 2, 0, 0], [O, 5, 0, 0, 0, 7, 0, 0, 0], [0, 0, 0, 0, 4, 5, 7, 0, 0], [0, 0, 0, 1, 0, 0, 0, 3, 0], [0, 0, 1, 0, 0, 0, 0, 6, 8], [0, 0, 8, 5, 0, 0, 0, 1, 0], [O, 9, 0, 0, 0, 0, 4, 0, 0] ] 5 | . . 7. 45 | 7 1 . | 1 . 3.1 . . . 1 | 8 | 5 1.68 1 4 | 9 . +- get_options() This function should accept three parameters named puzzle, row, and col. The parameters row and col should be integers indicating the position of a cell in the puzzle represented by puzzle. If the cell contains a value, then the function should return None. If the cell is empty, then the function should return a list of valid numbers that could be placed in that cell. It should do this by scanning the row, column, and 3x3 block that contain the cell, eliminating from the possible options any values that appear in those collections of cells. For example, if puzzle is the list provided in the first page of these instructions, then: get_options(puzzle, 2, 4) should return None, since the cell in row 2, column 4 contains a 9. get_options(puzzle, 2, 5) should return [1, 3, 4, 8]. 2,7, and 9 are NOT valid options since they appear in the same row as this cell. o 5 and 7 are NOT valid options since they appear in the same column as this cell. 6 and 9 are NOT valid options since they appear in the same block as this cell. The steps below explain one way to accomplish the desired tasks: 1. Check to see if the cell of puzzle indicated by the values row and col contains a value greater than 0. If it does, then return None. 2. Create an empty list named used. We will fill this list with the non-zero numbers that are contained the the row, column, and 3x3 block that contain the indicated cell. 3. Loop over the indicated row of puzzle. Append each non-zero value in that row to used. 4. Loop over the indicated column of puzzle. Append each non-zero value in that column to used. 5. Use nested loops to scan over the block containing the current cell. Append each non-zero value in that column to used. To scan over the desired block, you will have to identify the index of the row and column that start the block. For example: If row is 0, 1, or 2, then the first row in the block is at index 0. If row is 3, 4, or 5, then the first row in the block is at index 3. If row is 6, 7, or 8, then the first row in the block is at index 6. Similar rules fold for the starting column. You can us the following code to calculate these starting values: start_row = 3*int(row/3) start_col = 3*int(col/3) 6. After completing steps 2-5, the list used will contain all of the invalid options. We now wish to identify the valid options. Create an empty list named options. 7. Loop over the digits 1 - 9. Check to see if each digit appears in used. If it does not, then append it to options. 8. Return options. solve() This function should accept three parameters named puzzle, row, and col. The parameter puzzle is expected to be a list representing a puzzle state, while row and col are expected to be integers indicating the position of a specific cell in the puzzle. The default values of row and col should be set to 0, indicating that the function will begin the serach for a solution by looking at the upper-left cell. The function should return a list of lists representing the solved state of the puzzle, if one exists. If no solution exists, then the function should return None. The function should find the solution to the puzzle recursively by following the steps below: 1. Check to see if the cell indicated by the parameters row and col is blank (which would be indicated by a value of Ostored at the appropriate location in puzzle). If this cell is not blank, then we will move to the next cell, if one exists. In this case, perform the following steps: a. Use get_next() to obtain the position of the next cell. Store the resulting values in next_row and next_col. b. Check to see if next_row is None. If so, then we are at the last cell, and will have finished construction the solution. Return puzzle, which will store the completed solution. C. If next_row is not None, then we will move on to the next cell. Call solve() again, passing it puzzle, next_row, and next_col. 2. If the current cell is blank, then we will identify the possible values that could be placed within this cell. Call get_options(), passing it puzzle and the location of the current cell. Store the results in a list named options. 3. If options is empty, then there are no value digits that could be placed in this cell. Return None to indicate that the current puzzle state is not solvable. This will end this branch of the recursion, causing the function to backtrack and consider different values for previously filled-in cells. 4. If options is not empty, then loop over the digits in this list. Perform the following steps for each such value: a. Use copy_puzzle() to create a new copy of the puzzle, named new_puzzle. b. Use row and col to set the entry of new_puzzle corresponding to the current cell to the current value of options that is being considered. We are filling in a valid number in this cell and will check to see if this leads to a solution. c. Call solve(), passing it new_puzzle, row, and col. Store the result in a variable named result. This is the step in which we attempt to see if the new puzzle state leads to a solution. Note that if a solution was found, then result will contain that solution. If no possible solution can be found using the current state, then result will contain None. d. If result is not equal to None, then this means that a solution was eventually found. Return result, which should store the solved puzzle state. e. If result is equal to None, then no additional action should be taken. In this case, the loop will continue executing, and the function will try out different values for the current cell