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 :(

+3


source to share


1 answer


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.

+2


source







All Articles