Algorithm for solving Sudoku

Question

I want to write a code in python to solve a sudoku puzzle  Do you guys have any idea about a good algorithm for this purpose  I read somewhere in net about a algorithm which solves it by filling the whole box with all possible numbers  then inserts known values into the corresponding boxes From the row and coloumn of known values the known value is removed If you guys know any better algorithm than this please help me to write one  Also I am confused that how i should read the known values from the user  It is really hard to enter the values one by one through console  Any easy way for this other than using gui

User · Answer

Hi I ve blogged about writing a sudoku solver from scratch in Python and currently writing a whole series about writing a constraint programming solver in Julia  another high level but faster language  You can read the sudoku problem from a file which seems to be easier more handy than a gui or cli way  The general idea it uses is constraint programming  I use the all different   unique constraint but I coded it myself instead of using a constraint programming solver  If someone is interested   The old Python version  https   opensourc es blog sudoku The new Julia series  https   opensourc es blog constraint-solver-1

User · Answer

Here is my sudoku solver in python  It uses simple backtracking algorithm to solve the puzzle  For simplicity no input validations or fancy output is done  It s the bare minimum code which solves the problem    Algorithm   Find all legal values of a given cell For each legal value  Go recursively and try to solve the grid   Solution  It takes 9X9 grid partially filled with numbers  A cell with value 0 indicates that it is not filled    Code  def findNextCellToFill grid  i  j           for x in range i 9                   for y in range j 9                           if grid x  y     0                                  return x y         for x in range 0 9                   for y in range 0 9                           if grid x  y     0                                  return x y         return -1 -1  def isValid grid  i  j  e           rowOk   all  e    grid i  x  for x in range 9            if rowOk                  columnOk   all  e    grid x  j  for x in range 9                    if columnOk                            finding the top left x y co-ordinates of the section containing the i j cell                         secTopX  secTopY   3   i  3   3   j  3   floored quotient should be used here                           for x in range secTopX  secTopX 3                                   for y in range secTopY  secTopY 3                                           if grid x  y     e                                                  return False                         return True         return False  def solveSudoku grid  i 0  j 0           i j   findNextCellToFill grid  i  j          if i    -1                  return True         for e in range 1 10                   if isValid grid i j e                           grid i  j    e                         if solveSudoku grid  i  j                                   return True                           Undo the current cell for backtracking                         grid i  j    0         return False   Testing the code        input     5 1 7 6 0 0 0 3 4   2 8 9 0 0 4 0 0 0   3 4 6 2 0 5 0 9 0   6 0 2 0 0 0 0 1 0   0 3 8 0 0 6 0 4 7   0 0 0 0 0 0 0 0 0   0 9 0 0 0 0 0 7 8   7 0 3 4 0 0 5 6 0   0 0 0 0 0 0 0 0 0       solveSudoku input  True     input   5  1  7  6  9  8  2  3  4    2  8  9  1  3  4  7  5  6    3  4  6  2  7  5  8  9  1    6  7  2  8  4  9  3  1  5    1  3  8  5  2  6  9  4  7    9  5  4  7  1  3  6  8  2    4  9  5  3  6  2  1  7  8    7  2  3  4  8  1  5  6  9    8  6  1  9  5  7  4  2  3      The above one is very basic backtracking algorithm which is explained at many places  But the most interesting and natural of the sudoku solving strategies I came across is this one from here

User · Answer

Not gonna write full code  but I did a sudoku solver a long time ago  I found that it didn t always solve it  the thing people do when they have a newspaper is incomplete    but now think I know how to do it    Setup  for each square  have a set of flags for each number showing the allowed numbers  Crossing out  just like when people on the train are solving it on paper  you can iteratively cross out known numbers  Any square left with just one number will trigger another crossing out  This will either result in solving the whole puzzle  or it will run out of triggers  This is where I stalled last time  Permutations  there s only 9    362880 ways to arrange 9 numbers  easily precomputed on a modern system  All of the rows  columns  and 3x3 squares must be one of these permutations  Once you have a bunch of numbers in there  you can do what you did with the crossing out  For each row column 3x3  you can cross out 1 9 of the 9  permutations if you have one number  1  8 9  if you have 2  and so forth  Cross permutations  Now you have a bunch of rows and columns with sets of potential permutations  But there s another constraint  once you set a row  the columns and 3x3s are vastly reduced in what they might be  You can do a tree search from here to find a solution

User · Answer

