src/sudoku.c
L_SUDOKU *
sudokuGenerate(l_int32  *array,
               l_int32   seed,
               l_int32   minelems,
               l_int32   maxtries)
{
l_int32    index, sector, nzeros, removefirst, tries, val, oldval, unique;
L_SUDOKU  *sud, *testsud;

    PROCNAME("sudokuGenerate");

    if (!array)
        return (L_SUDOKU *)ERROR_PTR("array not defined", procName, NULL);
    if (minelems > 80)
        return (L_SUDOKU *)ERROR_PTR("minelems must be < 81", procName, NULL);

        /* Remove up to 30 numbers at random from the solution.
         * Test if the solution is valid -- the initial 'solution' may
         * have been invalid.  Then test if the sudoku with 30 zeroes
         * is unique -- it almost always will be. */
    srand(seed);
    nzeros = 0;
    sector = 0;
    removefirst = L_MIN(30, 81 - minelems);
    while (nzeros < removefirst) {
        genRandomIntegerInRange(9, 0, &val);
        index = 27 * (sector / 3) + 3 * (sector % 3) +
                9 * (val / 3) + (val % 3);
        if (array[index] == 0) continue;
        array[index] = 0;
        nzeros++;
        sector++;
        sector %= 9;
    }
    testsud = sudokuCreate(array);
    sudokuSolve(testsud);
    if (testsud->failure) {
        sudokuDestroy(&testsud);
        L_ERROR("invalid initial solution", procName);
        return NULL;
    }
    sudokuTestUniqueness(testsud->init, &unique);
    sudokuDestroy(&testsud);
    if (!unique) {
        L_ERROR("non-unique result with 30 zeroes", procName);
        return NULL;
    }

        /* Remove more numbers, testing at each removal for uniqueness. */
    tries = 0;
    sector = 0;
    while (1) {
        if (tries > maxtries) break;
        if (81 - nzeros <= minelems) break;

        if (tries == 0) {
            fprintf(stderr, "Trying %d zeros\n", nzeros);
            tries = 1;
        }

            /* Choose an element to be zeroed.  We choose one
             * at random in succession from each of the nine sectors. */
        genRandomIntegerInRange(9, 0, &val);
        index = 27 * (sector / 3) + 3 * (sector % 3) +
                9 * (val / 3) + (val % 3);
        sector++;
        sector %= 9;
        if (array[index] == 0) continue;

            /* Save the old value in case we need to revert */
        oldval = array[index];

            /* Is there a solution?  If not, try again. */
        array[index] = 0;
        testsud = sudokuCreate(array);
        sudokuSolve(testsud);
        if (testsud->failure == TRUE) {
            sudokuDestroy(&testsud);
            array[index] = oldval;  /* revert */
            tries++;
            continue;
        }

            /* Is the solution unique?  If not, try again. */
        sudokuTestUniqueness(testsud->init, &unique);
        sudokuDestroy(&testsud);
        if (!unique) {  /* revert and try again */
            array[index] = oldval;
            tries++;
        }
        else {  /* accept this */
            tries = 0;
            fprintf(stderr, "Have %d zeros\n", nzeros);
            nzeros++;
        }
    }
    fprintf(stderr, "Final: nelems = %d\n", 81 - nzeros);

        /* Show that we can recover the solution */
    sud = sudokuCreate(array);
    sudokuOutput(sud, L_SUDOKU_INIT);
    sudokuSolve(sud);
    sudokuOutput(sud, L_SUDOKU_STATE);

    return sud;
}
/*!
 *  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 @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.
 */
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

