#include "allheaders.h"

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_ok	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 []

Detailed Description

 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.

Function Documentation

◆ sudokuCompareState()

static l_int32 sudokuCompareState	(	L_SUDOKU *	sud1,
		L_SUDOKU *	sud2,
		l_int32	quads,
		l_int32 *	psame
	)

static

sudokuCompareState()

Parameters

[in]	sud1,sud2
[in]	quads	rotation of sud2 input with respect to sud1, in units of 90 degrees cw
[out]	psame	1 if all 4 results are identical; 0 otherwise

Returns: 0 if OK, 1 on error

Notes:
     (1) The input to sud2 has been rotated by quads 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 623 of file sudoku.c.

References L_Sudoku::state, and sudokuRotateArray().

Referenced by sudokuTestUniqueness().

◆ sudokuCreate()

L_SUDOKU* sudokuCreate ( l_int32 * array )

sudokuCreate()

Parameters

[in] array of 81 numbers, 9 rows of 9 numbers each

Returns: 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 301 of file sudoku.c.

References L_Sudoku::failure, L_Sudoku::finished, L_Sudoku::init, L_Sudoku::locs, L_Sudoku::num, and L_Sudoku::state.

Referenced by sudokuGenerate(), and sudokuTestUniqueness().

◆ sudokuDestroy()

void sudokuDestroy ( L_SUDOKU ** psud )

sudokuDestroy()

Parameters

[in,out] psud to be nulled

Returns: void

Definition at line 337 of file sudoku.c.

References L_Sudoku::init, L_Sudoku::locs, and L_Sudoku::state.

Referenced by sudokuGenerate(), and sudokuTestUniqueness().

◆ sudokuGenerate()

L_SUDOKU* sudokuGenerate	(	l_int32 *	array,
		l_int32	seed,
		l_int32	minelems,
		l_int32	maxtries
	)

sudokuGenerate()

Parameters

[in]	array	of 81 numbers, 9 rows of 9 numbers each
[in]	seed	random number
[in]	minelems	min non-zero elements allowed; <= 80
[in]	maxtries	max tries to remove a number and get a valid sudoku

Returns: 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 minelems, the minimum
         number of non-zero elements, is reached, or when the
         number of attempts to remove the next element exceeds maxtries.
     (3) No sudoku is known with less than 17 nonzero elements.

Definition at line 731 of file sudoku.c.

References L_Sudoku::failure, genRandomIntegerInRange(), L_Sudoku::init, sudokuCreate(), sudokuDestroy(), sudokuOutput(), sudokuSolve(), and sudokuTestUniqueness().

◆ sudokuNewGuess()

static l_int32 sudokuNewGuess ( L_SUDOKU * sud )

static

sudokuNewGuess()

Parameters

[in] sud l_sudoku

Returns: 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 449 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, and sudokuTestState().

Referenced by sudokuSolve().

◆ sudokuOutput()

l_int32 sudokuOutput	(	L_SUDOKU *	sud,
		l_int32	arraytype
	)

sudokuOutput()

Parameters

[in]	sud	l_sudoku at any stage
[in]	arraytype	L_SUDOKU_INIT, L_SUDOKU_STATE

Returns: void

Notes:
     (1) Prints either the initial array or the current state
         of the solution.

Definition at line 854 of file sudoku.c.

Referenced by sudokuGenerate().

◆ sudokuReadFile()

l_int32* sudokuReadFile ( const char * filename )

sudokuReadFile()

Parameters

[in] filename of formatted sudoku file

Returns: 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 181 of file sudoku.c.

References L_StrCode::data, l_binaryRead(), L_COPY, L_NOCOPY, sarrayAddString(), sarrayCreate(), sarrayCreateLinesFromString(), sarrayCreateWordsFromString(), sarrayDestroy(), sarrayGetCount(), and sarrayGetString().

◆ sudokuReadString()

l_int32* sudokuReadString ( const char * str )

sudokuReadString()

Parameters

[in] str of input data

Returns: array of 81 numbers, or NULL on error

Notes:
     (1) The string is formatted as 81 single digits, each separated
         by 81 spaces.

Definition at line 260 of file sudoku.c.

◆ sudokuRotateArray()

static l_int32 * sudokuRotateArray	(	l_int32 *	array,
		l_int32	quads
	)

static

sudokuRotateArray()

Parameters

[in]	array	of 81 numbers; 9 lines of 9 numbers each
[in]	quads	1-3; number of 90 degree cw rotations

Returns: rarray rotated array, or NULL on error

Definition at line 666 of file sudoku.c.

Referenced by sudokuCompareState(), and sudokuTestUniqueness().

◆ sudokuSolve()

l_int32 sudokuSolve ( L_SUDOKU * sud )

sudokuSolve()

Parameters

[in] sud l_sudoku starting in initial state

Returns: 1 on success, 0 on failure to solve note reversal of typical unix returns

Definition at line 371 of file sudoku.c.

References L_Sudoku::failure, L_Sudoku::finished, L_Sudoku::init, L_Sudoku::nguess, sudokuNewGuess(), and sudokuValidState().

Referenced by sudokuGenerate(), and sudokuTestUniqueness().

◆ sudokuTestState()

static l_int32 sudokuTestState	(	l_int32 *	state,
		l_int32	index
	)

static

sudokuTestState()

Parameters

[in]	state	current state: array of 81 values
[in]	index	into state element that we are testing

Returns: 1 if valid; 0 if invalid no error checking

Definition at line 491 of file sudoku.c.

Referenced by sudokuNewGuess(), and sudokuValidState().

◆ sudokuTestUniqueness()

l_ok sudokuTestUniqueness	(	l_int32 *	array,
		l_int32 *	punique
	)

sudokuTestUniqueness()

Parameters

[in]	array	of 81 numbers, 9 lines of 9 numbers each
[out]	punique	1 if unique, 0 if not

Returns: 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 562 of file sudoku.c.

References sudokuCompareState(), sudokuCreate(), sudokuDestroy(), sudokuRotateArray(), and sudokuSolve().

Referenced by sudokuGenerate().

◆ sudokuValidState()

static l_int32 sudokuValidState ( l_int32 * state )

static

sudokuValidState()

Parameters

[in] state array of size 81

Returns: 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 412 of file sudoku.c.

References sudokuTestState().

Referenced by sudokuSolve().

Variable Documentation

◆ valid_solution

const char valid_solution[]

static

Initial value:

= "3 8 7 2 6 4 1 9 5 "
                                     "2 6 5 8 9 1 4 3 7 "
                                     "1 4 9 5 3 7 6 8 2 "
                                     "5 2 3 7 1 6 8 4 9 "
                                     "7 1 6 9 4 8 2 5 3 "
                                     "8 9 4 3 5 2 7 1 6 "
                                     "9 7 2 1 8 5 3 6 4 "
                                     "4 3 1 6 7 9 5 2 8 "
                                     "6 5 8 4 2 3 9 7 1 "

Definition at line 152 of file sudoku.c.

Functions

Variables

Detailed Description

Function Documentation

◆ sudokuCompareState()

◆ sudokuCreate()

◆ sudokuDestroy()

◆ sudokuGenerate()

◆ sudokuNewGuess()

◆ sudokuOutput()

◆ sudokuReadFile()

◆ sudokuReadString()

◆ sudokuRotateArray()

◆ sudokuSolve()

◆ sudokuTestState()

◆ sudokuTestUniqueness()

◆ sudokuValidState()

Variable Documentation

◆ valid_solution