I also wrote a Sudoku solver in Python  It is a backtracking algorithm too  but I wanted to share my implementation as well   Backtracking can be fast enough given that it is moving within the constraints and is choosing cells wisely  You might also want to check out my answer in this thread about optimizing the algorithm  But here I will focus on the algorithm and code itself   The gist of the algorithm is to start iterating the grid and making decisions what to do - populate a cell  or try another digit for the same cell  or blank out a cell and move back to the previous cell  etc  It s important to note that there is no deterministic way to know how many steps or iterations you will need to solve the puzzle  Therefore  you really have two options - to use a while loop or to use recursion  Both of them can continue iterating until a solution is found or until a lack of solution is proven  The advantage of the recursion is that it is capable of branching out and generally supports more complex logics and algorithms  but the disadvantage is that it is more difficult to implement and often tricky to debug  For my implementation of the backtracking I have used a while loop because no branching is needed  the algorithm searches in a single-threaded linear fashion   The logic goes like this   While True   main iterations    If all blank cells have been iterated and the last blank cell iterated doesn t have any remaining digits to be tried - stop here because there is no solution  If there are no blank cells validate the grid  If the grid is valid stop here and return the solution  If there are blank cells choose the next cell  If that cell has at least on possible digit  assign it and continue to the next main iteration  If there is at least one remaining choice for the current cell and there are no blank cells or all blank cells have been iterated  assign the remaining choice and continue to the next main iteration  If none of the above is true  then it is time to backtrack  Blank out the current cell and enter the below loop    While True   backtrack iterations    If there are no more cells to backtrack to - stop here because there is no solution  Select the previous cell according to the backtracking history  If the cell doesn t have any choices left  blank out the cell and continue to the next backtrack iteration  Assign the next available digit to the current cell  break out from backtracking and return to the main iterations    Some features of the algorithm    it keeps a record of the visited cells in the same order so that it can backtrack at any time it keeps a record of choices for each cell so that it doesn t try the same digit for the same cell twice the available choices for a cell are always within the Sudoku constraints  row  column and 3x3 quadrant  this particular implementation has a few different methods of choosing the next cell and the next digit depending on input parameters  more info in the optimization thread  if given a blank grid  then it will generate a valid Sudoku puzzle  use with optimization parameter  C  in order to generate random grid every time  if given a solved grid it will recognize it and print a message   The full code is   import random  math  time  class Sudoku      def   init    self   g               self  input grid        store a copy of the original input grid for later use         self grid        this is the main grid that will be iterated         for i in  g    copy the nested lists by value  otherwise Python keeps the reference for the nested lists             self  input grid append  i                  self grid append  i           self empty cells   set     set of all currently empty cells  by index number from left to right  top to bottom      self empty cells initial   set     this will be used to compare against the current set of empty cells in order to determine if all cells have been iterated     self current cell   None   used for iterating     self current choice   0   used for iterating     self history        list of visited cells for backtracking     self choices        dictionary of sets of currently available digits for each cell     self nextCellWeights        a dictionary that contains weights for all cells  used when making a choice of next cell     self nextCellWeights 1   lambda x  None   the first function that will be called to assign weights     self nextCellWeights 2   lambda x  None   the second function that will be called to assign weights     self nextChoiceWeights        a dictionary that contains weights for all choices  used when selecting the next choice     self nextChoiceWeights 1   lambda x  None   the first function that will be called to assign weights     self nextChoiceWeights 2   lambda x  None   the second function that will be called to assign weights      self search space   1   the number of possible combinations among the empty cells only  for information purpose only     self iterations   0   number of main iterations  for information purpose only     self iterations backtrack   0   number of backtrack iterations  for information purpose only      self digit heuristic     1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0     store the number of times each digit is used in order to choose the ones that are least most used  parameter  3  and  4      self centerWeights        a dictionary of the distances for each cell from the center of the grid  calculated only once at the beginning        populate centerWeights by using Pythagorean theorem     for id in range  81            row   id    9         col   id   9         self centerWeights  id     int  round  100   math sqrt   row-4   2    col-4   2                for debugging purposes     def dump  self   custom text   file object             custom text       cell      choice      choices      empty      history      grid     n  format              self current cell  self current choice  self choices  self empty cells  self history  self grid            file object write   custom text          to be called before each solve of the grid     def reset  self            self grid              for i in self  input grid              self grid append  i               self empty cells   set           self empty cells initial   set           self current cell   None         self current choice   0         self history              self choices               self nextCellWeights              self nextCellWeights 1   lambda x  None         self nextCellWeights 2   lambda x  None         self nextChoiceWeights              self nextChoiceWeights 1   lambda x  None         self nextChoiceWeights 2   lambda x  None          self search space   1         self iterations   0         self iterations backtrack   0          self digit heuristic     1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0        def validate  self              validate all rows         for x in range 9               digit count     0 1  1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0               for y in range 9                   digit count  self grid  x    y        1             for i in digit count                  if digit count  i      1                      return False            validate all columns         for x in range 9               digit count     0 1  1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0               for y in range 9                   digit count  self grid  y    x        1             for i in digit count                  if digit count  i      1                      return False            validate all 3x3 quadrants         def validate quadrant   grid  from row  to row  from col  to col                digit count     0 1  1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0               for x in range  from row  to row   1                    for y in range  from col  to col   1                        digit count   grid  x    y        1             for i in digit count                  if digit count  i      1                      return False             return True          for x in range  0  7  3                for y in range  0  7  3                    if not validate quadrant  self grid  x  x 2  y  y 2                        return False         return True      def setCell  self   id   value            row    id    9         col    id   9         self grid  row    col      value      def getCell  self   id            row    id    9         col    id   9         return self grid  row    col          returns a set of IDs of all blank cells that are related to the given one  related means from the same row  column or quadrant     def getRelatedBlankCells  self   id            result   set           row    id    9         col    id   9          for i in range  9                if self grid  row    i      0  result add  row   9   i           for i in range  9                if self grid  i    col      0  result add  i   9   col           for x in range   row  3  3   row  3  3   3                for y in range   col  3  3   col  3  3   3                    if self grid  x    y      0  result add  x   9   y            return set  result     return by value        get the next cell to iterate     def getNextCell  self            self nextCellWeights              for id in self empty cells              self nextCellWeights  id     0          self nextCellWeights 1  1000     these two functions will always be called  but behind them will be a different weight function depending on the optimization parameters provided         self nextCellWeights 2  1            return min  self nextCellWeights  key   self nextCellWeights get        def nextCellWeights A  self   factor      the first cell from left to right  from top to bottom         for id in self nextCellWeights              self nextCellWeights  id      id    factor      def nextCellWeights B  self   factor      the first cell from right to left  from bottom to top         self nextCellWeights A   factor   -1        def nextCellWeights C  self   factor      a randomly chosen cell         for id in self nextCellWeights              self nextCellWeights  id      random randint  0  999      factor      def nextCellWeights D  self   factor      the closest cell to the center of the grid         for id in self nextCellWeights              self nextCellWeights  id      self centerWeights  id      factor      def nextCellWeights E  self   factor      the cell that currently has the fewest choices available         for id in self nextCellWeights              self nextCellWeights  id      len  self getChoices  id        factor      def nextCellWeights F  self   factor      the cell that currently has the most choices available         self nextCellWeights E   factor   -1        def nextCellWeights G  self   factor      the cell that has the fewest blank related cells         for id in self nextCellWeights              self nextCellWeights  id      len  self getRelatedBlankCells  id        factor      def nextCellWeights H  self   factor      the cell that has the most blank related cells         self nextCellWeights G   factor   -1        def nextCellWeights I  self   factor      the cell that is closest to all filled cells         for id in self nextCellWeights              weight   0             for check in range  81                    if self getCell  check      0                      weight    math sqrt    id  9 - check  9    2     id 9 - check 9    2        def nextCellWeights J  self   factor      the cell that is furthest from all filled cells         self nextCellWeights I   factor   -1        def nextCellWeights K  self   factor      the cell whose related blank cells have the fewest available choices         for id in self nextCellWeights              weight   0             for id blank in self getRelatedBlankCells  id                    weight    len  self getChoices  id blank                 self nextCellWeights  id      weight    factor      def nextCellWeights L  self   factor      the cell whose related blank cells have the most available choices         self nextCellWeights K   factor   -1            for a given cell return a set of possible digits within the Sudoku restrictions     def getChoices  self   id            available choices    1 2 3 4 5 6 7 8 9          row    id    9         col    id   9            exclude digits from the same row         for y in range  0  9                if self grid  row    y   in available choices                  available choices remove  self grid  row    y                exclude digits from the same column         for x in range  0  9                if self grid  x    col   in available choices                  available choices remove  self grid  x    col                exclude digits from the same quadrant         for x in range   row  3  3   row  3  3   3                for y in range   col  3  3   col  3  3   3                    if self grid  x    y   in available choices                      available choices remove  self grid  x    y              if len  available choices      0  return set           else  return set  available choices     return by value      def nextChoice  self            self nextChoiceWeights              for i in self choices  self current cell                self nextChoiceWeights  i     0          self nextChoiceWeights 1  1000           self nextChoiceWeights 2  1            self current choice   min  self nextChoiceWeights  key   self nextChoiceWeights get           self setCell  self current cell  self current choice           self choices  self current cell   remove  self current choice        def nextChoiceWeights 0  self   factor      the lowest digit         for i in self nextChoiceWeights              self nextChoiceWeights  i      i    factor      def nextChoiceWeights 1  self   factor      the highest digit         self nextChoiceWeights 0   factor   -1        def nextChoiceWeights 2  self   factor      a randomly chosen digit         for i in self nextChoiceWeights              self nextChoiceWeights  i      random randint  0  999      factor      def nextChoiceWeights 3  self   factor      heuristically  the least used digit across the board         self digit heuristic     1 0  2 0  3 0  4 0  5 0  6 0  7 0  8 0  9 0           for id in range  81                if self getCell  id      0  self digit heuristic  self getCell  id        1         for i in self nextChoiceWeights              self nextChoiceWeights  i      self digit heuristic  i      factor      def nextChoiceWeights 4  self   factor      heuristically  the most used digit across the board         self nextChoiceWeights 3   factor   -1        def nextChoiceWeights 5  self   factor      the digit that will cause related blank cells to have the least number of choices available         cell choices              for id in self getRelatedBlankCells  self current cell                cell choices  id     self getChoices  id            for c in self nextChoiceWeights              weight   0             for id in cell choices                  weight    len  cell choices  id                     if c in cell choices  id    weight -  1             self nextChoiceWeights  c      weight    factor      def nextChoiceWeights 6  self   factor      the digit that will cause related blank cells to have the most number of choices available         self nextChoiceWeights 5   factor   -1        def nextChoiceWeights 7  self   factor      the digit that is the least common available choice among related blank cells         cell choices              for id in self getRelatedBlankCells  self current cell                cell choices  id     self getChoices  id            for c in self nextChoiceWeights              weight   0             for id in cell choices                  if c in cell choices  id    weight    1             self nextChoiceWeights  c      weight    factor      def nextChoiceWeights 8  self   factor      the digit that is the most common available choice among related blank cells         self nextChoiceWeights 7   factor   -1        def nextChoiceWeights 9  self   factor      the digit that is the least common available choice across the board         cell choices              for id in range  81                if self getCell  id      0                  cell choices  id     self getChoices  id            for c in self nextChoiceWeights              weight   0             for id in cell choices                  if c in cell choices  id    weight    1             self nextChoiceWeights  c      weight    factor      def nextChoiceWeights a  self   factor      the digit that is the most common available choice across the board         self nextChoiceWeights 9   factor   -1            the main function to be called     def solve  self   nextCellMethod   nextChoiceMethod   start time   prefillSingleChoiceCells   False            s   self         s reset              initialize optimization functions based on the optimization parameters provided                     A - the first cell from left to right  from top to bottom         B - the first cell from right to left  from bottom to top         C - a randomly chosen cell         D - the closest cell to the center of the grid         E - the cell that currently has the fewest choices available         F - the cell that currently has the most choices available         G - the cell that has the fewest blank related cells         H - the cell that has the most blank related cells         I - the cell that is closest to all filled cells         J - the cell that is furthest from all filled cells         K - the cell whose related blank cells have the fewest available choices         L - the cell whose related blank cells have the most available choices                     if  nextCellMethod  0   in  ABCDEFGHIJKLMN               s nextCellWeights 1   getattr  s   nextCellWeights      nextCellMethod 0            elif  nextCellMethod  0                       s nextCellWeights 1   lambda x  None         else              print    A  Incorrect optimization parameters provided                return False          if len   nextCellMethod    gt  1              if  nextCellMethod  1   in  ABCDEFGHIJKLMN                   s nextCellWeights 2   getattr  s   nextCellWeights      nextCellMethod 1                elif  nextCellMethod  1                           s nextCellWeights 2   lambda x  None             else                  print    B  Incorrect optimization parameters provided                    return False         else              s nextCellWeights 2   lambda x  None            initialize optimization functions based on the optimization parameters provided                     0 - the lowest digit         1 - the highest digit         2 - a randomly chosen digit         3 - heuristically  the least used digit across the board         4 - heuristically  the most used digit across the board         5 - the digit that will cause related blank cells to have the least number of choices available         6 - the digit that will cause related blank cells to have the most number of choices available         7 - the digit that is the least common available choice among related blank cells         8 - the digit that is the most common available choice among related blank cells         9 - the digit that is the least common available choice across the board         a - the digit that is the most common available choice across the board                     if  nextChoiceMethod  0   in  0123456789a               s nextChoiceWeights 1   getattr  s   nextChoiceWeights      nextChoiceMethod 0            elif  nextChoiceMethod  0                       s nextChoiceWeights 1   lambda x  None         else              print    C  Incorrect optimization parameters provided                return False          if len   nextChoiceMethod    gt  1              if  nextChoiceMethod  1   in  0123456789a                   s nextChoiceWeights 2   getattr  s   nextChoiceWeights      nextChoiceMethod 1                elif  nextChoiceMethod  1                           s nextChoiceWeights 2   lambda x  None             else                  print    D  Incorrect optimization parameters provided                    return False         else              s nextChoiceWeights 2   lambda x  None            fill in all cells that have single choices only  and keep doing it until there are no left  because as soon as one cell is filled this might bring the choices down to 1 for another cell         if  prefillSingleChoiceCells    True              while True                  next   False                 for id in range  81                        if s getCell  id      0                          cell choices   s getChoices  id                           if len  cell choices      1                              c   cell choices pop                               s setCell  id  c                               next   True                 if not next  break            initialize set of empty cells         for x in range  0  9  1                for y in range  0  9  1                    if s grid  x    y      0                      s empty cells add  9 x   y           s empty cells initial   set  s empty cells     copy by value            calculate search space         for id in s empty cells              s search space    len  s getChoices  id                initialize the iteration by choosing a first cell         if len  s empty cells    lt  1              if s validate                    print   Sudoku provided is valid                     return True             else                  print   Sudoku provided is not valid                     return False         else  s current cell   s getNextCell            s choices  s current cell     s getChoices  s current cell           if len  s choices  s current cell      lt  1              print    C  Sudoku cannot be solved                 return False              start iterating the grid         while True               if time time   -  start time  gt  2 5  return False   used when doing mass tests and don t want to wait hours for an inefficient optimization to complete              s iterations    1                if all empty cells and all possible digits have been exhausted  then the Sudoku cannot be solved             if s empty cells    s empty cells initial and len  s choices  s current cell      lt  1                  print    A  Sudoku cannot be solved                     return False                if there are no empty cells  it s time to validate the Sudoku             if len  s empty cells    lt  1                  if s validate                        print   Sudoku has been solved                          print   search space is     format  self search space                         print   empty cells      iterations      backtrack iterations      format  len  self empty cells initial    self iterations  self iterations backtrack                         for i in range 9                           print  self grid i                        return True                if there are empty cells  then move to the next one             if len  s empty cells    gt  0                   s current cell   s getNextCell     get the next cell                 s history append  s current cell     add the cell to history                 s empty cells remove  s current cell     remove the cell from the empty queue                 s choices  s current cell     s getChoices  s current cell     get possible choices for the chosen cell                  if len  s choices  s current cell      gt  0    if there is at least one available digit  then choose it and move to the next iteration  otherwise the iteration continues below with a backtrack                     s nextChoice                       continue                if all empty cells have been iterated or there are no empty cells  and there are still some remaining choices  then try another choice             if len  s choices  s current cell      gt  0 and   s empty cells    s empty cells initial or len  s empty cells    lt  1                     s nextChoice                   continue                if none of the above  then we need to backtrack to a cell that was previously iterated               first  restore the current cell                s history remove  s current cell        by removing it from history             s empty cells add  s current cell        adding back to the empty queue             del s choices  s current cell        scrapping all choices             s current choice   0             s setCell  s current cell  s current choice        and blanking out the cell                   and then  backtrack to a previous cell             while True                  s iterations backtrack    1                  if len  s history    lt  1                      print    B  Sudoku cannot be solved                         return False                  s current cell   s history  -1     after getting the previous cell  do not recalculate all possible choices because we will lose the information about has been tried so far                  if len  s choices  s current cell      lt  1    backtrack until a cell is found that still has at least one unexplored choice                        s history remove  s current cell                       s empty cells add  s current cell                       s current choice   0                     del s choices  s current cell                       s setCell  s current cell  s current choice                       continue                       and when such cell is found  iterate it                 s nextChoice                   break   and break out from the backtrack iteration but will return to the main iteration   Example call using the world s hardest Sudoku as per this article http   www telegraph co uk news science science-news 9359579 Worlds-hardest-sudoku-can-you-crack-it html  hardest sudoku          8 0 0 0 0 0 0 0 0        0 0 3 6 0 0 0 0 0        0 7 0 0 9 0 2 0 0        0 5 0 0 0 7 0 0 0        0 0 0 0 4 5 7 0 0        0 0 0 1 0 0 0 3 0        0 0 1 0 0 0 0 6 8        0 0 8 5 0 0 0 1 0        0 9 0 0 0 0 4 0 0    mySudoku   Sudoku  hardest sudoku   start   time time   mySudoku solve   A    0   time time    False   print   solved in    seconds  format  time time   - start       And example output is   Sudoku has been solved  search space is 9586591201964851200000000000000000000 empty cells  60  iterations  49559  backtrack iterations  49498  8  1  2  7  5  3  6  4  9   9  4  3  6  8  2  1  7  5   6  7  5  4  9  1  2  8  3   1  5  4  2  3  7  8  9  6   3  6  9  8  4  5  7  2  1   2  8  7  1  6  9  5  3  4   5  2  1  9  7  4  3  6  8   4  3  8  5  2  6  9  1  7   7  9  6  3  1  8  4  5  2  solved in 1 1600663661956787 seconds

