{"id":223,"date":"2013-05-11T00:41:23","date_gmt":"2013-05-11T00:41:23","guid":{"rendered":"http:\/\/96.126.106.214\/?p=223"},"modified":"2023-11-26T01:03:13","modified_gmt":"2023-11-26T01:03:13","slug":"sudoku-solver-in-python","status":"publish","type":"post","link":"https:\/\/codingismycraft.blog\/index.php\/2013\/05\/11\/sudoku-solver-in-python\/","title":{"rendered":"Sudoku Solver in Python"},"content":{"rendered":"

A great way to learn a new language is to simulate a game using it. Implementing a solution for something that seems so simple as a black jack game or texas holdem usually presents enough of a challenge to at least get the feeling of the language.<\/p>\n

Sudoku seemed like interesting puzzle to me when stacked in a NYC subway wagon I was watching the guy next to me scribbling numbers on his paper trying to solve it. It got my attention, but I admit that after solving a couple of them later that night, I quickly lost my interest to it. I guess us developers we are more interested in general solutions as opposed to repeating the same thinking process over and over solving the same problem with different parameters.<\/p>\n

So, it was more natural for me to write a simple Sudoku Solver in Python program something that this wonderful language allowed me to implement a relatively brutal solution very quickly in a matter of an hour or two! If I have time I will re-implement it using a more sophisticated algorithm but even this one seems to be reasonably fast…<\/p>\n

If you are interested here you can see the code that you can run in any system supporting python (for ms-windows systems you might need to commend out the very first line)…<\/p>\n

Here you can see a web interface around this code that is calling the python code from a wordpress \/ php environment<\/a><\/p>\n

Please let me know if you find any bug or you have a question about the algorithm…<\/p>\n

\r\n#!\/usr\/bin\/python\r\n#!\/usr\/bin\/python\r\n\r\n# sudoku_solver.py\r\n\r\n'''\r\nYou can test the module using the following command:\r\n\r\nnosetests -v --with-doctest sudoku_solver.py\r\n\r\n>>> s = Sudoku()\r\n>>> test_values = ( (0,2,5), (0,3,3), (1,0,8), (1,7,2), (2,1,7), (2,4,1), (2,6,5), (3,0,4), (3,5,5), (3,6,3), (4,1,1), (4,4,7), (4,8,6), (5,2,3), (5,3,2), (5,7,8), (6,1,6), (6,3,5), (6,8,9), (7,2,4), (7,7,3), (8,5,9), (8,6,7))\r\n>>> for v in test_values: s.set_at(*v)\r\n>>> s.solve()\r\nTrue\r\n>>> str(s)\r\n'145327698839654127672918543496185372218473956753296481367542819984761235521839764'\r\n\r\n'''\r\n\r\nclass Cell:\r\n'''\r\nRepresents a single cell of the sudoku matrix\r\nHolds the selected value for the cell and a list\r\nwith all the possible values it can accept at any time\r\nbased in the groups that it belongs\r\n'''\r\ndef __init__(self):\r\nself.selection = None\r\nself.rewind()\r\n\r\ndef rewind(self):\r\nself.acceptable = [] if self.selection else range(1,10)\r\n\r\nclass Sudoku:\r\n'''\r\nRepresents the sudoko grid, mainting a list of all the cells\r\nallowing the user to set and get their values and to\r\nsolve it by calling the corresponding function.\r\n'''\r\n\r\n# groups :\r\n#\r\n# All the possible groups of values that need\r\n# to contain the values from 1 to 9 are defined\r\n# in the class level variable groups. Note that based\r\n# in how the game is played, we are going to have exactly\r\n# 27 groups:\r\n#\r\n# 9 groups for each horizontal line\r\n#\r\n# 9 groups for each vertical line\r\n#\r\n# 9 groups for each 3X3 box\r\n\r\ngroups = [\r\n[0, 1, 2, 3, 4, 5, 6, 7, 8],\r\n[9, 10, 11, 12, 13, 14, 15, 16, 17],\r\n[18, 19, 20, 21, 22, 23, 24, 25, 26],\r\n[27, 28, 29, 30, 31, 32, 33, 34, 35],\r\n[36, 37, 38, 39, 40, 41, 42, 43, 44],\r\n[45, 46, 47, 48, 49, 50, 51, 52, 53],\r\n[54, 55, 56, 57, 58, 59, 60, 61, 62],\r\n[63, 64, 65, 66, 67, 68, 69, 70, 71],\r\n[72, 73, 74, 75, 76, 77, 78, 79, 80],\r\n[0, 9, 18, 27, 36, 45, 54, 63, 72],\r\n[1, 10, 19, 28, 37, 46, 55, 64, 73],\r\n[2, 11, 20, 29, 38, 47, 56, 65, 74],\r\n[3, 12, 21, 30, 39, 48, 57, 66, 75],\r\n[4, 13, 22, 31, 40, 49, 58, 67, 76],\r\n[5, 14, 23, 32, 41, 50, 59, 68, 77],\r\n[6, 15, 24, 33, 42, 51, 60, 69, 78],\r\n[7, 16, 25, 34, 43, 52, 61, 70, 79],\r\n[8, 17, 26, 35, 44, 53, 62, 71, 80],\r\n[0, 1, 2, 9, 10, 11, 18, 19, 20],\r\n[3, 4, 5, 12, 13, 14, 21, 22, 23],\r\n[6, 7, 8, 15, 16, 17, 24, 25, 26],\r\n[27, 28, 29, 36, 37, 38, 45, 46, 47],\r\n[30, 31, 32, 39, 40, 41, 48, 49, 50],\r\n[33, 34, 35, 42, 43, 44, 51, 52, 53],\r\n[54, 55, 56, 63, 64, 65, 72, 73, 74],\r\n[57, 58, 59, 66, 67, 68, 75, 76, 77],\r\n[60, 61, 62, 69, 70, 71, 78, 79, 80]\r\n]\r\n\r\nROWS , COLS = 9, 9\r\n\r\ndef __init__(self):\r\n''' Initialized the list of available cells '''\r\nself.cells = [ Cell() for i in range(self.ROWS * self.COLS)]\r\n\r\ndef process_group(self, group):\r\n'''\r\nFor the passed in group it goes through all the cells\r\nremoving the acceptable values for it\r\n'''\r\ngroup_cells = [ self.cells[i] for i in group ]\r\nselected_numbers = [ cell.selection for cell in group_cells if cell.selection ]\r\nfor cell in [ c for c in group_cells if c.selection is None]:\r\nfor n in selected_numbers:\r\nif n in cell.acceptable:\r\ncell.acceptable.remove(n)\r\n\r\ndef row_col_to_flat_index(self,row,col):\r\n'''Converts a row - col to its corresponding flat list index '''\r\nreturn (row % Sudoku.ROWS) * Sudoku.ROWS + col\r\n\r\ndef set_at(self,row,col,n):\r\n'''Sets the value of the cell at row - col to n'''\r\ncell = self.cells[self.row_col_to_flat_index(row,col)]\r\ncell.selection = n\r\n\r\ndef get_at(self,row,col):\r\n'''Gets the value of the cell at row - col'''\r\ncell = self.cells[self.row_col_to_flat_index(row,col)]\r\nreturn cell.selection\r\n\r\ndef prepare_cells(self):\r\n'''\r\nGoes through all the cells assigning the accepted values\r\nthe trick is that if a cell is already assigned with a value\r\nit is assigned to no accepted values at all.\r\nYou have to understand that this method will be called in a\r\nrecourive manner until a solution is found\r\n'''\r\nmap( lambda cell : cell.rewind(), self.cells)\r\nmap(self.process_group, Sudoku.groups)\r\n\r\ndef found_solution(self):\r\n'''Returns true if the sudoku was solved'''\r\nreturn len([ cell for cell in self.cells if cell.selection is None ]) == 0\r\n\r\ndef solve(self):\r\n''' Will try to solve the sudoku return true or false'''\r\nif self.found_solution():\r\nreturn True\r\n\r\nself.prepare_cells()\r\n\r\nif len([ c for c in self.cells if not c.selection and len(c.acceptable) == 0 ] ) > 0:\r\nreturn False\r\n\r\nunassigned = [ c for c in self.cells if not c.selection]\r\ncell_with_min_choices = sorted(unassigned,key=lambda v: len(v.acceptable))[0]\r\n\r\nfor n in cell_with_min_choices.acceptable:\r\ncell_with_min_choices.selection = n\r\nif self.solve():\r\nreturn True\r\n\r\ncell_with_min_choices.selection = None\r\nreturn False\r\n\r\ndef print_it(self):\r\n'''Nice printout to the console'''\r\nfor row in range(Sudoku.ROWS):\r\nfor col in range(Sudoku.COLS):\r\nprint self.get_at(row,col), ' ',\r\nprint\r\n\r\ndef __str__(self):\r\ns = []\r\nfor row in range(Sudoku.ROWS):\r\nfor col in range(Sudoku.COLS):\r\ns.append(str(self.get_at(row,col)))\r\nreturn ''.join(s)\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
A great way to learn a new language is to simulate a game using it. Implementing a solution for something that seems so simple as…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-223","post","type-post","status-publish","format-standard","hentry","category-programming"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[{"id":30,"url":"https:\/\/codingismycraft.blog\/index.php\/2013\/03\/11\/python-is-great\/","url_meta":{"origin":223,"position":0},"title":"Python is great","author":"john","date":"March 11, 2013","format":false,"excerpt":"I have fallen in love with several programming languages in the past, with C++ being the most dominate of them. During the last years though, I have become a Python fan boy, trying to use it as much as I can, something that translates to use it almost everywhere except\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":279,"url":"https:\/\/codingismycraft.blog\/index.php\/2024\/10\/03\/the-challenges-of-python-migration-lessons-from-c-and-beyond\/","url_meta":{"origin":223,"position":1},"title":"The Challenges of Python Migration: Lessons from C++ and Beyond","author":"john","date":"October 3, 2024","format":false,"excerpt":"One project that confirmed the need for caution and conservatism when estimating deadlines involved migrating a massive codebase of over 4,000 Python files and 250+ open-source libraries from Python 3.6 to 3.10. What was initially seen as a straightforward task, expected to take just a few weeks, ended up consuming\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":213,"url":"https:\/\/codingismycraft.blog\/index.php\/2017\/10\/04\/adding-descriptors-to-your-python-arsenal\/","url_meta":{"origin":223,"position":2},"title":"Adding descriptors to your python arsenal","author":"john","date":"October 4, 2017","format":false,"excerpt":"Python\u00a0provides a\u00a0 rich programming paradigm providing the ability to the programmer to express his solutions in a very concise and elegant way.\u00a0 One of the python features that is not in wide use although it gives the opportunity to simplify certain pieces of code,\u00a0is the descriptor protocol which is the\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":219,"url":"https:\/\/codingismycraft.blog\/index.php\/2014\/05\/23\/python-decorators-basics\/","url_meta":{"origin":223,"position":3},"title":"Python Decorators Basics","author":"john","date":"May 23, 2014","format":false,"excerpt":"Introduction to decorators Decorators introduce a programming paradigm that is not found in statically linked languages, like C++ or Java. Taking advantage of closures and the fact that functions are first class citizens of python, we can easily change the behaviour of them adding a single line of code. If\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":217,"url":"https:\/\/codingismycraft.blog\/index.php\/2014\/05\/26\/interface-driven-programming-in-python\/","url_meta":{"origin":223,"position":4},"title":"Interface Driven Programming In Python","author":"john","date":"May 26, 2014","format":false,"excerpt":"If it looks like a duck, quacks like a duck and walks like a duck, it's a duck Probably the greatest feature of python is its dynamic nature.\u00a0 By this we mean that variable names are not bound to types and they also can be assigned at run time, this\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":211,"url":"https:\/\/codingismycraft.blog\/index.php\/2020\/07\/01\/thinking-about-algorithmic-problems\/","url_meta":{"origin":223,"position":5},"title":"Thinking about Algorithmic problems","author":"john","date":"July 1, 2020","format":false,"excerpt":"In this posting we will discuss algorithmic thinking and try to propose a way of thinking that might become helpful when trying to solve a problem that does not have an obvious solution and some level of improvisation is required. Based on my experience the three most important qualities of\u2026","rel":"","context":"In "Programming"","block_context":{"text":"Programming","link":"https:\/\/codingismycraft.blog\/index.php\/category\/programming\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/comments?post=223"}],"version-history":[{"count":1,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/223\/revisions"}],"predecessor-version":[{"id":224,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/posts\/223\/revisions\/224"}],"wp:attachment":[{"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/media?parent=223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/categories?post=223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codingismycraft.blog\/index.php\/wp-json\/wp\/v2\/tags?post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}