sudoku.c

Go to the documentation of this file.

/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/


#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_int32 *sudokuRotateArray(l_int32  *array, l_int32  quads);

    /* An example of a valid solution */
static const char valid_solution[] = "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 ";


/*---------------------------------------------------------------------*
 *               Read input data from file or string                   *
 *---------------------------------------------------------------------*/
l_int32 *
sudokuReadFile(const char  *filename)
{
char     *str, *strj;
l_uint8  *data;
l_int32   i, j, nlines, val, index, error;
l_int32  *array;
size_t    size;
SARRAY   *saline, *sa1, *sa2;

    PROCNAME("sudokuReadFile");

    if (!filename)
        return (l_int32 *)ERROR_PTR("filename not defined", procName, NULL);
    data = l_binaryRead(filename, &size);
    sa1 = sarrayCreateLinesFromString((char *)data, 0);
    sa2 = sarrayCreate(9);

        /* Filter out the comment lines; verify that there are 9 data lines */
    nlines = sarrayGetCount(sa1);
    for (i = 0; i < nlines; i++) {
        str = sarrayGetString(sa1, i, L_NOCOPY);
        if (str[0] != '#')
            sarrayAddString(sa2, str, L_COPY);
    }
    LEPT_FREE(data);
    sarrayDestroy(&sa1);
    nlines = sarrayGetCount(sa2);
    if (nlines != 9) {
        sarrayDestroy(&sa2);
        L_ERROR("file has %d lines\n", procName, nlines);
        return (l_int32 *)ERROR_PTR("invalid file", procName, NULL);
    }

        /* Read the data into the array, verifying that each data
         * line has 9 numbers. */
    error = FALSE;
    array = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
    for (i = 0, index = 0; i < 9; i++) {
        str = sarrayGetString(sa2, i, L_NOCOPY);
        saline = sarrayCreateWordsFromString(str);
        if (sarrayGetCount(saline) != 9) {
            error = TRUE;
            sarrayDestroy(&saline);
            break;
        }
        for (j = 0; j < 9; j++) {
            strj = sarrayGetString(saline, j, L_NOCOPY);
            if (sscanf(strj, "%d", &val) != 1)
                error = TRUE;
            else
                array[index++] = val;
        }
        sarrayDestroy(&saline);
        if (error) break;
    }
    sarrayDestroy(&sa2);

    if (error) {
        LEPT_FREE(array);
        return (l_int32 *)ERROR_PTR("invalid data", procName, NULL);
    }

    return array;
}


l_int32 *
sudokuReadString(const char  *str)
{
l_int32   i;
l_int32  *array;

    PROCNAME("sudokuReadString");

    if (!str)
        return (l_int32 *)ERROR_PTR("str not defined", procName, NULL);

        /* Read in the initial solution */
    array = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
    for (i = 0; i < 81; i++) {
        if (sscanf(str + 2 * i, "%d ", &array[i]) != 1) {
            LEPT_FREE(array);
            return (l_int32 *)ERROR_PTR("invalid format", procName, NULL);
        }
    }

    return array;
}


/*---------------------------------------------------------------------*
 *                        Create/destroy sudoku                        *
 *---------------------------------------------------------------------*/
L_SUDOKU *
sudokuCreate(l_int32  *array)
{
l_int32    i, val, locs_index;
L_SUDOKU  *sud;

    PROCNAME("sudokuCreate");

    if (!array)
        return (L_SUDOKU *)ERROR_PTR("array not defined", procName, NULL);

    locs_index = 0;  /* into locs array */
    sud = (L_SUDOKU *)LEPT_CALLOC(1, sizeof(L_SUDOKU));
    sud->locs = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
    sud->init = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
    sud->state = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
    for (i = 0; i < 81; i++) {
        val = array[i];
        sud->init[i] = val;
        sud->state[i] = val;
        if (val == 0)
            sud->locs[locs_index++] = i;
    }
    sud->num = locs_index;
    sud->failure = FALSE;
    sud->finished = FALSE;
    return sud;
}


void
sudokuDestroy(L_SUDOKU  **psud)
{
L_SUDOKU  *sud;

    PROCNAME("sudokuDestroy");

    if (psud == NULL) {
        L_WARNING("ptr address is NULL\n", procName);
        return;
    }
    if ((sud = *psud) == NULL)
        return;

    LEPT_FREE(sud->locs);
    LEPT_FREE(sud->init);
    LEPT_FREE(sud->state);
    LEPT_FREE(sud);

    *psud = NULL;
    return;
}


