From 9742ed3c4af77b4b0d138ab00ea1cebe037878ef Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sun, 2 Sep 2018 11:30:03 +0200
Subject: solve_bt_bfs: more powerful isValid

---
 solve_bt_bfs.cpp | 51 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 37 insertions(+), 14 deletions(-)

diff --git a/solve_bt_bfs.cpp b/solve_bt_bfs.cpp
index bf14218..672b167 100644
--- a/solve_bt_bfs.cpp
+++ b/solve_bt_bfs.cpp
@@ -70,52 +70,75 @@ static ostream& operator<<(ostream &os, const Sudoku &su) {
 	return os;
 }
 
+template <bool checkPoss>
 static bool isValid(const Sudoku &su) {
 	for (int y = 0; y < 9; y++) {
 		int i = 9 * y;
-		uint8_t seen[9];
-		memset(seen, 0, 9);
+
+		uint16_t seen = 0;
+		uint16_t seenPoss = 0;
+
 		for (int x = 0; x < 9; x++, i++) {
 			int v = su[i];
 			if (v != -1) {
-				if (seen[v]) return false;
-				else seen[v] = 1;
+				if (seen & (1<<v)) return false;
+				else seen |= 1<<v;
+			} else {
+				if (checkPoss) seenPoss |= su.poss[i];
 			}
 		}
+
+		if (checkPoss) {
+			if ((seenPoss | seen) != 0x1ff) return false;
+		}
 	}
 
 	for (int x = 0; x < 9; x++) {
 		int i = x;
-		uint8_t seen[9];
-		memset(seen, 0, 9);
+
+		uint16_t seen = 0;
+		uint16_t seenPoss = 0;
+
 		for (int y = 0; y < 9; y++, i += 9) {
 			int v = su[i];
 			if (v != -1) {
-				if (seen[v]) return false;
-				else seen[v] = 1;
+				if (seen & (1<<v)) return false;
+				else seen |= 1<<v;
+			} else {
+				if (checkPoss) seenPoss |= su.poss[i];
 			}
 		}
+
+		if (checkPoss) {
+			if ((seenPoss | seen) != 0x1ff) return false;
+		}
 	}
 
 	int i = 0;
 	for (int by = 0; by < 9; by += 3) {
 		for (int bx = 0; bx < 9; bx += 3) {
-			uint8_t seen[9];
-			memset(seen, 0, 9);
+			uint16_t seen = 0;
+			uint16_t seenPoss = 0;
 
 			int j = i;
 			for (int y = 0; y < 3; y++) {
 				for (int x = 0; x < 3; x++) {
 					int v = su[j];
 					if (v != -1) {
-						if (seen[v]) return false;
-						else seen[v] = 1;
+						if (seen & (1<<v)) return false;
+						else seen |= 1<<v;
+					} else {
+						if (checkPoss) seenPoss |= su.poss[j];
 					}
 					j++;
 				}
 				j += 6;
 			}
 
+			if (checkPoss) {
+				if ((seenPoss | seen) != 0x1ff) return false;
+			}
+
 			i += 3;
 		}
 		i += 18;
@@ -301,7 +324,7 @@ static Resolution solve(const Sudoku &su) {
 			item.su[i] = v;
 			scratchAround(item.su, i);
 
-			if (isValid(item.su)) {
+			if (isValid<true>(item.su)) {
 				// item.maxposs = calcMaxposs(item.su);
 				item.init = {i, v};
 				qu.push_back(move(item));
@@ -335,7 +358,7 @@ static Resolution solve(const Sudoku &su) {
 				item.su[i] = v;
 				scratchAround(item.su, i);
 
-				if (isValid(item.su)) {
+				if (isValid<true>(item.su)) {
 					// item.maxposs = calcMaxposs(item.su);
 					qu.push_back(move(item));
 
-- 
cgit v1.2.3