Leptonica 1.54
Файл src/sudoku.c
#include "allheaders.h"

Функции

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_int32sudokuRotateArray (l_int32 *array, l_int32 quads)
l_int32sudokuReadFile (const char *filename)
l_int32sudokuReadString (const char *str)
L_SUDOKUsudokuCreate (l_int32 *array)
void sudokuDestroy (L_SUDOKU **psud)
l_int32 sudokuSolve (L_SUDOKU *sud)
l_int32 sudokuTestUniqueness (l_int32 *array, l_int32 *punique)
L_SUDOKUsudokuGenerate (l_int32 *array, l_int32 seed, l_int32 minelems, l_int32 maxtries)
l_int32 sudokuOutput (L_SUDOKU *sud, l_int32 arraytype)

Переменные

static const char valid_solution [] = "6 5 8 4 2 3 9 7 1 "

Функции

static l_int32 sudokuCompareState ( L_SUDOKU sud1,
L_SUDOKU sud2,
l_int32  quads,
l_int32 psame 
) [static]

sudokuCompareState()

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.

L_SUDOKU* sudokuCreate ( l_int32 array)

sudokuCreate()

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.

void sudokuDestroy ( L_SUDOKU **  psud)

sudokuDestroy()

Input: &l_sudoku (<to be="" nulled>="">) Return: void

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

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.

static l_int32 sudokuNewGuess ( L_SUDOKU sud) [static]

sudokuNewGuess()

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.

l_int32 sudokuOutput ( L_SUDOKU sud,
l_int32  arraytype 
)

sudokuOutput()

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.

l_int32* sudokuReadFile ( const char *  filename)

sudokuReadFile()

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

l_int32* sudokuReadString ( const char *  str)

sudokuReadString()

Input: str (of input data) Return: array (of 81 numbers), or null on error

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

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

sudokuRotateArray()

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

l_int32 sudokuSolve ( L_SUDOKU sud)

sudokuSolve()

Input: l_sudoku (starting in initial state) Return: 1 on success, 0 on failure to solve (note reversal of typical unix returns)

static l_int32 sudokuTestState ( l_int32 state,
l_int32  index 
) [static]

sudokuTestState()

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)

l_int32 sudokuTestUniqueness ( l_int32 array,
l_int32 punique 
)

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.

static l_int32 sudokuValidState ( l_int32 state) [static]

sudokuValidState()

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.


Переменные

const char valid_solution[] = "6 5 8 4 2 3 9 7 1 " [static]