ASCIIMath creating images

Thursday, May 29, 2014

A Sudoku solver in Python

I'm not that great at Python yet.  But practice makes perfect, so just to see if I can do it, I wrote this Sudoku solver in Python (needs v3).  The algorithm is my own though I don't think it is very (or at all) novel, just actually looking for other solvers would spoil the fun!

The implementation is also probably overly byzantine, mostly due to the way the state is stored.  This is done as follows: at the bottom is a list of states for each symbol in a given cell, the states are one of "this symbol is possible here", "this symbol is impossible here", "this symbol is here (set by specification)", and "this symbol is here (set by the solver)".  The last two are really the same for the algorithm but eased my own understanding and debugging - but this adds lines to the code since both states need to be checked in some cases.

The set of states for each cell are then bunched into a list for each row, and then all rows are bunched into a list.  So, to find out if the "4" is possible in column 3, row 7, check if state[3][7][4] is set to 0.

The solver algorithm can now be simply described by three steps: 
  1. After setting a cell to some symbol, mark the same symbol as being impossible in cells in the same groups (row, column box). 
  2. For all cells, check if there is the case where a single symbol is not impossible.  If so, set the cell to that symbol.
  3. For all groups, check where within a group a given symbol is possible in only one cell.  If so, assign that symbol to the open cell.
If in either of step 2 or 3 a cell was set to some symbol, restart from one.  Repeat this until neither of the two last steps sets a new cell to a symbol, at which point the puzzle is solved, it's not completely specified, or there is an ambiguity that I don't handle in this code (I think it is possible for some sort of circular ambiguity to exist).