#include 

struct state_t { 
	short S[9][9]; /* The Sudoku matrix, each cell has 9 bits representing each possible value for that cell */
	short D[9][9]; /* Number of bits still on for each cell */
} ; 

typedef struct state_t state_t; 

/* Initialize the object */
void init_SD(state_t *S)
{
	int i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for (i=0; i<9; i++)
		for (j=0; j<9; j++)
			S->S[i][j]=511; /* 511 is 1 1111 1111 in binary */
	for (i=0; i<9; i++)
		for (j=0; j<9; j++)
			S->D[i][j]=9;   /* no cell is done yet, so each cell has 9 possibilities */
}

/* Print a Sudoku matrix */
void print_S(state_t *S)
{
	int i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	printf("-------------------------------------------------------------------------------------------\n");
	for (i=0; i<9; i++) {
		for (j=0; j<9; j++)
			switch (S->S[i][j]) {
				case   0: printf("print_S() ERROR! Zero in S[%d][%d]\n", i, j); break; 
				case   1: printf("|    1    "); break; 
				case   2: printf("|    2    "); break;
				case   4: printf("|    3    "); break;
				case   8: printf("|    4    "); break;
				case  16: printf("|    5    "); break;
				case  32: printf("|    6    "); break;
				case  64: printf("|    7    "); break;
				case 128: printf("|    8    "); break;
				case 256: printf("|    9    "); break;
				default : printf("|         "); break; /* unsolved cell */
			}
		printf("|\n");
		printf("-------------------------------------------------------------------------------------------\n");
	} 
	printf("\n");
}

/* Print the "Done" matrix */ 
void print_D(state_t *S)
{
	int i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	printf("-------------------------------------------------------------------------------------------\n");
	for (i=0; i<9; i++) {
		for (j=0; j<9; j++)
			switch (S->D[i][j]) {
				case   0: printf("print_D() ERROR! D[%d][%d] has value 0\n",i, j); break;
				case   1: printf("|    X    "); break; /* when that cell has exactly one possibily, it's done */
				case   2:
				case   3:
				case   4:
				case   5:
				case   6:
				case   7:
				case   8:
				case   9: printf("|         "); break; 
				default : printf("print_D() ERROR! D[%d][%d] has value > 9\n", i, j); break;
			}
		printf("|\n");
		printf("-------------------------------------------------------------------------------------------\n");
	} 
	printf("\n");
}

/* show the possibilities remaining in a cell */
void show_cell(state_t *S, int x, int y) 
{
	int m; 
	int i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for  (i=1; i<=9; i++) {
		m = 1 << (i-1);      /* 0 0000 0001 moved 0-8 times */
		if (S->S[x][y] & m)  /* bit-wise AND to see if that bit is still on */
			printf("%d", i); 
		else 
			printf(" "); 
	}
}

/* get the value of a cell whose value has been determined */
int get_cell(state_t *S, int x, int y) 
{
	int m; 
	int i, j, k;
	int return_value, found; 

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	if (S->D[x][y] > 1) { /* assert: cell's value must have been determined */
		printf("get_cell() called on a that is NOT done, x=%d, y=%d\n", x, y);
		show_cell(S, x, y); 
		return 0;
	}

	found = 0; 
	return_value = 0; 
	for  (i=1; i<=9; i++) {
		m = 1 << (i-1);       /* 0 0000 0001 moved 0-8 times */
		if (S->S[x][y] & m) { /* bit-wise AND to find the cell's value */
			if (! found) {
				found = 1;
				return_value += i;
			}
			else {
				printf("get_cell(): ERROR! D[%d][%d] is 1 but S shows more than one possibility\n", x, y); 
				printf("get_cell(): the cell is: ");
				show_cell(S, x, y);
				printf("\n");
				return return_value; /* return the old value */
			}
		}
	}
	
	return return_value;
}

