{"id":8581,"date":"2021-05-03T15:11:14","date_gmt":"2021-05-03T09:41:14","guid":{"rendered":"https:\/\/www.csestack.org\/?p=8581"},"modified":"2021-05-03T15:11:16","modified_gmt":"2021-05-03T09:41:16","slug":"sudoku-python-backtracking","status":"publish","type":"post","link":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/","title":{"rendered":"Sudoku Solver in Python w\/ Backtracking | Explained with Example"},"content":{"rendered":"\n<p>Backtracking is one of the most popular algorithms used to find the solution to computational problems. Problems include <a href=\"https:\/\/en.wikipedia.org\/wiki\/Crosswords\" target=\"_blank\" rel=\"noreferrer noopener\">crosswords<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Verbal_arithmetic\" target=\"_blank\" rel=\"noreferrer noopener\">verbal arithmetic<\/a>, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithmics_of_sudoku\" target=\"_blank\" rel=\"noreferrer noopener\">Sudoku<\/a>, and many other puzzles.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Table of Contents<\/p>\n<label for=\"ez-toc-cssicon-toggle-item-69fd5af537c75\" class=\"ez-toc-cssicon-toggle-label\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #000000;color:#000000\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #000000;color:#000000\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-69fd5af537c75\"  aria-label=\"Toggle\" \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#How_does_Backtracking_Algorithm_Work\" >How does Backtracking Algorithm Work?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#Backtracking_Problem_Example_Sudoku\" >Backtracking Problem Example | Sudoku<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#Python_Program_to_Solve_Sudoku_Problem\" >Python Program to Solve Sudoku Problem<\/a><ul class='ez-toc-list-level-4' ><li class='ez-toc-heading-level-4'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#Optimizing_Sudoku_Solver_in_Python\" >Optimizing Sudoku Solver in Python<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h3 class=\"has-text-align-center wp-block-heading\"><span class=\"ez-toc-section\" id=\"How_does_Backtracking_Algorithm_Work\"><\/span>How does Backtracking Algorithm Work?<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>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 \u201cmove\u201d in a given situation. Program then continues with applying following actions at the following positions until all \u201cmoves\u201d were taken and the problem has been solved.<\/p>\n\n\n\n<p>\u00a0If 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.<\/p>\n\n\n\n<h3 class=\"has-text-align-center wp-block-heading\"><span class=\"ez-toc-section\" id=\"Backtracking_Problem_Example_Sudoku\"><\/span>Backtracking Problem Example | Sudoku<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>A typical problem, for which such a backtracking algorithm is perfectly suited is the <strong><em>knight&#8217;s tour<\/em><\/strong> problem. But let\u2019s look at a similar, far more practical task, solving the <strong><em>Sudoku<\/em><\/strong>.<\/p>\n\n\n\n<div class=\"wp-block-image is-style-default\"><figure class=\"aligncenter size-large\"><a href=\"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png\"><img fetchpriority=\"high\" decoding=\"async\" width=\"242\" height=\"242\" src=\"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png\" alt=\"sudoku puzzle solver in Python\" class=\"wp-image-8606\" srcset=\"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png 242w, https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle-100x100.png 100w, https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle-150x150.png 150w, https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle-75x75.png 75w, https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle-240x240.png 240w\" sizes=\"(max-width: 242px) 100vw, 242px\" \/><\/a><\/figure><\/div>\n\n\n\n<p>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&#215;3 sub grid) will be filled with numbers between 1 and 9 without occurring any of them more than once.<\/p>\n\n\n\n<p>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 <code>solve()<\/code> function:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Start with a certain grid position (for example the first upper left field, which is Grid[0]), or which is provided as an argument. \u00a0\u00a0<\/li><li>Select the digit from the allowable (1, &#8230;, 9) digits (as the first it will be digit 1).<\/li><li>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\u2019t occur in the first row, nor in the first column, nor in the first box).\u00a0<\/li><li>If the test fails, the following digit has to be tried. In our case, the first acceptable digit is 4, as this one doesn\u2019t 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.<\/li><li>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.<\/li><li>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. <\/li><li>If the solve() function returns false, it means that the digit found in this step (digit 4) can\u2019t be used at the given position (Grid[0]). So, remove the value of 4 from the <code>Grid[0]<\/code> 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.<\/li><\/ol>\n\n\n\n<h3 class=\"has-text-align-center wp-block-heading\"><span class=\"ez-toc-section\" id=\"Python_Program_to_Solve_Sudoku_Problem\"><\/span>Python Program to Solve Sudoku Problem<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>We can now start to write the program in Python, which will have the above-described <code>solve()<\/code> function implemented. However, there will be other functions and data required. <\/p>\n\n\n\n<p>Before we proceed, it is recommended that have <a href=\"https:\/\/www.csestack.org\/python\/\">basic understanding of Python<\/a>.<\/p>\n\n\n\n<p>Let\u2019s start with the class sudoku definition:\u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">class sudoku:\n    def __init__(self):\n        self.attempt = 0\t# will count the number of backtracking\n        self.field = 0    \t# will count the resolved fields of the Sudoku grid\n        self.grid = [0]*81 \t# Sudoku grid (list) originally empty (filled with 0) \n\n        self.rowInd = []\t# will contain 9 indexes of each row\n        self.colInd = []\t# will contain 9 indexes of each columns\n        self.boxInd = []\t# will contain indexes of each 3\u00d73 sub-grid\n\n        for i in range(0, 81, 9):\n            self.rowInd.append(range(i, i+9))\n\n        for i in range(9):\n            self.colInd.append(range(i, 81, 9))\n\n        for i in range(0,9,3):\nself.boxInd.append(self.rowInd[i][0:3]+self.rowInd[i+1][0:3]+self.rowInd[i+2][0:3])\nself.boxInd.append(self.rowInd[i][3:6]+self.rowInd[i+1][3:6]+self.rowInd[i+2][3:6])\nself.boxInd.append(self.rowInd[i][6:9]+self.rowInd[i+1][6:9]+self.rowInd[i+2][6:9])<\/pre>\n\n\n\n<p>Its first method, <code>__init__()<\/code>, 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 <code>self.boxInd<\/code> list items, can be confusing. So you can replace it by definition and concurrently initialization of the <code>self.boxInd<\/code> list as follows:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">self.boxInd = [[0, 1, 2, 9, 10, 11, 18, 19, 20], \n                        [3, 4, 5, 12, 13, 14, 21, 22, 23],\n                        [6, 7, 8, 15, 16, 17, 24, 25, 26],\n                        [27, 28, 29, 36, 37, 38, 45, 46, 47],\n                        [30, 31, 32, 39, 40, 41, 48, 49, 50],\n                        [33, 34, 35, 42, 43, 44, 51, 52, 53],\n                        [54, 55, 56, 63, 64, 65, 72, 73, 74],\n                        [57, 58, 59, 66, 67, 68, 75, 76, 77],\n                        [60, 61, 62, 69, 70, 71, 78, 79, 80]]<\/pre>\n\n\n\n<p>We are using <a href=\"https:\/\/www.csestack.org\/python-list\/\">Python list and their associated methods<\/a> for data manipulation.<\/p>\n\n\n\n<p>The next method, <code>__check(n, pos)<\/code>, is the method, which our <code>solve()<\/code> 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, <code>pos<\/code>, the function immediately returns <code>False<\/code>. Only if no occurrence found the function returns <code>True<\/code>.\u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">  # Checks occurrence of 'n' at the position 'pos'\n  def __check(self, n, pos):\n        current_row = pos\/9\n        # extract the row index from the position\n\n        current_col = pos%9\n        # extract the column index from the position     \n\n        current_box = (current_row\/3)*3 + (current_col\/3)\n        # extract the box index\n\n        for i in self.rowInd[current_row]:\n            if (self.grid[i] == n):\n                return False\n\n        for i in self.colInd[current_col]:\n            if (self.grid[i] == n):\n                return False\n\n        for i in self.boxInd[current_box]:\n            if (self.grid[i] == n):\n                return False\n\n        return True<\/pre>\n\n\n\n<p>The next method\/function is the backtracking function, <code>solve()<\/code>, 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 \u201celegant\u201d.\u00a0 <\/p>\n\n\n\n<p>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. \u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">def solve(self, start):    # Recursive back-tracking solution\n        i = start\n        while True:\t\t\t# Find the first available grid position\n            if i > 80:\n                i = 0\n            if (self.grid[i] == 0): # if position unoccupied\n                break            \t\t# value of i can be used to access grid[i]\n            i += 1\t\t\t  # else try the next index\/position \n            \n        n = 0       \t\t# first value to fill field before incrementing \n        while(True):     \n            n += 1              # increment current value n\n            if (n > 9):         # if no valid value could be used\n                self.attempt += 1\n                return False\n            if self.__check(n, i):  # if value at the field grid[i] is acceptable\n                self.grid[i] = n  \t\t# record it\n                self.field += 1\t\t# indicate another solved field\n                if (self.field > 80): # if all grid fields solved\n                    print \"Solution found in %d attempts.\" % self.attempt\n                    return True\n                q = self.solve(i + 1)\t# call solve() with the next index value \t\n                if q == False:\t\t# if solve() failed\n                    self.grid[i] = 0\t\t# clear the current, i-th, grid field\n                    self.field -= 1\t\t# remove one solved field and continue\n                else:\t\t\t# if success\n                    return True\t\t\t# return True<\/pre>\n\n\n\n<p>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 &#8220;Sudoku.txt&#8221; at the same directory where this <code>Sudoku.py<\/code> program resides. In the text file, you may have several Sudoku grids, each starting with the line Grid XX, like for example:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"> Grid 01\n 008000300\n 016008000\n 000000001\n 103000000\n 490000000\n 002007000\n 005094010\n 600005000\n 700600000\n\n Grid 02\n 000090030\n 009730000\n 350200000\n 000000104\n 020000006\n 060000000\n 000009060\n 002061000\n 400800070  <\/pre>\n\n\n\n<p>Now you need to write a method\/function, which will be able to open, read and process the data from such &#8220;Sudoku.txt&#8221; text file. Notice that after each field is updated in the initially empty sudoku grid, the <code>self.field<\/code> variable is incremented, so we will know how many remaining fields have to be solved. \u00a0\u00a0\u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">def inputs(self):\n        self.attempt = 0\t\t# initial number of failed attempts\t\n        self.field = 0          \t# resolved field of the Sudoku grid\n        self.grid = [0]*81      \t# empty Sudoku grid\n\n        word_file = 'Sudoku.txt'\n        try:\n            f = open(word_file)\n            word = list(f.read().splitlines())\t# copy all lines from the file\n            f.close()\n            line = 0\n            title = \"Grid\"\n            while(True):\n                while title not in word[line] and line &lt; len(word)-1:\n                    line += 1\t\n                if line == len(word) - 1:\n                    print title + \" could not be found in the file\"\n                    break\n                print word[line]\t# find and print the next \u201cGrid XX\u201d text line\n                line += 1\n                if line >= len(word) - 9:\n                    print \"The Grid is not fully defined!\"\n                    break\n                for i in range(9):\t# copy entire Sudoku grid and check validity\n                    for j in range(9):\n                        pos = i * 9 + j\n                        number = int(word[line + i][j])\n                        if number == 0:\n                            continue\n                        if (self.__check(number, pos) == True):\n                            self.grid[pos] = number\n                            self.field += 1\n                        else:\n                            print \"Value: %d at position: %d was invalid\" % (number, pos)\n                self.result()\n                print \"If the grid is O.K press 1, for different grid press 2: \",\n                ans = int(raw_input())\n                if ans == 1:\n                    break\n                else:\t# prepare to start with another Sudoku grid\n                    self.attempt = 0\n                    self.field = 0          \n                    self.grid = [0]*81      \n                    continue\n\n        except IOError:\n            print(\"The \\\"Sudoku.txt\\\" file not found\")<\/pre>\n\n\n\n<p>The last function in our program is <code>result()<\/code>, which will display the Sudoku grid values as a 9 x 9 matrix.<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">def result(self):\n        for i in range(9):\n            print self.grid[i*9:i*9+9]\n        print '\\n'<\/pre>\n\n\n\n<p>Finally, we can write the <code>main()<\/code> 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\u00a0class. In a loop, we can select and download a desired, initial Sudoku grid setting. And then solve it and display the result. \u00a0\u00a0\u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">if __name__ == \"__main__\" :\n    print \"Running Sudoku...\"\n    ans = 'y'\n    t = sudoku()\n    while (ans == 'y'):\n        t.inputs()\n        t.solve(0)\t\t# call solve() with the initial grid position\n        t.result()\n        print 'Next sudoku solving? Press \\'y\\', otherwise press \\'q\\' ',\n        ans = raw_input()\n\n<\/pre>\n\n\n\n<p>Now run the program and select the first, Grid 01, setting. Don\u2019t 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 <strong>more than 12 million attempts (backtracking steps)<\/strong> until the successful combination of digits was found.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Optimizing_Sudoku_Solver_in_Python\"><\/span>Optimizing Sudoku Solver in Python<span class=\"ez-toc-section-end\"><\/span><\/h4>\n\n\n\n<p>This \u201cbrute force\u201d 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.<\/p>\n\n\n\n<p>So, let\u2019s 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 <code>optimize()<\/code> function: \u00a0\u00a0\u00a0\u00a0\u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">def __optimize(self):\n        rowVal = [] \n        # will keep number of resolved fields in each row\n\n        row_i = 0\n\n        colVal = [] \n        # will keep number of resolved fields in each column\n\n        col_i = 0\n\n        boxVal = []\n        # will keep number of resolved fields in each box\n\n        box_i = 0\n        \n        for n in range(0, 9):\n            max = 0\n            for i in self.rowInd[n]:\n                if self.grid[i] > 0:\n                    max += 1\n            if max &lt; 9:\n                rowVal.append(max)\n            else:\n                rowVal.append(-1)\n            max = 0\n            for i in self.colInd[n]:\n                if self.grid[i] > 0:\n                    max += 1\n            if max &lt; 9:\n                colVal.append(max)\n            else:\n                colVal.append(-1)\n            max = 0\n            for i in self.boxInd[n]:\n                if self.grid[i] > 0:\n                    max += 1\n            if max &lt; 9:\n                boxVal.append(max)\n            else:\n                boxVal.append(-1)\n            \n        rmax = 0\n        for n in range(0, 9):\n            if rowVal[n] > rmax:\n                # find row with max resolved fields but not all \n                rmax = rowVal[n]\n                row_i = n\n        cmax = 0\n        for n in range(0, 9):\n            if colVal[n] > cmax: \n                # find column with max resolved fields but not all\n                cmax = colVal[n]\n                col_i = n\n        bmax = 0\n        for n in range(0, 9):\n            if boxVal[n] > bmax: \n                # find column with max resolved fields but not all\n                bmax = boxVal[n]\n                box_i = n\n                \n        if rmax > cmax:         \n            # choose between optimal raw, column or box \n            if rmax > bmax:\n                return self.rowInd[row_i]     \n                # return list of indexes of the optimal row \n            else:\n                return self.boxInd[box_i]\n                # return list of indexes of the optimal box \n        else:\n            if cmax > bmax:\n                return self.colInd[col_i]\n                # return list of indexes of the optimal col \n            else:\n                return self.boxInd[box_i]\n                # return list of indexes of the optimal box \n<\/pre>\n\n\n\n<p>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!<\/p>\n\n\n\n<p>And here you can see how our <code>solve()<\/code> has to be modified if using the <code>optimize()<\/code> function. Notice that <code>solve()<\/code> now doesn\u2019t take any argument, so fix this everywhere (inside the function itself and in the main part) where the <code>solve()<\/code> function is called. \u00a0\u00a0<\/p>\n\n\n\n<pre class=\"wp-block-syntaxhighlighter-code\">def solve(self):    # Recursive back-tracking solution\n        ind = self.__optimize()\t# get optimal list of indexes\n           \n        for k in range(0, 9):    \t# find the first available field index   \n            i = ind[k]\n            if (self.grid[i] == 0):   # if position initially unoccupied\n                break                   \t# index can be used \n\n\t n = 0       \t\t# first value to fill field before incrementing\n\t ...<\/pre>\n\n\n\n<p>Now run the program again and select the first Grid. <\/p>\n\n\n\n<p><strong>The solution will be found after 42 attempts! A very significant improvement from the previous 12 million attempts!<\/strong>\u00a0<\/p>\n\n\n\n<p>This is all about sudoku solver in Python. Please leave any comments or questions below. \u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"<p>How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73],"tags":[72],"class_list":["post-8581","post","type-post","status-publish","format-standard","hentry","category-python","tag-python"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.3 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Sudoku Solver in Python w\/ Backtracking | Explained with Example<\/title>\n<meta name=\"description\" content=\"How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.csestack.org\/sudoku-python-backtracking\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Sudoku Solver in Python w\/ Backtracking | Explained with Example\" \/>\n<meta property=\"og:description\" content=\"How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.csestack.org\/sudoku-python-backtracking\/\" \/>\n<meta property=\"og:site_name\" content=\"CSEstack\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/aniruddha.ca\" \/>\n<meta property=\"article:published_time\" content=\"2021-05-03T09:41:14+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-05-03T09:41:16+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png\" \/>\n<meta name=\"author\" content=\"Peter Galan\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@CSEStack\" \/>\n<meta name=\"twitter:site\" content=\"@ani_chaudhari\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Peter Galan\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"11 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/\"},\"author\":{\"name\":\"Peter Galan\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/133bd8a3f8b38beecbbcb58a4f256fa2\"},\"headline\":\"Sudoku Solver in Python w\\\/ Backtracking | Explained with Example\",\"datePublished\":\"2021-05-03T09:41:14+00:00\",\"dateModified\":\"2021-05-03T09:41:16+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/\"},\"wordCount\":1275,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\"},\"image\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2021\\\/05\\\/sudoku-puzzle.png\",\"keywords\":[\"Python\"],\"articleSection\":[\"Python\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/\",\"name\":\"Sudoku Solver in Python w\\\/ Backtracking | Explained with Example\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2021\\\/05\\\/sudoku-puzzle.png\",\"datePublished\":\"2021-05-03T09:41:14+00:00\",\"dateModified\":\"2021-05-03T09:41:16+00:00\",\"description\":\"How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#primaryimage\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2021\\\/05\\\/sudoku-puzzle.png\",\"contentUrl\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2021\\\/05\\\/sudoku-puzzle.png\",\"width\":242,\"height\":242,\"caption\":\"sudoku puzzle\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/sudoku-python-backtracking\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.csestack.org\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Sudoku Solver in Python w\\\/ Backtracking | Explained with Example\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#website\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/\",\"name\":\"CSEstack\",\"description\":\"Computer Science &amp; Programming Portal\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.csestack.org\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/634ef1a9c4f38b0d340c6d45fa771218\",\"name\":\"Aniruddha Chaudhari\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\",\"contentUrl\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\",\"width\":634,\"height\":634,\"caption\":\"Aniruddha Chaudhari\"},\"logo\":{\"@id\":\"https:\\\/\\\/www.csestack.org\\\/wp-content\\\/uploads\\\/2019\\\/03\\\/Aniruddha-Chaudhari.jpg\"},\"description\":\"I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.\",\"sameAs\":[\"https:\\\/\\\/www.csestack.org\",\"https:\\\/\\\/www.facebook.com\\\/aniruddha.ca\",\"pythonwithani\",\"https:\\\/\\\/www.linkedin.com\\\/in\\\/aniruddha28\\\/\",\"https:\\\/\\\/x.com\\\/ani_chaudhari\",\"https:\\\/\\\/www.youtube.com\\\/channel\\\/UCw0a__B0eJsvCujkSIfLTAA\"]},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.csestack.org\\\/#\\\/schema\\\/person\\\/133bd8a3f8b38beecbbcb58a4f256fa2\",\"name\":\"Peter Galan\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/91bef02b539ebc8866fd253761ed425f253d5dc2f87260dc88d7ca13d30f08e4?s=96&d=monsterid&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/91bef02b539ebc8866fd253761ed425f253d5dc2f87260dc88d7ca13d30f08e4?s=96&d=monsterid&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/91bef02b539ebc8866fd253761ed425f253d5dc2f87260dc88d7ca13d30f08e4?s=96&d=monsterid&r=g\",\"caption\":\"Peter Galan\"},\"description\":\"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\u2019s Slovakia). He holds a Ph.D. degree in Automated Control Systems and M.Eng degree in Applied Cybernetics (from Czech Technical University in Prague).\",\"url\":\"https:\\\/\\\/www.csestack.org\\\/author\\\/galan\\\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Sudoku Solver in Python w\/ Backtracking | Explained with Example","description":"How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/","og_locale":"en_US","og_type":"article","og_title":"Sudoku Solver in Python w\/ Backtracking | Explained with Example","og_description":"How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.","og_url":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/","og_site_name":"CSEstack","article_publisher":"https:\/\/www.facebook.com\/aniruddha.ca","article_published_time":"2021-05-03T09:41:14+00:00","article_modified_time":"2021-05-03T09:41:16+00:00","og_image":[{"url":"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png","type":"","width":"","height":""}],"author":"Peter Galan","twitter_card":"summary_large_image","twitter_creator":"@CSEStack","twitter_site":"@ani_chaudhari","twitter_misc":{"Written by":"Peter Galan","Est. reading time":"11 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#article","isPartOf":{"@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/"},"author":{"name":"Peter Galan","@id":"https:\/\/www.csestack.org\/#\/schema\/person\/133bd8a3f8b38beecbbcb58a4f256fa2"},"headline":"Sudoku Solver in Python w\/ Backtracking | Explained with Example","datePublished":"2021-05-03T09:41:14+00:00","dateModified":"2021-05-03T09:41:16+00:00","mainEntityOfPage":{"@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/"},"wordCount":1275,"commentCount":0,"publisher":{"@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218"},"image":{"@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#primaryimage"},"thumbnailUrl":"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png","keywords":["Python"],"articleSection":["Python"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.csestack.org\/sudoku-python-backtracking\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/","url":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/","name":"Sudoku Solver in Python w\/ Backtracking | Explained with Example","isPartOf":{"@id":"https:\/\/www.csestack.org\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#primaryimage"},"image":{"@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#primaryimage"},"thumbnailUrl":"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png","datePublished":"2021-05-03T09:41:14+00:00","dateModified":"2021-05-03T09:41:16+00:00","description":"How to write sudoku solver in Python with and without backtracking (brute force)? Algorithm explained with example.","breadcrumb":{"@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.csestack.org\/sudoku-python-backtracking\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#primaryimage","url":"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png","contentUrl":"https:\/\/www.csestack.org\/wp-content\/uploads\/2021\/05\/sudoku-puzzle.png","width":242,"height":242,"caption":"sudoku puzzle"},{"@type":"BreadcrumbList","@id":"https:\/\/www.csestack.org\/sudoku-python-backtracking\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.csestack.org\/"},{"@type":"ListItem","position":2,"name":"Sudoku Solver in Python w\/ Backtracking | Explained with Example"}]},{"@type":"WebSite","@id":"https:\/\/www.csestack.org\/#website","url":"https:\/\/www.csestack.org\/","name":"CSEstack","description":"Computer Science &amp; Programming Portal","publisher":{"@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.csestack.org\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/www.csestack.org\/#\/schema\/person\/634ef1a9c4f38b0d340c6d45fa771218","name":"Aniruddha Chaudhari","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg","url":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg","contentUrl":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg","width":634,"height":634,"caption":"Aniruddha Chaudhari"},"logo":{"@id":"https:\/\/www.csestack.org\/wp-content\/uploads\/2019\/03\/Aniruddha-Chaudhari.jpg"},"description":"I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.","sameAs":["https:\/\/www.csestack.org","https:\/\/www.facebook.com\/aniruddha.ca","pythonwithani","https:\/\/www.linkedin.com\/in\/aniruddha28\/","https:\/\/x.com\/ani_chaudhari","https:\/\/www.youtube.com\/channel\/UCw0a__B0eJsvCujkSIfLTAA"]},{"@type":"Person","@id":"https:\/\/www.csestack.org\/#\/schema\/person\/133bd8a3f8b38beecbbcb58a4f256fa2","name":"Peter Galan","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/91bef02b539ebc8866fd253761ed425f253d5dc2f87260dc88d7ca13d30f08e4?s=96&d=monsterid&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/91bef02b539ebc8866fd253761ed425f253d5dc2f87260dc88d7ca13d30f08e4?s=96&d=monsterid&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/91bef02b539ebc8866fd253761ed425f253d5dc2f87260dc88d7ca13d30f08e4?s=96&d=monsterid&r=g","caption":"Peter Galan"},"description":"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\u2019s Slovakia). He holds a Ph.D. degree in Automated Control Systems and M.Eng degree in Applied Cybernetics (from Czech Technical University in Prague).","url":"https:\/\/www.csestack.org\/author\/galan\/"}]}},"_links":{"self":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts\/8581","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/comments?post=8581"}],"version-history":[{"count":17,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts\/8581\/revisions"}],"predecessor-version":[{"id":8609,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/posts\/8581\/revisions\/8609"}],"wp:attachment":[{"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/media?parent=8581"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/categories?post=8581"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.csestack.org\/wp-json\/wp\/v2\/tags?post=8581"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}