Fix the implementation

A number of things wrong with the quickie code initially committed,
chiefly not mutating the caller's copy of the board when that was the
intention. This commit fixes this and produces a working solver for all
boards that can be solved without exploration/uncertainty.

3 files changed, 259 insertions, 50 deletions

diff --git a/TODO b/TODO
new file mode 100644
index 0000000..1d87a91
--- /dev/null
+++ b/TODO
@@ -0,0 +1,17 @@
+The solver can only solve when at least one cell can be solved with certainty
+at each step of the process until repeating this eventually results in a solved
+board.
+The next step here is to allow exploration/trail of possible solutions.
+Presumably, would want to keep a copy of the board just before each "guess"
+that's taken to be able to easily roll back if failure.
+
+This would probably work really nicely as a recursive call:
+
+	board = get_fresh_board(board)
+	solve_all_certainties(board)
+	for each possible board as cand_board:
+		solution = solve_all_certainties(cand_board)
+		if complete(solution)
+			success
+	/* we should have solution presuming board was solvable */
+
diff --git a/display.c b/display.c
index f147570..9ddcf26 100644
--- a/display.c
+++ b/display.c
@@ -7,10 +7,13 @@ void display(struct cell board[9][9])
 	int x;
 	int y;
 	int val;
+	printf("    A B C  D E F  G H I\n"
+	      "   ---------------------\n");
 	for (y = 0; y < 9; y++)
 	{
 		if (y % 3 == 0 && y != 0)
-			printf("------+------+------\n");
+			printf("  |-------+------+------\n");
+		printf("%d | ", y + 1);
 		for (x = 0; x < 9; x++)
 		{
 			if (x % 3 == 0 && x != 0)
diff --git a/solve.c b/solve.c
index f8947c9..797837d 100644
--- a/solve.c
+++ b/solve.c
@@ -4,7 +4,26 @@
 #include "cell.h"
 #include "display.h"
 
-void update_not_row_col(struct cell b[9][9])
+static const char row_letter_lookup[] = "ABCDEFGHI";
+static const char col_letter_lookup[] = "123456789";
+
+#define NAME_CELL(x,y) row_letter_lookup[x], col_letter_lookup[y]
+
+//#define DEBUG
+#ifdef DEBUG
+# define DEBUG_LOG(args...)     printf(args)
+#else
+# define DEBUG_LOG(...)
+#endif
+
+
+/*
+ * FIXME rename
+ * For each unsolved cell on the board, update its list of values that it
+ * cannot be based on the solved cells in the same row or the same column
+ * Does not attempt to solve cells
+ */
+void update_not_row_col(struct cell (*b)[9][9])
 {
 	int x = 0;
 	int y = 0;
@@ -15,21 +34,28 @@ void update_not_row_col(struct cell b[9][9])
 	{
 		for (x = 0; x < 9; x++)
 		{
-			val = b[x][y].val;
+			val = (*b)[x][y].val;
 			if (val != 0)
 			{
+				DEBUG_LOG("Update: (%d,%d) has value %d\n", x, y, val);
 				for (i = 0; i < 9; i++)
 				{
-					b[i][y].not[val - 1] = 1;
-					b[x][i].not[val - 1] = 1;
+					(*b)[i][y].not[val - 1] = 1;
+					(*b)[x][i].not[val - 1] = 1;
 				}
 			}
 		}
 	}
 }
 
-void not_to_val_row_col(struct cell b[9][9])
+/*
+ * FIXME rename
+ * For all unsolved cells on the board, solve them if they have been marked as
+ * impossible to be 8/9 values
+ */
+int not_to_val_row_col(struct cell (*b)[9][9])
 {
+	int change_count = 0;
 	int x = 0;
 	int y = 0;
 	int i = 0;
@@ -41,27 +67,38 @@ void not_to_val_row_col(struct cell b[9][9])
 		total = 0;
 		for (x = 0; x < 9; x++)
 		{
-			if (b[x][y].val != 0)
+			if ((*b)[x][y].val != 0)
 				continue;
 
 			for (i = 0; i < 9; i++)
 			{
-				if (b[x][y].not[i])
+				if ((*b)[x][y].not[i])
 				{
 					total++;
 				} else {
 					val = i + 1;
 				}
 			}
-			if (total == 8)
-				b[x][y].val = val;
+			if (total == 8) {
+				printf("%c%c must be %d because it is the only missing value in its row or column\n", NAME_CELL(x,y), val);
+				DEBUG_LOG("ROW/COL: (%d,%d) must be %d\n", x, y, val);
+				(*b)[x][y].val = val;
+				change_count++;
+			}
 		}
 	}
+	return change_count;
 }
 
 
-void not_to_val_cell(struct cell b[9][9])
+/*
+ * FIXME rename - cell != cell
+ * For all unsolved cells on the board, solve them if they are the only place
+ * left in their local 3x3 that a value missing from that 3x3 could fit
+ */
+int not_to_val_cell(struct cell (*b)[9][9])
 {
+	int change_count = 0;
 	int cx = 0;
 	int cy = 0;
 	int x = 0;
@@ -69,7 +106,7 @@ void not_to_val_cell(struct cell b[9][9])
 	int n = 0;
 	int potentials = 0;
 	int okx, oky;
-	struct cell c;
+	struct cell *c;
 
 	/* refactor this crap */
 	for (cy = 0; cy < 9; cy += 3)
@@ -83,17 +120,17 @@ void not_to_val_cell(struct cell b[9][9])
 				{
 					for (x = 0; x < 3; x++)
 					{
-						c = b[cx+x][cy+y];
-						if (c.val == n)
+						c = &(*b)[cx+x][cy+y];
+						if (c->val == n)
 						{
 							potentials = 0;
 							y = 3;
 							break;
 						}
-						if (c.val)
+						if (c->val)
 							continue;
 
-						if (c.not[n-1] == 0)
+						if (c->not[n-1] == 0)
 						{
 							potentials++;
 							okx = x;
@@ -103,14 +140,109 @@ void not_to_val_cell(struct cell b[9][9])
 				}
 				if (potentials == 1)
 				{
-					b[cx+okx][cy+oky].val = n;
+					DEBUG_LOG("CELL: (%d,%d) must be %d\n", cx + okx, cy + oky, n);
+					printf("%c%c must be %d because it can't be anything else\n",
+						NAME_CELL(cx+okx, cy+oky), n);
+					(*b)[cx+okx][cy+oky].val = n;
 					potentials = 0;
+					change_count++;
+				} else if(potentials) {
+					DEBUG_LOG("CELL: (%d,%d) could be one of %d\n", cx + okx, cy + oky, potentials);
+					int k = 0;
+					for (k = 0; k < 9; k++) {
+						if (!(*b)[cx+okx][cy+oky].not[k]) {
+							DEBUG_LOG("   %d", k+1);
+						}
+					}
+					DEBUG_LOG("\n\n");
 				}
 			}
 		}
 	}
+	return change_count;
 }
 
