# How can I optimise my recursive backtracking sudoku algorithm?

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, thanks.

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
Dec 3 '21 at 2:50