building a sudoku solver

[usercat123]

Hi,

For some reason, a call to solve_sudoku() will not print the solved sudoku, "test" is not even printed and I don't see why. Can anyone help me?

import numpy as np

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

def solve_sudoku():
    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_sudoku()
                        grid[i][j] = 0
                return
    print("test")
    print(np.matrix(grid))



def main():
    global grid
    grid = [
                    [3,0,0,8,0,0,0,0,1],
                    [0,0,0,0,0,2,0,0,0],
                    [0,4,1,5,0,0,8,3,0],
                    [0,2,0,0,0,1,0,0,0],
                    [8,5,0,4,0,3,0,1,7],
                    [0,0,0,7,0,0,0,2,0],
                    [0,8,5,0,0,9,7,4,0],
                    [0,0,0,1,0,0,0,0,0],
                    [9,0,0,0,0,7,0,0,6]
                ]
    solve_sudoku()

if __name__ == '__main__':
    main()

[deanhystad]

This is an odd solver. Took me a while to see how it works.

"test" is only printed if you solve the puzzle. Your solver cannot solve the puzzle because there is an error in "possible()"

[usercat123]

"test" will never be printed. The function contains a return that prevents every reaching the print command.

It doesn't matter though, because your program has a lot of errors. You recursively call the solver, but you don't pass any information so no progress is made. It just starts over from the beginning. The return is in the wrong place so your program gives gives up after solving the first cell. The solver doesn't return a status, so even if you did find a solution the program would continue running trying to find a solution.

But return is within the scope of

if grid[i][j] == 0: 

so it should only return after the recursion has finished right? And for the last case - where every square is not 0 - the statement

if grid[i][j] == 0:

is ignored entirely and instead print should be called?

[deanhystad]

I edited my early response because I found the bug, but by then you had replied. Look at the part in possible where you check if n is in the square containing x,y. That is where you have a bug.

[usercat123]

I'm too dumb to spot the bug, can you tell me whats wrong?

[deanhystad]

Almost 90% of the time you are looking at the wrong part of the grid when doing this test:

    for i in range(3):
        for j in range(3):
            if grid[x0+i][y0+j] == n:
                return False

Try different values for x and y and see what you get x0 and y0. For example, what is x0 when x is 5? What should X0 be?

[usercat123]

Thanks I overlooked that one. On another note, I have now expanded with a sudoku generator. First, I want to generate a valid sudoku but I have made a mistake while doing so. Here is the updated code. Can you spot it (again...)? A index out of range exception is thrown when executing place_random

import numpy as np
import random

def possible(x,y,n):
    if grid[x][y] != 0:
        return False
    for i in range(9):
        if grid[i][y] == n or grid[x][i] == n:
            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] == n:
                return False
    return True

def solve_sudoku():
    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_sudoku()
                        grid[i][j] = 0
                return
    print(np.matrix(grid))

def place_random(x,y):
    n = random.sample(range(1,10),9)
    i = 0
    while not possible(x,y,n[i]):
        i += 1
    grid[x][y] = n[i]

def generate_sudoku():
    global grid
    for i in range(9):
        for j in range(9):
            place_random(i,j)
    print(np.matrix(grid))



def main():
    global grid
    grid = [[0]*9]*9
    """
    grid = [
                    [3,0,0,8,0,0,0,0,1],
                    [0,0,0,0,0,2,0,0,0],
                    [0,4,1,5,0,0,8,3,0],
                    [0,2,0,0,0,1,0,0,0],
                    [8,5,0,4,0,3,0,1,7],
                    [0,0,0,7,0,0,0,2,0],
                    [0,8,5,0,0,9,7,4,0],
                    [0,0,0,1,0,0,0,0,0],
                    [9,0,0,0,0,7,0,0,6]
                ]
    """
    generate_sudoku()

if __name__ == '__main__':
    main()

[deanhystad]

The loop in place_random() ends when it finds a number that can be placed in the cell, but what happens if there are no valid numbers?

def place_random(x,y):
    n = random.sample(range(1,10),9)
    i = 0
    while not possible(x,y,n[i]):  # <- What is the value for i if there are no possible solutions for this cell?
        i += 1
    grid[x][y] = n[i]

This is ugly code anyway. Why are you using while?

def place_random(x, y):
    for n in random.sample(range(1, 10), 9)
        if possible(x, y, n):
            grid[x][y] = n
            return True
    return False

Returns True if the cell is filled, else False.

Not that it matters much since you cannot generate sudoku puzzles using your approach. Most of the puzzles your generator makes will end up being invalid. You will need to make a backtracking algorithm similar to your solver that backs up when it encounters an invalid puzzle and tries again.