#include <assert.h>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <errno.h>
#include <string.h>

int poss[9][9];
int field[9][9];

#define UNKNOWN	-1

#define TYPE_ROW	0
#define TYPE_COL	1
#define TYPE_CELL	2

struct coord {
	int x;
	int y;
};

void row(int x, int y, struct coord l[9]) {
	int i;
	for (i = 0; i < 9; i++) {
		l[i].x = i;
		l[i].y = y;
	}
}
void col(int x, int y, struct coord l[9]) {
	int i;
	for (i = 0; i < 9; i++) {
		l[i].x = x;
		l[i].y = i;
	}
}
void cell(int x, int y, struct coord l[9]) {
	int i, j;
	int cellx, celly;
	cellx = (x / 3) * 3;
	celly = (y / 3) * 3;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			l[i*3+j].x = cellx+j;
			l[i*3+j].y = celly+i;
		}
	}
}

void printField(int field[9][9]);
void setValue(int x, int y, int number);
void setImpossible(int x, int y, int number);

struct hq {
	void (*h)(int, int, int);
	int x, y, n;
	struct hq *next;
};

/* this must be equal to the number of IGN_ values */
#define QUEUE_COUNT	6

struct queue {
	struct hq *first[QUEUE_COUNT];
	struct hq *last[QUEUE_COUNT];
	int length;
	int maxlength;
	int count;
};

struct queue *queue;

#define IGN_NONE	0
#define IGN_ROW		1
#define IGN_COL		2
#define IGN_VAL		3
#define IGN_CELL	4
#define IGN_LOC		5

/* XXX this should use some hashing instead of searching the queue */
void enqueue(void (*h)(int, int, int), int x, int y, int n, int comp) {
	if (comp != IGN_NONE) {
		struct hq *chq = queue->first[comp];
		while (chq != NULL) {
			if (chq->h == h) {
				switch (comp) {
					case IGN_ROW:
						if ((chq->y == y)
							&& (chq->n == n)) 
							return;
						break;
					case IGN_COL:
						if ((chq->x == x)
							&& (chq->n == n)) 
							return;
						break;
					case IGN_VAL:
						if ((chq->x == x)
							&& (chq->y == y)) 
							return;
						break;
					case IGN_CELL:
						if ((chq->x/3 == x/3)
							&& (chq->y/3 == y/3)
							&& (chq->n == n)) 
							return;
						break;
					case IGN_LOC:
						if (chq->n == n)
							return;
						break;
				}
			}
			chq = chq->next;
		}
	}
	struct hq *hq = (struct hq*)malloc(sizeof(struct hq));
	hq->h = h;
	hq->x = x;
	hq->y = y;
	hq->n = n;
	hq->next = NULL;
	
	if (queue->last[comp]) {
		queue->last[comp]->next = hq;
	}
	else {
		queue->first[comp] = hq;
	}
	queue->last[comp] = hq;
	queue->count++;
	queue->length++;
	if (queue->length > queue->maxlength) {
		queue->maxlength = queue->length;
	}
}

struct hq* dequeue() {
	struct hq *hq;
	int i;
	for (i = 0; i < QUEUE_COUNT; i++) {
		hq = queue->first[i];
		if (hq) {
			queue->first[i] = hq->next;
			if (queue->first[i] == NULL) {
				queue->last[i] = NULL;
			}
			queue->length--;
			return hq;
		}
	}
	return NULL;
}

void H1(int x, int y, int n) {
	int count, i, last;
	// H1: if there is only one possibility for this field left, 
	// take it (singles)
	count = 0;
	for (i = 0; (i < 9) && (count < 2); i++) {
		if (poss[x][y] & (1 << i)) {
			count++;
			last = i;
		}
	}
	if (count == 1) {
		printf("H1  %i, %i=  %i\n", x+1, y+1, last+1);
		setValue(x, y, last);
	}
}

