1
\$\begingroup\$

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
```
\$\endgroup\$
1
  • \$\begingroup\$ Haven't looked at your code at all, but Peter Norvig's is often worth studying. \$\endgroup\$
    – FMc
    Dec 3 '21 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.