/*
 * Solve a Sudoku puzzle by a backtracking algorithm.
 * Nicholas Lydeen, 2017/04/24
 */

#include <stdio.h>

#ifdef ANIMATED
#include <signal.h>
#include <stdlib.h>
#include <time.h>
struct timespec tm = {.tv_sec = 0, .tv_nsec = 1e8};

void clear_screen(int sig) {
    printf("\e[H\e[2J");
}

void cleanup(int sig) {
    printf("\e[2J\e[?47l\e8");
    exit(0);
}
#endif

int initial_grid[81] = {
    9, 0, 0, 0, 0, 5, 7, 0, 1,
    2, 0, 8, 9, 1, 4, 0, 0, 0,
    1, 6, 0, 0, 8, 0, 0, 0, 2,
    0, 0, 0, 5, 0, 2, 9, 4, 0,
    0, 5, 0, 1, 0, 9, 3, 7, 0,
    6, 3, 0, 0, 0, 0, 2, 0, 0,
    0, 1, 6, 0, 7, 0, 0, 2, 0,
    8, 0, 7, 0, 5, 1, 0, 0, 4,
    0, 0, 4, 8, 0, 0, 0, 5, 7
};

int is_legal(int grid[81]) {
    for(int i = 0; i < 9; ++i) {
        int counter_1[10], counter_2[10];
        for(int j = 0; j < 10; ++j)
            counter_1[j] = counter_2[j] = 0;
        for(int j = 0; j < 9; ++j) {
            int k_1 = 9 * i + j,
                k_2 = 9 * j + i;
            ++counter_1[grid[k_1]];
            ++counter_2[grid[k_2]];
            if(grid[k_1] > 0 && counter_1[grid[k_1]] > 1)
                return 0;
            else if(grid[k_2] > 0 && counter_2[grid[k_2]] > 1)
                return 0;
        }
    }

    for(int p = 0; p < 3; ++p)
        for(int q = 0; q < 3; ++q) {
            int counter[10];
            for(int i = 0; i < 10; ++i)
                counter[i] = 0;
            for(int i = 0; i < 3; ++i)
                for(int j = 0; j < 3; ++j) {
                    int k = (27 * p + 3 * q) + (9 * i + j);
                    ++counter[grid[k]];
                    if(grid[k] > 0 && counter[grid[k]] > 1)
                        return 0;
                }
        }

    return 1;
}

void display(int grid[81]) {
    puts("Lydeen's Backtracking Sudoku Solver\n");
    for(int k = 0; k < 81; ++k) {
        if(grid[k])
            printf("%d ", grid[k]);
        else
            printf(". ");
        if(k % 9 == 8)
            putchar('\n');
    }
}

int main() {
    #ifdef ANIMATED
    signal(SIGWINCH, clear_screen);
    signal(SIGINT, cleanup);
    printf("\e7\e[?47h\e[H\e[2J\e[?25l");
    #endif

    int grid[81];
    for(int k = 0; k < 81; ++k)
        grid[k] = initial_grid[k];

    int k = 0;
    while(k < 81)
        if(initial_grid[k] != 0)
            ++k;
        else {
            do
                ++grid[k];
            while(grid[k] < 9 && !is_legal(grid));

            if(grid[k] <= 9 && is_legal(grid))
                ++k;
            else {
                grid[k] = 0;
                do
                    --k;
                while(k > 0 && initial_grid[k] != 0);
            }

            #ifdef ANIMATED
            printf("\e[1;1H");
            display(grid);
            nanosleep(&tm, NULL);
            #endif
        }

    #ifdef ANIMATED
    puts("\nSolved! Press ^C to exit.");
    tm.tv_sec = 1e12;
    while(1)
        nanosleep(&tm, NULL);
    #else
    display(grid);
    #endif

    return 0;
}