/**

 * sudoku.c

 * Copyright (C) 2008 Markus Broeker

 *

 * Sudoku - The Game

 */

#include <stdio.h>

#include <stdlib.h>

#include <getopt.h>

#include <string.h>

#include <errno.h>

#include <limits.h>

#ifndef DIM

#define DIM 9

#endif

#define COLORED "\e[31m"

#define FGCOLOR "\e[37m"

#define BGCOLOR "\e[40m\e[2J"

#define   RESET "\e[0m"

#define TRUE   1

#define FALSE  0

#ifndef u_int

typedef unsigned int u_int;

#endif

#ifndef MAX_ITERATIONS

#define MAX_ITERATIONS 10000000

#endif

struct Field {

    u_int value;

    int isConst;

};

/* the easiest way to get statistics */

static unsigned long iterations = 0;

typedef struct Field Field;

typedef Field **Board;

/**

 * read nxn fields from commandline and store it in the Board variable

 */

int readBoard (Board board)

{

    int i, j;

    u_int c;

    for (i = 0; i < DIM; i++) {

        for (j = 0; j < DIM; j++) {

            if (scanf ("%u", &c) < 1) {

                fprintf (stderr, "readBoard: Not enough elements\n");

                fprintf (stderr, "readBoard: Got %d, needed %d\n", i * DIM + j, (DIM) * (DIM));

                return FALSE;

            }

            board[i][j].value = c;

            board[i][j].isConst = (c == 0) ? 0 : 1;

        }

    }

    return TRUE;

}

/**

 * Show the content of the Board in a human readable manner

 */

void showBoard (Board board, int colored)

{

    int i, j;

    for (i = 0; i < DIM; i++) {

        if ((i % 3) == 0)

            printf ("\n");

        for (j = 0; j < DIM; j++) {

            if ((board[i][j].isConst && colored))

                printf ("%s%2u%s ", COLORED, board[i][j].value, FGCOLOR);

            else

                printf ("%2u ", board[i][j].value);

            if (((j + 1) % 3) == 0)

                printf ("  ");

        }

        printf ("\n");

    }

}

/**

 * checks for the possibility of value at board[row][col]

 */

int check (Board board, int row, int col, u_int value)

{

    int i, j;

    if (board[row][col].value > 0)

        return FALSE;

    for (i = 0; i < DIM; i++) {

        /*

         * check vertically

         */

        if (board[row][i].value == value)

            return FALSE;

        /*

         * check horizontally

         */

        if (board[i][col].value == value)

            return FALSE;

    }

    /*

     * check block for unique values

     */

    for (i = row - (row % 3); i < row - (row % 3) + 3; i++)

        for (j = col - (col % 3); j < col - (col % 3) + 3; j++)

            if (board[i][j].value == value)

                return FALSE;

    return TRUE;

}

/**

 * go recursive from k to DIM^2 and try to solve the puzzle

 */

int solveBoard (Board board, int k)

{

    u_int i;

    int q;

    if ((++iterations > MAX_ITERATIONS))

        return FALSE;

    while (k < (DIM) * (DIM) && (board[k / DIM][k % DIM].value != 0))

        k++;

    if (k == (DIM) * (DIM))

        return TRUE;

    for (q = FALSE, i = 1; q == FALSE && i <= 9; i++) {

        if (check (board, k / DIM, k % DIM, i) == TRUE) {

            board[k / DIM][k % DIM].value = i;

            if (((DIM) * (DIM) - 1) == k)

                q = TRUE;

            else if ((q = solveBoard (board, k + 1)) == FALSE) {

                board[k / DIM][k % DIM].value = 0;

            }

        }

    }

    return q;

}

/**

 * Deletes every Field of the Board (CLEANUP)

 */

void freeBoard (const Board board)

{

    int i;

    for (i = 0; i < DIM; i++) {

        if (board[i] != NULL)

            free (board[i]);

    }

}

/**

 * Show plain usage screen

 */

void usage (char *name)

{

    printf ("Usage: %s [-c] [-h]\n\n", name);

    printf ("-c\t\tcolored output\n");

    printf ("-h\t\tshows this help\n");

    printf ("Report bugs to mbroeker@largo.homelinux.org\n");

}

int main (int argc, char **argv)

{

    Board b;

    int i;

    int ret;

    int colored = 0;

    while ((i = getopt (argc, argv, "ch")) != -1) {

        switch (i) {

        case 'h':

            usage (argv[0]);

            return EXIT_SUCCESS;

        case 'c':

            printf ("%s%s", BGCOLOR, FGCOLOR);

            colored = 1;

            break;

        default:

            usage (argv[0]);

            return EXIT_FAILURE;

        }

    }

    if ((DIM % 3) != 0) {

        fprintf (stderr, "DIM must be a multiple of 3\n");

        fprintf (stderr, "RECOMPILE WITH -DDIM=9\n");

        return EXIT_FAILURE;

    }

    if ((b = calloc (DIM, sizeof (Field *))) == NULL) {

        perror ("calloc");

        return EXIT_FAILURE;

    }

    for (i = 0; i < DIM; i++) {

        if ((b[i] = malloc ((DIM * sizeof (Field)) + 1)) == NULL) {

            perror ("malloc");

            return EXIT_FAILURE;

        }

    }

    printf ("Sudoku - Enter a %dx%d Matrix\n", DIM, DIM);

    if (readBoard (b) == FALSE) {

        fprintf (stderr, "Input Error: Aborting\n");

        return EXIT_FAILURE;

    }

    showBoard (b, colored);

    if ((ret = solveBoard (b, 0)) == TRUE)

        printf ("\nPuzzle solved after %lu recursions\n", iterations);

    else

        printf ("\nCannot solve your puzzle after %lu recursions\n", iterations);

    showBoard (b, colored);

    freeBoard (b);

    if (b != NULL)

        free (b);

    if (colored)

        printf ("%s", RESET);

    return EXIT_SUCCESS;

}