Python backtracking algorithm to solve sudoku

Question

I have recently gotten back into writing python and i decided to take up a project of writing a backtracking algorithm in python to solve Sudoku puzzles

How it Works

A matrix is declared to represent the Sudoku grid the blank spaces on the Sudoku grid are represented by zero A function is declared that checks for all the zeros in the grid, another function is the declared to check the answers are valid by checking against a variable declared as Row_Values it also checks against a variable declared as column_values then another function is declared which calls the first function to locate where it can make guesses it returns none if all the spaces are filled, it inputs a number between 1 and 9 in a valid place and then checks it doesn't conflict it then uses recursion to call the function it repeatedly checks if anything is invalid if it becomes invalid it uses backtracking to try new number(s) it returns false if the puzzle is invalid

Code

import numpy as np
import time

start_time = time.time()

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

print (np.matrix(grid))

def find_empty_box(sudoku): 
    for x in range(9):
        for y in range(9):
            if sudoku[x][y] == 0:
                return x, y 
    
    return None, None

def Answer_Valid(sudoku, guess, row, col): 
    row_values = sudoku[row]    
    if guess in row_values:
        return False

    column_values = [sudoku[i][col]for i in range(9)]
    if guess in column_values:
        return False

    row_start = (row // 3) * 3
    col_start = (col // 3) * 3 

    for x in range(row_start, row_start + 3):
        for y in range(col_start, col_start + 3):
            if sudoku[x][y] == guess:
                return False

        return True

def Solver(sudoku):
    row, col = find_empty_box(sudoku)

    if row is None:
        return True

    for guess in range(1,10):
        if Answer_Valid(sudoku, guess, row, col):
            sudoku[row][col] = guess

            if Solver(sudoku):
                return True

        sudoku[row][col] = 0

    return False

print(Solver(grid))

print(np.matrix(grid))

print("%s seconds " % (time.time() - start_time))

Answer 1

The bug in Answer_Valid

for x in range(row_start, row_start + 3):
    for y in range(col_start, col_start + 3):
        if sudoku[x][y] == guess:
            return False

    return True

it works fine when i run it on my computer

Does it actually? There's no question that it will run. The consequences of this bug aren't of the form "not running", but giving bad results. The main consequence is that True will be returned too early, without checking the entire 3x3 block. That may result in invalid solutions. The program would still run, but do the wrong thing. And of course the program may also give a correct solution, by getting lucky, so getting some correct solutions does not mean that there is no problem.

Unconventional use of x and y

Using x to index rows and y to index columns is transposed from how the usual order. It means that x increases down, and y increases across. That's strange and confusing, I initially thought there were many bugs due to that, but it seems like there aren't. That's still an issue worth addressing: code that looks wrong even if it isn't wrong is still not a good thing.

The conventional meanings of x and y would cause the indexing expressions to look like sudoku[y][x] which looks odd, using a 2D numpy array would allow proper 2D indexing. By the way, matrix should be avoided according to its documentation, prefer to use a 2D array.

Algorithmic techniques could be improved

The grid you used as an example is solved in a reasonable time, but there are grids that cause trouble. For example:

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

After solving the bug, I believe that such hard instances would be solved eventually, but it took too long for me to let it finish. There are some commonly used algorithmic techniques that would enable solving more sudokus in a reasonable amount of time:

1. Process trivial cells without waiting for them to be "picked" to be guessed. If a cell only has one possible value left (aka a Naked Single), just fill it in (but be careful to empty them again when backtracking).
2. Look at the puzzle from the point of view of "where in this row could I put the 5". If there is only one place where it can go (aka a Hidden Single), it will have to go there, so you can fill a cell. Techniques 1 and 2 can be iterated together until they stop finding cells to fill. I tried adding this to your solver, and that made it powerful enough to solve the example grid that I showed.
3. (more advanced) Pick an empty cell to guess based on how many possibilities it has left, rather than the simply the first one. Cells with a small domain should be done first. That causes conflicts to occur earlier, which in backtracking is exponentially better. This sort of subsumes the first technique (cells with only one possibility left would be picked one by one and filled with the only possible "guess"), but it still makes sense to break that out into its own thing.

Answer 2

Here are a few comments in no particular order:

• To find the time taken to solve the sudoku, you are now taking into account the time taken to declare the functions used and the time taken to print to std. Probably that is not intended.

• As per PEP-8, function names youd be spelled as answer_valid and solver.

• There is no validation on your input data. For an example, it should be fine, but if you are going to assume your sudoku is always 9x9, you should at least check that and raise a ValueError.