+
+/* For the numbers 1-9 not filled into a cell, fill in those which have only
+ * one place they can go */
+int cell_fill_certainties(struct cell (*b)[9][9], int cx, int cy)
+{
+	int change_count = 0;
+	int will_take_count = 0;
+	int will_take_x = 0;
+	int will_take_y = 0;
+//	struct cell *will_take = NULL;
+	int val = 0;
+	int cell_has[9] = {0};
+	int x,y;
+
+	/* Translate cell-based index to tile-based */
+	cx *= 3;
+	cy *= 3;
+
+	/* First: walk the cell and find which values it has */
+	for (x = cx; x < cx + 3; x++) {
+		for (y = cy; y < cy + 3; y++) {
+			val = (*b)[x][y].val;
+			if (val) {
+				DEBUG_LOG("CELL_CERT: Cell (%d,%d) has %d\n", cx/3, cy/3, val);
+				cell_has[val - 1] = 1;
+			}
+		}
+	}
+
+	/* Second: For all missing values, see if only one tile will take it.
+	 * If only one will have it, put it in */
+	for (val = 0; val < 9; val++) {
+
+		will_take_count = 0;
+
+		/* Does the cell lack the value? */
+		if (!cell_has[val]) {
+
+			DEBUG_LOG("Try to solve for %d\n", val + 1);
+
+			/* Walk the cell and find which tile(s) will take it */
+			for (x = cx; x < cx + 3; x++) {
+				for (y = cy; y < cy + 3; y++) {
+					if ((*b)[x][y].val) {
+						continue;
+					}
+					if ((*b)[x][y].not[val] == 0) {
+						will_take_count++;
+						will_take_x = x;
+						will_take_y = y;
+					}
+				}
+			}
+			DEBUG_LOG("will_take_count is %d\n", will_take_count);
+			/* Don't make indeterminate choices here*/
+			if (will_take_count == 1) {
+				printf("%c%c must be %d because it is the only place in its 3x3 this will fit\n",
+					NAME_CELL(will_take_x, will_take_y),
+					val + 1);
+				(*b)[will_take_x][will_take_y].val = val + 1;
+				change_count++;
+			}
+		}
+	}
+	return change_count;
+}
+
+int cells_fill_certainties(struct cell (*b)[9][9])
+{
+	int change_count = 0;
+	int x, y;
+
+	for (x = 0; x < 3; x++) {
+		for (y = 0; y < 3; y++) {
+			change_count += cell_fill_certainties(b, x, y);
+		}
+	}
+	return change_count;
+}
+
+
 int main(int argc, char **argv)
 {
 //	int x = 0;
@@ -119,56 +251,113 @@ int main(int argc, char **argv)
 
 	memset(board, 0, sizeof(board));
 
+	board[1][0].val = 6;
+	board[2][0].val = 1;
+	board[3][0].val = 5;
+	board[8][0].val = 9;
 
-	board[7][0].val = 3;
-	board[4][1].val = 3;
-	board[0][7].val = 3;
-	board[1][4].val = 3;
+	board[1][1].val = 7;
+	board[2][1].val = 5;
+	board[3][1].val = 4;
+	board[4][1].val = 9;
+	board[5][1].val = 3;
+	board[6][1].val = 6;
 
-	/* dummy board taken from the guardian lol */
-	/* FIXME: have  a way to input boards, silly */
-	board[0][0].val = 7;
-	board[0][4].val = 5;
+	board[0][2].val = 9;
+	board[3][2].val = 6;
+	board[7][2].val = 7;
 
-	board[1][2].val = 5;
-	board[1][4].val = 9;
+	board[0][3].val = 4;
+	board[3][3].val = 2;
+	board[5][3].val = 6;
 
-	board[2][1].val = 6;
-	board[2][2].val = 4;
-	board[2][5].val = 2;
+	board[0][4].val = 3;
+	board[2][4].val = 9;
+	board[6][4].val = 2;
+	board[8][4].val = 7;
 
-	board[3][0].val = 1;
 	board[3][5].val = 9;
-	board[3][6].val = 7;
+	board[5][5].val = 5;
+	board[8][5].val = 3;
+
+	board[1][6].val = 8;
+	board[5][6].val = 9;
+	board[8][6].val = 5;
 
-	board[4][0].val = 9;
-	board[4][2].val = 6;
-	board[4][3].val = 4;
-	board[4][7].val = 8;
-	board[4][8].val = 5;
 
-	board[5][4].val = 2;
+	board[2][7].val = 4;
+	board[3][7].val = 7;
+	board[4][7].val = 5;
+	board[5][7].val = 2;
+	board[6][7].val = 8;
+	board[7][7].val = 9;
 
-	board[6][4].val = 8;
-	board[6][6].val = 5;
-	board[6][7].val = 6;
 
-	board[7][1].val = 8;
-	board[7][6].val = 3;
+	board[0][8].val = 5;
+	board[5][8].val = 1;
+	board[6][8].val = 7;
+	board[7][8].val = 3;
 
-	board[8][0].val = 4;
-	board[8][4].val = 1;
-	board[8][5].val = 7;
-	board[8][8].val = 8;
+//	board[7][0].val = 3;
+//	board[4][1].val = 3;
+//	board[0][7].val = 3;
+//	board[1][4].val = 3;
+//
+//	/* dummy board taken from the guardian lol */
+//	/* FIXME: have  a way to input boards, silly */
+//	board[0][0].val = 7;
+//	board[0][4].val = 5;
+//
+//	board[1][2].val = 5;
+//	board[1][4].val = 9;
+//
+//	board[2][1].val = 6;
+//	board[2][2].val = 4;
+//	board[2][5].val = 2;
+//
+//	board[3][0].val = 1;
+//	board[3][5].val = 9;
+//	board[3][6].val = 7;
+//
+//	board[4][0].val = 9;
+//	board[4][2].val = 6;
+//	board[4][3].val = 4;
+//	board[4][7].val = 8;
+//	board[4][8].val = 5;
+//
+//	board[5][4].val = 2;
+//
+//	board[6][4].val = 8;
+//	board[6][6].val = 5;
+//	board[6][7].val = 6;
+//
+//	board[7][1].val = 8;
+//	board[7][6].val = 3;
+//
+//	board[8][0].val = 4;
+//	board[8][4].val = 1;
+//	board[8][5].val = 7;
+//	board[8][8].val = 8;
 
 
 
 	display(board);
 
-	update_not_row_col(board);
-	not_to_val_cell(board);
-	not_to_val_row_col(board);
+	int i = 0;
+	int total_changes = 0;
+	int change_count = -1;
+	/* 9*9 is worst case */
+	for (i = 0; i < 9*9 && change_count; i++) {
+		change_count = 0;
+		update_not_row_col(&board);
+		change_count += not_to_val_cell(&board);
+		change_count += not_to_val_row_col(&board);
+		change_count += cells_fill_certainties(&board);
+		total_changes += change_count;
+//		display(board);
+	}
 
+	printf("Solution (%d changes)\n", total_changes);
 	display(board);
 
 }