User · Answer

I know I m late  but this is my version  from time import perf counter  board          8  0  0  0  0  0  0  0  0        0  0  3  6  0  0  0  0  0        0  7  0  0  9  0  2  0  0        0  5  0  0  0  7  0  0  0        0  0  0  0  4  5  7  0  0        0  0  0  1  0  0  0  3  0        0  0  1  0  0  0  0  6  8        0  0  8  5  0  0  0  1  0        0  9  0  0  0  0  4  0  0      def solve bo       find   find empty bo      if not find     if find is None or False         return True     else          row  col   find      for num in range 1  10           if valid bo  num   row  col                bo row  col    num              if solve bo                   return True              bo row  col    0      return False   def valid bo  num  pos          Check row     for i in range len bo 0             if bo pos 0   i     num and pos 1     i              return False        Check column     for i in range len bo            if bo i  pos 1      num and pos 0     i              return False        Check box     box x   pos 1     3     box y   pos 0     3      for i in range box y 3  box y 3   3           for j in range box x 3  box x 3   3               if bo i  j     num and  i  j     pos                  return False      return True   def print board bo       for i in range len bo            if i   3    0              if i    0                  print  quot   -------------------------  quot               else                  print  quot   -------------------------  quot            for j in range len bo 0                 if j   3    0                  print  quot     quot   end  quot   quot                if j    8                  print bo i  j    quot    quot               else                  print bo i  j   end  quot   quot        print  quot   -------------------------  quot     def find empty bo       for i in range len bo            for j in range len bo 0                 if bo i  j     0                  return i  j    row  column      return None  print   n-------------------------------------- n    print     Unsolved Suduku  -   print board board   print   n-------------------------------------- n    t1   perf counter   solve board  t2   perf counter   print     Solved Suduku  -   print board board   print   n-------------------------------------- n    print f  TIME TAKEN    round t2-t1 3   SECONDS    print   n-------------------------------------- n    It uses backtracking  But is not coded by me  it s Tech With Tim s  That list contains the world hardest sudoku  and by implementing the timing function  the time is                               Finished in 2 838 seconds                               But with a simple sudoku puzzle like  board          7  8  0  4  0  0  1  2  0        6  0  0  0  7  5  0  0  9        0  0  0  6  0  1  0  7  8        0  0  7  0  4  0  2  6  0        0  0  1  0  5  0  9  3  0        9  0  4  0  6  0  0  0  5        0  7  0  3  0  0  0  1  2        1  2  0  0  0  7  4  0  0        0  4  9  2  0  6  0  0  7     The result is                                Finished in 0 011 seconds                               Pretty fast I can say