(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.
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 ( 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 .
L_SUDOKU *
sudokuGenerate(l_int32  *array,
               l_int32   seed,
               l_int32   minelems,
               l_int32   maxtries)
{
l_int32    index, sector, nzeros, removefirst, tries, val, oldval, unique;
L_SUDOKU  *sud, *testsud;
    PROCNAME("sudokuGenerate");
    if (!array)
        return (L_SUDOKU *)ERROR_PTR("array not defined", procName, NULL);
    if (minelems > 80)
        return (L_SUDOKU *)ERROR_PTR("minelems must be < 81", procName, NULL);
    srand(seed);
    nzeros = 0;
    sector = 0;
    removefirst = L_MIN(30, 81 - minelems);
    while (nzeros < removefirst) {
        genRandomIntegerInRange(9, 0, &val);
        index = 27 * (sector / 3) + 3 * (sector % 3) +
                9 * (val / 3) + (val % 3);
        if (array[index] == 0) continue;
        array[index] = 0;
        nzeros++;
        sector++;
        sector %= 9;
    }
    testsud = sudokuCreate(array);
    sudokuSolve(testsud);
    if (testsud->failure) {
        sudokuDestroy(&testsud);
        L_ERROR("invalid initial solution", procName);
        return NULL;
    }
    sudokuTestUniqueness(testsud->init, &unique);
    sudokuDestroy(&testsud);
    if (!unique) {
        L_ERROR("non-unique result with 30 zeroes", procName);
        return NULL;
    }
    tries = 0;
    sector = 0;
    while (1) {
        if (tries > maxtries) break;
        if (81 - nzeros <= minelems) break;
        if (tries == 0) {
            fprintf(stderr, "Trying %d zeros\n", nzeros);
            tries = 1;
        }
        genRandomIntegerInRange(9, 0, &val);
        index = 27 * (sector / 3) + 3 * (sector % 3) +
                9 * (val / 3) + (val % 3);
        sector++;
        sector %= 9;
        if (array[index] == 0) continue;
        oldval = array[index];
        array[index] = 0;
        testsud = sudokuCreate(array);
        sudokuSolve(testsud);
        if (testsud->failure == TRUE) {
            sudokuDestroy(&testsud);
            array[index] = oldval;  
            tries++;
            continue;
        }
        sudokuTestUniqueness(testsud->init, &unique);
        sudokuDestroy(&testsud);
        if (!unique) {  
            array[index] = oldval;
            tries++;
        }
        else {  
            tries = 0;
            fprintf(stderr, "Have %d zeros\n", nzeros);
            nzeros++;
        }
    }
    fprintf(stderr, "Final: nelems = %d\n", 81 - nzeros);
    sud = sudokuCreate(array);
    sudokuOutput(sud, L_SUDOKU_INIT);
    sudokuSolve(sud);
    sudokuOutput(sud, L_SUDOKU_STATE);
    return sud;
}
L_SUDOKU * sudokuGenerate ( l_int32 * array , l_int32 seed , l_int32 minelems , l_int32 maxtries ) { l_int32 index , sector , nzeros , removefirst , tries , val , oldval , unique ; L_SUDOKU * sud , * testsud ; PROCNAME ( " " ) ; if ( ! array ) return ( L_SUDOKU * ) ERROR_PTR ( " " , procName , NULL ) ; if ( minelems > 80 ) return ( L_SUDOKU * ) ERROR_PTR ( " " , procName , NULL ) ; srand ( seed ) ; nzeros = 0 ; sector = 0 ; removefirst = L_MIN ( 30 , 81 - minelems ) ; while ( nzeros < removefirst ) { genRandomIntegerInRange ( 9 , 0 , & val ) ; index = 27 * ( sector / 3 ) + 3 * ( sector % 3 ) + 9 * ( val / 3 ) + ( val % 3 ) ; if ( array [ index ] == 0 ) continue ; array [ index ] = 0 ; nzeros ++ ; sector ++ ; sector %= 9 ; } testsud = sudokuCreate ( array ) ; sudokuSolve ( testsud ) ; if ( testsud -> failure ) { sudokuDestroy ( & testsud ) ; L_ERROR ( " " , procName ) ; return NULL ; } sudokuTestUniqueness ( testsud -> init , & unique ) ; sudokuDestroy ( & testsud ) ; if ( ! unique ) { L_ERROR ( " " , procName ) ; return NULL ; } tries = 0 ; sector = 0 ; while ( 1 ) { if ( tries > maxtries ) break ; if ( 81 - nzeros <= minelems ) break ; if ( tries == 0 ) { fprintf ( stderr , " \n " , nzeros ) ; tries = 1 ; } genRandomIntegerInRange ( 9 , 0 , & val ) ; index = 27 * ( sector / 3 ) + 3 * ( sector % 3 ) + 9 * ( val / 3 ) + ( val % 3 ) ; sector ++ ; sector %= 9 ; if ( array [ index ] == 0 ) continue ; oldval = array [ index ] ; array [ index ] = 0 ; testsud = sudokuCreate ( array ) ; sudokuSolve ( testsud ) ; if ( testsud -> failure == TRUE ) { sudokuDestroy ( & testsud ) ; array [ index ] = oldval ; tries ++ ; continue ; } sudokuTestUniqueness ( testsud -> init , & unique ) ; sudokuDestroy ( & testsud ) ; if ( ! unique ) { array [ index ] = oldval ; tries ++ ; } else { tries = 0 ; fprintf ( stderr , " \n " , nzeros ) ; nzeros ++ ; } } fprintf ( stderr , " \n " , 81 - nzeros ) ; sud = sudokuCreate ( array ) ; sudokuOutput ( sud , L_SUDOKU_INIT ) ; sudokuSolve ( sud ) ; sudokuOutput ( sud , L_SUDOKU_STATE ) ; return sud ; }
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
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
/* Remove up to 30 numbers at random from the solution.
         * Test if the solution is valid -- the initial 'solution' may
         * have been invalid.  Then test if the sudoku with 30 zeroes
         * is unique -- it almost always will be. */ /* Remove more numbers, testing at each removal for uniqueness. */ /* Choose an element to be zeroed.  We choose one
             * at random in succession from each of the nine sectors. */ /* Save the old value in case we need to revert */ /* Is there a solution?  If not, try again. */ /* revert */ /* Is the solution unique?  If not, try again. */ /* revert and try again */ /* accept this */ /* Show that we can recover the solution */