Backtracking is one of the most popular algorithms used to find the solution to computational problems. Problems include crosswords, verbal arithmetic, Sudoku, and many other puzzles.
Table of Contents
Such a program starts with a first possible action at a certain position. This position (and action) can be a random one, a first in the set of all actions and/or positions, or it can be an optimal “move” in a given situation. Program then continues with applying following actions at the following positions until all “moves” were taken and the problem has been solved.
If there is no further action available and the problem is still not solved, the applied action at the last position is backtracked (removed) and another, not yet tried action is applied.
A typical problem, for which such a backtracking algorithm is perfectly suited is the knight’s tour problem. But let’s look at a similar, far more practical task, solving the Sudoku.
You are very likely familiar with solving Sudoku. You know that the goal is to fill the empty fields in the grid of 9 x 9 fields with the numbers between 1 and 9 such a way, that every line, every column, and every box (3×3 sub grid) will be filled with numbers between 1 and 9 without occurring any of them more than once.
How the backtracking algorithm will be solving Sudoku? Here is the sequence of the necessary tasks to be executed. They will create a body of the recursive solve() function:
Grid[0] and decrement the number of resolved fields. Now continue with step (task) 2, where you select the next digit (i.e. digit 5). And then follow the steps/tasks 3, 4, and so on.We can now start to write the program in Python, which will have the above-described solve() function implemented. However, there will be other functions and data required.
Before we proceed, it is recommended that have basic understanding of Python.
Let’s start with the class sudoku definition:
class sudoku:
def __init__(self):
self.attempt = 0 # will count the number of backtracking
self.field = 0 # will count the resolved fields of the Sudoku grid
self.grid = [0]*81 # Sudoku grid (list) originally empty (filled with 0)
self.rowInd = [] # will contain 9 indexes of each row
self.colInd = [] # will contain 9 indexes of each columns
self.boxInd = [] # will contain indexes of each 3×3 sub-grid
for i in range(0, 81, 9):
self.rowInd.append(range(i, i+9))
for i in range(9):
self.colInd.append(range(i, 81, 9))
for i in range(0,9,3):
self.boxInd.append(self.rowInd[i][0:3]+self.rowInd[i+1][0:3]+self.rowInd[i+2][0:3])
self.boxInd.append(self.rowInd[i][3:6]+self.rowInd[i+1][3:6]+self.rowInd[i+2][3:6])
self.boxInd.append(self.rowInd[i][6:9]+self.rowInd[i+1][6:9]+self.rowInd[i+2][6:9])
Its first method, __init__(), is an object constructor, so it is responsible for the preparation of all the necessary attributes and other variables needed for the Sudoku solution object. Their purpose is clear from their comments. Just the last action, generating the self.boxInd list items, can be confusing. So you can replace it by definition and concurrently initialization of the self.boxInd list as follows:
self.boxInd = [[0, 1, 2, 9, 10, 11, 18, 19, 20],
[3, 4, 5, 12, 13, 14, 21, 22, 23],
[6, 7, 8, 15, 16, 17, 24, 25, 26],
[27, 28, 29, 36, 37, 38, 45, 46, 47],
[30, 31, 32, 39, 40, 41, 48, 49, 50],
[33, 34, 35, 42, 43, 44, 51, 52, 53],
[54, 55, 56, 63, 64, 65, 72, 73, 74],
[57, 58, 59, 66, 67, 68, 75, 76, 77],
[60, 61, 62, 69, 70, 71, 78, 79, 80]]
We are using Python list and their associated methods for data manipulation.
The next method, __check(n, pos), is the method, which our solve() function will use to test whether the value/digit, n, can be placed in the Sudoku grid at the position, pos. If the value is already present in either the row, column or in the box associated with the position, pos, the function immediately returns False. Only if no occurrence found the function returns True.
# Checks occurrence of 'n' at the position 'pos'
def __check(self, n, pos):
current_row = pos/9
# extract the row index from the position
current_col = pos%9
# extract the column index from the position
current_box = (current_row/3)*3 + (current_col/3)
# extract the box index
for i in self.rowInd[current_row]:
if (self.grid[i] == n):
return False
for i in self.colInd[current_col]:
if (self.grid[i] == n):
return False
for i in self.boxInd[current_box]:
if (self.grid[i] == n):
return False
return True
The next method/function is the backtracking function, solve(), which we have analyzed above. This is a recursive form of the backtracking procedure. A non-recursive form exists as well, though it is not so “elegant”.
The function takes one argument, the initial grid position, though it is not necessary to provide it. The function will find the first available grid position anyway.
def solve(self, start): # Recursive back-tracking solution
i = start
while True: # Find the first available grid position
if i > 80:
i = 0
if (self.grid[i] == 0): # if position unoccupied
break # value of i can be used to access grid[i]
i += 1 # else try the next index/position
n = 0 # first value to fill field before incrementing
while(True):
n += 1 # increment current value n
if (n > 9): # if no valid value could be used
self.attempt += 1
return False
if self.__check(n, i): # if value at the field grid[i] is acceptable
self.grid[i] = n # record it
self.field += 1 # indicate another solved field
if (self.field > 80): # if all grid fields solved
print "Solution found in %d attempts." % self.attempt
return True
q = self.solve(i + 1) # call solve() with the next index value
if q == False: # if solve() failed
self.grid[i] = 0 # clear the current, i-th, grid field
self.field -= 1 # remove one solved field and continue
else: # if success
return True # return True
Our program has to access somehow the initial Sudoku setting. You could type it, value after value, or, more elegantly you can read and download it from a prepared text file. Such a text file you can manually create and save under the name “Sudoku.txt” at the same directory where this Sudoku.py program resides. In the text file, you may have several Sudoku grids, each starting with the line Grid XX, like for example:
Grid 01 008000300 016008000 000000001 103000000 490000000 002007000 005094010 600005000 700600000 Grid 02 000090030 009730000 350200000 000000104 020000006 060000000 000009060 002061000 400800070
Now you need to write a method/function, which will be able to open, read and process the data from such “Sudoku.txt” text file. Notice that after each field is updated in the initially empty sudoku grid, the self.field variable is incremented, so we will know how many remaining fields have to be solved.
def inputs(self):
self.attempt = 0 # initial number of failed attempts
self.field = 0 # resolved field of the Sudoku grid
self.grid = [0]*81 # empty Sudoku grid
word_file = 'Sudoku.txt'
try:
f = open(word_file)
word = list(f.read().splitlines()) # copy all lines from the file
f.close()
line = 0
title = "Grid"
while(True):
while title not in word[line] and line < len(word)-1:
line += 1
if line == len(word) - 1:
print title + " could not be found in the file"
break
print word[line] # find and print the next “Grid XX” text line
line += 1
if line >= len(word) - 9:
print "The Grid is not fully defined!"
break
for i in range(9): # copy entire Sudoku grid and check validity
for j in range(9):
pos = i * 9 + j
number = int(word[line + i][j])
if number == 0:
continue
if (self.__check(number, pos) == True):
self.grid[pos] = number
self.field += 1
else:
print "Value: %d at position: %d was invalid" % (number, pos)
self.result()
print "If the grid is O.K press 1, for different grid press 2: ",
ans = int(raw_input())
if ans == 1:
break
else: # prepare to start with another Sudoku grid
self.attempt = 0
self.field = 0
self.grid = [0]*81
continue
except IOError:
print("The \"Sudoku.txt\" file not found")
The last function in our program is result(), which will display the Sudoku grid values as a 9 x 9 matrix.
def result(self):
for i in range(9):
print self.grid[i*9:i*9+9]
print '\n'
Finally, we can write the main() function (though we know that this is not a function, it is a conditional execution of the code which follows). At first, we create one object of the sudoku class. In a loop, we can select and download a desired, initial Sudoku grid setting. And then solve it and display the result.
if __name__ == "__main__" :
print "Running Sudoku..."
ans = 'y'
t = sudoku()
while (ans == 'y'):
t.inputs()
t.solve(0) # call solve() with the initial grid position
t.result()
print 'Next sudoku solving? Press \'y\', otherwise press \'q\' ',
ans = raw_input()
Now run the program and select the first, Grid 01, setting. Don’t worry, your program is not dead. It can take dozens of seconds (depending on the speed of your PC) until the puzzle is solved. And then you will understand why it took so long to solve it. There were more than 12 million attempts (backtracking steps) until the successful combination of digits was found.
This “brute force” approach, while it works, can be however substantially improved! What we need to do is to imitate the human approach to solving such a puzzle. Any, though a little bit experienced Sudoku solver would not just blindly trying to fill the first empty field, nor a randomly picked out field. He/she would try to find a row, or a column or a box, which already has the most fields filled. This will minimize uncertainty in filling the empty fields.
So, let’s write such a function. It will examine each row, column and box, and will find the one with the highest number of fields already resolved. What this function will return is the list of indexes of a found row/column/box. Here is such a optimize() function:
def __optimize(self):
rowVal = []
# will keep number of resolved fields in each row
row_i = 0
colVal = []
# will keep number of resolved fields in each column
col_i = 0
boxVal = []
# will keep number of resolved fields in each box
box_i = 0
for n in range(0, 9):
max = 0
for i in self.rowInd[n]:
if self.grid[i] > 0:
max += 1
if max < 9:
rowVal.append(max)
else:
rowVal.append(-1)
max = 0
for i in self.colInd[n]:
if self.grid[i] > 0:
max += 1
if max < 9:
colVal.append(max)
else:
colVal.append(-1)
max = 0
for i in self.boxInd[n]:
if self.grid[i] > 0:
max += 1
if max < 9:
boxVal.append(max)
else:
boxVal.append(-1)
rmax = 0
for n in range(0, 9):
if rowVal[n] > rmax:
# find row with max resolved fields but not all
rmax = rowVal[n]
row_i = n
cmax = 0
for n in range(0, 9):
if colVal[n] > cmax:
# find column with max resolved fields but not all
cmax = colVal[n]
col_i = n
bmax = 0
for n in range(0, 9):
if boxVal[n] > bmax:
# find column with max resolved fields but not all
bmax = boxVal[n]
box_i = n
if rmax > cmax:
# choose between optimal raw, column or box
if rmax > bmax:
return self.rowInd[row_i]
# return list of indexes of the optimal row
else:
return self.boxInd[box_i]
# return list of indexes of the optimal box
else:
if cmax > bmax:
return self.colInd[col_i]
# return list of indexes of the optimal col
else:
return self.boxInd[box_i]
# return list of indexes of the optimal box
Please notice that when looking for a row/column/box with the maximum number of resolved fields, we must ignore those, which have already all 9 fields resolved!
And here you can see how our solve() has to be modified if using the optimize() function. Notice that solve() now doesn’t take any argument, so fix this everywhere (inside the function itself and in the main part) where the solve() function is called.
def solve(self): # Recursive back-tracking solution
ind = self.__optimize() # get optimal list of indexes
for k in range(0, 9): # find the first available field index
i = ind[k]
if (self.grid[i] == 0): # if position initially unoccupied
break # index can be used
n = 0 # first value to fill field before incrementing
...
Now run the program again and select the first Grid.
The solution will be found after 42 attempts! A very significant improvement from the previous 12 million attempts!
This is all about sudoku solver in Python. Please leave any comments or questions below.
Peter Galan is (now retired) control system designer with extensive experience in electronics, control systems and software design. He worked for many companies like ZTS, GE, Husky, Nortel, JDSU (in Canada) and previously at the Technical University in Kosice (today’s Slovakia). He holds a Ph.D. degree in Automated Control Systems and M.Eng degree in Applied Cybernetics (from Czech Technical University in Prague).