/* given that a cell S(x,y) has been set to v, prune v from the rest of the row */
int prune_row(state_t *S, int x, int y, int v)
{
	int m, i, j, k;
	int made_change = 0;
	int m_prime;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	m       = ~ (1 << (v-1));    /* complement of mask */
	m_prime = 1<< (v-1);         /* mask for value v */
	// printf("prune_row(): v is %x and mask for v, m, is %x\n", v, m); 

	for (j=0; j<9; j++) 
		if ( (S->D[x][j] > 1) &&         /* that cell has > 1 possibilities */
		     (S->S[x][j] & m_prime) &&   /* has v amongst those possibilities */
		     (j != y) ) {                /* NOT the cell that we just set, unlikely, given first condition of >1 possibilities */
			// printf("prune_row(): BEFORE S[%d][%d] = ", x, j); 
			// show_cell(S, x, j); 
			// printf("\n");
			S->S[x][j] &= m;         /* mask out that bit */
			S->D[x][j]--;            /* one possibility less */
			made_change++;           /* count it as a change made */
			// printf("prune_row(): AFTER  S[%d][%d] = ", x, j); 
			// show_cell(S, x, j); 
			// printf("\n");
		} 
	if (made_change > 8) {
		printf("prune_row(): ERROR! made more than 8 prunes in a row for S[%d][%d] value %d\n", x, y, v); 
	}
	return made_change;
}

/* given that a cell S(x,y) has been set to v, prune v from the rest of the column */
int prune_column(state_t *S, int x, int y, int v)
{
	int m, i, j, k;
	int made_change = 0;
	int m_prime;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	m       = ~ (1 << (v-1));    /* complement of mask */
	m_prime = 1<< (v-1);         /* mask for value v */
	// printf("prune_column(): v is %x and mask for v, m, is %x\n", v, m); 

	for (i=0; i<9; i++) 
		if ( (S->D[i][y] > 1) &&         /* that cell has > 1 possibilities */
		     (S->S[i][y] & m_prime) &&   /* has v amongst those possibilities */
		     (i != x) ) {                /* NOT the cell that we just set, unlikely, given first condition of >1 possibilities */
			// printf("prune_column(): BEFORE S[%d][%d] = ", i, y); 
			// show_cell(S, i, y); 
			// printf("\n");
			S->S[i][y] &= m;         /* mask out that bit */
			S->D[i][y]--;            /* one possibility less */
			made_change++;           /* count it as a change made */
			// printf("prune_column(): AFTER  S[%d][%d] = ", i, y); 
			// show_cell(S, i, y); 
			// printf("\n");
		} 
	if (made_change > 8) {
		printf("prune_column(): ERROR! made more than 8 prunes in a row for S[%d][%d] value %d\n", x, y, v); 
	}
	return made_change;
}

/* given that a cell S(x,y) has been set to v, prune v from the rest of the block */
int prune_block(state_t *S, int x, int y, int v)
{
	int m, i, j, k;
	int made_change = 0;
	int m_prime;

	int Bx      = x/3;
	int start_x = Bx * 3;
	int end_x   = start_x + 2;

	int By      = y/3;
	int start_y = By * 3;
	int end_y   = start_y + 2;

	m       = ~ (1 << (v-1));    /* complement of mask */
	m_prime = 1<< (v-1);         /* mask for value v */

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	if (S->D[x][y] != 1) {
		printf("loop_neighbour(): ERROR! given a cell S[%d][%d] that has not been set to $d\n", x, y, v);  
		return 0;
	}

	for (i=start_x; i<=end_x; i++) {
		for (j=start_y; j<=end_y; j++) {
			if ((i != x) && (j != y) &&     /* not the cell that we just set */
		            (S->D[i][j] > 1) &&         /* that cell has > 1 possibilities, must be */
			    (S->S[i][j] & m_prime)) {   /* and v is in that cell's possibilities */
				S->S[i][j] &= m;         /* mask out that bit */
				S->D[i][j]--;            /* one possibility less */
				made_change++;           /* count it as a change made */
			}
		}
	}
	return made_change; 
}

