Backtracing Sudoku solver

Question

I have made a backtracking Sudoku solver in Python but it's working quite slow.

Originally, It had been working on 4 by 4 grids, which worked fine.

But now, trying to solve 9 by 9 grids takes a very long time.

I haven't found out the exact reason but I feel that there is one major flaw that is making it so time consuming, However, I could not identify it.

I have seen similar programs and they seem faster.

The main class is Sudoku, however specifically the code which solves the Sudoku is in Sudoku.solve().

The Sudoku array is a NumPy array.

import numpy
def is_proper_sudoku(iterable):
    count = {}
    for val in iterable:
        if val in count.keys():
            count[val] += 1
        else:
            count[val] = 1
    for var in count.keys():
        if var != 0 and count[var] > 1:
            return False
    return True

# CLASSES
class Sudoku:
    def __init__(self, size):
        self.size = size #Size for future use

        map_list = [[0 for val in range(size**2)] for val in range(size**2)]
        self.map = numpy.array(map_list, numpy.int8) #Sudoku Body

        self.empty = [(each_y, each_x) for each_y in range(size**2) for each_x in range(size**2)]

        self.strides = self.map.itemsize * numpy.array([size**4, size, size**2, 1])

        self.bulge_blocks = numpy.lib.stride_tricks.as_strided(self.map, (size, size, size, size), self.strides)
        self.blocks = numpy.array([row.flatten() for row in self.bulge_blocks]).reshape(size, size, size**2) #Defining Blocks

    def solve(self): #https://en.wikipedia.org/wiki/Sudoku_solving_algorithms

        if not self.check_valid:
            return False

        y, x = 0, 0 #Setting the starting position.

        done = False

        global tried, changes

        tried = [] #Stores the not working:(<y location>, <x location>, <inserted_value>, <arrray_string>) #inserted_value or then_array
        changes = [] #All Changes: Tuples: (<last y location>, <last x location>, <last value>)

        while not done: #Looping

            if self.map[y, x] == 0: #Making sure that the space is empty

                self.update_blocks()

                for num in range(1, self.size**2+1): #All the possible numbers
                    #print()
                    #print('Not in tried?', not (y, x, num, self.map.dumps()) in tried)
                    print((y, x, num))

                    if num not in self.map[y] and num not in self.map.T[x] and\
                            num not in self.blocks[y//self.size, x//self.size]\
                            and not (y, x, num, self.map.dumps()) in tried: #Checking if no numbers that make it invalid

                        #print('Making the right way', self.map[y, x], 'at', y, x, 'Val: ', num)

                        tried.append((y, x, num, self.map.dumps())) #For future reference       
                        changes.append((y, x)) #You need to maintain a record


                        self.map[y, x] = num #Changing

                        break

                    else:
                        #print(num, 'Not Valid at', y, x)

                        map_string = self.map.dumps()

                        # HERE'S THE CHANGE
                        if (y, x, num, map_string) in tried and num == self.size**2:
                            try:
                                last_y, last_x = changes.pop()
                                self.map[last_y, last_x] = 0
                                y, x = last_y, last_x
                                #print('Making the wrong way', self.map[y, x], 'at', last_y, last_x, 'Val: ', 0)
                            except IndexError:
                                return False

                            self.update_blocks()

                        else:
                            tried.append((y, x, num, self.map.dumps())) #For future reference
                            continue

            else:
                if y == (self.size**2)-1 and x == (self.size**2)-1:
                    self.solved = self.map
                    break                

                elif x < (self.size**2)-1:
                    x = x + 1

                elif x == (self.size**2)-1:
                    y = y + 1
                    x = 0

                print('Going over to change the location to', y, x)


    def check_valid(self):
        for major_array in [self.map, self.map.T]:
            for sub_array in major_array:
                if not is_proper_sudoku(sub_array):
                    return False
        return True

    def update_blocks(self):
        self.bulge_blocks = numpy.lib.stride_tricks.as_strided(self.map, (self.size, self.size, self.size, self.size), self.strides)
        self.blocks = numpy.array([row.flatten() for row in self.bulge_blocks]).reshape(self.size, self.size, self.size**2) #Redefining Blocks 


    def __str__(self):
        return(str(self.map))

main = Sudoku(3)
##print(main)
##print()
##main.solve()
##print()
##print(main)

I think I have the error in the program. I think that I should start with the cell which has the least possibilities. This might reduce the running time of the program. Can you implement that idea in the program? I have no idea how to do so?

Answer 1

Function calling bug

if not self.check_valid:
        return False

You omitted the parenthesis, this means you are talking about the value of the function object, that is always true. So this check is basically jumped.

The fix is:

if not self.check_valid():
        return False

Usage of built-ins : Counter and all

The definition of is_proper_sudoku that you use feels low-level as you re-invent the Counter and all built-ins:

def is_proper_sudoku(iterable):
    count = {}
    for val in iterable:
        if val in count.keys():
            count[val] += 1
        else:
            count[val] = 1
    for var in count.keys():
        if var != 0 and count[var] > 1:
            return False
    return True

You could write that as:

def is_proper_sudoku(iterable):
    count = collections.Counter(iterable)
    return all(not (var != 0 and count[var] > 1) for var in count.keys())

Answer 2

I made some improvements in the program but it is still not efficient enough to solve the program.

import numpy

# CLASSES
class Sudoku:
    def __init__(self, size):
        self.size = size

        self.map = numpy.zeros((self.size**2, self.size**2)).astype(numpy.int8) #Sudoku Body

        self.strides = self.map.itemsize * numpy.array([size**4, size, size**2, 1])

        self.loops = 0
        self.backs = 0

    def solve(self): #https://en.wikipedia.org/wiki/Sudoku_solving_algorithms     
        y, x = 0, 0 #Setting the starting position.
        num = 1



        changes = [] #All Changes: Tuples: (<last y location>, <last x location>, <inserted value>)

        while True: #Looping
            print(self)

            self.loops += 1

            self.update_blocks()

            if num not in self.map[y] and num not in self.map.T[x] and\
                    num not in self.blocks[y//self.size, x//self.size]: #Checking if no numbers that make it invalid

                changes.append((y, x, num)) #Appending the movements to changes

                self.map[y, x] = num #Changing

                if y == (self.size**2)-1 and x == (self.size**2)-1:
                    break                

                elif x < (self.size**2)-1:
                    x = x + 1

                elif x == (self.size**2)-1:
                    y = y + 1
                    x = 0

                num = 1
                continue

            else:
                if num == self.size**2:
                    self.map[y, x] = 0

                    last_y, last_x, last_value = changes.pop()

                    while last_value == self.size**2:
                        self.map[last_y, last_x] = last_value
                        last_y, last_x, last_value = changes.pop()

                    self.map[last_y, last_x] = 0

                    y, x = last_y, last_x

                    num = last_value + 1

                    self.backs += 1

                else:
                    num += 1
                    continue

    def unsolve(self):
        self.map = numpy.zeros((self.size**2, self.size**2)).astype(numpy.int8)


    def update_blocks(self):
        self.bulge_blocks = numpy.lib.stride_tricks.as_strided(self.map, (self.size, self.size, self.size, self.size), self.strides)
        self.blocks = numpy.array([row.flatten() for row in self.bulge_blocks]).reshape(self.size, self.size, self.size**2) #Redefining Blocks 


    def __str__(self):
        return(str(self.map))


main = Sudoku(2)

##print(main)
##print()
##main.solve()
##print()
##print(main)