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
Gridand 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 = *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
# 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 = *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 = *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
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.