void H2(int x, int y, int n, int i) {
	/* if there is only one place in this col/row/cell left that this value
	 * could be placed, put it there (hidden singles)
	 * */
	struct coord c[9];
	int j, count, last;
	switch (i) {
		case TYPE_ROW:
			row(x, y, c);
			break;
		case TYPE_COL:
			col(x, y, c);
			break;
		case TYPE_CELL:
			cell(x, y, c);
			break;
	}
	count = 0;
	for (j = 0; j < 9; j++) {
		if (poss[c[i].x][c[i].y] & (1 << n)) {
			count++;
			last = j;
		}
	}
	if (count == 1) {
		printf("H2  %i, %i=  %i\n", c[last].x+1, c[last].y+1, n+1);
		setValue(c[last].x, c[last].y, n);	
	}
}

void H2a(int x, int y, int n) {
	H2(x, y, n, TYPE_ROW);
}

void H2b(int x, int y, int n) {
	H2(x, y, n, TYPE_COL);
}

void H2c(int x, int y, int n) {
	H2(x, y, n, TYPE_CELL);
}

void H3(int x, int y, int n) {
	// H3: if all the remaining possibilities for this value in this cell
	// are in the same row/column, then possibilities outside this cell in 
	// this row/column can be eliminated (locked candidates)
	struct coord c[9];
	int i, j, count, last;
	int t[9];
	cell(x, y, c);
	for (j = 0; j < 9; j++) {
		t[j] = 0;
	}
	for (i = TYPE_ROW; i <= TYPE_COL; i++) {
		for (j = 0; j < 9; j++) {
			if (poss[c[j].x][c[j].y] & (1 << n)) {
				if (i == TYPE_ROW) {
					t[c[j].y]++;
				}
				else if (i == TYPE_COL) {
					t[c[j].x]++;
				}
			}
		}
		count = 0; 
		for (j = 0; j < 9; j++) {
			if (t[j] > 0) {
				last = j;
				count++;
			}
		}
		if (count == 1) {
			for (j = 0; j < 9; j++) {
				if (i == TYPE_ROW) {
					if ((j / 3) != (x / 3)) {
						if (poss[j][last] & (1 << n)) {
							printf("H3  %i, %i: !%i\n", j+1, last+1, n+1);
							setImpossible(j, last, n);
						}
					}
				}
				else if (i == TYPE_COL) {
					if ((j / 3) != (y / 3)) {
						if (poss[last][j] & (1 << n)) {
							printf("H3  %i, %i: !%i\n", last+1, j+1, n+1);
							setImpossible(last, j, n);
						}
					}
				}
			}
		}
	}
}

void H4(int x, int y, int n, int i) {
	// H4: if all remaining possibilities for this value in this row/col
	// are within the same cell, then you can delete the other possibilities 
	// of this value in that cell (locked candidates 2)
	int j, k, last, count;
	int cells[3];
	for (j = 0; j < 3; j++) {
		cells[j] = 0;
	}
	for (j = 0; j < 9; j++) {
		if (i == TYPE_ROW) {
			if (poss[j][y] & (1 << n)) {
				cells[j/3] = 1;
			}
		}
		else if (i == TYPE_COL) {
			if (poss[x][j] & (1 << n)) {
				cells[j/3] = 1;
			}
		}
	}
	count = 0;
	for (j = 0; j < 3; j++) {
		if (cells[j] == 1) {
			last = j;
			count++;
		}
	}
	if (count == 1) {
		for (j = 0; j < 3; j++) {
			for (k = 0; k < 3; k++) {
				if (i == TYPE_ROW) {
					if (y/3*3+k != y) {
						if (poss[last*3+j][y/3*3+k] & (1 << n)) {
							printf("H4  %i, %i: !%i\n", last*3+j+1, 
								y/3*3+k+1, n+1);
							setImpossible(last*3+j, y/3*3+k, n);
						}
					}
				}
				else if (i == TYPE_COL) {
					if (x/3*3+j != x) {
						if (poss[x/3*3+j][last*3+k] & (1 << n)) {
							printf("H4  %i, %i: !%i\n", x/3*3+j+1, 
								last*3+k+1, n+1);
							setImpossible(x/3*3+j, last*3+k, n);
						}
					}
				}
			}
		}
	}
}

void H4a(int x, int y, int n) {
	H4(x, y, n, TYPE_ROW);
}

void H4b(int x, int y, int n) {
	H4(x, y, n, TYPE_COL);
}

