Recursive backtracking Sudoku algorithm

Question

I've tried optimising my program by removing invalid values for possible spaces instead of searching from 1-9, and by choosing values with the lowest number of empty spaces in its row and column, but these are marginal improvements and sometimes slow it down.

I've heard of constraint satisfaction being used to optimise it, and I'm not sure if that's what I've already done or something else entirely. I've attached my final function that solves the sudoku and my full code below. Any help would be greatly appreciated.

def sudoku_solver(sudoku):
    nextEmpty = lowestZero(sudoku)
    if nextEmpty == None:
        print(sudoku)
        return True
    for i in possible_values(sudoku,row,column):
        if validityCheck(sudoku,i,row,column)==True:
            sudoku[row][column]=i
            if sudoku_solver(sudoku)==True:
                return True
        sudoku[row][column]=0
    return False

And this is my full code:

import numpy as np

def row(sudoku,row):
    return sudoku[row]

def column(sudoku,column):
    columnList = []
    for i in range(0,9):
        columnList.append((sudoku[i])[column])
    return columnList

def square(sudoku,row,column):
    if row in [0,1,2]:
        row = 0
    elif row in [3,4,5]:
        row = 3
    elif row in [6,7,8]:
        row = 6
    if column in [0,1,2]:
        column = 0
    elif column in [3,4,5]:
        column = 3
    elif column in [6,7,8]:
        column = 6
    squareList = []
    for i in range(0,3):
        for j in range(0,3):
            squareList.append(sudoku[row+i][column+j])
    return squareList

def validityCheck(sudoku,number,rowNum,columnNum):
    rowList = row(sudoku,rowNum)
    columnList = column(sudoku,columnNum)
    squareList = square(sudoku,rowNum,columnNum)
    if (number in rowList):
        return False
    if (number in columnList):
        return False
    if (number in squareList):
        return False
    else:
        return True

def find_next_empty(sudoku):
    for i in range(0,9):
        for j in range(0,9):
            if sudoku[i][j]==0:
                return[i,j]

def solvedSudoku(sudoku):
    isSolved = True
    for i in range(0,9):
        for j in range(0,9):
            if sudoku[i][j]==0:
                isSolved = False
    return isSolved

def noValidInp(sudoku):
    noneValid = False
    emptyVals = findEmpty(sudoku)
    for i in emptyVals:
        for j in range(0,9):
            if validityCheck(sudoku,j,i[0],i[1]) == True:
                noneValid = True
    if noneValid == False:
        return True
    else:
        return False
    
def invalidSudoku(sudoku):
    for i in range(0,9):
        for j in range(0,9):
            num=sudoku[i][j]
            sudoku[i][j]=0
            if num!=0:
                if validityCheck(sudoku,num,i,j)==False:
                    return False
                else:
                    sudoku[i][j]=num
    return True

def possible_values(sudoku,rowInp,columnInp):
    inputList=[]
    rowList = row(sudoku,rowInp)
    columnList = column(sudoku,columnInp)
    squareList = square(sudoku,rowInp,columnInp)
    for i in range(1,10):
        if i not in rowList:
            inputList.append(i)
    return inputList

def zeroList(sudokuInp):
    list=[]
    for row in range(0,9):
        for column in range(0,9):
            if sudokuInp[row][column]==0:
                list.append([(row),(column)])
    return list

def nOfZeros(sudoku,rowInp,columnInp):
    zeroCount=0
    rowList=row(sudoku,rowInp)
    columnList=column(sudoku,columnInp)
    squareList=square(sudoku,rowInp,columnInp)
    for i in rowList:
        if i==0:
            zeroCount+=1
    for j in columnList:
        if j==0:
            zeroCount+=1
    return zeroCount-2

def lowestZero(sudoku):
    list=zeroList(sudoku)
    if list==[]:
        return None
    currentLowest=[0,0,81]
    for i in list:
        zeroNum=nOfZeros(sudoku,i[0],i[1])
        if zeroNum<currentLowest[2]:
            currentLowest=[i[0],i[1],zeroNum]
    return currentLowest

def sudoku_solver_ting(sudoku):
    nextEmpty = lowestZero(sudoku)
    if nextEmpty == None or nextEmpty==[]:
        return True
    for i in possible_values(sudoku,nextEmpty[0],nextEmpty[1]):
        row=nextEmpty[0]
        column=nextEmpty[1]
        if validityCheck(sudoku,i,row,column)==True:
            sudoku[row][column]=i
            if sudoku_solver_ting(sudoku)==True:
                return True
        sudoku[row][column]=0
    return False

def sudoku_solver(sudokuInp):
    if invalidSudoku(sudokuInp)==False:
        for i in range(0,9):
                for j in range(0,9):
                    sudokuInp[i][j]=-1
        return sudokuInp
    if sudoku_solver_ting(sudokuInp)==True:
        if solvedSudoku(sudokuInp)==False:
            for i in range(0,9):
                for j in range(0,9):
                    sudokuInp[i][j]=-1
        return sudokuInp
    else:
        for i in range(0,9):
            for j in range(0,9):
                sudokuInp[i][j]=-1.
        return sudokuInp

Haven't looked at your code at all, but Peter Norvig's is often worth studying. — FMc
– FMc, Commented Dec 3, 2021 at 2:50

toolic · Accepted Answer · 2025-02-02 12:20:16Z

DRY

In the square function, the if/elif code is repeated twice: once for a row, and another time for a column. You could refactor that code into a helper function, and further simplify it. For example:

def square(sudoku,row,column):
    def adjust(position):
        if position < 3:
            return 0
        elif position < 6:
            return 3
        else:
            return 6

    row = adjust(row)
    column = adjust(column)

I replaced your 2nd elif with the simpler else, assuming the row and column can only be 0-8.

In the sudoku_solver function, the nested for loops are repeated 3 times. Also, it seems like they are executed unconditionally, despite the if/else conditions. I think this function can be simplified.

Documentation

The PEP 8 style guide recommends docstrings for functions. They should describe the inputs types and return values for example.

def column(sudoku,column):
    """
    Given a column number and the puzzle,
    return a list of columns.
    """

Naming

The function named row does not convey any meaning of what the function does. Perhaps something like get_row would be more meaningful. This would also distinguish it from the variable named row

It is common practice to use plural nouns for array variables. For example, columnList would be better as columns.

PEP-8 recommends using snake_case for functions and variables. For example, validityCheck would be validity_check.

Simpler

The range call in lines like this:

for i in range(0,9):

can be simplified by omitting the start value of 0:

for i in range(9):

Efficiency

The solvedSudoku function can be more efficient. You can return from the function as soon as a 0 is found in sudoku. The function should also be renamed to comply with PEP-8, and it is common to use the is_ prefix for functions which return a boolean:

def is_solved(sudoku):
    for i in range(9):
        for j in range(9):
            if sudoku[i][j] == 0:
                return False
    return True

Note that the function is also simplified in that the isSolved variable is no longer needed.

Tools

You could run code development tools to automatically find some style issues with your code.

ruff finds things like:

Remove unused import: numpy
Undefined name findEmpty
Avoid equality comparisons to True; use if sudoku_solver_ting(sudoku): for truth checks

The black program can be used to automatically reformat the code using consistent whitespace around operators.

Stack Exchange Network

Recursive backtracking Sudoku algorithm

1 Answer 1

DRY

Documentation

Naming

Simpler

Efficiency

Tools

You must log in to answer this question.

Hot Network Questions

1 Answer 1

Documentation

Naming

Simpler

Efficiency

Tools

You must log in to answer this question.

Related