/**
 * 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;
}