/*
 * Copyright 2011 Peter Cherepanov
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/* The program has been developed and tested under GNU/Linux operating system */
/* using GCC and Eclipse integrated development environment. */

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

#define MASK 0xfffffffeeeeeeeeeULL
#define VERSION "1.0"

static unsigned long long sud[81];

static struct stack_elem {
    int x, y;
    int i;
} stack[81];

/* Return error message on error and exit. */
static void xit(const char *s) {
    fprintf(stderr, "%s\n", s);
    exit(1);
}

/* Check whether the sudoku is valid. */
/* A number in the sudoku cell is represented by a bit field. */
/* Sudoku is valid when the sum of bit field has no regroup (in binary). */
/* The bit fields are spaced to ensure that they don't interfere with one */
/* another even in the worst case. */
static bool check(int i, int j) {
    int k = 9*j;
    /* Test a row */
    if ((sud[k] + sud[k+1] + sud[k+2] + sud[k+3] + sud[k+4] + sud[k+5] + sud[k+6] + sud[k+7] + sud[k+8]) & MASK)
        return false;
    /* Test a column */
    if ((sud[i] + sud[i+9] + sud[i+18] + sud[i+27] + sud[i+36] + sud[i+45] + sud[i+54] + sud[i+63] + sud[i+72]) & MASK)
        return false;
    k=i-i%3 + 9*(j-j%3);
    /* Test a square */
    if ((sud[k] + sud[k+1] + sud[k+2] + sud[k+9] + sud[k+10] + sud[k+11] + sud[k+18] + sud[k+19] + sud[k+20]) & MASK)
        return false;
    return true;
}

/* Check 9 cells that belong to every row, column, and block */
static bool validate(void) {
	return check(0,0) && check (3,1) && check (6,2)
  		&& check(1,3) && check (4,4) && check (7,5)
		&& check(2,6) && check (5,7) && check (8,8);
}

/* Convert a field to an integer for easy-to-read output */
static int field2int(unsigned long long field) {
    if (field == 0)
        return 0;
    else {
        int i;
 
        for (i=0; i<9; i++) {
            if (field & 1ULL<<(i*4))
                break;
        }
        return i+1;
    }
}

/* Print the finished sudoku */ 
static void print_sud(void) {
	int i,j;
	for(i=0; i<9; i++){
		for (j=0; j<9; j++){
			printf("%d ", field2int(sud[j+(i*9)]));
		}
		printf("\n");
	}
}

int main(int argc, char **argv) {
    int i, j, zeros, z;

    /* Implement GNU conventions */
    for(i = 1; i < argc; i++) {
        if (strcmp(argv[i], "-h")==0 || strcmp(argv[i], "--help") == 0) {
            printf("Usage: desud [OPTIONS]\n"
                   "Solve Sudoku puzzle using backtracking method.\n"
                   "Read input data from standard input and write the results to standard output.\n"
                   "Use 0 to represent unknown data in the input table.\n");
    	    exit(0);
    	} else if (strcmp(argv[i], "--version") == 0) {
            printf("%s\n", VERSION);
            exit(0);
        }
    }

    /* Read the puzzle */
    for(i=0; i<81; i++) {
        int n;
        if (scanf("%1d", &n) != 1)
            xit("Error reading source data");
        if (n==0)
            sud[i] = 0;
        else
            sud[i] = 1ULL<<((n-1)*4);
    }

    if (!validate())
        xit("Bad source data");

    /* Count the zeros and store their locations */
    zeros = 0;
    for (i=0; i<9; i++) {
        for (j=0; j<9; j++) {
            if (sud[j+i*9] == 0) {
                stack[zeros].x = j;
                stack[zeros].y = i;
                stack[zeros++].i = 1;
            }
        }
    }

    /* Solves puzzle by backtracking */
    z = 0;
    while (z < zeros) {
        int y = stack[z].y;
        int x = stack[z].x;
        int y9x = y*9 + x;

        if (stack[z].i > 9) {
            /* No more digits, backtrack */
            stack[z].i = 1;
            sud[y9x] = 0;
            z--;
            if (z < 0)
                break; /* Unsolvable */
            stack[z].i++;
        } else {
            sud[y9x] = 1ULL<<((stack[z].i - 1)*4);
	    if (check(x, y))
                z++; /* One cell filled, advance */
            else
                stack[z].i++; /* Try next digit */
        }
    }

    /* Print solved puzzle */
    print_sud();
    if (z < 0)
        xit("Can't find a solution");
    /* Self-check */
    if(!validate())
       xit("Bad solution!");

    return EXIT_SUCCESS;
}