I am fairly new to programming and I have recently started working on a sudoko solver, everything works fine aside from the solving algorithm itself, I used a bit of help from the internet, but because I wrote the methods myself, I can't find an accurate solution to my code, any help would be greatly appreciated!
The problem: The code runs until it cannot enter a value into one of the empty (0) index's and rather than backtracking, it just stops.
If you could let me know what i'm doing wrong, or suggest possible ways to improve the code altogether, anything would be a huge help!
My code is here:
import time
start_time = time.time()
grid = [
[7, 8, 0, 4, 0, 0, 1, 2, 0],
[6, 0, 0, 0, 7, 5, 0, 0, 9],
[0, 0, 0, 6, 0, 1, 0, 7, 8],
[0, 0, 7, 0, 4, 0, 2, 6, 0],
[0, 0, 1, 0, 5, 0, 9, 3, 0],
[9, 0, 4, 0, 6, 0, 0, 0, 5],
[0, 7, 0, 3, 0, 0, 0, 1, 2],
[1, 2, 0, 0, 0, 7, 4, 0, 0],
[0, 4, 9, 2, 0, 6, 0, 0, 7]
]
def printBoard():
print("Suduko Board")
for row in grid:
for elem in row:
print(elem, end=' ')
print()
def checkInRow(grid,row, num):
for i in range(0,9):
if(grid[row][i] == num):
return True
return False
def checkInCol(grid,col, num):
for i in range(0,9):
if(grid[i][col] == num):
return True
return False
def checkInBox(grid, row, col, num):
#This will give the starting point for the box
boxX = (row // 3) * 3
boxY = (col // 3) * 3
for i in range(3):
for j in range(3):
if((grid[boxY + j][boxX + i]) == num):
return True
return False
def findNextEmpty(grid, num):
for row in range(9):
for col in range(9):
if(grid[row][col] == num):
return row, col
return None
def checkSafe(grid, row, col, num): #Returns true if safe returns false if unsafe
return not checkInRow(grid,row,num) and not checkInCol(grid,col,num) and not checkInBox(grid,row,col,num)
#PROBLEM IS HERE \/
def solveSudoko(grid, i,j):
if not findNextEmpty(grid,0):
return True
else:
i = findNextEmpty(grid,0)[0] # Finds Row #
j = findNextEmpty(grid,0)[1] # Finds Col #
print(i, j)
for value in range(1,10):
if checkSafe(grid,i,j,value) == True:
grid[i][j] = value
printBoard()
print("--- %s seconds ---" % (time.time() - start_time))
if(solveSudoko(grid,i,j)):
return True
grid[i][j] = 0
return False
#print(str(value) + " can go in grid[" + str(i) + "]" + "[" + str(j) + "]")
printBoard()
solveSudoko(grid,0,0)
I believe the problem is that your grid is a list i.e. mutable. That means if you call solveSudoko(grid,i,j) it does not make a copy of the grid but you have just one grid in memory. So after solveSudoko ran into a problem it can't roll back since you have changed the original grid. Possible solutions are working with a non mutable data types like tuples or a bit ugly but also possible is to make a copy of the grid.
Example:
grid = [1,2,3]
def test(grid):
grid[0] = 0
test(grid)
print(grid)
---> [0,2,3]
You probably could get away with adding an import copy at the beginning of your code and replacing
if(solveSudoko(grid,i,j)):
by
if(solveSudoko(copy.deepcopy(grid),i,j)):
Example:
grid = [1,2,3]
def test(grid):
grid[0] = 0
test(copy.deepcopy(grid))
print(grid)
---> [1,2,3]
Notice that using copy.copy instead of copy.deepcopy would also work in the example since integers are immutable but with a list of lists as in your code you need copy.deepcopy.
Example:
grid = (1,2,3)
def test(grid):
grid = (0,2,3)
test(grid)
print(grid)
---> (1,2,3)
The problem with tuples is getting a new grid is not fun. I would probably use a little class managing the grid for me:
class Grid:
def __init__(self, grid):
assert type(grid) == tuple
self.grid = grid
@staticmethod
def gird_from_list(list_):
return Grid(tuple(list_[i][j] for i in range(len(list_)) for j in range(len(list_[0]))))
def __repr__(self):
return "\n".join(str(self.grid[i*9:(i+1)*9]) for i in range(9))
def set(self, i, j, value):
return Grid(tuple(value if i+j*9==k else x for k,x in enumerate(self.grid)))
tuple_grid = Grid.gird_from_list(gird)
tuple_grid2 = tuple_grid.set(8,8,0)
Here grid_from_list is just to convert your list into my format and __repr__ is giving you a nice representation as a 2d grid even though I am acutally only keeping a 1d tuple. In case you didn't know __repr__ is always called when you print an instance of the class.
Now printing tuple_grid would yield
(7, 8, 0, 4, 0, 0, 1, 2, 0)
(6, 0, 0, 0, 7, 5, 0, 0, 9)
(0, 0, 0, 6, 0, 1, 0, 7, 8)
(0, 0, 7, 0, 4, 0, 2, 6, 0)
(0, 0, 1, 0, 5, 0, 9, 3, 0)
(9, 0, 4, 0, 6, 0, 0, 0, 5)
(0, 7, 0, 3, 0, 0, 0, 1, 2)
(1, 2, 0, 0, 0, 7, 4, 0, 0)
(0, 4, 9, 2, 0, 6, 0, 0, 7)
And printing tuple_grid2 would yield
(7, 8, 0, 4, 0, 0, 1, 2, 0)
(6, 0, 0, 0, 7, 5, 0, 0, 9)
(0, 0, 0, 6, 0, 1, 0, 7, 8)
(0, 0, 7, 0, 4, 0, 2, 6, 0)
(0, 0, 1, 0, 5, 0, 9, 3, 0)
(9, 0, 4, 0, 6, 0, 0, 0, 5)
(0, 7, 0, 3, 0, 0, 0, 1, 2)
(1, 2, 0, 0, 0, 7, 4, 0, 0)
(0, 4, 9, 2, 0, 6, 0, 0, 0)
So the gird does not change when you call set but gives you an entirely new gird with the new value.