Python Recursive Sudoku Solver Doesn't Return the Solution

user_13456662 0
Viewed 383

I tried to optimize this code and my final code was as shown below

import numpy as np
sudoku = np.array([[0, 9, 0, 0, 5, 0, 6, 0, 8],
                   [0, 0, 0, 7, 1, 0, 3, 5, 0],
                   [2, 1, 0, 0, 0, 0, 7, 0, 4],
                   [0, 0, 1, 5, 0, 0, 0, 0, 6],
                   [6, 3, 0, 2, 0, 8, 0, 4, 5],
                   [7, 0, 0, 0, 0, 4, 9, 0, 0],
                   [9, 0, 3, 0, 0, 0, 0, 2, 1],
                   [0, 4, 8, 0, 2, 7, 0, 0, 0],
                   [5, 0, 6, 0, 8, 0, 0, 3, 0]])

#Checking if the number (n) can be placed there (row, col)
def check(sudoku, row, col, n):
    # Row check
    if np.sum(sudoku[row,:] == n) != 0: return False;
    # Col check
    if np.sum(sudoku[:,col] == n) != 0: return False;
    # Sqr check
    row0, col0 = (row//3)*3, (col//3)*3
    if np.sum(sudoku[row0:row0+3,col0:col0+3] == n) != 0: return False;
    return True

def solve_sudoku(sudoku):
    rows, cols = np.where(sudoku == 0)
    for row in rows:
        for col in cols:
            for num in range(1, 10):
                if check(sudoku, row, col, num):
                    sudoku[row, col] = num
                    solve_sudoku(sudoku)
                    sudoku[row, col] = 0
            return
    print(sudoku)
    return sudoku

solved = solve_sudoku(sudoku)

My problem is that even though the solution is successfully printed as shown below, the variable solved is just a NoneType and stores nothing.

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

TL;DR The function prints the solution but returns nothing. What should I do to store the printed solution?

sudoku numpy python
5 Answers

Consider this code:

if check(sudoku, row, col, num):
    sudoku[row, col] = num
    solve_sudoku(sudoku)
    sudoku[row, col] = 0  # undo this move

If the Sudoku is solvable, a solve_sudoku(sudoku) call will eventually find the solution. When you get your solution, you should immediately stop backtracking using return. Otherwise, the next line sudoku[row, col] = 0 will undo the solution you found and further iterations keep trying the next possible numbers. Since Sudoku has only one solution, checking more numbers after finding a solution is not necessary. You may just return a true value to end the recursion.

For example, you may code like this:

if solve_sudoku(sudoku):
    return True

or

if solve_sudoku(sudoku):
    return sudoku

This prevents sudoku[row, col] = 0 from erasing the solution and ultimately returns the solved grid to the initial caller after the recursive call stack unwinds.

user_153817660

The problem is here in your code:

                    solve_sudoku(sudoku)
                    sudoku[row, col] = 0
            return

In the first line, you recur, but you ignore the return value, which discards any return value from that call and all recursions below it.

In the last line, you return the default value on None. Either of these kills your continuity of recursion return values.

user_47851850

The print(sudoku) call is happening when solve_sudoku is called with a completely-filled Sudoku array (one without any remaining zeroes), not in the top-level recursive call.

Each time solve_sudoku is called with an incomplete Sudoku array, you are testing each number between one and ten in the upper-leftmost zero-filled cell, and if the number can be placed in the cell, you place it there, attempt to solve the rest of the grid, and then set the cell back to zero. Once you do this for each number between one and ten, you return None, which is why you are seeing None returned from the top-level solve_sudoku call.

user_67889850

After a few hours, I came up with this solution. solved stores the solution now.

import numpy as np
sudoku = np.array([[0, 9, 0, 0, 5, 0, 6, 0, 8],
                   [0, 0, 0, 7, 1, 0, 3, 5, 0],
                   [2, 1, 0, 0, 0, 0, 7, 0, 4],
                   [0, 0, 1, 5, 0, 0, 0, 0, 6],
                   [6, 3, 0, 2, 0, 8, 0, 4, 5],
                   [7, 0, 0, 0, 0, 4, 9, 0, 0],
                   [9, 0, 3, 0, 0, 0, 0, 2, 1],
                   [0, 4, 8, 0, 2, 7, 0, 0, 0],
                   [5, 0, 6, 0, 8, 0, 0, 3, 0]])
solved = np.zeros_like(sudoku)

def check(arg, row, col, n):
    if np.sum(arg[row,:] == n) != 0: return False;
    if np.sum(arg[:,col] == n) != 0: return False;
    row0, col0 = (row//3)*3, (col//3)*3
    if np.sum(arg[row0:row0+3,col0:col0+3] == n) != 0: return False;
    return True

def solve_sudoku(arg):
    global solved
    rows, cols = np.where(arg == 0)
    for row in rows:
        for col in cols:
            for num in range(1, 10):
                if check(arg, row, col, num):
                    arg[row, col] = num
                    solve_sudoku(arg)
                    arg[row, col] = 0
            return
    solved = arg.copy()
solve_sudoku(sudoku)

I don't know if it it is the best way to optimize the code, feedbacks are welcomed.

user_134566620 
def check(grid, num, x, y):
    for i in range(9):
        if grid[i][y] == num:
            return False
    for j in range(9):
        if grid[x][j] == num:
            return False
    x0 = (x//3) * 3
    y0 = (y//3) * 3
    for i in range(3):
        for j in range(3):
            if grid[x0+i][y0+j] == num:
                return False
    return True

def solve(grid):
    for i in range(9 + 1):
        if i==9:
            return True
        for j in range(9):
            if grid[i][j] == 0:
                for num in range(1,10):
                    if check(grid, num, i, j):
                        grid[i][j] = num
                        if solve(grid):
                            return True
                        grid[i][j] = 0
                return False

This should work for you. It does not return the array but modifies it. So if you pass

solve(sudoku_grid)

and then print sudoku_grid it will give you the solved output

user_141516750
Related