User · Answer

a short attempt to achieve same algorithm using backtracking   def solve sudoku        using recursion and backtracking  here we go      empties     i j  for i in range 9  for j in range 9  if sudoku i  j     0      predict   lambda i  j  set range 1 10  -set  sudoku i  j   -set  sudoku y range 1 10 3  i  3   x range 1 10 3  j  3   for y in  -1 0 1  for x in  -1 0 1   -set sudoku i  -set list zip  sudoku   j       if len empties   0 return True     gap   next iter empties       predictions   predict  gap      for i in predictions          sudoku gap 0   gap 1     i         if solve sudoku  return True         sudoku gap 0   gap 1     0     return False

User · Answer

I wrote a simple program that solved the easy ones  It took its input from a file which was just a matrix with spaces and numbers  The datastructure to solve it was just a 9 by 9 matrix of a bit mask  The bit mask would specify which numbers were still possible on a certain position  Filling in the numbers from the file would reduce the numbers in all rows columns next to each known location  When that is done you keep iterating over the matrix and reducing possible numbers  If each location has only one option left you re done  But there are some sudokus that need more work  For these ones you can just use brute force  try all remaining possible combinations until you find one that works

User · Answer

Here is a much faster solution based on hari s answer  The basic difference is that we keep a set of possible values for cells that don t have a value assigned  So when we try a new value  we only try valid values and we also propagate what this choice means for the rest of the sudoku  In the propagation step  we remove from the set of valid values for each cell the values that already appear in the row  column  or the same block  If only one number is left in the set  we know that the position  cell  has to have that value    This method is known as forward checking and look ahead  http   ktiml mff cuni cz  bartak constraints propagation html     The implementation below needs one iteration  calls of solve  while hari s implementation needs 487  Of course my code is a bit longer  The propagate method is also not optimal   import sys from copy import deepcopy  def output a       sys stdout write str a    N   9  field     5 1 7 6 0 0 0 3 4             2 8 9 0 0 4 0 0 0             3 4 6 2 0 5 0 9 0             6 0 2 0 0 0 0 1 0             0 3 8 0 0 6 0 4 7             0 0 0 0 0 0 0 0 0             0 9 0 0 0 0 0 7 8             7 0 3 4 0 0 5 6 0             0 0 0 0 0 0 0 0 0    def print field field       if not field          output  No solution           return     for i in range N           for j in range N               cell   field i  j              if cell    0 or isinstance cell  set                   output                  else                  output cell              if  j   1    3    0 and j  lt  8                  output                    if j    8                  output              output   n           if  i   1    3    0 and i  lt  8              output  - - -   - - -   - - - n    def read field           Read field into state  replace 0 with set of possible values           state   deepcopy field      for i in range N           for j in range N               cell   state i  j              if cell    0                  state i  j    set range 1 10        return state  state   read field    def done state           Are we done           for row in state          for cell in row              if isinstance cell  set                   return False     return True   def propagate step state               Propagate one step        return   A two-tuple that says whether the configuration               is solvable and whether the propagation changed               the state                       new units   False        propagate row rule     for i in range N           row   state i          values   set  x for x in row if not isinstance x  set            for j in range N               if isinstance state i  j   set                   state i  j  -  values                 if len state i  j      1                      val   state i  j  pop                       state i  j    val                     values add val                      new units   True                 elif len state i  j      0                      return False  None        propagate column rule     for j in range N           column    state x  j  for x in range N           values   set  x for x in column if not isinstance x  set            for i in range N               if isinstance state i  j   set                   state i  j  -  values                 if len state i  j      1                      val   state i  j  pop                       state i  j    val                     values add val                      new units   True                 elif len state i  j      0                      return False  None        propagate cell rule     for x in range 3           for y in range 3               values   set               for i in range 3   x  3   x   3                   for j in range 3   y  3   y   3                       cell   state i  j                      if not isinstance cell  set                           values add cell              for i in range 3   x  3   x   3                   for j in range 3   y  3   y   3                       if isinstance state i  j   set                           state i  j  -  values                         if len state i  j      1                              val   state i  j  pop                               state i  j    val                             values add val                              new units   True                         elif len state i  j      0                              return False  None      return True  new units  def propagate state           Propagate until we reach a fixpoint         while True          solvable  new unit   propagate step state          if not solvable              return False         if not new unit              return True   def solve state           Solve sudoku          solvable   propagate state       if not solvable          return None      if done state           return state      for i in range N           for j in range N               cell   state i  j              if isinstance cell  set                   for value in cell                      new state   deepcopy state                      new state i  j    value                     solved   solve new state                      if solved is not None                          return solved                 return None  print field solve state

