Exit clause in recursive call

Question

I am creating a recursive algorithm to brute force a Sudoku puzzle. I have gotten everything to work properly, however, I am trying to figure out how to stop the process once it correctly finishes a puzzle. Here is what I have so far.

def solve(board, cell):

    #calculate row and column of board
    row = cell // 9
    col = cell - (row*9)

    #check if unfilled cell
    if board[row][col] == 0:

        #calculates possible numbers for cell 
        nums = getCandidates(row, col)

        #if no possibilities previous cell must be wrong
        if(len(nums) == 0):
            return 0

        #Iterate all possibilities assume each num is correct until proven wrong
        for i in nums:
            board[row][col] = i
            solve(board, cell + 1)

        #No possibilities were correct previous cell must be wrong
        #Clear current cell and return to previous instance of solve()
        board[row][col] = 0

    else:
        #Cell already filled skip to next
        solve(board, cell+1)

I need a exit statement that would exit all recursive calls once puzzle solution is reached. I can't figure out how to do this and could use help. I would also, in the future, like to add a feature where the algorithm will continue past a solution checking for any other possible solutions. Keep this in mind so the exit statement would be adaptable for this. Thanks!

Answer 1

I could provide you with exact code that works, but

1. I feel like you're trying to discover things yourself,
2. There are plenty of examples on the Internet already.

So here's a more general hint - you can rework your algorithm to work like this:

def solve(problem):
    if problem is trivial / all candidates were filled:
        return if it succeeded

    for candidate in possible candidates:
        try candidate
        if solve(smaller problem):
            return True

    raise RuntimeError('Problem has no solutions')

Basically, make use of solve() return values and check them each time you call it recursively. It is very common approach in brute force oriented searches. I.e. make use of that 0 (which should be False BTW) you return in one place, add some return True and an if... and you're set.

Note that brute forcing sudoku puzzles, while might be good educational experience, is not the best approach in general.