void naked(int x, int y, int n, int i, int o, char *hn) {
	struct coord c[9];
	struct coord f[9];
	int j, k, count;
	int p[9];
	count = 0;
	for (j = 0; (j < 9) && (count <= o); j++) {
		if (poss[x][y] & (1 << j)) {
			p[count] = j;
			count++;
		}
	}
	if (count != o) {
		return;
	}
	switch (i) {
		case TYPE_ROW:
			row(x, y, c);
			break;
		case TYPE_COL:
			col(x, y, c);
			break;
		case TYPE_CELL:
			cell(x, y, c);
			break;
	}
	count = 0;
	for (j = 0; j < 9; j++) {
		if (poss[c[j].x][c[j].y] == poss[x][y]) {
			f[count] = c[j];
			count++;
		}
	}
	if (count == o) {
		for (j = 0; j < 9; j++) {
			if (poss[c[j].x][c[j].y] != poss[x][y]) {
				for (k = 0; k < o; k++) {
					if (poss[c[j].x][c[j].y] & (1 << p[k])) {
						printf("%s %i, %i: !%i\n", hn, c[j].x+1, 
							c[j].y+1, p[k]+1);
						setImpossible(c[j].x, c[j].y, p[k]);
					}
				}
			}
		}
	}
}

void H5a(int x, int y, int n) {
	// H5: if two values remain and these two are in one other position in this
	// group as well, you can remove them from all other positions (naked 
	// pairs)
	naked(x, y, n, TYPE_ROW, 2, "H5 ");
}

void H5b(int x, int y, int n) {
	naked(x, y, n, TYPE_COL, 2, "H5 ");
}

void H5c(int x, int y, int n) {
	naked(x, y, n, TYPE_CELL, 2, "H5 ");
}

void H6a(int x, int y, int n) {
	// H6: if three values remain and these three are in two other position in 
	// this group as well, you can remove them from all other positions 
	// (naked triples)
	naked(x, y, n, TYPE_ROW, 3, "H6 ");
}

void H6b(int x, int y, int n) {
	naked(x, y, n, TYPE_COL, 3, "H6 ");
}

void H6c(int x, int y, int n) {
	naked(x, y, n, TYPE_CELL, 3, "H6 ");
}

void H7a(int x, int y, int n) {
	// H7: if four values remain and these four are in three other position in 
	// this group as well, you can remove them from all other positions 
	// (naked quads)
	naked(x, y, n, TYPE_ROW, 4, "H7 ");
}

void H7b(int x, int y, int n) {
	naked(x, y, n, TYPE_COL, 4, "H7 ");
}

void H7c(int x, int y, int n) {
	naked(x, y, n, TYPE_CELL, 4, "H7 ");
}

void hidden(int x, int y, int n, int i, int o, char *hn) {
	struct coord c[9];
	int perm[9];
	int j, k, cp, l, found;
	int inmask, outmask;
	switch (i) {
		case TYPE_ROW:
			row(x, y, c);
			break;
		case TYPE_COL:
			col(x, y, c);
			break;
		case TYPE_CELL:
			cell(x, y, c);
			break;
	}
	for (j = 0; j < o; j++) {
		perm[j] = j;
	}
	do {
		/* fill in the rest of the numbers */
		cp = o;
		for (k = 0; k < 9; k++) {
			found = 0;
			for (l = 0; l < o; l++) {
				if (k == perm[l]) {
					found = 1;
					break;
				}
			}
			if (!found) {
				perm[cp] = k;
				cp++;
			}
		}
		/* we now have our permutation: in the first o fields of perm we
		 * have the "in" fields and in the rest the "out" fields */
		outmask = 0;
		inmask = 0;
		/* "and" up the "in" fields */
		for (k = 0; k < o; k++) {
			inmask |= poss[c[perm[k]].x][c[perm[k]].y];
		}
		/* or up the out fields */
		for (; k < 9; k++) {
			outmask |= poss[c[perm[k]].x][c[perm[k]].y];
		}
		/* remove everything that is in the outmask from the inmask */
		inmask &= ~outmask;
		/* count the common possibilities in the "in" group */
		cp = 0;
		for (k = 0; k < 9; k++) {
			if (inmask & (1 << k)) {
				cp++;
			}
		}
		/* our rule */
		if (cp == o) {
			for (k = 0; k < 9; k++) {
				for (l = 0; l < o; l++) {
					if ((poss[c[perm[l]].x][c[perm[l]].y] & (1 << k))
						&& (!(inmask & (1 << k)))) {
						printf("%s %i, %i: !%i\n", hn, c[perm[l]].x+1, 
							c[perm[l]].y+1, k+1);
						setImpossible(c[perm[l]].x, c[perm[l]].y, k);
					}
				}
			}
		}

		/* generate the next permutation */
		perm[o-1]++;
		if (perm[o-1] == 9) {
			perm[o-2]++;
			perm[o-1] = perm[o-2]+1;
			if ((o >= 3) && (perm[o-1] == 9)) {
				perm[o-3]++;
				perm[o-2] = perm[o-3]+1;
				perm[o-1] = perm[o-2]+1;
				if ((o == 4) && (perm[o-1] == 9)) {
					perm[o-4]++;
					perm[o-3] = perm[o-4]+1;
					perm[o-2] = perm[o-3]+1;
					perm[o-1] = perm[o-2]+1;
				}
			}
		}
	} while (perm[o-1] < 9);
}


