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

#define GRIDSIZE 9
#define MAXLINE GRIDSIZE+2

unsigned int grid[GRIDSIZE][GRIDSIZE];
unsigned int col[GRIDSIZE];
unsigned int row[GRIDSIZE];
unsigned int region[GRIDSIZE];
unsigned int istack[GRIDSIZE*GRIDSIZE];
unsigned int jstack[GRIDSIZE*GRIDSIZE];
unsigned int stackp;

void grid_input(char *filename);
void grid_display();
void placenum(unsigned n, unsigned i, unsigned j);
void removenum(unsigned n, unsigned i, unsigned j);
unsigned solve();
unsigned legal(unsigned n, unsigned i, unsigned j);

main(int argc, char **argv) {
    grid_input(argv[1]);
    grid_display();
    if (solve()) {
	printf("Solution found!\n");
	grid_display();
    }
    else {
	printf("No solution found\n");
    }
    exit(0);
}

/* read initial grid from specified file */
void grid_input(char *filename) {

    FILE *fp;
    char line[MAXLINE];
    unsigned i,j;

    if ((fp = fopen(filename, "r")) == NULL) {
	fprintf(stderr, "Couldn't open input file\n");
	exit(1);
    }
    stackp = 0;
    for (i = 0; i < GRIDSIZE; i++) {
	if (fgets(line, MAXLINE, fp)) {
	    for (j = 0; j < GRIDSIZE; j++) {
		if (line[j] >= '1' && line[j] <= '9') {
		    placenum(line[j] - '0', i, j);
		}
		else { /* assume empty */
		    istack[stackp] = i;
		    jstack[stackp] = j;
		    stackp++;
		}
	    }
	}
	else {
	    fprintf(stderr, "Unexpected input error\n");
	    exit(1);
	}
    }
}

/* solve grid with current stack of empty squares */
unsigned solve() {
    int n;
    int i, j;

    if (stackp <= 0) { /* no empty squares so */
        return 1; /* solved */
    }
    stackp--;
    i = istack[stackp];
    j = jstack[stackp];

    for (n = 1; n <= 9; n++) {
	if (legal(n, i, j)) {
	    placenum(n, i, j);
	    if (solve()) {
	        return 1;
	    }
	    removenum(n, i, j);
	}
    }
    /* no solution at all from this point */
    stackp++;
    return 0;
}


/* is it legal to put value n at row i, column j? */
unsigned legal(unsigned n, unsigned i, unsigned j) {
    return (grid[i][j] == 0) &&
        ((row[i] & (1 << (n-1))) == 0) &&
        ((col[j] & (1 << (n-1))) == 0) &&
	((region[3 * (i/3) + (j/3)] & (1 << (n-1))) == 0);
}

/* place number n at row i, column j */
void placenum(unsigned n, unsigned i, unsigned j) {
    unsigned r;

    grid[i][j] = n;
    row[i] ^= (1 << (n-1));
    col[j] ^= (1 << (n-1));
    region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}

/* remove number n at row i, column j */
void removenum(unsigned n, unsigned i, unsigned j) {
    unsigned r;

    grid[i][j] = 0;
    row[i] ^= (1 << (n-1));
    col[j] ^= (1 << (n-1));
    region[3 * (i/3) + (j/3)] ^= (1 << (n-1));
}



/* display current grid */
void grid_display() {
    unsigned i, j;

    for (i = 0; i < GRIDSIZE; i++) {
	for (j = 0; j < GRIDSIZE; j++) {
	    printf("+---");
	}
	printf("+\n");
	for (j = 0; j < GRIDSIZE; j++) {
	    if (grid[i][j] == 0) {
	        printf("|   ");
	    }
	    else {
		printf("| %d ", grid[i][j]);
	    }
	}
	printf("|\n");
    }
    for (j = 0; j < GRIDSIZE; j++) {
	printf("+---");
    }
    printf("+\n");
}