/* given S(x, y) which has been set to v, remove v from its neighbours in the same block */
int loop_neighbour(state_t *S, int x, int y, int v) 
{
	int i, j, k;
	int m, m_prime;
	int made_change = 0; 

	/* neighbour calculation worked out with Jeff Barto :-) */
	int r       = x/3;
	int start_x = r*3; 
	int end_x   = start_x + 2; 
	int rr      = y/3;
	int start_y = rr*3;
	int end_y   = start_y + 2;

	/*
	printf("loop_neighbour() called with S[%d][%d] = %d --- cell is: ", x, y, v); 
	show_cell(S, x, y); 
	printf("\n"); 
	*/

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	if (S->D[x][y] != 1) {
		printf("loop_neighbour(): ERROR! given a cell S[%d][%d] that has not been set to $d\n", x, y, v);  
		return 0;
	}

	m       = ~ (1 << (v-1)); 
	m_prime =    1 << (v-1); 

	for (i = start_x; i <= end_x; i++) 
		for (j = start_y; j <= end_y; j++) {
				/*
				printf("loop_neighbour(): testing  neighbour S[%d][%d]             %d --- cell is: ", i, j, v); 
				show_cell(S, i, j); 
				printf("\n"); 
				*/
			if ((i != x) && (j != y)          && /* not the cell itself */
			    (S->D[i][j] != 1)             && /* not a set cell */
			    (S->S[i][j] & m_prime) ) {       /* but that cell has v as a possibility */
				/*
				printf("loop_neighbour(): changing neighbour S[%d][%d] masking out %d --- cell is: ", i, j, v); 
				show_cell(S, i, j); 
				printf("\n"); 
				*/
				S->S[i][j] &= m; 
				S->D[i][j]--;
				/*
				printf("loop_neighbour(): after changing     S[%d][%d] masking out %d --- cell is: ", i, j, v); 
				show_cell(S, i, j); 
				printf("\n"); 
				*/
				made_change++;
			}
		}
	return made_change;
}

/* set the value of a cell to v, update the corresponding "Done" value for that cell */
/* then, prune the row and column */
int set_cell(state_t *S, int x, int y, int v)
{
	int m, i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	// printf("set_cell() setting S[%d][%d] to %d; value of S is origininally ---- ", x, y, v); 
	// show_cell(S, x, y); 
	// printf("\n");
	switch (v) {
		case   0: break; 
		case   1: S->S[x][y] =   1; S->D[x][y] = 1; break; 
		case   2: S->S[x][y] =   2; S->D[x][y] = 1; break;
		case   3: S->S[x][y] =   4; S->D[x][y] = 1; break;
		case   4: S->S[x][y] =   8; S->D[x][y] = 1; break;
		case   5: S->S[x][y] =  16; S->D[x][y] = 1; break;
		case   6: S->S[x][y] =  32; S->D[x][y] = 1; break;
		case   7: S->S[x][y] =  64; S->D[x][y] = 1; break;
		case   8: S->S[x][y] = 128; S->D[x][y] = 1; break;
		case   9: S->S[x][y] = 256; S->D[x][y] = 1; break;
		default : printf("set_cell(): ERROR! Value in a cell can only be 0-9\n"); break;
	}

	// printf("set_cell() result of setting S[%d][%d] to %d; value of S now   ---- ", x, y, v); 
	// show_cell(S, x, y); 
	// printf("\n"); 
	return 1+prune_row(S, x, y, v)+prune_column(S, x, y, v)+prune_block(S, x, y, v); 
}

/* Get input from the command line, 0 for a blank cell and all others can only have values of 1-9 */
void read_S(state_t *S, int argc, char *argv[])
{
	int n, i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	if (argc != 82) {
		printf("Usage %s data\n", argv[0]); 
		printf("(Use 0 to represent a blank)\n"); 
		return;
	}

	for (n=1; n i = %d j = %d ---> k = %d\n", n, argv[n], i, j, k); 
	} 
}

/* check out all the "Done" values in a Sudoku matrix to determine if we have finished */
int done(state_t *S) 
{
	int i, j, k;
	int d = 1; 

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for (i=0; i<9; i++) 
		for (j=0; j<9; j++)
			d = d && (S->D[i][j] == 1); /* every "DONE" value must be exactly 1 */
	return d;
}

