Sudoku
A Sudoku puzzle is a 9x9 grid comprised of cells that can assume values 0 to 9 inclusive. The board is seeded with some starting numbers (at least 17, usually many more). It is complete when each row, column, and box (3x3 subgrid, of which there are 9) is filled with all values 0 to 9 -- that is, there are no duplicates in any row, column, or box.
To solve a Sudoku puzzle programmatically, one approach is to consider each cell a set of values 0 to 9. The solver's goal is then to find ways to reduce the possible values of each set, until the entire board is comprised of singleton sets.
These slides describe the solver logic at a high level. This iPython notebook steps through the complete algorithm.
Visualization Legend Ley
A Sudoku puzzle is a 9x9 grid comprised of cells that can assume values 0 to 9 inclusive. The board is seeded with some starting numbers (at least 17, usually many more). It is complete when each row, column, and box (3x3 subgrid, of which there are 9) is filled with all values 0 to 9 -- that is, there are no duplicates in any row, column, or box.
To solve a Sudoku puzzle programmatically, one approach is to consider each cell a set of values 0 to 9. The solver's goal is then to find ways to reduce the possible values of each set, until the entire board is comprised of singleton sets.
These slides describe the solver logic at a high level. This iPython notebook steps through the complete algorithm.
Visualization Legend Ley
- Iter: count of the solver's logical iterations
- Score: count of possible (cell, number) combinations (a completed board has 81)
- Stack: count of boards on the stack
- Action: action taken by the solver (Prune, Fill, Extend, Backtrack, None)
- Transform: board transformation applied (Rows, Columns, or Boxes)