2023W-EFFPROG

commit 018e6f4f232846a6292f4c7aec4e44545e5e03b6
parent 5cccb57065e466f0a2abea80864ac26b49684716
Author: Christoph Kern <christoph.michael.kern@gmail.com>
Date:   Wed,  3 Jan 2024 14:50:18 +0100

Merge pull request #6 from markhun/bisecting_labeling_searchspace

Bisect labeling searchspace
Diffstat:
M
magichex/src/magichex.c
 | 
54
+++++++++++++++++++++++++++++++++---------------------

1 file changed, 33 insertions(+), 21 deletions(-)
diff --git a/magichex/src/magichex.c b/magichex/src/magichex.c
@@ -310,40 +310,52 @@ unsigned long *makeCornerSpiralPermutation()
    the constraints hold */
 void labeling(HexagonEntry hexagon[], unsigned long index, unsigned long *order)
 {
-  register long i;
   unsigned long entryIndex = order[index];
 
   HexagonEntry *hexagonEntry = &hexagon[entryIndex];
+
   if (index >= H) {
+    // All hexagonEntries fully constrained, print solution.
     printhexagon(hexagon);
     solutions++;
     leafs++;
     printf("leafs visited: %lu\n\n",leafs);
     return;
   }
+
   if (hexagonEntry->id == PLACEHOLDER_ENTRY_ID)
-    // call labeling again as we do not need to process placeholders
+    // Do not process placeholder entries, continue to next hexagon index.
     return labeling(hexagon,index+1,order); 
-  for (i = hexagonEntry->lo; i <= hexagonEntry->hi; i++) {
-    HexagonEntry newHexagon[number_hex_entries];
-    HexagonEntry* newHexagonEntry = &newHexagon[entryIndex];
-    memmove(newHexagon,hexagon,number_hex_entries*sizeof(HexagonEntry));
-    newHexagonEntry->lo = i;
-    newHexagonEntry->hi = i;
-#if 0
-    for (HexagonEntry *hexagonEntry = newHexagon; hexagonEntry<=newHexagonEntry; hexagonEntry++) {
-      if (hexagonEntry->id != PLACEHOLDER_ENTRY_ID) {
-        assert(hexagonEntry->lo == hexagonEntry->hi);
-        printf(" %ld",hexagonEntry->lo); fflush(stdout);
-      }
-    }
-    printf("\n");
-#endif
-    if (solve(newHexagon))
-      labeling(newHexagon,index+1,order);
-    else
-      leafs++;
+  if(hexagonEntry->lo == hexagonEntry->hi)
+    // hexagonEntry already fully constrained, continue to next hexagon index.
+    return labeling(hexagon,index+1,order);
+
+
+
+  HexagonEntry newHexagon[r*r];
+  // bisect the range [lo,hi] to new Hexagons and recurse on them.
+  long midpoint = (hexagonEntry->lo + hexagonEntry->hi) >> 1;
+  if(hexagonEntry->lo + hexagonEntry->hi < 0 && (hexagonEntry->lo + hexagonEntry->hi) % 2 != 0){
+    midpoint--;  // nudge midpoint for negative values to avoid endless recursion
+  }
+  // Initalize newHexagon to hexagon to explore lower halve of original range [lo,hi]
+  memmove(newHexagon,hexagon,number_hex_entries*sizeof(HexagonEntry));
+  newHexagon[entryIndex].lo = hexagonEntry->lo;
+  newHexagon[entryIndex].hi = midpoint;
+  if (solve(newHexagon)) {
+    labeling(newHexagon,index,order);
   }
+  else
+    leafs++;
+  // Initalize newHexagon to hexagon to explore upper halve of original range [lo,hi]
+  memmove(newHexagon,hexagon,number_hex_entries*sizeof(HexagonEntry));
+  newHexagon[entryIndex].lo = midpoint+1;
+  newHexagon[entryIndex].hi = hexagonEntry->hi;
+  if (solve(newHexagon)) {
+    labeling(newHexagon,index,order); 
+    }
+  else
+    leafs++;
 }
 
 HexagonEntry *makehexagon()