/* print out the full Sudoku matrix with the possibilities of each cell */
void print_full_S(state_t *S)
{
	int i, j, k;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	printf("-------------------------------------------------------------------------------------------\n");
	for (i=0; i<9; i++) {
		printf("|");
		for (j=0; j<9; j++) {
			show_cell(S, i,j); 
			printf("|");
		}
		printf("\n"); 
		printf("-------------------------------------------------------------------------------------------\n");
	} 
	printf("\n");
}

/* given a block, make sure a value v appears only once in the 9 cells that make up that block, return non-zero if error found */
int once_in_block(state_t *S, int Bx, int By, int *made_change)
{
	int i, j, k;
	int m;
	int found;
	int num; 

	int num_x = -1;
	int num_y = -1;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for (num=1; num<=9; num++) {
		m = 1 << (num-1); 
		found = 0; 

		for (i = Bx*3; i < 3*Bx+3; i++)
			for (j = By * 3; j < 3*By+3; j++)
				if (S->S[i][j] & m) {
					found++; 
					num_x = i; 
					num_y = j;
				}

		if (! found) {
			// printf("once_in_block: ERROR %d not found in block Bx=%d By=%d\n", Bx, By);
			return num;
		}
		else if ((found == 1) && (S->D[num_x][num_y] != 1)) { 
			/* found a value in this block that can only appear in one cell, and that cell has NOT been set to value */
			// printf("once_in_block: calling set_cell for  S[%d][%d] = %d; cell is --- ", num_x, num_y, num); 
			// show_cell(S, num_x, num_y); 
			// printf(" with D value = %d", S->D[num_x][num_y]);
			// printf("\n");
			*made_change += set_cell(S, num_x, num_y, num);
			// printf("once_in_block: made_change:  S[%d][%d] = %d\n", num_x, num_y, num); 
		}
		/* else, v is in more than one cell in block, ie: we can't eliminate the possibilities for that value v in that block yet */
	}
	return 0; 
}

/* given a column, make sure a value v appears only once in the 9 cells that make up that column */
int once_in_column(state_t *S, int column, int *made_change)
{
	int i, j, k;
	int v; 
	int m;
	int found;
	int found_row;
	
	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for (v=0; v<9; v++) {
		m = 1 << v; 
		found = 0; 
		for (i=0; i<9; i++) 
			if (S->S[i][column] & m) {
				found++;
				found_row = i;
			}
		if (! found) {
			// printf("once_in_column: ERROR %d not found in column %d\n", v+1, column);
			return v+1;
		}
		else if ((found == 1) && (S->D[found_row][column] != 1)) { /* found v only in a cell but that cell is not set to v */
			// printf("once_in_column: calling set_cell setting %d in S[%d][%d]; cell is --- ", v+1, found_row, column);
			// show_cell(S, found_row, column); 
			// printf("\n");
			*made_change += set_cell(S, found_row, column, v+1);
		}
		/* else, v is in more than one column, ie: we can't eliminate the possibilities for that value v in that column yet */
	}
	return 0;
}

/* given a row, make sure a value v appears only once in the 9 cells that make up that row */
int once_in_row(state_t *S, int row, int *made_change)
{
	int i, j, k;
	int v; 
	int m;
	int found;
	int found_column;
	
	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for (v=0; v<9; v++) {
		m = 1 << v; 
		found = 0; 
		for (j=0; j<9; j++) 
			if (S->S[row][j] & m) {
				found++;
				found_column = j;
			}
		if (! found) {
			// printf("once_in_row: ERROR %d not found in row %d\n", v+1, row);
			return v;
		}
		else if ((found == 1) && (S->D[row][found_column] != 1)) { /* found v only in a cell but that cell is not set to v */
			// printf("once_in_row: calling set_cell setting %d in S[%d][%d]; cell is --- ", v+1, row, found_column);
			// show_cell(S, row, found_column); 
			// printf("\n");
			*made_change += set_cell(S, row, found_column, v+1);
		}
		/* else, v is in more than one row, ie: we can't eliminate the possibilities for that value v in that row yet */
	}
	return 0; 
} 

