commit 60c25832c0c7f378ed159d9bcf90ffc91075b3c0
parent efe64dea2c09f67442b71162184ee96a18370e0e
Author: Markus Hunner <26381538+markhun@users.noreply.github.com>
Date: Sat, 30 Dec 2023 13:26:53 +0100
Globalize hexagon properties
Diffstat:
1 file changed, 42 insertions(+), 36 deletions(-)
diff --git a/magichex/src/magichex.c b/magichex/src/magichex.c
@@ -42,6 +42,12 @@ typedef struct hexagonEntry HexagonEntry;
lowest value = dr - (H-1)/2
highest value = dr + (H-1)/2
*/
+static long n;
+static long number_hex_entries;
+static long d;
+static unsigned long r;
+static unsigned long H;
+static unsigned long M;
unsigned long solutions = 0; /* counter of solutions */
unsigned long leafs = 0; /* counter of leaf nodes visited in the search tree */
@@ -104,12 +110,12 @@ CHANGE_IDENTIFIER lessthan(HexagonEntry *v1, HexagonEntry *v2)
return (setlo(v2, v1->lo+1));
}
-CHANGE_IDENTIFIER sum(HexagonEntry hexagon[], unsigned long nv, unsigned long stride, long sum,
+CHANGE_IDENTIFIER sum(HexagonEntry hexagon[], unsigned long nv, unsigned long stride,
HexagonEntry *hexagonStart, HexagonEntry *hexagonEnd)
{
unsigned long i;
- long hi = sum;
- long lo = sum;
+ long hi = M;
+ long lo = M;
HexagonEntry *hexagonEntry_p;
#if 0
printf("sum(hexagonStart+%ld, %lu, %lu, %ld, hexagonStart, hexagonStart+%ld) ",hexagon-hexagonStart,nv,stride,sum,hexagonEnd-hexagonStart); fflush(stdout);
@@ -146,11 +152,8 @@ CHANGE_IDENTIFIER sum(HexagonEntry hexagon[], unsigned long nv, unsigned long st
/* reduce the ranges of the variables as much as possible (with the
constraints we use); returns 1 if all variables still have a
non-empty range left, 0 if one has an empty range */
-bool solve(unsigned long n, long d, HexagonEntry hexagon[])
+bool solve(HexagonEntry hexagon[])
{
- unsigned long r = 2*n-1;
- unsigned long H = 3*n*n-3*n+1;
- long M = d*H;
long o = d*r - (H-1)/2; /* offset in occupation array */
unsigned long occupation[H]; /* if hexagon[i] has value x, occupation[x-o]==i,
if no hexagon[*] has value x, occupation[x-o]==H */
@@ -159,12 +162,12 @@ bool solve(unsigned long n, long d, HexagonEntry hexagon[])
//printf("(re)start\n");
/* deal with the alldifferent constraint */
for (i=0; i<H; i++)
- occupation[i] = r*r;
+ occupation[i] = number_hex_entries;
restart:
- for (i=0; i<r*r; i++) {
+ for (i=0; i<number_hex_entries; i++) {
HexagonEntry *hexagonEntry = &hexagon[i];
if (hexagonEntry->lo == hexagonEntry->hi && occupation[hexagonEntry->lo-o] != i) {
- if (occupation[hexagonEntry->lo-o] < r*r)
+ if (occupation[hexagonEntry->lo-o] < number_hex_entries)
return false; /* another variable has the same value */
occupation[hexagonEntry->lo-o] = i; /* occupy hexagonEntry->lo */
//goto restart;
@@ -172,14 +175,14 @@ bool solve(unsigned long n, long d, HexagonEntry hexagon[])
}
bool k = false;
/* now propagate the alldifferent results to the bounds */
- for (i=0; i<r*r; i++) {
+ for (i=0; i<number_hex_entries; i++) {
HexagonEntry *hexagonEntry = &hexagon[i];
if (hexagonEntry->lo < hexagonEntry->hi) {
- if (occupation[hexagonEntry->lo-o] < r*r) {
+ if (occupation[hexagonEntry->lo-o] < number_hex_entries) {
hexagonEntry->lo++;
k = true;
}
- if (occupation[hexagonEntry->hi-o] < r*r) {
+ if (occupation[hexagonEntry->hi-o] < number_hex_entries) {
hexagonEntry->hi--;
k = true;
}
@@ -207,25 +210,25 @@ bool solve(unsigned long n, long d, HexagonEntry hexagon[])
for (i=0; i<r; i++) {
CHANGE_IDENTIFIER f;
/* line */
- f = sum(hexagon+r*i+max(0,i+1-n), min(i+n,r+n-i-1), 1, M, hexagon, hexagon+r*r);
+ f = sum(hexagon+r*i+max(0,i+1-n), min(i+n,r+n-i-1), 1, hexagon, hexagon+number_hex_entries);
if (f==NOSOLUTION) return false;
if (f==CHANGED) goto restart;
/* column (diagonal down-left in the hexagon) */
- f = sum(hexagon+i+max(0,i+1-n)*r, min(i+n,r+n-i-1), r, M, hexagon, hexagon+r*r);
+ f = sum(hexagon+i+max(0,i+1-n)*r, min(i+n,r+n-i-1), r, hexagon, hexagon+number_hex_entries);
if (f==NOSOLUTION) return false;
if (f==CHANGED) goto restart;
/* diagonal (down-right) */
- f = sum(hexagon-n+1+i+max(0,n-i-1)*(r+1), min(i+n,r+n-i-1), r+1, M, hexagon, hexagon+r*r);
+ f = sum(hexagon-n+1+i+max(0,n-i-1)*(r+1), min(i+n,r+n-i-1), r+1, hexagon, hexagon+number_hex_entries);
if (f==NOSOLUTION) return false;
if (f==CHANGED) goto restart;
}
return true; // all done
}
-void printhexagon(unsigned long n, HexagonEntry hexagon[])
+void printhexagon(HexagonEntry hexagon[])
{
unsigned long i,j;
- unsigned r=2*n-1;
+
for (i=0; i<r; i++) {
unsigned long l=0;
unsigned long h=r;
@@ -255,13 +258,13 @@ void printhexagon(unsigned long n, HexagonEntry hexagon[])
/* assign values to hexagon[index] and all later variables in hexagon such that
the constraints hold */
-void labeling(unsigned long n, long d, HexagonEntry hexagon[], unsigned long index)
+void labeling(HexagonEntry hexagon[], unsigned long index)
{
long i;
- unsigned long r = 2*n-1;
+
HexagonEntry *hexagonEntry = &hexagon[index];
- if (index >= r*r) {
- printhexagon(n,hexagon);
+ if (index >= number_hex_entries) {
+ printhexagon(hexagon);
solutions++;
leafs++;
printf("leafs visited: %lu\n\n",leafs);
@@ -269,11 +272,11 @@ void labeling(unsigned long n, long d, HexagonEntry hexagon[], unsigned long ind
}
if (hexagonEntry->id == PLACEHOLDER_ENTRY_ID)
// call labeling again as we do not need to process placeholders
- return labeling(n,d,hexagon,index+1);
+ return labeling(hexagon,index+1);
for (i = hexagonEntry->lo; i <= hexagonEntry->hi; i++) {
- HexagonEntry newHexagon[r*r];
+ HexagonEntry newHexagon[number_hex_entries];
HexagonEntry* newHexagonEntry = &newHexagon[index];
- memmove(newHexagon,hexagon,r*r*sizeof(HexagonEntry));
+ memmove(newHexagon,hexagon,number_hex_entries*sizeof(HexagonEntry));
newHexagonEntry->lo = i;
newHexagonEntry->hi = i;
#if 0
@@ -285,22 +288,21 @@ void labeling(unsigned long n, long d, HexagonEntry hexagon[], unsigned long ind
}
printf("\n");
#endif
- if (solve(n,d,newHexagon))
- labeling(n,d,newHexagon,index+1);
+ if (solve(newHexagon))
+ labeling(newHexagon,index+1);
else
leafs++;
}
}
-HexagonEntry *makehexagon(unsigned long n, long d)
+HexagonEntry *makehexagon()
{
unsigned long i,j;
- unsigned long r = 2*n-1;
- unsigned long H = 3*n*n-3*n+1;
+
- HexagonEntry *hexagon = calloc(r*r,sizeof(HexagonEntry));
+ HexagonEntry *hexagon = calloc(number_hex_entries,sizeof(HexagonEntry));
unsigned long id = 0;
- for (i=0; i<r*r; i++) {
+ for (i=0; i<number_hex_entries; i++) {
hexagon[i].id = PLACEHOLDER_ENTRY_ID;
hexagon[i].lo = 1;
hexagon[i].hi = 0;
@@ -328,8 +330,7 @@ int main(int argc, char *argv[])
{
unsigned long i;
unsigned long j=0;
- unsigned long n;
- long d;
+
if (argc < 3) {
fprintf(stderr, "Usage: %s <order> <deviation> <value> ... <value>\n", argv[0]);
exit(1);
@@ -340,14 +341,19 @@ int main(int argc, char *argv[])
exit(1);
}
d = strtol(argv[2],NULL,10);
- HexagonEntry *hexagon = makehexagon(n,d);
+ r = 2*n-1;
+ number_hex_entries = r*r;
+ H = 3*n*n-3*n+1;
+ M = d*H;
+
+ HexagonEntry *hexagon = makehexagon();
for (i=3; i<argc; i++) {
while (hexagon[j].id == PLACEHOLDER_ENTRY_ID)
j++; // skip this entry as it is a placeholder
hexagon[j].lo = hexagon[j].hi = strtol(argv[i],NULL,10);
j++;
}
- labeling(n,d,hexagon,0);
+ labeling(hexagon,0);
printf("%lu solution(s), %lu leafs visited\n",solutions, leafs);
//(void)solve(n, d, hexagon);
//printhexagon(n, hexagon);
