 |
Leptonica 1.68
C Image Processing Library
|
|
Leptonica 1.68
C Image Processing Library
|
Solve a sudoku by brute force search. More...
#include "allheaders.h"Go to the source code of this file.
Functions | |
| static l_int32 | sudokuValidState (l_int32 *state) |
| static l_int32 | sudokuNewGuess (L_SUDOKU *sud) |
| static l_int32 | sudokuTestState (l_int32 *state, l_int32 index) |
| static l_int32 | sudokuCompareState (L_SUDOKU *sud1, L_SUDOKU *sud2, l_int32 quads, l_int32 *psame) |
| static l_int32 * | sudokuRotateArray (l_int32 *array, l_int32 quads) |
| l_int32 * | sudokuReadFile (const char *filename) |
| l_int32 * | sudokuReadString (const char *str) |
| L_SUDOKU * | sudokuCreate (l_int32 *array) |
| void | sudokuDestroy (L_SUDOKU **psud) |
| l_int32 | sudokuSolve (L_SUDOKU *sud) |
| l_int32 | sudokuTestUniqueness (l_int32 *array, l_int32 *punique) |
| L_SUDOKU * | sudokuGenerate (l_int32 *array, l_int32 seed, l_int32 minelems, l_int32 maxtries) |
| l_int32 | sudokuOutput (L_SUDOKU *sud, l_int32 arraytype) |
Variables | |
| static const char | valid_solution [] = "6 5 8 4 2 3 9 7 1 " |
Solve a sudoku by brute force search.
Solve a sudoku by brute force search
Read input data from file or string
l_int32 *sudokuReadFile()
l_int32 *sudokuReadString()
Create/destroy
L_SUDOKU *sudokuCreate()
void sudokuDestroy()
Solve the puzzle
l_int32 sudokuSolve()
static l_int32 sudokuValidState()
static l_int32 sudokuNewGuess()
static l_int32 sudokuTestState()
Test for uniqueness
l_int32 sudokuTestUniqueness()
static l_int32 sudokuCompareState()
static l_int32 *sudokuRotateArray()
Generation
L_SUDOKU *sudokuGenerate()
Output
l_int32 sudokuOutput()
Solving sudokus is a somewhat addictive pastime. The rules are
simple but it takes just enough concentration to make it rewarding
when you find a number. And you get 50 to 60 such rewards each time
you complete one. The downside is that you could have been doing
something more creative, like keying out a new plant, staining
the deck, or even writing a computer program to discourage your
wife from doing sudokus.
My original plan for the sudoku solver was somewhat grandiose.
The program would model the way a person solves the problem.
It would examine each empty position and determine how many possible
numbers could fit. The empty positions would be entered in a priority
queue keyed on the number of possible numbers that could fit.
If there existed a position where only a single number would work,
it would greedily take it. Otherwise it would consider a
positions that could accept two and make a guess, with backtracking
if an impossible state were reached. And so on.
Then one of my colleagues announced she had solved the problem
by brute force and it was fast. At that point the original plan was
dead in the water, because the two top requirements for a leptonica
algorithm are (1) as simple as possible and (2) fast. The brute
force approach starts at the UL corner, and in succession at each
blank position it finds the first valid number (testing in
sequence from 1 to 9). When no number will fit a blank position
it backtracks, choosing the next valid number in the previous
blank position.
This is an inefficient method for pruning the space of solutions
(imagine backtracking from the LR corner back to the UL corner
and starting over with a new guess), but it nevertheless gets
the job done quickly. I have made no effort to optimize
it, because it is fast: a 5-star (highest difficulty) sudoku might
require a million guesses and take 0.05 sec. (This BF implementation
does about 20M guesses/sec at 3 GHz.)
Proving uniqueness of a sudoku solution is tricker than finding
a solution (or showing that no solution exists). A good indication
that a solution is unique is if we get the same result solving
by brute force when the puzzle is also rotated by 90, 180 and 270
degrees. If there are multiple solutions, it seems unlikely
that you would get the same solution four times in a row, using a
brute force method that increments guesses and scans LR/TB.
The function sudokuTestUniqueness() does this.
And given a function that can determine uniqueness, it is
easy to generate valid sudokus. We provide sudokuGenerate(),
which starts with some valid initial solution, and randomly
removes numbers, stopping either when a minimum number of non-zero
elements are left, or when it becomes difficult to remove another
element without destroying the uniqueness of the solution.
For further reading, see the Wikipedia articles:
(1) http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
(2) http://en.wikipedia.org/wiki/Sudoku
How many 9x9 sudokus are there? Here are the numbers.
- From ref(1), there are about 6 x 10^27 "latin squares", where
each row and column has all 9 digits.
- There are 7.2 x 10^21 actual solutions, having the added
constraint in each of the 9 3x3 squares. (The constraint
reduced the number by the fraction 1.2 x 10^(-6).)
- There are a mere 5.5 billion essentially different solutions (EDS),
when symmetries (rotation, reflection, permutation and relabelling)
are removed.
- Thus there are 1.3 x 10^12 solutions that can be derived by
symmetry from each EDS. Can we account for these?
- Sort-of. From an EDS, you can derive (3!)^8 = 1.7 million solutions
by simply permuting rows and columns. (Do you see why it is
not (3!)^6 ?)
- Also from an EDS, you can derive 9! solutions by relabelling,
and 4 solutions by rotation, for a total of 1.45 million solutions
by relabelling and rotation. Then taking the product, by symmetry
we can derive 1.7M x 1.45M = 2.45 trillion solutions from each EDS.
(Something is off by about a factor of 2 -- close enough.)
Another interesting fact is that there are apparently 48K EDS sudokus
(with unique solutions) that have only 17 givens. No sudokus are known
with less than 17, but there exists no proof that this is the minimum.
Definition in file sudoku.c.
Input: state (array of size 81) Return: 1 if valid, 0 if invalid
Notes: (1) This can be used on either the initial state (init) or on the current state (state) of the l_soduku. All values of 0 are ignored.
Definition at line 393 of file sudoku.c.
References ERROR_INT, PROCNAME, and sudokuTestState().
Referenced by sudokuSolve().
Input: l_sudoku Return: 0 if OK; 1 if no solution is possible
Notes: (1) This attempts to increment the number in the current location. If it can't, it backtracks (sets the number in the current location to zero and decrements the current location). If it can, it tests that number, and if the number is valid, moves forward to the next empty location (increments the current location). (2) If there is no solution, backtracking will eventually exhaust possibilities for the first location.
Definition at line 428 of file sudoku.c.
References L_Sudoku::current, L_Sudoku::failure, L_Sudoku::finished, L_Sudoku::locs, L_Sudoku::nguess, L_Sudoku::num, L_Sudoku::state, sudokuTestState(), and TRUE.
Referenced by sudokuSolve().
Input: state (current state: array of 81 values) index (into state element that we are testing) Return: 1 if valid; 0 if invalid (no error checking)
Definition at line 471 of file sudoku.c.
Referenced by sudokuNewGuess(), and sudokuValidState().
| static l_int32 sudokuCompareState | ( | L_SUDOKU * | sud1, |
| L_SUDOKU * | sud2, | ||
| l_int32 | quads, | ||
| l_int32 * | psame | ||
| ) | [static] |
Input: sud1, sud2 quads (rotation of sud2 input with respect to sud1, in units of 90 degrees cw) &same (<return> 1 if all 4 results are identical; 0 otherwise) Return: 0 if OK, 1 on error
Notes: (1) The input to sud2 has been rotated by relative to the input to sud1. Therefore, we must rotate the solution to sud1 by the same amount before comparing it to the solution to sud2.
Definition at line 599 of file sudoku.c.
References L_Stack::array, ERROR_INT, FALSE, FREE, NULL, PROCNAME, L_Sudoku::state, sudokuRotateArray(), and TRUE.
Referenced by sudokuTestUniqueness().
Input: array (of 81 numbers; 9 lines of 9 numbers each) quads (1-3; number of 90 degree cw rotations) Return: rarray (rotated array), or null on error
Definition at line 642 of file sudoku.c.
References CALLOC, ERROR_PTR, NULL, and PROCNAME.
Referenced by sudokuCompareState(), and sudokuTestUniqueness().
| l_int32* sudokuReadFile | ( | const char * | filename | ) |
Input: filename (of formatted sudoku file) Return: array (of 81 numbers), or null on error
Notes: (1) The file format has: * any number of comment lines beginning with '#' * a set of 9 lines, each having 9 digits (0-9) separated by a space
Definition at line 166 of file sudoku.c.
References L_Stack::array, CALLOC, ERROR_PTR, FALSE, FREE, l_binaryRead(), L_COPY, L_ERROR_INT, L_NOCOPY, NULL, PROCNAME, sarrayAddString(), sarrayCreate(), sarrayCreateLinesFromString(), sarrayCreateWordsFromString(), sarrayDestroy(), sarrayGetCount(), sarrayGetString(), size, and TRUE.
Referenced by main().
| l_int32* sudokuReadString | ( | const char * | str | ) |
Input: array (of 81 numbers, 9 rows of 9 numbers each) Return: l_sudoku, or null on error
Notes: (1) The input array has 0 for the unknown values, and 1-9 for the known initial values. It is generated from a file using sudokuReadInput(), which checks that the file data has 81 numbers in 9 rows.
Definition at line 280 of file sudoku.c.
References CALLOC, ERROR_PTR, L_Sudoku::failure, FALSE, L_Sudoku::finished, L_Sudoku::init, L_Sudoku::locs, NULL, L_Sudoku::num, PROCNAME, and L_Sudoku::state.
Referenced by main(), sudokuGenerate(), and sudokuTestUniqueness().
| void sudokuDestroy | ( | L_SUDOKU ** | psud | ) |
Input: &l_sudoku (<to be="" nulled>="">) Return: void
Definition at line 320 of file sudoku.c.
References FREE, L_Sudoku::init, L_WARNING, L_Sudoku::locs, NULL, PROCNAME, and L_Sudoku::state.
Referenced by main(), sudokuGenerate(), and sudokuTestUniqueness().
Input: l_sudoku (starting in initial state) Return: 1 on success, 0 on failure to solve (note reversal of typical unix returns)
Definition at line 354 of file sudoku.c.
References ERROR_INT, L_Sudoku::failure, L_Sudoku::finished, L_Sudoku::init, L_Sudoku::nguess, PROCNAME, sudokuNewGuess(), sudokuValidState(), and TRUE.
Referenced by main(), sudokuGenerate(), and sudokuTestUniqueness().
Input: array (of 81 numbers, 9 lines of 9 numbers each) &punique (<return> 1 if unique, 0 if not) Return: 0 if OK, 1 on error
Notes: (1) This applies the brute force method to all four 90 degree rotations. If there is more than one solution, it is highly unlikely that all four results will be the same; consequently, if they are the same, the solution is most likely to be unique.
Definition at line 540 of file sudoku.c.
References ERROR_INT, FREE, PROCNAME, sudokuCompareState(), sudokuCreate(), sudokuDestroy(), sudokuRotateArray(), and sudokuSolve().
Referenced by main(), and sudokuGenerate().
Input: array (of 81 numbers, 9 rows of 9 numbers each) seed (random number) minelems (min non-zero elements allowed; <= 80) maxtries (max tries to remove a number and get a valid sudoku) Return: l_sudoku, or null on error
Notes: (1) This is a brute force generator. It starts with a completed sudoku solution and, by removing elements (setting them to 0), generates a valid (unique) sudoku initial condition. (2) The process stops when either , the minimum number of non-zero elements, is reached, or when the number of attempts to remove the next element exceeds . (3) No sudoku is known with less than 17 nonzero elements.
Definition at line 707 of file sudoku.c.
References ERROR_PTR, L_Sudoku::failure, genRandomIntegerInRange(), L_Sudoku::init, L_ERROR, L_MIN, L_SUDOKU_INIT, L_SUDOKU_STATE, NULL, PROCNAME, sudokuCreate(), sudokuDestroy(), sudokuOutput(), sudokuSolve(), sudokuTestUniqueness(), and TRUE.
Referenced by main().
Input: l_sudoku (at any stage) arraytype (L_SUDOKU_INIT, L_SUDOKU_STATE) Return: void
Notes: (1) Prints either the initial array or the current state of the solution.
Definition at line 829 of file sudoku.c.
References L_Stack::array, ERROR_INT, L_Sudoku::init, L_SUDOKU_INIT, L_SUDOKU_STATE, PROCNAME, and L_Sudoku::state.
Referenced by main(), and sudokuGenerate().
const char valid_solution[] = "6 5 8 4 2 3 9 7 1 " [static] |
1.7.3