Return to Question

added 2 characters in body; edited tags; edited title

Source Link

edited Feb 2 at 12:19

16.4k
6
29
221

How can I optimise my recursive Recursive backtracking sudokuSudoku algorithm?

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.

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
```

How can I optimise my recursive backtracking sudoku algorithm?

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.

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
```

Recursive backtracking Sudoku algorithm

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

Source Link

asked Dec 2, 2021 at 19:48

idkDude

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.

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
```

python recursion sudoku backtracking