/*---------------------------------------------------------------------*
 *                           Solve the puzzle                          *
 *---------------------------------------------------------------------*/
l_int32
sudokuSolve(L_SUDOKU  *sud)
{
    PROCNAME("sudokuSolve");

    if (!sud)
        return ERROR_INT("sud not defined", procName, 0);

    if (!sudokuValidState(sud->init))
        return ERROR_INT("initial state not valid", procName, 0);

    while (1) {
        if (sudokuNewGuess(sud))
            break;
        if (sud->finished == TRUE)
            break;
    }

    if (sud->failure == TRUE) {
        fprintf(stderr, "Failure after %d guesses\n", sud->nguess);
        return 0;
    }

    fprintf(stderr, "Solved after %d guesses\n", sud->nguess);
    return 1;
}


static l_int32
sudokuValidState(l_int32  *state)
{
l_int32  i;

    PROCNAME("sudokuValidState");

    if (!state)
        return ERROR_INT("state not defined", procName, 0);

    for (i = 0; i < 81; i++) {
        if (!sudokuTestState(state, i))
            return 0;
    }

    return 1;
}


static l_int32
sudokuNewGuess(L_SUDOKU  *sud)
{
l_int32   index, val, valid;
l_int32  *locs, *state;

    locs = sud->locs;
    state = sud->state;
    index = locs[sud->current];  /* 0 to 80 */
    val = state[index];
    if (val == 9) {  /* backtrack or give up */
        if (sud->current == 0) {
            sud->failure = TRUE;
            return 1;
        }
        state[index] = 0;
        sud->current--;
    } else {  /* increment current value and test */
        sud->nguess++;
        state[index]++;
        valid = sudokuTestState(state, index);
        if (valid) {
            if (sud->current == sud->num - 1) {  /* we're done */
                sud->finished = TRUE;
                return 0;
            } else {  /* advance to next position */
                sud->current++;
            }
        }
    }

    return 0;
}


static l_int32
sudokuTestState(l_int32  *state,
                l_int32   index)
{
l_int32  i, j, val, row, rowstart, rowend, col;
l_int32  blockrow, blockcol, blockstart, rowindex, locindex;

    if ((val = state[index]) == 0)  /* automatically valid */
        return 1;

        /* Test row.  Test val is at (x, y) = (index % 9, index / 9)  */
    row = index / 9;
    rowstart = 9 * row;
    for (i = rowstart; i < index; i++) {
        if (state[i] == val)
            return 0;
    }
    rowend = rowstart + 9;
    for (i = index + 1; i < rowend; i++) {
        if (state[i] == val)
            return 0;
    }

        /* Test column */
    col = index % 9;
    for (j = col; j < index; j += 9) {
        if (state[j] == val)
            return 0;
    }
    for (j = index + 9; j < 81; j += 9) {
        if (state[j] == val)
            return 0;
    }

        /* Test local 3x3 block */
    blockrow = 3 * (row / 3);
    blockcol = 3 * (col / 3);
    blockstart = 9 * blockrow + blockcol;
    for (i = 0; i < 3; i++) {
        rowindex = blockstart + 9 * i;
        for (j = 0; j < 3; j++) {
            locindex = rowindex + j;
            if (index == locindex) continue;
            if (state[locindex] == val)
                return 0;
        }
    }

    return 1;
}


/*---------------------------------------------------------------------*
 *                         Test for uniqueness                         *
 *---------------------------------------------------------------------*/