void H8(int x, int y, int n, int i) {
	// H8: if two positions in a group (row, column, cell) contain the same 
	// two possibilites (among others), and no other position contains them, 
	// then the other posibilities in these two positions can be removed 
	// (hidden pairs)
	hidden(x, y, n, i, 2, "H8 ");
}

void H8a(int x, int y, int n) {
	H8(x, y, n, TYPE_ROW);
}

void H8b(int x, int y, int n) {
	H8(x, y, n, TYPE_COL);
}

void H8c(int x, int y, int n) {
	H8(x, y, n, TYPE_CELL);
}

void H9(int x, int y, int n, int i) {
	// H9: hidden triples (see above)
	hidden(x, y, n, i, 3, "H9 ");
}

void H9a(int x, int y, int n) {
	H9(x, y, n, TYPE_ROW);
}

void H9b(int x, int y, int n) {
	H9(x, y, n, TYPE_COL);
}

void H9c(int x, int y, int n) {
	H9(x, y, n, TYPE_CELL);
}

void H10(int x, int y, int n, int i) {
	// H10: hidden quads (see above)
	hidden(x, y, n, i, 4, "H10");
}

void H10a(int x, int y, int n) {
	H10(x, y, n, TYPE_ROW);
}

void H10b(int x, int y, int n) {
	H10(x, y, n, TYPE_COL);
}

void H10c(int x, int y, int n) {
	H10(x, y, n, TYPE_CELL);
}

/* XXX collapse the two x-wings and make sure it doesn't always search the 
 * whole space */
void H11(int x, int y, int n) {
	// H11: x-wing
	int p[9];
	int c[9];
	int o[2];
	int i, j, k;
	for (i = 0; i < 9; i++) {
		p[i] = 0;
		c[i] = 0;
	}
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if (poss[j][i] & (1 << n)) {
				p[i] |= (1 << j);
				c[i]++;
			}
		}
	}
	if (c[y] != 2) {
		return;
	}
	i = 0;
	for (j = 0; j < 9; j++) {
		if (p[y] & (1 << j)) {
			o[i] = j;
			i++;
		}
	}
	for (i = 0; i < 9; i++) {
		if (i != y) {
			if (p[i] == p[y]) {
				/* found */
				for (j = 0; j < 9; j++) {
					if ((j != y) && (j != i)) {
						for (k = 0; k <= 1; k++) {
							if (poss[o[k]][j] & (1 << n)) {
								printf("H11 %i, %i: !%i\n", o[k]+1, 
									j+1, n+1);
								setImpossible(o[k], j, n);
							}
						}
					}
				}
				break;
			}
		}
	}
}

