Sudoku Solver in Python w/ Backtracking | Explained with Example

Sudoku Solver in Python w/ Backtracking | Explained with Example

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.

How does Backtracking Algorithm Work?

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.

Backtracking Problem Example | Sudoku

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.

sudoku puzzle solver in Python

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:

  1. Start with a certain grid position (for example the first upper left field, which is Grid[0]), or which is provided as an argument.   
  2. Select the digit from the allowable (1, …, 9) digits (as the first it will be digit 1).
  3. Test whether the selected digit (digit 1) at the selected grid position (Grid[0]) comforts the required condition, i.e. whether the same digit doesn’t occur in the first row, nor in the first column, nor in the first box). 
  4. If the test fails, the following digit has to be tried. In our case, the first acceptable digit is 4, as this one doesn’t occur in the first row/column/box. But it can happen that none of the available digits will suit the required conditions. Then the solve() function will have to return false.
  5. Assign the successfully found digit to the grid, Increase the number of resolved fields. And if all 81 fields have already assigned their digits, the Sudoku problem is successfully solved and the function returns true.
  6. If not all fields are resolved, call the solve() function again. You can provide an argument to it, which is the following position in the Sudoku grid.
  7. If the solve() function returns false, it means that the digit found in this step (digit 4) can’t be used at the given position (Grid[0]). So, remove the value of 4 from the 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.

Python Program to Solve Sudoku Problem

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

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 
            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 program resides. In the text file, you may have several Sudoku grids, each starting with the line Grid XX, like for example:

 Grid 01

 Grid 02

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'
            f = open(word_file)
            word = list(	# copy all lines from the file
            line = 0
            title = "Grid"
                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"
                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!"
                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:
                        if (self.__check(number, pos) == True):
                            self.grid[pos] = number
                            self.field += 1
                            print "Value: %d at position: %d was invalid" % (number, pos)
                print "If the grid is O.K press 1, for different grid press 2: ",
                ans = int(raw_input())
                if ans == 1:
                else:	# prepare to start with another Sudoku grid
                    self.attempt = 0
                    self.field = 0          
                    self.grid = [0]*81      

        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.solve(0)		# call solve() with the initial grid position
        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.

Optimizing Sudoku Solver in Python

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:
            max = 0
            for i in self.colInd[n]:
                if self.grid[i] > 0:
                    max += 1
            if max < 9:
            max = 0
            for i in self.boxInd[n]:
                if self.grid[i] > 0:
                    max += 1
            if max < 9:
        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 
                return self.boxInd[box_i]
                # return list of indexes of the optimal box 
            if cmax > bmax:
                return self.colInd[col_i]
                # return list of indexes of the optimal col 
                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.  

Leave a Reply

Your email address will not be published. Required fields are marked *