Recursion issues when solving Sudoku puzzles-CodePudding

I'm trying to write a program to solve a Sudoku puzzle. I have a dictionary that holds all empty cell position as keys and their respective possible values in a list. Shown below is a part of the dictionary

empty_cells = {'00': ['3', '5', '6'], '01': ['1', '3', '5'], '06': ['1', '6']}

I'm trying to recursively call a function to brute force through this list but I can't seem to progress through the list.

def brute(board):
    for cell in list(empty_cells):
        for n in empty_cells[cell]:

            board[int(cell[0])][int(cell[1])] = n

            brute(board)

            board[int(cell[0])][int(cell[1])] = "."   
        
        return

I'm not really sure why whenever I call the brute function, the function does not move on to the next empty cell in the list and just stays at the 00 cell till the recursive depth is reached.

CodePudding user response：

I think it iterates ok, but you are assigning to something else

try changing

board[int(cell[0])][int(cell[1])]

board[int(key[0])][int(key[1])]

CodePudding user response：

The problem is that you have no way of keeping track of your progress. If you think about it thoroughly, you are forever calling brute, arriving at key "00", at option '3', setting board[int(cell[0])][int(cell[1])] to '3', and repeating, setting board[int(cell[0])][int(cell[1])] to '3' again in the next recursion, and again and again.

To fix this implement some way to keep track of the current state. I suggest instead of iterating through all possibilities you make a function that finds the next open cell. And of course, your code needs some kind of condition to check if you have won or not