void H12(int x, int y, int n) {
	// H12: y-wing
	int p[9];
	int c[9];
	int o[2];
	int i, j, k;
	for (i = 0; i < 9; i++) {
		p[i] = 0;
		c[i] = 0;
	}
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if (poss[j][i] & (1 << n)) {
				p[j] |= (1 << i);
				c[j]++;
			}
		}
	}
	if (c[x] != 2) {
		return;
	}
	i = 0;
	for (j = 0; j < 9; j++) {
		if (p[x] & (1 << j)) {
			o[i] = j;
			i++;
		}
	}
	for (i = 0; i < 9; i++) {
		if (i != x) {
			if (p[i] == p[x]) {
				/* found */
				for (j = 0; j < 9; j++) {
					if ((j != x) && (j != i)) {
						for (k = 0; k <= 1; k++) {
							if (poss[j][o[k]] & (1 << n)) {
								printf("H12 %i, %i: !%i\n", j+1, 
									o[k]+1, n+1);
								setImpossible(j, o[k], n);
							}
						}
					}
				}
				break;
			}
		}
	}
}

int markConjugates(int x, int y, int tfield[9][9], int color[9][9], 
	int c, int n){
	struct coord group[9];
	int i, j, count, last;
	int k, l, t;
	int found = 0;
	for (i = TYPE_ROW; i <= TYPE_CELL; i++) {
		switch (i) {
			case TYPE_ROW:
				row(x, y, group);
				break;
			case TYPE_COL:
				col(x, y, group);
				break;
			case TYPE_CELL:
				cell(x, y, group);
				break;
		}
		count = 0;
		for (j = 0; j < 9; j++) {
			if (tfield[group[j].x][group[j].y]) {
				count++;
				if ((group[j].x != x) || (group[j].y != y)) {
					last = j;
				}
			}
		}
		if (count == 2) {
			/* if the starting point is not yet colored, do it */
			if (!(color[x][y] & (3 << c))) {
				color[x][y] |= (1 << c);
			}
			/* if the other point is not yet colored, recurse */
			if (!(color[group[last].x][group[last].y] & (3 << c))) {
				if (color[x][y] & (1 << c)) {
					color[group[last].x][group[last].y] |= (1 << (c+1));
				}
				else {
					color[group[last].x][group[last].y] |= (1 << c);
				}
				found += markConjugates(group[last].x, group[last].y, tfield, 
					color, c, n);
			}
		}
		if (count >= 2) {
			/* check if there are multiple of the same color, if yes
			 * remove all possibilities of this color */
			for (t = 0; t < 9; t++) {
				if (((group[t].x != x) || (group[t].y != y)) &&
					(color[x][y] & (3 << c)) &&
				   ((color[group[t].x][group[t].y] & (3 << c)) ==
					(color[x][y] & (3 << c)))) {
					/* we found a contradiction, all elements of this color can
					 * be removed */
					for (k = 0; k < 9; k++) {
						for (l = 0; l < 9; l++) {
							if ((color[k][l] & (3 << c)) 
								== (color[x][y] & (3 << c))) {
								if (poss[k][l] & (1 << n)) {
									printf("H13 %i, %i: !%i\n", k+1, l+1, n+1);
									setImpossible(k, l, n);
								}
							}
						}
					}
					return 1;
				}
			}
		}
	}
	return found;
}

int checkForbidden(int tfield[9][9], int color[9][9], int c, int n) {
	int ffield[9][9];
	struct coord co[9]; 
	int i, j, k, t;
	int found = 0;
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			ffield[i][j] = 0;
		}
	}
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			for (t = TYPE_ROW; t <= TYPE_CELL; t++) {
				switch (t) {
					case TYPE_ROW:
						row(i, j, co);
						break;
					case TYPE_COL:
						col(i, j, co);
						break;
					case TYPE_CELL:
						cell(i, j, co);
						break;
				}
				for (k = 0; k < 9; k++) {
					ffield[co[k].x][co[k].y] |= color[i][j];
				}
			}
		}
	}
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if ((tfield[i][j])
				&& ((ffield[i][j] & (3 << c)) == (3 << c))
				&& ((color[i][j] & (3 << c)) == 0)
				&& (poss[i][j] & (1 << n))) {
				printf("H13 %i, %i: !%i\n", i+1, j+1, n+1);
				setImpossible(i, j, n);
				found = 1;
			}
		}
	}
	return found;
}

