solved we are seeking goal which is the solution of the puzzle we could randomly try value in cell of the puzzle and try to solve the puzzle after having made that guess the guess would lead to new state of the puzzle butif the guess were wrong we may have to go back and undo our guess wrong guess could lead to dead end this process of guessingtrying to finish the puzzleand undoing bad guesses is called depth first search looking for goal by making guesses is called depth first search of problem space when dead end is found we may have to backtrack backtracking involves undoing bad guesses and then trying the next guess to see if the problem can be solved by making the new guess the description here leads to the depth first search algorithm in sect depth-first search algorithm def dfs(currentgoal)if current =goalreturn [current for next in adjacent(current)result dfs(nextif result !nonereturn [currentresult return none the depth first search algorithm may be written recursively in this code the depth first search algorithm returns the path from the current node to the goal node the backtracking occurs if the for loop completes without finding an appropriate adjacent node in that casenone is returned and the previous recursive call of dfs goes on to the next adjacent node to look for the goal on that path in the last an algorithm was presented for solving sudoku puzzles that works for many puzzlesbut not all in these casesdepth first search can be applied to the puzzle after reducing the problem as far as possible it is important to first apply the rules of the last to reduce the puzzle because otherwise the search space is too big to search in reasonable amount of time the solve function in sect includes depth first search that will solve any sudoku puzzle assuming that the reduce function applies the rules of the last to all the groups within puzzle the copy module must be imported for this code to run correctly sudoku depth-first search def solutionviable(matrix)check that no set is empty for in range( )for in range( )if len(matrix[ ][ ]= return false return true def solve(matrix)this copy belongs to 'acha