/* lame sudoku solver
 * adomas.paltanavicius@gmail.com
 * 2006 jun 16: initial coding
 */

#include <sys/signal.h>
#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <unistd.h>
#include <time.h>

/* example sudoku. */
char input_format[] = "\
Seems you have provided sudoku in format I cannot understand.\n\
The input to this program should be like this one:\n\
\n\
*62 34* 75*\n\
1** **5 6**\n\
57* *** *4*\n\
\n\
*** *94 8**\n\
4** *** **6\n\
**5 83* ***\n\
\n\
*3* *** *91\n\
**6 4** **7\n\
*59 *83 26*\n\
\n\
You must use 1-9 for filled-in digits and * for empty cell.\n\
You might also use _ for empty cells which you do not\n\
want to see (anti-spoiler).\n\
Whitespace is ignored, newlines are not required.";

char *numbers[] = {
	"", "first", "second", "third", "fourth",
	"fifth", "sixth", "seventh", "eighth", "ninth"
};

char *boxes[] = {
	"upper left", "upper center", "upper right",
	"middle left", "center", "middle right",
	"lower left", "lower center", "lower right"
};

/* mapping table for index -> box */
int which_box[] = {
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	0, 0, 0, 1, 1, 1, 2, 2, 2,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	3, 3, 3, 4, 4, 4, 5, 5, 5,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
	6, 6, 6, 7, 7, 7, 8, 8, 8,
};

/* single, ever-changing board. */
char board[81];

/* packing/unpacking */
#define encode(row, col) ((row)*9+(col))
#define row(e) ((e)/9)
#define col(e) ((e)%9)

/* nesting level. */
int nesting = 0;

/* saving stack space. yes, words (32 on x86 etc) work fastest. */
int unfilled[81];
int nunfilled;

/* antispoiler */
int antispoiler[81];

/* using bits 1..9 of each. */
int left_cols[9];
int left_rows[9];
int left_boxes[9];

/* running time. */
struct timeval start, end;

/* some prototypes. */
void print_board();
void print_avail(int);
void print_spent();
void die(char *, ...);

/* main func. */
void solve() {
	/* Used stack space: 3 words per call. 
	 * TODO: vars for col, row and box. */
	int first;
	int i, j;
	
	/* if all filled, then done. */
	if (nunfilled == 0) {
		print_board();
		print_spent();
		exit(0);
	}

	/* find first unfilled. */
	for (first=0; first<81; first++) {
		if (unfilled[first])
			break;
	}

	/* what do we have here? */
	j = left_cols[col(first)] &
		left_rows[row(first)] &
		left_boxes[which_box[first]];
	if (j) {
		for (i=1; i<=9; i++) {
			if (j & (1<<i)) {
				/* enter */
				board[first] = '0' + i;
				unfilled[first] = 0;
				nunfilled--;
				nesting++;
				left_cols[col(first)] &= ~(1 << i);
				left_rows[row(first)] &= ~(1 << i);
				left_boxes[which_box[first]] &= ~(1 << i);
				solve();
				/* return -- TODO: move this out of loop. */
				nesting--;
				nunfilled++;
				unfilled[first] = 1;
				board[first] = '*';
				left_cols[col(first)] |= 1 << i;
				left_rows[row(first)] |= 1 << i;
				left_boxes[which_box[first]] |= 1 << i;
			}
		}
	}
	
	return;
}

void prepare() {
	int i;
	/* unfilled */
	nunfilled = 0;
	for (i = 0; i < 81; i++) {
		unfilled[i] = board[i] == '*' || board[i] == '_';
		if (unfilled[i])
			nunfilled++;
		if (board[i] == '_')
			antispoiler[i] = 1;
	}
	/* digits. */
	for (i=0; i<9; i++) {
		left_cols[i] = left_rows[i] = left_boxes[i] = ~0U;
	}
	for (i=0; i<81; i++) {
		if (board[i] != '*' && board[i] != '_') {
			/* could be - '1', but do not overcomplicate without savings.*/
			int x = board[i] - '0';
			if (left_cols[col(i)] & (1 << x))
				left_cols[col(i)] &= ~(1 << x);
			else
				die("you wrote %d in %s row %s column, but %1$d "
					"has already been used in %3$s column before!",
					x, numbers[row(i)+1], numbers[col(i)+1]);
			if (left_rows[row(i)] & (1 << x))
				left_rows[row(i)] &= ~(1 << x);
			else
				die("you wrote %d in %s row %s column, but %1$d "
					"has already been used in %2$s row before!",
					x, numbers[row(i)+1], numbers[col(i)+1]);
			if (left_boxes[which_box[i]] & (1 << x))
				left_boxes[which_box[i]] &= ~(1 << x);
			else
				die("you wrote %d in %s row %s column, but %1$d "
					"has already been used in %s square before!",
					x, numbers[row(i)+1], numbers[col(i)+1],
					boxes[which_box[i]]);
		}
	}
}

/* read board */
void read_board() {
	int pos = 0;
	int c;
	while (pos<81 && (c = getchar()) != EOF) {
		if ((c >= '0' && c <= '9') ||
		     c == '*' || c == '_') {
			board[pos++] = c;
		}
	}
	if (pos != 81) {
		die(input_format);
	}
}

/* print board in a nice way. */
void print_board() {
	int i, j;
	for (i=0; i<9; i++) {
		if (i && i%3 == 0)
			printf("           \n");
		for (j=0; j<9; j++) {
			int enc = encode(i, j);
			if (j && j%3 == 0)
				putchar(' ');
			if (antispoiler[enc])
				putchar('_');
			else
				putchar(board[enc]);
		}
		putchar('\n');
	}
}

/* print set bits 1..9 */
void print_avail(int x) {
	int how = 0;
	int i;
	for (i=1; i<=9; i++) {
		if (x & (1<<i)) {
			if (how)
				printf(",");
			printf("%d", i);
			how++;
		}
	}
	if (!how)
		printf("-");
}

/* termination function. */
void die(char *fmt, ...) {
	va_list ap;

	printf("Oops, ");
	va_start(ap, fmt);
	vprintf(fmt, ap);
	printf("\n");
	exit(0);
}

void print_spent() {
		unsigned spent;
		gettimeofday(&end, NULL);
		spent = end.tv_usec - start.tv_usec;
		printf("(Spent %.2f seconds.)\n", (float) spent/1000000.);
}

void timeout() {
	die("time limit of 5 seconds exceeded!\n"
		"Maybe the server is under heavy load, try later.");
}

void setup() {
	static struct sigaction sa;

	gettimeofday(&start, NULL);
	sa.sa_handler = &timeout;
	sigaction(SIGALRM, &sa, NULL);
	alarm(5);
}

/* entry func. */
int main() {
	setup();
	read_board();
	prepare();
	solve();
	die("No solutions found!? A bug?");
	print_spent();
	exit(0);
}

// vi: ts=4 sw=4 ai