void H13(int x, int y, int n) {
	// H13: coloring
	int tfield[9][9];
	int color[9][9];
	int i, j, c;

	/* bit-mark all positions that are possible */
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if (poss[i][j] & (1 << n)) {
				tfield[i][j] = 1;
			}
			else {
				tfield[i][j] = 0;
			}
			color[i][j] = 0;
		}
	}
	c = 0;
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if (tfield[i][j]) {
				if (color[i][j] == 0) {
					if (markConjugates(i, j, tfield, color, c, n)) {
						/* we already found something */
						return;
					}
					/* see through the field to check if any of the
					 * possibilities is forbidden by both conjugates */
					if (checkForbidden(tfield, color, c, n)) {
						return;
					}
					c += 2;
				}
			}
		}
	}
}

// XXX merge these two
void H14(int x, int y, int n) {
	int cfield[9][9];
	int row[9];
	int rc[9];
	int i, j, k, l, c, count;
	c = y;
	for (i = 0; i < 9; i++) {
		rc[i] = 0;
	}
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if (poss[i][j] & (1 << n)) {
				cfield[i][j] = 1;
				rc[j]++;
			}
			else {
				cfield[i][j] = 0;
			}
		}
	}
	if ((rc[c] != 0) && (rc[c] <=3)) {
		for (i = 0; i < 9; i++) {
			if ((i != c) && (rc[i] != 0)) {
				for (j = i; j < 9; j++) {
					if ((j != i) && (j != c) && (rc[j] != 0)) {
						count = 0;
						for (k = 0; k < 9; k++) {
							row[k] = cfield[k][c] | cfield[k][i] | cfield[k][j];
							if (row[k]) {
								count++;
							}
						}
						if (count == 3) {
							for (k = 0; k < 9; k++) {
								for (l = 0; l < 9; l++) {
									if ((row[l]) && (k != c) 
										&& (k != i) && (k != j)) {
										if (cfield[l][k]) {
											printf("H14 %i, %i: !%i\n", 
												l+1, k+1, n+1);
											setImpossible(l, k, n);
										}
									}
								}
							}
							break;
						}
					}
				}
			}
		}
	}
}

void H15(int x, int y, int n) {
	int cfield[9][9];
	int row[9];
	int rc[9];
	int i, j, k, l, c, count;
	c = x;
	for (i = 0; i < 9; i++) {
		rc[i] = 0;
	}
	for (i = 0; i < 9; i++) {
		for (j = 0; j < 9; j++) {
			if (poss[i][j] & (1 << n)) {
				cfield[j][i] = 1;
				rc[i]++;
			}
			else {
				cfield[j][i] = 0;
			}
		}
	}
	if ((rc[c] != 0) && (rc[c] <=3)) {
		for (i = 0; i < 9; i++) {
			if ((i != c) && (rc[i] != 0)) {
				for (j = i; j < 9; j++) {
					if ((j != i) && (j != c) && (rc[j] != 0)) {
						count = 0;
						for (k = 0; k < 9; k++) {
							row[k] = cfield[k][c] | cfield[k][i] | cfield[k][j];
							if (row[k]) {
								count++;
							}
						}
						if (count == 3) {
							for (k = 0; k < 9; k++) {
								for (l = 0; l < 9; l++) {
									if ((row[l]) && (k != c) 
										&& (k != i) && (k != j)) {
										if (cfield[l][k]) {
											printf("H15 %i, %i: !%i\n", 
												k+1, l+1, n+1);
											setImpossible(k, l, n);
										}
									}
								}
							}
							break;
						}
					}
				}
			}
		}
	}
}

void setPossible(int x, int y, int number) {
	poss[x][y] |= 1 << number;
}

