{"id":12995,"date":"2021-02-25T03:17:46","date_gmt":"2021-02-25T03:17:46","guid":{"rendered":"https:\/\/www.askpython.com\/?p=12995"},"modified":"2022-07-21T12:54:38","modified_gmt":"2022-07-21T12:54:38","slug":"sudoku-solver-in-python","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/examples\/sudoku-solver-in-python","title":{"rendered":"Sudoku Solver in Python"},"content":{"rendered":"\n<p>Let&#8217;s build a sudoku solver in Python today! Sudoku Puzzle is a very popular puzzle that appears in the daily newspaper that attracts the attention of a lot of people. There are a lot of difficult, unsolved problems about sudoku puzzles and their generalizations which makes this puzzle interesting, specifically to a lot of mathematics lovers. <\/p>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">What is a Sudoku Puzzle?<\/h2>\n\n\n\n<p>In the Sudoku puzzle, we need to fill in every empty box with an integer between 1 and 9 in such a way that every number from 1 up to 9 appears once in every row, every column, and every one of the small 3 by 3 boxes highlighted with thick borders.<\/p>\n\n\n\n<p>The difficulty of this puzzle might vary. The more the difficulty level of Sudoku puzzles, the more challenging the research problem it becomes for computational scientists. Difficult puzzles mostly have less prescribed symbols. <\/p>\n\n\n\n<p>The Sudoku puzzles which are published for entertainment have unique solutions. A Sudoku puzzle is believed to be well-formed if it has a unique solution. Another challenging research problem is to determine how few boxes need to be filled for a Sudoku puzzle to be well-formed. Well-formed Sudoku with 17 symbols exists. It is unknown whether or not there exists a well-formed puzzle with only 16 clues. The lesser the clues, the higher the chances of multiple solutions.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Steps to solve the Sudoku Puzzle in Python<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>In this method for solving the sudoku puzzle, first, we assign the size of the 2D matrix to a variable M (M*M). <\/li><li>Then we assign the utility function (puzzle) to print the grid.  <\/li><li>Later it will assign num to the row and col. <\/li><li>If we find the same num in the same row or same column or in the specific 3*3 matrix, &#8216;false&#8217; will be returned. <\/li><li>Then we will check if we have reached the 8th row and 9th column and return true for stopping further backtracking. <\/li><li>Next, we will check if the column value becomes 9 then we move to the next row and column.<\/li><li>Further now we see if the current position of the grid has a value greater than 0, then we iterate for the next column.<\/li><li>After checking if it is a safe place, we move to the next column and then assign the num in the current (row, col) position of the grid. Later we check for the next possibility with the next column.<\/li><li>As our assumption was wrong, we discard the assigned num and then we go for the next assumption with a different num value<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Implementing the Sudoku Solver in Python<\/h2>\n\n\n\n<p>We&#8217;ll use the backtracking method to create our sudoku solver in Python. Backtracking means switching back to the previous step as soon as we determine that our current solution cannot be continued into a complete one. We use this principle of backtracking to implement the sudoku algorithm. It&#8217;s also called the brute force algorithm way to solve the sudoku puzzle.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\nM = 9\ndef puzzle(a):\n\tfor i in range(M):\n\t\tfor j in range(M):\n\t\t\tprint(a&#x5B;i]&#x5B;j],end = &quot; &quot;)\n\t\tprint()\ndef solve(grid, row, col, num):\n\tfor x in range(9):\n\t\tif grid&#x5B;row]&#x5B;x] == num:\n\t\t\treturn False\n\t\t    \n\tfor x in range(9):\n\t\tif grid&#x5B;x]&#x5B;col] == num:\n\t\t\treturn False\n\n\n\tstartRow = row - row % 3\n\tstartCol = col - col % 3\n\tfor i in range(3):\n\t\tfor j in range(3):\n\t\t\tif grid&#x5B;i + startRow]&#x5B;j + startCol] == num:\n\t\t\t\treturn False\n\treturn True\n\ndef Suduko(grid, row, col):\n\n\tif (row == M - 1 and col == M):\n\t\treturn True\n\tif col == M:\n\t\trow += 1\n\t\tcol = 0\n\tif grid&#x5B;row]&#x5B;col] &gt; 0:\n\t\treturn Suduko(grid, row, col + 1)\n\tfor num in range(1, M + 1, 1): \n\t\n\t\tif solve(grid, row, col, num):\n\t\t\n\t\t\tgrid&#x5B;row]&#x5B;col] = num\n\t\t\tif Suduko(grid, row, col + 1):\n\t\t\t\treturn True\n\t\tgrid&#x5B;row]&#x5B;col] = 0\n\treturn False\n\n&#039;&#039;&#039;0 means the cells where no value is assigned&#039;&#039;&#039;\ngrid = &#x5B;&#x5B;2, 5, 0, 0, 3, 0, 9, 0, 1],\n        &#x5B;0, 1, 0, 0, 0, 4, 0, 0, 0],\n\t&#x5B;4, 0, 7, 0, 0, 0, 2, 0, 8],\n\t&#x5B;0, 0, 5, 2, 0, 0, 0, 0, 0],\n\t&#x5B;0, 0, 0, 0, 9, 8, 1, 0, 0],\n\t&#x5B;0, 4, 0, 0, 0, 3, 0, 0, 0],\n\t&#x5B;0, 0, 0, 3, 6, 0, 0, 7, 2],\n\t&#x5B;0, 7, 0, 0, 0, 0, 0, 0, 3],\n\t&#x5B;9, 0, 3, 0, 0, 0, 6, 0, 4]]\n\nif (Suduko(grid, 0, 0)):\n\tpuzzle(grid)\nelse:\n\tprint(&quot;Solution does not exist:(&quot;)\n<\/pre><\/div>\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\n====================== RESTART: C:\/Users\/SIDDHI\/sudoku.py ===========\n2 5 8 7 3 6 9 4 1 \n6 1 9 8 2 4 3 5 7 \n4 3 7 9 1 5 2 6 8 \n3 9 5 2 7 1 4 8 6 \n7 6 2 4 9 8 1 3 5 \n8 4 1 6 5 3 7 2 9 \n1 8 4 3 6 9 5 7 2 \n5 7 6 1 4 2 8 9 3 \n9 2 3 5 8 7 6 1 4 \n<\/pre><\/div>\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>That&#8217;s all for building a sudoku solver in Python! I hope you had fun reading through the article and learning how we implemented the code.<\/p>\n\n\n\n<p><em>Psst&#8230; there&#8217;s also an easier way to build a sudoku solver in Python! <\/em><\/p>\n\n\n\n<p>You can import the sudoku <strong>py-sudoku.PyPI<\/strong> module from <a aria-label=\"https:\/\/pypi.org\/project\/py-sudoku\/ (opens in a new tab)\" href=\"https:\/\/pypi.org\/project\/py-sudoku\/\" target=\"_blank\" rel=\"noreferrer noopener\" class=\"rank-math-link\">https:\/\/pypi.org\/project\/py-sudoku\/<\/a>. It is a simple Python program that generates and solves m x n Sudoku puzzles.<\/p>\n\n\n\n<p>Pretty cool, ain&#8217;t it? Now it&#8217;s time for you to play around with sudoku puzzles!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">What&#8217;s Next?<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/www.askpython.com\/python\/examples\/easy-games-in-python\">Easy Games in Python<\/a><\/li><li><a href=\"https:\/\/www.askpython.com\/python\/examples\/number-guessing-game-command-line\">Number Guessing Game in Python<\/a><\/li><li><a href=\"https:\/\/www.askpython.com\/python-modules\/pygame-adding-background-music\">Adding Background Music to a Python Game<\/a><\/li><li><a href=\"https:\/\/www.askpython.com\/python\/examples\/rock-paper-scissors-in-python-with-ascii-hand\">Rock Paper Scissor Game in Python<\/a><\/li><li><a href=\"https:\/\/www.askpython.com\/python\/examples\/hangman-game-in-python\">Hangman Game in Python<\/a><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Resources<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Sudoku\" target=\"_blank\" rel=\"noopener\">Sudoku Wikipedia<\/a><\/li><li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Sudoku_solving_algorithms\" target=\"_blank\" rel=\"noopener\">Sudoku Solving Algorithms<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Let&#8217;s build a sudoku solver in Python today! Sudoku Puzzle is a very popular puzzle that appears in the daily newspaper that attracts the attention of a lot of people. There are a lot of difficult, unsolved problems about sudoku puzzles and their generalizations which makes this puzzle interesting, specifically to a lot of mathematics [&hellip;]<\/p>\n","protected":false},"author":22,"featured_media":13062,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-12995","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/12995","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/22"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=12995"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/12995\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/13062"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=12995"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=12995"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=12995"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}