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

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

Python Interview Questions eBook

Leave a Reply