void setImpossible(int x, int y, int number) {
	// mark as impossible
	if (poss[x][y] & (1 << number)) {
		poss[x][y] &= ~(1 << number);

		enqueue(H1, x, y, number, IGN_VAL);
		enqueue(H2a, x, y, number, IGN_ROW);
		enqueue(H2b, x, y, number, IGN_COL);
		enqueue(H2c, x, y, number, IGN_CELL);
		enqueue(H3, x, y, number, IGN_CELL);
		enqueue(H4a, x, y, number, IGN_ROW);
		enqueue(H4b, x, y, number, IGN_COL);
		enqueue(H5a, x, y, number, IGN_ROW);
		enqueue(H5b, x, y, number, IGN_COL);
		enqueue(H5c, x, y, number, IGN_CELL);
		enqueue(H6a, x, y, number, IGN_ROW);
		enqueue(H6b, x, y, number, IGN_COL);
		enqueue(H6c, x, y, number, IGN_CELL);
		enqueue(H7a, x, y, number, IGN_ROW);
		enqueue(H7b, x, y, number, IGN_COL);
		enqueue(H7c, x, y, number, IGN_CELL);
/*		enqueue(H8a, x, y, number, IGN_ROW);
		enqueue(H8b, x, y, number, IGN_COL);
		enqueue(H8c, x, y, number, IGN_CELL);
		enqueue(H9a, x, y, number, IGN_ROW);
		enqueue(H9b, x, y, number, IGN_COL);
		enqueue(H9c, x, y, number, IGN_CELL);
		enqueue(H10a, x, y, number, IGN_ROW);
		enqueue(H10b, x, y, number, IGN_COL);
		enqueue(H10c, x, y, number, IGN_CELL);*/
		enqueue(H11, x, y, number, IGN_ROW);
		enqueue(H12, x, y, number, IGN_COL);
//		enqueue(H13, x, y, number, IGN_LOC);
		enqueue(H14, x, y, number, IGN_ROW);
		enqueue(H15, x, y, number, IGN_COL);
		/* XXX missing heuristics:
		 * swordfish
		 * yellyfish
		 * xy-wing
		 * multi-colors
		 * */
	}
}

void setValue(int x, int y, int number) {
	int c;
	int celly, cellx;
	int i, j;

	// idempotent
	if (field[x][y] == number) {
		return;
	}
	
	cellx = (x / 3) * 3;
	celly = (y / 3) * 3;
	
	// make sure this is valid
	assert(field[x][y] == UNKNOWN);
	for (c = 0; c < 9; c++) {
		if (c != x) {
			assert(field[c][y] != number);
		}
		if (c != y) {
			assert(field[x][c] != number);
		}
	}
	// make sure there is no equal one in this cell
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			assert(field[cellx + i][celly + j] != number);
		}
	}
	// mark this field
	field[x][y] = number;
	poss[x][y] = 0;
	// mark every other occurence in this row and column impossible
	for (c = 0; c < 9; c++) {
		setImpossible(c, y, number);
		setImpossible(x, c, number);
	}
	// mark every other occurence in this cell impossible
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 3; j++) {
			setImpossible(cellx + i, celly + j, number);
		}
	}
}

void printField(int field[9][9]) {
	int x, y;
	for (y = 0; y < 9; y++) {
		if ((y % 3) == 0) {
			printf("+-----+-----+-----+\n");
		}
		for (x = 0; x < 9; x++) {
			if ((x % 3) == 0) {
				printf("|");
			}
			else {
				printf(" ");
			}
			if (field[x][y] != UNKNOWN) {
				printf("%i", field[x][y]+1);
			}
			else {
				printf(" ");
			}
		}
		printf("|\n");
	}
	printf("+-----+-----+-----+\n");
}

int checkField() {
	int n, x, y, i, j, c[9];
	int count;
	for (y = 0; y < 9; y++) {
		for (n = 0; n < 9; n++) {
			c[n] = 0;
		}
		for (x = 0; x < 9; x++) {
			c[field[x][y]]++;
		}
		for (n = 0; n < 9; n++) {
			if (c[n] > 1) {
				printf("Error in row %i: %i used multiple times\n", y+1, n+1);
				return -1;
			}
		}
	}
	for (x = 0; x < 9; x++) {
		for (n = 0; n < 9; n++) {
			c[n] = 0;
		}
		for (y = 0; y < 9; y++) {
			c[field[x][y]]++;
		}
		for (n = 0; n < 9; n++) {
			if (c[n] > 1) {
				printf("Error in col %i: %i used multiple times\n", x+1, n+1);
				return -1;
			}
		}
	}
	for (x = 0; x < 3; x++) {
		for (y = 0; y < 3; y++) {
			for (n = 0; n < 9; n++) {
				c[n] = 0;
			}
			for (i = 0; i < 3; i++) {
				for (j = 0; j < 3; j++) {
					c[field[x*3+i][y*3+j]]++;
				}
			}
			for (n = 0; n < 9; n++) {
				if (c[n] > 1) {
					printf("Error in cell %ix%i: %i used multiple times\n", 
					x+1, y+1, n+1);
					return -1;
				}
			}
		}
	}
	count = 0;
	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			if (field[x][y] != UNKNOWN) {
				count++;
			}
			if ((poss[x][y] == 0) && (field[x][y] == UNKNOWN)) {
				printf("Error: no option left in field %i,%i\n", x+1, y+1);
				return -1;
			}
		}
	}
	if (count == 81) {
		return 1;
	}
	return 0;
}

