# Backtracing Sudoku solver

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?

• 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. Dec 27, 2015 at 12:00
• 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?) Dec 27, 2015 at 14:01
• @Attilio I was using them while debugging as global variables. Thanks I'll change it.
– user93290
Dec 27, 2015 at 14:03
• @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. Dec 27, 2015 at 22:30
• 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.) Dec 30, 2015 at 8:05

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

• Thanks. Could you find a way to reduce the time consumption.
– user93290
Dec 27, 2015 at 14:31
• You see the function is_proper_sudoku is executed only once. The time consumption wouldn't be affected much by that.
– user93290
Dec 27, 2015 at 14:54
• @DhruvSomani Yes, but that does not mean it should not be improved :) Dec 27, 2015 at 14:54
• Okay! Will make the changes.
– user93290
Dec 27, 2015 at 14:55
• @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. Dec 29, 2015 at 12:56

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)