Python Recursive Sudoku Solver Doesn't Return the Solution

Question

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?

You need to use the result of your recursive call to solve_sudoku and check whether the game is finished at that point. — kingkupps
– kingkupps, Commented Sep 10, 2020 at 0:34

ggorlen · Accepted Answer · 2021-08-14 20:33:16Z

1

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.

edited Aug 14, 2021 at 20:33

ggorlen

59.3k8 gold badges119 silver badges173 bronze badges

answered Mar 13, 2021 at 18:49

zerozero nine

392 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Prune · Accepted Answer · 2020-09-10 00:34:38Z

0

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.

answered Sep 10, 2020 at 0:34

Prune

78k14 gold badges63 silver badges83 bronze badges

Comments

Steve Hart · Accepted Answer · 2020-09-10 01:38:13Z

0

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.

answered Sep 10, 2020 at 1:38

Steve Hart

8681 gold badge5 silver badges15 bronze badges

Comments

gokdumano · Accepted Answer · 2020-09-10 08:56:01Z

0

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.

edited Sep 10, 2020 at 8:56

answered Sep 10, 2020 at 8:43

gokdumano

806 bronze badges

1 Comment

ggorlen Over a year ago

It's a bad idea to use global state like this. It's brittle (variable name changes break the function), it's non-reentrant, in a large codebase it'd be a nightmare if a bug occurred to figure out which functions messing with global state have done what when. Better to return the solution up the call stack so all modifications to state are completely internal to the function.

hypnos · Accepted Answer · 2020-11-28 08:50:29Z

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

Collectives™ on Stack Overflow

Python Recursive Sudoku Solver Doesn't Return the Solution

5 Answers 5

Comments

Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related