Computerphile's Python Solver - return None value-CodePudding

I've just copied code from this YT video.

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

def solve_grid():
    for i in range(9):
        for j in range(9): 
            if grid[i, j] == 0:
                for n in range(1, 10):
                    if possible(i, j, n):
                        grid[i, j] = n
                        solve_grid() 
                        grid[i, j] = 0
                return       
    print(grid)

grid = np.array([[0, 6, 0, 0, 4, 0, 0, 8, 5],
                 [0, 8, 9, 0, 0, 5, 0, 1, 7],
                 [0, 3, 0, 0, 0, 1, 0, 0, 0],
                 [0, 5, 3, 0, 6, 0, 7, 0, 0],
                 [0, 0, 2, 0, 1, 7, 0, 9, 0],
                 [1, 0, 0, 9, 2, 0, 0, 4, 0],
                 [0, 0, 0, 8, 0, 0, 0, 0, 9],
                 [4, 0, 7, 0, 0, 0, 6, 0, 0],
                 [8, 0, 5, 3, 9, 0, 2, 0, 0]])

solve_grid()

I'd like to assign solution to a variable instead of printing it, but simple exchanging printing into return results in None value.

Any ideas? Thanks in advance.

CodePudding user response：

This is actually pretty interesting. Your problem isn't exactly with returning the value, but with stopping the function after it's found a solution. It would seem that this program finds all the solutions possible, not just the first that it encounters. With the example Sodoku board you gave, there is only one solution so this feature was not readily apparent. To get sodoku board(s) out of the function, we have options: stopping the function prematurely to only get the first result is a little tricky, but just grabbing all the results is easy and I don't even have to have a complete understanding of the function's flow. I'll have a list and every time a solution is found, I'll add a copy of the current grid array to the solution set (It's technically a list because np.arrays aren't hashable, apparently). Figuring out where to append to the list in the code was easy, it's just where the print statement has been. I just had the list returned at the old return point and the implicit return at the end of the function. The only notable change I made was in the solve_grid function. Okay, so here's the code:

import numpy as np
from pprint import pprint
def possible(y, x, n):
    for i in range(9):
        if grid[y, i] == n:
            return False
    for i in range(9):
        if grid[i, x] == n:
            return False
    y0 = (y//3)*3
    x0 = (x//3)*3
    for i in range(3):
        for j in range(3):
            if grid[y0 i, x0 j] == n:
                return False
    return True

def solve_grid(solutions = None):
    if(solutions==None):
        solutions = []
    for i in range(9):
        for j in range(9): 
            if grid[i, j] == 0:
                for n in range(1, 10):
                    if possible(i, j, n):
                        grid[i, j] = n
                        solve_grid(solutions) 
                        grid[i, j] = 0
                return solutions     
    #print(grid)
    solutions.append(grid.copy())
    return solutions
grid = np.array([[0, 0, 0, 0, 0, 0, 0, 8, 5],
                 [0, 8, 9, 0, 0, 5, 0, 1, 7],
                 [0, 3, 0, 0, 0, 1, 0, 0, 0],
                 [0, 5, 3, 0, 6, 0, 7, 0, 0],
                 [0, 0, 0, 0, 1, 7, 0, 9, 0],
                 [1, 0, 0, 9, 0, 0, 0, 4, 0],
                 [0, 0, 0, 8, 0, 0, 0, 0, 9],
                 [4, 0, 7, 0, 0, 0, 6, 0, 0],
                 [8, 0, 5, 3, 9, 0, 2, 0, 0]])

#print(solve_grid())
pprint(solve_grid())

You could also do something so that it only finds the first x solutions, which might be interesting. And it would be best not to use a global array, but to pass the board into the function.

CodePudding user response：

I think the idea behind this code was to make some operations with the grid, but make the global grid not changeable. You can still have that by using copy() method and you will be able to get non-None value:

import numpy as np


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


def solve_grid(grid):
    g = grid.copy()
    for i in range(9):
        for j in range(9):
            if g[i, j] == 0:
                for n in range(1, 10):
                    if possible(g, i, j, n):
                        g[i, j] = n
    return g


grid = np.array([[0, 6, 0, 0, 4, 0, 0, 8, 5],
                 [0, 8, 9, 0, 0, 5, 0, 1, 7],
                 [0, 3, 0, 0, 0, 1, 0, 0, 0],
                 [0, 5, 3, 0, 6, 0, 7, 0, 0],
                 [0, 0, 2, 0, 1, 7, 0, 9, 0],
                 [1, 0, 0, 9, 2, 0, 0, 4, 0],
                 [0, 0, 0, 8, 0, 0, 0, 0, 9],
                 [4, 0, 7, 0, 0, 0, 6, 0, 0],
                 [8, 0, 5, 3, 9, 0, 2, 0, 0]])


grid1 = solve_grid(grid)

print(grid)
print(grid1)