kaoD

/* sudoku.txt de ejemplo:

002|006|000
035|020|680
000|000|002
---+---+---
003|400|170
507|000|309
091|008|200
---+---+---
600|000|000
054|080|920
000|900|400

sudoku de bLaKnI (mas complejo y con solucion unica)

000000010
400000000
020000000
000050407
008000300
001090000
300400200
050100000
000806000

*/

#include <stdio.h>
#include <string.h>

#define VERBOSE     1
#define NO_VERBOSE  0

FILE *fSolucion;
int solucion=0;

void imprimeSudoku(const char sudoku[9][9])
{
    int i, j;

    for (i=0; i<9; i++)
    {
        if (i == 0)
            fprintf (fSolucion, "+- Solucion %-5d-+\n", solucion);

        for (j=0; j<9; j++)
        {
            if (j == 0)
                fprintf (fSolucion, "|");

            fprintf (fSolucion, "%d", sudoku[i][j]);
            if (j%3 == 2)
                fprintf (fSolucion, "|");
            else
                fprintf (fSolucion, " ");
        }
        fprintf (fSolucion, "\n");

        if (i%3 == 2)
            fprintf (fSolucion, "+-----+-----+-----+\n");
    }
    fprintf (fSolucion, "\n");

    return;
}

int compruebaSudoku(const char sudoku[9][9], const int verbose)
{
    int i, j, x, y, retval=0;
    /* Apariciones es un mapa de bits que recoge si un numero aparece o no
       La correspondencia con los bits es:
           987654321
       Ej: 000010010 significa que el 5 y el 2 aparecen */
    unsigned int apariciones;

    for (i=0; i<9; i++) // Por cada fila
    {
        apariciones = 0;
        for (j=0; j<9; j++) // Por cada elemento de esa fila
        {
            if (sudoku[i][j] != 0)
            {
                if ((apariciones & (1 << (sudoku[i][j]-1))) == 0)
                    apariciones |= (1 << (sudoku[i][j]-1));
                else
                {
                    if (verbose) printf ("ERROR: En la fila %d\n", i+1);
                    return -1;
                }
            }
        }

        if (apariciones != 511) // Hay algun numero no seteado
            retval = 1;
    }

    for (i=0; i<9; i++) // Por cada columna
    {
        apariciones = 0;
        for (j=0; j<9; j++) // Por cada elemento de esa columna
        {
            if (sudoku[j][i] != 0)
            {
                if ((apariciones & (1 << (sudoku[j][i]-1))) == 0)
                    apariciones |= (1 << (sudoku[j][i]-1));
                else
                {
                    if (verbose) printf ("ERROR: En la columna %d\n", i+1);
                    return -1;
                }
            }
        }
    }

    for (i=0; i<9; i++) // Por cada casillero
    {
        apariciones = 0;
        for (j=0; j<9; j++) // Por cada elemento de ese casillero
        {
            // i/3*3+j/3 donde i es el casillero y j el elemento del casillero es la posicion X en el sudoku
            x = i/3*3+j/3;
            // i%3*3+j%3 es la posicion Y en el sudoku
            y = i%3*3+j%3;
            if (sudoku[x][y] != 0)
            {
                if ((apariciones & (1 << (sudoku[x][y]-1))) == 0 )
                    apariciones |= (1 << (sudoku[x][y]-1));
                else
                {
                    if (verbose) printf ("ERROR: En el casillero %d\n", i+1);
                    return -1;
                }
            }
        }
    }

    return retval;
}

int generaPosibles (const char sudoku[9][9], int x, int y) // Usado para el metodo de recuento cruzado
{
    unsigned int posibles = 0;
    int i;

    for (i=0; i<9; i++) // Por cada elemento de esa fila
    {
        if (sudoku[i][y] != 0)
            posibles |= (1 << (sudoku[i][y]-1));
    }

    for (i=0; i<9; i++) // Por cada elemento de esa columna
    {
        if (sudoku[x][i] != 0)
            posibles |= (1 << (sudoku[x][i]-1));
    }

    int casillero = (x/3*3) + (y/3);

    for (i=0; i<9; i++) // Por cada elemento del casillero
    {
        if (sudoku[casillero/3*3+i/3][casillero%3*3+i%3] != 0)
            posibles |= (1 << (sudoku[casillero/3*3+i/3][casillero%3*3+i%3]-1));
    }

    return posibles ^ 511; // XOR 111111111 para que los posibles sean 1
}

void generaSudoku(const char sudoku[9][9])
{
    int x, y, i;
    unsigned int posibles;

    char sudoku_copia[9][9];

    i = compruebaSudoku(sudoku, NO_VERBOSE);
    if (i == 1) // El Sudoku esta incompleto
    {
        for (x=0; x<9; x++) // Buscamos en las casillas...
        {
            for (y=0; y<9; y++)
            {
                if (sudoku[x][y] == 0) // ...hasta encontrar un 0
                {
                    memcpy(sudoku_copia, sudoku, sizeof(sudoku_copia));

                    posibles = generaPosibles(sudoku, x, y);

                    for (i=1; i<=9; i++) // Probamos las 9 combinaciones...
                    {
                        if ((1 << (i-1)) & posibles) // ...siempre que sean validas
                        {
                            sudoku_copia[x][y] = i;
                            generaSudoku(sudoku_copia);
                            memcpy(sudoku_copia, sudoku, sizeof(sudoku_copia));
                        }
                    }
                    return;
                }
            }
        }
    }
    else if (i == 0) // El Sudoku esta completo y es valido
    {
        solucion++;
        imprimeSudoku(sudoku);
    }

    return;
}

int main(void)
{
    char sudoku[9][9];
    FILE *fSudoku;

    char buffer;
    char casilla = 0;

    memset(sudoku, -1, sizeof(sudoku));

    if ((fSudoku = fopen("sudoku.txt", "r")) == NULL)
    {
        printf ("ERROR: Abriendo el sudoku\n");
        return -1;
    }
    if ((fSolucion = fopen("sudoku_sol.txt", "w")) == NULL)
    {
        printf ("ERROR: Creando el fichero de soluciones\n");
        return -1;
    }

    while (fread(&buffer, sizeof(char), 1, fSudoku)) // Leer el sudoku atendiendo solo a numeros 0-9
    {
        if (buffer >= 48 && buffer <= 57) // 48 = 0, 57 = 9
        {
            sudoku[casilla/9][casilla%9] = buffer - 48;
            casilla++;
        }

        if (casilla == 82)
        {
            printf ("ERROR: Demasiadas casillas\n");
            return -1;
        }
    }

    if (sudoku[8][8] == -1)
    {
        printf ("ERROR: Faltan casillas\n");
        return -1;
    }

    int i = compruebaSudoku(sudoku, VERBOSE);
    if (i < 0)
        printf ("ERROR: Sudoku inicial con errores\n");
    else if (i == 0)
        printf ("ERROR?: Sudoku inicial completo\n");

    generaSudoku(sudoku);

    printf ("%d soluciones generadas en \"sudoku_sol.txt\"\n", solucion);

    return 0;
}