User · Answer

Using google ortools - the following will either generate a dummy sudoku array or will solve a candidate  The code is probably more verbose than required  any feedback is appreciated  The idea is to solve a constraint-programming problem that involves  List of 81 variables with integer bounds between 1 and 9  All different constraint for row vector All different constraint for column vector All different constraint for the sub-matrices  In addition  when trying to solve existing sudoku  we add additional constraints on variables that already have assigned value  from ortools constraint solver import pywrapcp import numpy as np  def sudoku solver candidate   None       solver   pywrapcp Solver  quot Sudoku quot        variables    solver IntVar 1 9 f quot x i  quot   for i in range 81       if len candidate  gt 0          candidate   np int64 candidate          for i in range 81               val   candidate i              if val   0                  solver Add variables i     int val        def set constraints            for i in range 9                 All columns should be different             q  variables j  for j in list range i 81 9                solver Add solver AllDifferent q                 All rows should be different             q2  variables j  for j in list range i 9  i 1  9                solver Add solver AllDifferent q2                 All values in the sub-matrix should be different             a   list range 81               sub blocks   a 3 i 3  i 9  9    a 3 i 1 3  i 9  1 9    a 3 i 2 3  i 9  2 9              q3    variables j  for j in sub blocks              solver Add solver AllDifferent q3                    set constraints       db   solver Phase variables  solver CHOOSE FIRST UNBOUND  solver ASSIGN MIN VALUE      solver NewSearch db               results store         num solutions  0     total solutions   5     while solver NextSolution   and num solutions lt total solutions          results    j Value   for j in variables          results store append results          num solutions   1              return results store  Solve the following sudoku candidate   np array  0  2  0  4  5  6  0  8  0  0  5  6  7  8  9  0  0  3  7  0  9  0         2  0  4  5  6  2  0  1  5  0  4  8  9  7  5  0  4  8  0  0  0  0         0  3  1  0  6  4  5  9  7  0  0  0  5  0  7  8  3  1  2  8  0  7         0  1  0  5  0  4  9  7  8  0  3  0  0  0  5     results store   sudoku solver candidate

