Sudoku solver with constraints and rollback in python
I realize this issue has been discussed a lot here and I read it all. However, my program doesn't work. Well, he solves light to medium diffusion lattices, but when it comes to some difficult puzzles, it seems like he is falling into an endless loop.
Again, I have read many articles on this topic, but still I cannot figure out why my program is not working. I would be very grateful if you could explain this to me.
I start off with some helper functions that work, so they don't really matter, but I'll post them - you might also give them feedback.
So, I have a list of lists with integers:
[[5, 0, 0, 7, 1, 9, 0, 0, 4],
[0, 0, 1, 0, 3, 0, 5, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 5, 9, 7, 2, 6, 4, 0],
[0, 0, 0, 6, 0, 1, 0, 0, 0],
[0, 2, 6, 3, 8, 5, 9, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 0, 5, 0, 2, 0, 0],
[8, 0, 0, 4, 9, 7, 0, 0, 6]]
First I define some helper functions
from copy import deepcopy
def nice_print(grid): #just printing tool
for line in grid:
print(line)
def box(row,col,grid): #returns a list of numbers that are in the same box
row = (row // 3)*3 #with grid[row][col]
col = (col // 3)*3
return grid[line][row:row+3:]+grid[line+1][row:row+3:]+grid[line+2][row:row+3:]
Now I need to check if there are any numbers that can be easily put into the grid
def constraints(grid):
ngrid = deepcopy(grid)
#in every cell with '0' i put a set{1..9}
for i in range(9):
for j in range(9):
if grid[i][j] == 0:
ngrid[i][j] = set(range(1,10))
#checking all conditions
for k in range(81):
for i in range(9):
for j in range(9):
if type(ngrid[i][j]) == set:
#square
if not ngrid[i][j].isdisjoint(set(box(i,j,grid))):
ngrid[i][j].difference_update(set(box(i,j,grid)))
#line
if not ngrid[i][j].isdisjoint(set(grid[i])):
ngrid[i][j].difference_update(set(grid[i]))
#row
if not ngrid[i][j].isdisjoint(set(list(zip(*grid))[j])):
ngrid[i][j].difference_update(set(list(zip(*grid))[j]))
#if there is the last remaining number i put it in the
#first grid and change the type of ngrid cell to int
if len(ngrid[i][j]) == 1:
grid[i][j] = list(ngrid[i][j])[0]
ngrid[i][j] = list(ngrid[i][j])[0]
#i parse from set&int to string
for i in range(9):
for j in range(9):
if type(ngrid[i][j])==set:
grid[i][j]=''
for item in ngrid[i][j]:
grid[i][j]+=str(item)
else:
grid[i][j]=str(grid[i][j])
return grid
Then I determine that it is - to be decided ...
def solved(grid):
ans = True
for num in range(1,10):
num=str(num)
#line
for line in grid:
if line.count(num) != 1:
ans = False
break
#row
for row in list(zip(*grid)):
if row.count(num) != 1:
ans = False
break
#square
for i in [0,3,6]:
for j in [0,3,6]:
if box(i,j,grid).count(num) != 1:
ans = False
break
return ans
Now I am defining some more helper functions
def grid_to_list(grid):
lst = []
for line in grid:
lst+=line
return lst
def parse_coordinate(s):
row = s // 9
col = s % 9
return row,col
def choice(x):
if len(x) > 1:
return len(x)
else:
return 10
def check_constraints(grid,value,row,col):
ans = True
if grid[row].count(value) > 0:
ans = False
if list(zip(*grid)).count(value) > 0:
ans = False
if box(row,col,grid).count(value) > 0:
ans = False
return ans
And finally, we get to the main part of this story - backtracking.
def explore(grid):
if solved(grid):
return True #YAY!!!
else:
while not solved(grid):
lst = grid_to_list(grid) #i parse grid to list because i need
sth = min(*lst,key=choice) #to find the cell with min length
pos = lst.index(sth)
sth = lst[pos]
row,col = parse_coordinate(pos)
for n in sth:
if check_constraints(grid,n,row,col): #if it safe to place
grid[row][col] = n #sth in grid[row][col]
if explore(grid): #i put it there and
return True #continue exploring
grid[row][col]=sth #if this doesn't work i return to the cell the previous value
return False
Some other features: bring it back together
def str_to_int(grid):
for i in range(9):
for j in range(9):
grid[i][j]=int(grid[i][j])
return grid
def solve(grid):
grid = constraints(grid)
if explore(grid):
nice_print(str_to_int(grid))
else:
print("there seems to be a problem")
So my program returns the following solution to the grid above:
[5, 6, 8, 7, 1, 9, 3, 2, 4]
[9, 7, 1, 2, 3, 4, 5, 6, 8]
[2, 3, 4, 5, 6, 8, 7, 9, 1]
[1, 8, 5, 9, 7, 2, 6, 4, 3]
[3, 9, 7, 6, 4, 1, 8, 5, 2]
[4, 2, 6, 3, 8, 5, 9, 1, 7]
[6, 1, 9, 8, 2, 3, 4, 7, 5]
[7, 4, 3, 1, 5, 6, 2, 8, 9]
[8, 5, 2, 4, 9, 7, 1, 3, 6]
But this mesh
[[0, 7, 1, 6, 8, 4, 0, 0, 0],
[0, 4, 9, 7, 0, 0, 0, 0, 0],
[5, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 0, 0, 0, 0, 5, 0, 4],
[0, 0, 0, 3, 0, 7, 0, 0, 0],
[2, 0, 3, 0, 0, 0, 0, 9, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 9],
[0, 0, 0, 0, 0, 3, 7, 2, 0],
[0, 0, 0, 4, 9, 8, 6, 1, 0]]
he cannot decide. it tries different numbers and doesn't stop :(
source to share
first, in def expl, I wouldn't have "if it was decided". this means that when it is not resolved, you will run the test twice. instead, you can simply have "return true" after the while loop. then if it is allowed it will never enter the while loop and return true.
I also suspect it pos = lst.index(sth)
might be a little slow. it is better to write a function that returns the pos
shortest list. probably not much difference if he makes comparative comparisons. I'm also surprised that choice()
testing len () on int doesn't blow up. this helper function can make this code a little cleaner:
def find_min_list(grid):
minRow = 0
minCol = 0
minLength = 10
for i in range(10):
for j in range(10):
if type(grid[i][j]) is list and len(grid[i][j]) < minLength:
minLength = len(grid[i][j])
minRow = i
minCol = j
return minRow, minCol
it is untested but has to do the trick
it's hard to diagnose what's going wrong just by looking at your code right now. I suggest trying to transfer some information to a text file. this way you can see if your researcher gets caught in an infinite loop (he may choose the same minimum set multiple times), or your solver just takes an insanely long time. if it is the latter, it is difficult to determine what even the problem is without output. Another option is to have your exploration function print out "depth" so you can see if it will either be very deep or constantly get stuck at depth 1.
EDIT: I suspect the big problem is that your researcher is VERY expensive. right now he is naively trying every combination of constraints for all unresolved parts of the list. one optimization would be to preform the "constraints" every time you try a number. which will hopefully cause your researcher not to go that deep because he will start deleting a lot of potential lists.
source to share