Sudoku Solver in Python keeps outputting FALSE solution-CodePudding

As title mentioned. Obviously, the code stoped at the second ROW of the output board.I have been checking it for more than a hundred times but I still could not find where it goes wrong. I would be so grateful if you guys can tell me where I did wrong. Below is my code.

def solve(board):

    if not find_zero(board):
        return True
    else:
        row, col = find_zero(board)

    for value in range(1, 10):
        if is_valid(board, row, col, value):
            board[row][col] = value
            if solve(board):
                return True
        board[row][col] == 0

    return False


def find_zero(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return i, j
    return None, None


def is_valid(board, row, col, value):

    # Check the row
    if value in board[row]:
        return False
        
    # Check the column
    col_vals = [board[i][col] for i in range(9)]
    if value in col_vals:
        return False

    # Check the grid
    x = (row // 3) * 3
    y = (col // 3) * 3

    for i in range(x, x   3):
        for j in range(y, y   3):
            if board[i][j] == value:
                return False

    return True

Here is the board and the output of my code.

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

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

CodePudding user response：

The find_zero method returns a tuple of length 2. A non-zero length tuple will always evaluate to True, irrespective of its contents, so the conditional at the start of the solve method can never return True.

Thus your code will never recognise a valid solution. You should return None or False from find_zero if it doesn't find any.

CodePudding user response：

In addition to the problem Conor pointed out. There also is the problem that board is mutable and you change the board in potentially invalid ways that need to be rolled back. If you make a deepcopy of it every time you pass it to solve it works. Since I only changed the solve method I will post just that:

import copy

def solve(board):
    if find_zero(board)[0] is None:
        for row in board:
            print(row)
        return True
    else:
        row, col = find_zero(board)

    for value in range(1, 10):
        if is_valid(board, row, col, value):
            new_board = copy.deepcopy(board) 
            new_board[row][col] = value
            if solve(new_board):
                return True
    return False

In the end you get

[5, 3, 4, 6, 7, 8, 9, 1, 2]
[6, 7, 2, 1, 9, 5, 3, 4, 8]
[1, 9, 8, 3, 4, 2, 5, 6, 7]
[8, 5, 9, 7, 6, 1, 4, 2, 3]
[4, 2, 6, 8, 5, 3, 7, 9, 1]
[7, 1, 3, 9, 2, 4, 8, 5, 6]
[9, 6, 1, 5, 3, 7, 2, 8, 4]
[2, 8, 7, 4, 1, 9, 6, 3, 5]
[3, 4, 5, 2, 8, 6, 1, 7, 9]
True