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

• FMc: Haven't looked at your code at all, but Peter Norvig's is often worth studying.

Answer 1

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.