From 734c30391d96c4cb74e328f94b05b33b4e2db98a Mon Sep 17 00:00:00 2001
From: David Phillips <david@sighup.nz>
Date: Mon, 11 Mar 2019 15:54:42 +1300
Subject: Replace cumbersome arrays with bitmasks

---
 cell.h   |  6 +++++-
 solve.c  | 30 ++++++++++--------------------
 update.c |  4 ++--
 3 files changed, 17 insertions(+), 23 deletions(-)

diff --git a/cell.h b/cell.h
index fc5f467..7041920 100644
--- a/cell.h
+++ b/cell.h
@@ -1,6 +1,10 @@
 #ifndef SUDOKU_CELL_H
 #define SUDOKU_CELL_H
 
+#define CELL_VALUE_MASK(x)          (1 << ((x)-1))
+#define CELL_SET_NOT(target, val)   ((target) |= CELL_VALUE_MASK(val))
+#define CELL_IS_NOT(cand, val)      ((cand & CELL_VALUE_MASK(val)))
+
 /* Description of a single cell on a sudoku board */
 struct cell
 {
@@ -10,7 +14,7 @@ struct cell
 	/* Array used to determine which values this cell can NOT be.
 	 * A non-zero value at index N indicates that this cell cannot have the
 	 * value N + 1 */
-	char not[9];
+	int not;
 };
 
 #endif /* SUDOKU_CELL_H */
diff --git a/solve.c b/solve.c
index a96ddab..9cfa38f 100644
--- a/solve.c
+++ b/solve.c
@@ -29,7 +29,7 @@ int solve_row_col(struct cell (*b)[9][9])
 
 			for (i = 0; i < 9; i++)
 			{
-				if ((*b)[x][y].not[i])
+				if (CELL_IS_NOT((*b)[x][y].not, val))
 				{
 					total++;
 				} else {
@@ -87,7 +87,7 @@ int not_to_val_cell(struct cell (*b)[9][9])
 						if (c->val)
 							continue;
 
-						if (c->not[n-1] == 0)
+						if (!CELL_IS_NOT(c->not, n))
 						{
 							potentials++;
 							okx = x;
@@ -103,15 +103,6 @@ int not_to_val_cell(struct cell (*b)[9][9])
 					(*b)[bx+okx][by+oky].val = n;
 					potentials = 0;
 					change_count++;
-				} else if(potentials) {
-					DEBUG_LOG("CELL: (%d,%d) could be one of %d\n", bx + okx, by + oky, potentials);
-					int k = 0;
-					for (k = 0; k < 9; k++) {
-						if (!(*b)[bx+okx][by+oky].not[k]) {
-							DEBUG_LOG("   %d", k+1);
-						}
-					}
-					DEBUG_LOG("\n\n");
 				}
 			}
 		}
@@ -128,9 +119,8 @@ int cell_fill_certainties(struct cell (*b)[9][9], int bx, int by)
 	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 cell_has = 0;
 	int x,y;
 
 	/* Translate cell-based index to tile-based */
@@ -143,21 +133,21 @@ int cell_fill_certainties(struct cell (*b)[9][9], int bx, int by)
 			val = (*b)[x][y].val;
 			if (val) {
 				DEBUG_LOG("CELL_CERT: Cell (%d,%d) has %d\n", bx/3, by/3, val);
-				cell_has[val - 1] = 1;
+				cell_has |= CELL_VALUE_MASK(val);
 			}
 		}
 	}
 
 	/* 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++) {
+	for (val = 1; val <= 9; val++) {
 
 		will_take_count = 0;
 
 		/* Does the cell lack the value? */
-		if (!cell_has[val]) {
+		if (!(cell_has & CELL_VALUE_MASK(val))) {
 
-			DEBUG_LOG("Try to solve for %d\n", val + 1);
+			DEBUG_LOG("Try to solve for %d\n", val);
 
 			/* Walk the cell and find which tile(s) will take it */
 			for (x = bx; x < bx + 3; x++) {
@@ -165,7 +155,7 @@ int cell_fill_certainties(struct cell (*b)[9][9], int bx, int by)
 					if ((*b)[x][y].val) {
 						continue;
 					}
-					if ((*b)[x][y].not[val] == 0) {
+					if (!CELL_IS_NOT((*b)[x][y].not, val)) {
 						will_take_count++;
 						will_take_x = x;
 						will_take_y = y;
@@ -177,8 +167,8 @@ int cell_fill_certainties(struct cell (*b)[9][9], int bx, int by)
 			if (will_take_count == 1) {
 				printf("%c%c must be %d because it is the only place in its boxthis will fit\n",
 					NAME_CELL(will_take_x, will_take_y),
-					val + 1);
-				(*b)[will_take_x][will_take_y].val = val + 1;
+					val);
+				(*b)[will_take_x][will_take_y].val = val;
 				change_count++;
 			}
 		}
diff --git a/update.c b/update.c
index 57c5dda..e2e4fbb 100644
--- a/update.c
+++ b/update.c
@@ -25,8 +25,8 @@ void update_not_row_col(struct cell (*b)[9][9])
 				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;
+					CELL_SET_NOT((*b)[i][y].not, val);
+					CELL_SET_NOT((*b)[x][i].not, val);
 				}
 			}
 		}
-- 
cgit v1.1