/* find the cell with the least number of possibilities and set its coordinates in the (x,y) pointers given */
void find_cell_with_min(state_t *S, int *x, int *y)
{
	int i, j, k;
	int min = 9; 

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	for (i=0; i<9; i++) 
		for (j=0; j<9; j++) 
			if ((S->D[i][j] > 1) && (S->D[i][j] < min)) {
				min = S->D[i][j]; 
				*x  = i;
				*y  = j;
			}
		
}

/* clone source Sudoku to destination Sudoku */
void clone(state_t *src, state_t *dest)
{
	int i, j, k;
	if (src == NULL) {
		printf("clone(): ERROR NULL source pointer\n"); 
		return;
	}
	if (dest == NULL) {
		printf("clone(): ERROR NULL destination pointer\n"); 
		return;
	}
	for (i=0; i<9; i++) 
		for (j=0; j<9; j++) {
			dest->S[i][j] = src->S[i][j];
			dest->D[i][j] = src->D[i][j];
		}
}

/* reduce as much as possible, if not, generate candidates and reduce them */
reduce_to_min(state_t *S, int iteration_count)
{
	int i, j, k;
	char r;
	state_t *new_S; 
	int made_change;
	int m;
	int v;

	int x, y;

	if (S == NULL) {
		printf("ERROR NULL S pointer\n"); 
		return;
	}

	// printf("reduce_to_min():  Entering reduce_to_min() with count %d\n", iteration_count);
	// printf("reduce_to_min(): Candidate matrix is: \n");
	// print_S(S);

	do {
		made_change = 0; 
		// printf("reduce_to_min(): Iteration %d\n", ++iteration_count);

		/*
		for (i=0; i<9; i++) 
			for (j=0; j<9; j++) 
				if (S->D[i][j] == 1) 
					made_change += loop_neighbour(S, i, j, get_cell(S, i, j));
		 */

		for (i=0; i<3; i++)
			for (j=0; j<3; j++) 
				if (once_in_block(S, i, j, &made_change)) {
					// printf("reduce_to_min() found_error when trying block Bx=%d By=%d\n", i, j);
					return;
				}
		for (i=0; i<9; i++)
			if (once_in_row(S, i, &made_change)) {
				// printf("reduce_to_min() found_error when trying row %d\n", i);
				return;
			}
		for (j=0; j<9; j++) 
			if (once_in_column(S, j, &made_change)) {
				// printf("reduce_to_min() found_error when trying column %d\n", j);
				return;
			}

		// print_D(S); print_full_S(S); print_S(S);
	} while (made_change && ! done(S));

	if (! made_change) {
		// printf("reduce_to_min(): Not Done\n");

		find_cell_with_min(S, &x, &y);
		// printf("reduce_to_min(): Found cell S[%d][%d]; cell is ---- ", x, y); 
		// show_cell(S, x, y); 
		// printf("\n");

		for (v=1; v<=9; v++) 
			if (S->S[x][y] & (1 << (v-1))) { /* v is a possible value in cell S[x][y] */
			
				new_S = (state_t *) malloc(sizeof(state_t)); 
				if (new_S == NULL) {
					printf("Out of memory\n"); 
					return 0;
				}

				clone(S, new_S);
				made_change += set_cell(new_S, x, y, v);
				reduce_to_min(new_S, iteration_count);
			}
	}
	else {
		// printf(" ***** ----- ^^^^^ ===== vvvvv Done ***** ----- ^^^^^ ===== vvvvv \n");
		print_S(S);
	}
}

/* 20 Mar 2008, created by Chia-Ling Lee */
int main(int argc, char *argv[]) 
{ 
	int i, j, k;
	state_t *S; 

	if (argc != 82) {
		printf("Usage %s data\n", argv[0]); 
		printf("(Use 0 to represent a blank)\n"); 
		return 0;
	}

	S = (state_t *) malloc(sizeof(state_t)); 
	if (S == NULL) {
		printf("Out of memory\n"); 
		return 0;
	}

	/*
	for (i=0; i








1