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?

• alexwlchan: Not an answer, but if you break up the solve() method into smaller, separate methods, you could profile the code for the 4*4 case and see where time is being lost.
• Attilio: What is the purpose of the lines: tried = tried changes = changes at the beginning of the loop? (I.e. why assign again those variables to themselves?)
• user93290: @Attilio I was using them while debugging as global variables. Thanks I'll change it.
• David Hammen: @DhruvSomani - Sometimes your code works for me, sometimes it doesn't. This is a very bad sign. It's hard to have an uninitialized (random) memory in python, but you've found a way to do so.
• 200_success: Did you read the link in my comment about what to do in that case? You can either wait for more answers or post a fresh follow-up question. (If you had more points, you could also offer a bounty.)

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

• user93290: Thanks. Could you find a way to reduce the time consumption.
• user93290: You see the function is_proper_sudoku is executed only once. The time consumption wouldn't be affected much by that.
• Caridorc: @DhruvSomani Yes, but that does not mean it should not be improved :)
• user93290: Okay! Will make the changes.
• Janne Karila: @DhruvSomani I see you reset self.map[last_y, last_x] = 0 when backtracking and lose information on which value you tried last. You should keep that information so that the next iteration tries the next value instead of starting from 1.

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)