Sudoku Backtracking Python to find Multiple Solutions-CodePudding

I have a code to solve a Sudoku recursively and print out the one solution it founds. But i would like to find the number of multiple solutions. How would you modify the code that it finds all possible solutions and gives out the number of solutions? Thank you! :)

code:


board = [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]


def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    else:
        row, col = find

    for num in range(1,10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          

            if solve(bo):                 
                return True

            bo[row][col] = 0              

    return False


def valid(bo, num, pos):
    # Check row
    for field in range(len(bo[0])):                     
        if bo[pos[0]][field] == num and pos[1] != field:
            return False

    # Check column
    for line in range(len(bo)):
        if bo[line][pos[1]] == num and pos[0] != line:
            return False

    # Check box
    box_x = pos[1] // 3
    box_y = pos[0] // 3

    for i in range(box_y*3, box_y*3   3):
        for j in range(box_x * 3, box_x*3   3):
            if bo[i][j] == num and (i,j) != pos:
                return False

    return True


def print_board(bo):
    for i in range(len(bo)):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - - - ")

        for j in range(len(bo[0])):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")

            if j == 8:
                print(bo[i][j])
            else:
                print(str(bo[i][j])   " ", end="")


def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return None
if __name__ == "__main__":
    print_board(board)
    solve(board)
    print("___________________")
    print("")
    print_board(board)

I already tried to change the return True term at the Solve(Bo) Function to return None/ deleted it(For both return Terms) that it continues… Then the Algorithm continues and finds multiple solutions, but in the end fills out the correct numbers from the very last found solutions again into 0’s. This is the solution then printed out.

CodePudding user response：

As asked:

How would you modify the code that it finds all possible solutions and gives out the number of solutions?

If you don't want to return ("give out") the solutions themselves, but the number of solutions, then you need to maintain a counter, and use the count you get back from the recursive call to update the owned counter:

def solve(bo):
    find = find_empty(bo)
    if not find:
        return 1

    count = 0
    row, col = find
    for num in range(1, 10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          
            count  = solve(bo)
            bo[row][col] = 0              

    return count

In the main program, you would no longer print the board, as you don't expect the filled board now, but a number:

    print(solve(board))  # Will output 1 for your example board.

Getting all solutions

If you don't just want to know the count, but every individual solution itself, then I would go for a generator function, that yields each solution:

def solve(bo):
    find = find_empty(bo)
    if not find:
        yield [row[:] for row in bo]  # Make a copy
        return
        
    row, col = find
    for num in range(1, 10):
        if valid(bo, num, (row, col)):
            bo[row][col] = num          
            yield from solve(bo)
            bo[row][col] = 0

Then the main program can do:

    count = 0
    for solution in solve(board):
        print("SOLUTION:")
        print_board(solution)
        count  = 1
    print("NUMBER of SOLUTIONS:", count)

CodePudding user response：

From a high-level view, it seems to me that a recursive approach to this should work as follows:

Check if the grid is valid:
- If the grid is invalid, return immediately
- Else, check if the grid is complete:
  - If the the grid is complete, add (a copy of) it to the list of solutions
  - Else, the grid is valid and incomplete, so find the first empty cell and run the function recursively on the grid with all possible values filled in for that box (and make sure to clear any modified cells at the end, after the loop)

Then, the list of solutions is generated, and the length of that list is the number of possible solutions. (If you find there are a lot of solutions and generating the list takes a very long time, you may just want to make a counter for the number of solutions found.)

Implementing this shouldn't be too difficult using what you have, since you already have functions for finding the first empty cell and verifying whether the grid is valid, etc.

How does that sound?