void hist() {
	int x, y, j, count, c[9];
	for (x = 0; x < 9; x++) {
		c[x] = 0;
	}
	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			count = 0;
			for (j = 0; j < 9; j++) {
				if (poss[x][y] & (1 << j)) {
					count++;
				}
			}
			c[count]++;
		}
	}
	fprintf(stderr, "%i\n", c[0]);
	for (x = 0; x < 9; x++) {
		printf("%i: %2i ", x, c[x]);
		for (y = 0; y < c[x]; y++) {
			printf("+");
		}
		printf("\n");
	}
}

void setString(char *s) {
	int x, y;

	for (y = 0; y < 9; y++) {
		for (x = 0; x < 9; x++) {
			if (s[y * 9 + x] != '.') {
				setValue(x, y, s[y * 9 + x] - '1');
			}
		}
	}
}

int solve(int d) {
	int bfield[9][9];
	int bposs[9][9];
	int nposs[9][9];
	int res, x, y, c, i, j, count, cc;
	int minpos, minx, miny;
	struct hq *hq;
	while ((hq = dequeue())) {
		hq->h(hq->x, hq->y, hq->n);
		free(hq);
	}
	res = checkField();
	minpos = 9;
	if (res == 0) {
		/* save state */
		for (x = 0; x < 9; x++) {
			for (y = 0; y < 9; y++) {
				bfield[x][y] = field[x][y];
				bposs[x][y] = poss[x][y];
				nposs[x][y] = 0;
				for (c = 0; c < 9; c++) {
					if (poss[x][y] & (1 << c)) {
						nposs[x][y]++;
					}
				}
				if ((nposs[x][y] < minpos) && (nposs[x][y] > 1)) {
					minpos = nposs[x][y];
					minx = x;
					miny = y;
				}
			}
		}
		for (c = 0; c < 9; c++) {
			if (poss[minx][miny] & (1 << c)) {
				/* try to set [x][y] to c */
				setValue(minx, miny, c);
				/* the run solve on it */
				res = solve(d+1);
				/* if we get a result, return ok */
				if (res == 1) {
					return 1;
				}
				/* else restore the state before */
				else {
					for (i = 0; i < 9; i++) {
						for (j = 0; j < 9; j++) {
							field[i][j] = bfield[i][j];
							poss[i][j] = bposs[i][j];
						}
					}
					/* and mark that as impossible */
					printf("S   %i, %i: !%i\n", 
							minx+1, miny+1, c+1);
					setImpossible(minx, miny, c);
				}
			}
		}
	}
	return checkField();
}

void solveProblem(char *problem) {
	int x, y, n, j;

	queue = (struct queue*)malloc(sizeof(struct queue));
	for (j = 0; j < QUEUE_COUNT; j++) {
		queue->first[j] = NULL;
		queue->last[j] = NULL;
	}
	queue->length = 0;
	queue->count = 0;
	queue->maxlength = 0;

	for (x = 0; x < 9; x++) {
		for (y = 0; y < 9; y++) {
			field[x][y] = UNKNOWN;
			for (n = 0; n < 9; n++) {
				setPossible(x, y, n);
			}
		}
	}
	setString(problem);

	solve(0);
	free(queue);

	printField(field);
	hist();

	printf("%i heuristics used, max queue length was %i\n", queue->count, 
			queue->maxlength);
}

int main(int argc, char *argv[]) {
	FILE *f;
	char buffer[100];
	char *c;
	f = fopen(argv[1], "r");
	if (f) {
		while (!feof(f)) {
			c = fgets(buffer, 100, f);
			solveProblem(buffer);
		} 
		fclose(f);
	}
	else {
		fprintf(stderr, "Could not open file \"%s\": %s\n", 
			argv[1], strerror(errno));
	}

	return 0;
}