https://github.com/francesquini/sudoku
This is a sequential Sudoku solver which uses Peter Norvig’s constraint propagation method: http://norvig.com/sudoku.html to solve arbitrarily large (square) Sudoku puzzles.
This was one of the problems used during the 11th Marathon of Parallel Programming. To count the number os solutions instead of finding a solution compile with -DSUDOKU_SOLVE_STRATEGY=SUDOKU_COUNT_SOLS.
Although not strictly necessary, we will assume valid Sudoku puzzles are squares, i.e, the number of cells in each line is the same number of cells in each column. Let N be the number of cells of a line. We will also assume valid puzzles have N boxes with N cells each and there is no intersection between the cells of each box. Clearly, traditional 9x9 Sudoku puzzles observe all of these properties. However, this definition gives as a nice way to extend grid sizes arbitrarily. Any grid of size N xN where N = n 2 for n = 3, 4, 5, . . ., such as 9x9, 16x16, and 25x25, with cell values ranging from 1 to N is now a valid grid size. We deliberately leave out of the definition n values below 3, since here we are only interested in bigger puzzles.
While traditionally Sudoku puzzles have only one solution, when compiled with
-DSUDOKU_SOLVE_STRATEGY=SUDOKU_COUNT_SOLS
the code will count the number of solutions instead of printing them. For more information on the reasons motivating this decision, please refer to the Problem C description of the 11th Marathon of Parallel Programming.
The example inputs were generated by the code written by C. Ansotegui, R. Bejar, C. Fernandez, C. Gomes and C. Mateu, as described in:
- The Impact of Balancing on Problem Hardness in a Highly Structured Domain, Proceedings of the AAAI 2006