User · Answer

There are four steps to solve a sudoku puzzle    Identify all possibilities for each cell  getting from the row  column and box  and try to develop a possible matrix  2 Check for double pair  if it exists then remove these two values from all the cells in that row column box  wherever the pair exists If any cell is having single possiblity then assign that run step 1 again Check for each cell with each row  column and box  If the cell has one value which does not belong in the other possible values then assign that value to that cell  run step 1 again If the sudoku is still not solved  then we need to start the following assumption  Assume the first possible value and assign  Then run step 1   3 If still not solved then do it for next possible value and run it in recursion  If the sudoku is still not solved  then we need to start the following assumption  Assume the first possible value and assign  Then run step 1   3   If still not solved then do it for next possible value and run it in recursion   import math import sys   def is solved l       for x  i in enumerate l           for y  j in enumerate i               if j    0                    Incomplete                 return None             for p in range 9                   if p    x and j    l p  y                         Error                     print  horizontal issue detected     x  y                       return False                 if p    y and j    l x  p                         Error                     print  vertical issue detected     x  y                       return False             i n  j n   get box start coordinate x  y              for  i  j  in   i  j  for p in range i n  i n   3  for q in range j n  j n   3                             if  p  q      x  y  and j    l p  q                          Error                 print  box issue detected     x  y                   return False       Solved     return True   def is valid l       for x  i in enumerate l           for y  j in enumerate i               if j    0                  for p in range 9                       if p    x and j    l p  y                             Error                         print  horizontal issue detected     x  y                           return False                     if p    y and j    l x  p                             Error                         print  vertical issue detected     x  y                           return False                 i n  j n   get box start coordinate x  y                  for  i  j  in   i  j  for p in range i n  i n   3  for q in range j n  j n   3                                 if  p  q      x  y  and j    l p  q                              Error                     print  box issue detected     x  y                       return False       Solved     return True   def get box start coordinate x  y       return 3   int math floor x 3    3   int math floor y 3     def get horizontal x  y  l       return  l x  i  for i in range 9  if l x  i   gt  0    def get vertical x  y  l       return  l i  y  for i in range 9  if l i  y   gt  0    def get box x  y  l       existing          i n  j n   get box start coordinate x  y      for  i  j  in   i  j  for i in range i n  i n   3  for j in range j n  j n   3            existing append l i  j   if l i  j   gt  0 else None     return existing   def detect and simplify double pairs l  pl       for  i  j  in   i  j  for i in range 9  for j in range 9  if len pl i  j      2           temp pair   pl i  j          for p in  p for p in range j 1  9  if len pl i  p      2 and len set pl i  p    amp  set temp pair      2               for q in  q for q in range 9  if q    j and q    p                   pl i  q    list set pl i  q   - set temp pair                   if len pl i  q      1                      l i  q    pl i  q  pop                       return True         for p in  p for p in range i 1  9  if len pl p  j      2 and len set pl p  j    amp  set temp pair      2               for q in  q for q in range 9  if q    i and p    q                   pl q  j    list set pl q  j   - set temp pair                   if len pl q  j      1                      l q  j    pl q  j  pop                       return True         i n  j n   get box start coordinate i  j          for  a  b  in   a  b  for a in range i n  i n 3  for b in range j n  j n 3                         if  a  b      i  j  and len pl a  b      2 and len set pl a  b    amp  set temp pair      2               for  c  d  in   c  d  for c in range i n  i n 3  for d in range j n  j n 3                             if  c  d      a  b  and  c  d      i  j                    pl c  d    list set pl c  d   - set temp pair                   if len pl c  d      1                      l c  d    pl c  d  pop                       return True     return False   def update unique horizontal x  y  l  pl       tl   pl x  y      for i in  i for i in range 9  if i    y           tl   list set tl  - set pl x  i        if len tl     1          l x  y    tl pop           return True     return False   def update unique vertical x  y  l  pl       tl   pl x  y      for i in  i for i in range 9  if i    x           tl   list set tl  - set pl i  y        if len tl     1          l x  y    tl pop           return True     return False   def update unique box x  y  l  pl       tl   pl x  y      i n  j n   get box start coordinate x  y      for  i  j  in   i  j  for i in range i n  i n 3  for j in range j n  j n 3  if  i  j      x  y            tl   list set tl  - set pl i  j        if len tl     1          l x  y    tl pop           return True     return False   def find and place possibles l       while True          pl   populate possibles l          if pl    False              return pl   def populate possibles l       pl       for j in i  for i in l      for  i  j  in   i  j  for i in range 9  for j in range 9  if l i  j     0           p   list set range 1  10   - set get horizontal i  j  l                                             get vertical i  j  l    get box i  j  l            if len p     1              l i  j    p pop               return False         else              pl i  j    p     return pl   def find and remove uniques l  pl       for  i  j  in   i  j  for i in range 9  for j in range 9  if l i  j     0           if update unique horizontal i  j  l  pl     True              return True         if update unique vertical i  j  l  pl     True              return True         if update unique box i  j  l  pl     True              return True     return False   def try with possibilities l       while True          improv   False         pl   find and place possibles l          if detect and simplify double pairs                  l  pl     True              continue         if find and remove uniques                  l  pl     True              continue         if improv    False              break     return pl   def get first conflict pl       for  x  y  in   x  y  for x  i in enumerate pl  for y  j in enumerate i  if len j   gt  0           return  x  y    def get deep copy l       new list    i    for i in l      return new list   def run assumption l  pl       try          c   get first conflict pl          fl   pl c 0                    c 1             print  Assumption Index      c            print  Assumption List      fl      except          return False     for i in fl          new list   get deep copy l          new list c 0   c 1     i         new pl   try with possibilities new list          is done   is solved new list          if is done    True              l   new list             return new list         else              new list   run assumption new list  new pl              if new list    False and is solved new list     True                  return new list     return False   if   name         main         l              0  0  0  0  0  0  0  0  0            0  0  8  0  0  0  0  4  0            0  0  0  0  0  0  0  0  0            0  0  0  0  0  6  0  0  0            0  0  0  0  0  0  0  0  0            0  0  0  0  0  0  0  0  0            2  0  0  0  0  0  0  0  0            0  0  0  0  0  0  2  0  0            0  0  0  0  0  0  0  0  0              This puzzle copied from Hacked rank test case     if is valid l     False          print  Sorry  Invalid            sys exit       pl   try with possibilities l      is done   is solved l      if is done    True          for i in l              print i          print  Solved              sys exit        print  Unable to solve by traditional ways       print  Starting assumption based solving       new list   run assumption l  pl      if new list    False          is done   is solved new list          print  is solved   -    is done          for i in new list              print i          if is done    True              print  Solved    with assumptions            sys exit       print l      print  Sorry  No Solution  Need to fix the valid function          sys exit

[python] Algorithm for solving Sudoku

Examples related to python

Examples related to algorithm

Examples related to sudoku