l_ok
sudokuTestUniqueness(l_int32  *array,
                     l_int32  *punique)
{
l_int32    same1, same2, same3;
l_int32   *array1, *array2, *array3;
L_SUDOKU  *sud, *sud1, *sud2, *sud3;

    PROCNAME("sudokuTestUniqueness");

    if (!punique)
        return ERROR_INT("&unique not defined", procName, 1);
    *punique = 0;
    if (!array)
        return ERROR_INT("array not defined", procName, 1);

    sud = sudokuCreate(array);
    sudokuSolve(sud);
    array1 = sudokuRotateArray(array, 1);
    sud1 = sudokuCreate(array1);
    sudokuSolve(sud1);
    array2 = sudokuRotateArray(array, 2);
    sud2 = sudokuCreate(array2);
    sudokuSolve(sud2);
    array3 = sudokuRotateArray(array, 3);
    sud3 = sudokuCreate(array3);
    sudokuSolve(sud3);

    sudokuCompareState(sud, sud1, 1, &same1);
    sudokuCompareState(sud, sud2, 2, &same2);
    sudokuCompareState(sud, sud3, 3, &same3);
    *punique = (same1 && same2 && same3);

    sudokuDestroy(&sud);
    sudokuDestroy(&sud1);
    sudokuDestroy(&sud2);
    sudokuDestroy(&sud3);
    LEPT_FREE(array1);
    LEPT_FREE(array2);
    LEPT_FREE(array3);
    return 0;
}


static l_int32
sudokuCompareState(L_SUDOKU  *sud1,
                   L_SUDOKU  *sud2,
                   l_int32    quads,
                   l_int32   *psame)
{
l_int32   i, same;
l_int32  *array;

    PROCNAME("sudokuCompareState");

    if (!psame)
        return ERROR_INT("&same not defined", procName, 1);
    *psame = 0;
    if (!sud1)
        return ERROR_INT("sud1 not defined", procName, 1);
    if (!sud2)
        return ERROR_INT("sud1 not defined", procName, 1);
    if (quads < 1 || quads > 3)
        return ERROR_INT("valid quads in {1,2,3}", procName, 1);

    same = TRUE;
    if ((array = sudokuRotateArray(sud1->state, quads)) == NULL)
        return ERROR_INT("array not made", procName, 1);
    for (i = 0; i < 81; i++) {
        if (array[i] != sud2->state[i]) {
            same = FALSE;
            break;
        }
    }
    *psame = same;
    LEPT_FREE(array);
    return 0;
}


static l_int32 *
sudokuRotateArray(l_int32  *array,
                  l_int32   quads)
{
l_int32   i, j, sindex, dindex;
l_int32  *rarray;

    PROCNAME("sudokuRotateArray");

    if (!array)
        return (l_int32 *)ERROR_PTR("array not defined", procName, NULL);
    if (quads < 1 || quads > 3)
        return (l_int32 *)ERROR_PTR("valid quads in {1,2,3}", procName, NULL);

    rarray = (l_int32 *)LEPT_CALLOC(81, sizeof(l_int32));
    if (quads == 1) {
        for (j = 0, dindex = 0; j < 9; j++) {
             for (i = 8; i >= 0; i--) {
                 sindex = 9 * i + j;
                 rarray[dindex++] = array[sindex];
             }
        }
    } else if (quads == 2) {
        for (i = 8, dindex = 0; i >= 0; i--) {
             for (j = 8; j >= 0; j--) {
                 sindex = 9 * i + j;
                 rarray[dindex++] = array[sindex];
             }
        }
    } else {  /* quads == 3 */
        for (j = 8, dindex = 0; j >= 0; j--) {
             for (i = 0; i < 9; i++) {
                 sindex = 9 * i + j;
                 rarray[dindex++] = array[sindex];
             }
        }
    }

    return rarray;
}


/*---------------------------------------------------------------------*
 *                              Generation                             *
 *---------------------------------------------------------------------*/
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\n", procName);
        return NULL;
    }
    sudokuTestUniqueness(testsud->init, &unique);
    sudokuDestroy(&testsud);
    if (!unique) {
        L_ERROR("non-unique result with 30 zeroes\n", 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;
}


/*---------------------------------------------------------------------*
 *                               Output                                *
 *---------------------------------------------------------------------*/
l_int32
sudokuOutput(L_SUDOKU  *sud,
             l_int32    arraytype)
{
l_int32   i, j;
l_int32  *array;

    PROCNAME("sudokuOutput");

    if (!sud)
        return ERROR_INT("sud not defined", procName, 1);
    if (arraytype == L_SUDOKU_INIT)
        array = sud->init;
    else if (arraytype == L_SUDOKU_STATE)
        array = sud->state;
    else
        return ERROR_INT("invalid arraytype", procName, 1);

    for (i = 0; i < 9; i++) {
        for (j = 0; j < 9; j++)
            fprintf(stderr, "%d ", array[9 * i + j]);
        fprintf(stderr, "\n");
    }

    return 0;
}