commit 62cc549c94265cfe2d452b0029f47fe99a208e0f
parent 9a0e046ad00764007a8a479bd790cb6c995bb010
Author: Markus Hunner <26381538+markhun@users.noreply.github.com>
Date: Fri, 8 Dec 2023 14:46:14 +0100
Setup project
Diffstat:
10 files changed, 1295 insertions(+), 2 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,3 +1,6 @@
+bin/
+build/
+
# Prerequisites
*.d
diff --git a/.vscode/extensions.json b/.vscode/extensions.json
@@ -0,0 +1,5 @@
+{
+ "recommendations": [
+ "ms-vscode.cpptools-extension-pack"
+ ]
+}+
\ No newline at end of file
diff --git a/.vscode/settings.json b/.vscode/settings.json
@@ -0,0 +1,17 @@
+{
+ "makefile.launchConfigurations": [
+ {
+ "name": "magichex 3 0",
+ "cwd": "/home/markhun/Development/2023W-EFFPROG/bin",
+ "binaryPath": "/home/markhun/Development/2023W-EFFPROG/bin/magichex",
+ "binaryArgs": ["3 0"]
+ },
+ {
+ "name": "magichex 3 2",
+ "cwd": "/home/markhun/Development/2023W-EFFPROG/bin",
+ "binaryPath": "/home/markhun/Development/2023W-EFFPROG/bin/magichex",
+ "binaryArgs": ["3 2"]
+ }
+ ],
+ "makefile.makefilePath": "./Makefile"
+}+
\ No newline at end of file
diff --git a/HEADER.html b/HEADER.html
@@ -0,0 +1,313 @@
+<title>Project for the course Efficient Programs WS23/24</title>
+
+<h1>Project for the course Efficient Programs WS23/24</h1>
+
+You can choose an arbitrary project.
+
+<p>If you don't have any project of your own, you can choose
+the <a href="#given">given project</a> for this semester.
+
+<p>Implementing the given project has some advantages: You don't need
+to spend precious presentation time on explaining the problem, and may
+also be able to spend less on explaining the algorithm, and the
+results are directly comparable to those of other groups. A
+disadvantage of using the given project is that you might be repeating
+what others have done and you may produce worse results (especially if
+you choose a later presentation date). If your results are worse,
+this does not influence the grading, though; the grading is based on
+whether you demonstrate that you have applied the content of the
+course.
+
+<p>Prepare an 18-minute presentation (I recommend doing a trial run).
+You do not have as much time as I had in the lecture, so I recommend
+that you present most optimization steps only superficially, and focus
+on those steps in more detail that are particularly interesting, e.g.,
+because they produced surprisingly good or suprisingly bad results.
+</p>
+
+<h2><a name="given">Given Project:</a> Magic Hexagon</h2>
+
+<h3>Background</h3>
+
+In a <a href="https://en.wikipedia.org/wiki/Magic_hexagon">Magic
+Hexagon</a> all the numbers in each row, in each of the three
+directions sum to the same number M; in addition, in our Magic
+Hexagons, all numbers are different, and they are all from a set of
+consecutive numbers. E.g.,
+
+<pre>
+ 3 17 18
+ 19 7 1 11
+16 2 5 6 9
+ 12 4 8 14
+ 10 13 15
+</pre>
+
+All lines sum up to M=38 in this magic hexagon.
+
+<h3>Given Program</h3>
+
+You can find the given program on the g0
+in <code>/nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-aufgabe23/</code>
+(use <code>cp -r to copy the whole directory to your account on the
+g0</code>), or <a href="effizienz-aufgabe23.tar.gz">on the web</a>
+
+You can compile the given
+program <a href="magichex.c"><code>magichex.c</code></a>
+with <code>make</code> (you need to copy magichex.c and
+the <a href="Makefile"><code>Makefile</code></a> for this. The
+resulting binary is called <code>magichex</code> and you can invoke it
+as follows:
+
+<pre>
+ ./magichex <n> <d> <value1> ... <valuem>
+</pre>
+
+The values are optional. n is the size of one side of the magic
+hexagon (also called the order of the magic hexagon); it is 3 for the
+example above. d is a parameter that influences the range of the set
+of consecutive numbers; the numbers are centered around d(2n-1); for
+the example above d=2, and the numbers are centered around 10 (from
+1-19). I.e., you get the result above with
+
+<pre>
+ ./magichex 3 2
+</pre>
+
+or with <code>make test1</code>. There is also a <code>make
+test2</code>, which tests <code>./magichex 3 0</code>, which produces
+26 solutions.
+
+<p>If you provide values, they fill in the hexagon starting with the
+leftmost element of the first line, then to the right, then the next
+line, and so on. This eliminates a lot of search space, reducing the
+possible number of solutions, but also reducing the needed amount of
+search time. E.g, if you perform</p>
+
+<pre>
+ ./magichex 3 0 -9
+</pre>
+
+you only get the 5 solutions of the 26 mentioned above where the left
+element of the top row is -9.
+
+<p>To evaluate your optimizations, start with</p>
+
+<pre>
+ perf stat -e cycles:u -e instructions:u -e branches:u -e branch-misses:u \
+ -e L1-dcache-load-misses:u ./magichex 4 3 14 33 30 34 39 6 24 20
+</pre>
+
+You can run this with an output check with <code>make measure</code>,
+or without (but showing the solutions on the terminal) with <code>make
+nocheck</code>.
+
+<p>With the given program compiled with -O3 this outputs 40 solutions
+(where all solutions are checked with <code>make measure</code>) and
+the following performance results:
+
+<pre>
+ 310194428814 cycles:u
+ 897820790268 instructions:u # 2.89 insn per cycle
+ 257049961217 branches:u
+ 2366511820 branch-misses:u # 0.92% of all branches
+ 141455 L1-dcache-load-misses
+
+ 66.160150710 seconds time elapsed
+
+ 66.123002000 seconds user
+ 0.003999000 seconds sys
+</pre>
+
+Your optimized program has to produce the same solutions in any order;
+you do not need to preserve the output of the number of visited leafs
+(this can be considered to be another kind of performance counter).
+To compare the output for correctness, process it with
+
+<pre>
+ ./magichex ... |
+ grep -v solution|
+ awk '/^leafs visited:/ {printf("\0")} /^leafs visited:/,/^$/ {next} 1'|
+ sort -z|
+ tr '\0' '\n\n' |
+ diff -u reference-output -
+</pre>
+
+<code>make measure</code> does this.
+
+<p>I expect that your optimizations will produce vast improvements in
+run-time. This may allow your program to solve larger problems while
+still taking <90s of CPU time (user+system). So if you improve
+your program, try larger problems by deleting some of the given values
+(starting from the right). Of course, this may produce additional
+solutions, so you will have to generate a new reference output (after
+first checking that your program still produces the given reference
+output for the original values) for your further work, using the same
+kind of canonicalization as shown above.
+
+<p>In your presentation, please report how many values you gave for
+evaluating your best version, report the cycles:u value, and the
+number of solutions (as a weak form of comaring the correctness with
+other solutions that use the same number of given values). Given the
+low number of cache misses, the cycles should be very representative
+and vary less than the run-time even in the face of clock frequency
+changes due to other load on the machine.
+
+<p>If you are using parallel programming to improve the elapsed time
+of your program, report the cycles:u, the CPU time and the elapsed
+time, but still report all solutions for a problem that does not take
+more than 90s of CPU time.
+
+<h3>Program explanation and suggestions</h3>
+
+This section explains how the program works and suggests some possible improvements.
+
+<p>The numbers that have to be found (as well as the numbers that are
+given) are represented in the <code>Var</code> type, which works like
+a variable in constraint logic programming: The value in the variable
+is usually not completely known, but is within bounds (represented by
+the fields <code>lo</code> and <code>hi</code>; note that the value
+of <code>hi</code> is a possible value of the variable, unlike the
+convention in many other cases in programming). There is also the
+array <code>occupation</code> in <code>solve()</code> which tells
+which variables already contain which values, and that these values
+are therefore unavailable to other variables (because they all have to
+have different values). While following a branch of the search tree
+towards a leaf, the bounds of the variables are tightened more and
+more, until the bounds of a variable are the same value (then the
+variable has that value), or until there is no value left for the
+variable (then there is no solution in that branch of the search
+tree).
+
+<p>These variables are involved in the following constraints:
+
+<ul>
+<li>An alldifferent constraint involving all the variables. It
+ensures that the variables all get different values. This constraint
+does not occur explicitly in the program, but is expressed in the
+first part of <code>solve()</code>
+
+<li>Sum constraints v1+...+vn=M for all the lines in all three
+directions through the hexagon. You can find them as
+function <code>sum()</code>, and in the calls to this function
+inside <code>solve()</code>.
+
+<li>Lessthan constraints (vx<vy) between the corners eliminate
+symmetric solutions. You can find them in the
+function <code>lessthan()</code> and in the calls of this function
+inside <code>solve()</code>.
+</ul>
+
+<p>The two most relevant functions for understanding (and probably for
+optimizing) the program are <code>labeling()</code>
+and <code>solve()</code>.
+
+<p><code>labeling()</code> explores the search tree by trying out one
+of the possible values of a variable, and then exploring the rest of
+the search tree with <code>labeling()</code>. If that part of the
+search tree is exhausted (whether a solution was found or not), the
+next value for the variable is tried, until all values for this
+variable have been exhausted. Given that the search tree grows
+exponentially, there is a potential for big speedups by better
+labeling.
+
+<p>In particular, you can choose to process the variables in a
+different order (the given program processes them line by line,
+left-to-righ). A common heuristic is to process the variable with the
+lowest number of remaining values first. For another magic hexagon
+program, I have used a fixed ordering starting with the corners,
+because the corners are involved in two of the sum constraints with
+the least variables (i.e., few additional variables need to get a
+value to fully determine all values in the constraint), and because
+they are involved in the lessthan constraints.
+
+<p>Instead of setting a variable directly to one of its values in a
+labeling step, you can also bisect its range by first setting its
+upper bound to some middle value x, and, after exploring that branch,
+its lower bound to x+1. The potential advantage is that you may find
+that one of these subranges does not contain a solution without
+exploring it in more depth.
+
+<p>You can get additional inspiration for possible labeling heuristics
+from <a href="https://swish.swi-prolog.org/pldoc/man?predicate=labeling/2">the
+SWI-Prolog documentation</a>.
+
+<p>One other interesting aspect of the present labeling approach is
+that it copies all variables before every choice it makes. This is
+probably a good choice given the relatively low number of variables
+and the probably large number of changes, but a more usual
+implementation of (constraint) logic programming instead uses a
+(value) trail stack that records changes to the variables as they are
+made, and, on backtracking (returning from an
+inner <code>labeling()</code> call), all the values since the choice
+point at hand are restored from the trail stack.
+
+<p><code>solve()</code> applies all constraints to reduce the possible
+values of all variables as much as possible (within the limits of
+looking at each constraint, one at a time). This is a polynomial
+process, but it still consumes a lot of time, and reducing that by a
+good factor will certainly help.
+
+<p>The current solver always starts from the beginning after every
+change to a variable or the <code>occupation</code> array. It may be
+faster to process further changes before restarting the solver.
+
+<p> It also reevaluates constraints that cannot be affected by the
+changes since the last evaluation (because the changed variable is not
+involved in the constraint). It may be faster to only reevaluate
+constraints that have been affected. However, if most constraints
+have been affected, the overhead of recording whether a constraint is
+affected may be larger than the performance improvement.
+
+<p>If you are really brave, you implement a stronger solver, such as a
+stronger implementation of alldifferent, e.g., using the methods
+of <a href="https://www.ijcai.org/Proceedings/03/Papers/036.pdf">Lopez-Ortiz
+et al.</a>
+or <a href="https://cdn.aaai.org/AAAI/1994/AAAI94-055.pdf">Regin</a>.
+
+<p>You should not pursue all of these ideas (some of which conflict
+with each other), but select some promising ideas, implement them,
+then optimize that implementation, and report the results.
+
+<h2>Putting the results online</h2>
+
+<p>You can publish your program and its documentation (e.g., the
+presentation) by putting a project on, e.g., Github
+or <a href="https://sr.ht/">Sourcehut</a>, and putting a web page with
+a link to that project
+on <code>/nfs/unsafe/httpd/ftp/pub/anton/lvas/effizienz-abgaben/2023w</code>
+(on the g0). Alternatively, you can also create a directory there and
+put your program and documentation there. This web page or directory
+is visible in the web
+through <a href="../effizienz-abgaben/2023w/">this page</a>.
+
+<p>The publication of your solution is not graded, so publishing it is
+completely optional.
+
+
+<p>Project tasks from
+[<a href="../effizienz-aufgabe02.html">WS02/03</a> |
+<a href="../effizienz-aufgabe03.html">WS03/04</a> | <a
+href="../effizienz-aufgabe04.html">WS04/05</a> | <a
+href="../effizienz-aufgabe05/">WS05/06</a> | <a
+href="../effizienz-aufgabe06/">WS06/07</a> | <a
+href="../effizienz-aufgabe07/">WS07/08</a> | <a
+href="../effizienz-aufgabe08/">WS08/09</a> | <a
+href="../effizienz-aufgabe09/">WS09/10</a> | <a
+href="../effizienz-aufgabe10/">WS10/11</a> | <a
+href="../effizienz-aufgabe11/">WS11/12</a> | <a
+href="../effizienz-aufgabe12/">WS12/13</a> | <a
+href="../effizienz-aufgabe13/">WS13/14</a> | <a
+href="../effizienz-aufgabe14/">WS14/15</a> | <a
+href="../effizienz-aufgabe15/">WS15/16</a> | <a
+href="../effizienz-aufgabe16/">WS16/17</a> | <a
+href="../effizienz-aufgabe17/">WS17/18</a> | <a
+href="../effizienz-aufgabe18/">WS18/19</a> | <a
+href="../effizienz-aufgabe19/">WS19/20</a> | <a
+href="../effizienz-aufgabe20/">WS20/21</a> | <a
+href="../effizienz-aufgabe21/">WS21/22</a> | <a
+href="../effizienz-aufgabe22/">WS22/23</a> ]
+
+<hr>
+<a href="../">Anton Ertl</a>
+
diff --git a/Makefile b/Makefile
@@ -0,0 +1,83 @@
+# Makefile settings
+CC = cc
+RM = rm -f
+CFLAGS =-Wall -O3
+#CFLAGS =-Wall -O -g
+LD = cc
+LDFLAGS =-g
+
+# Project specific settings
+SRC_DIR = ./magichex/src
+TESTS_DIR = ./magichex/tests
+BUILD_DIR = ./build
+BIN_DIR = ./bin
+SRC_LIST = $(wildcard $(SRC_DIR)/*.c)
+OBJ_LIST = $(BUILD_DIR)/$(notdir $(SRC_LIST:.c=.o))
+
+.PHONY: all clean directories test test1 test2 test3 profile profile-nocheck
+
+default: all
+
+all: magichex
+
+magichex: magichex.o directories
+ $(LD) $(LDFLAGS) $(OBJ_LIST) -o $(BIN_DIR)/$@
+
+magichex.o: $(SRC_DIR)/magichex.c directories
+ $(CC) $(CFLAGS) -c $(SRC_DIR)/magichex.c -o $(BUILD_DIR)/$@
+
+
+directories:
+ @mkdir -p $(BUILD_DIR)
+ @mkdir -p $(BIN_DIR)
+
+test: test1 test2 test3
+
+test1: magichex
+ @echo "Running test1: $(BIN_DIR)/magichex 4 3 14 33 30 34 39 6 24 20"
+ @$(BIN_DIR)/magichex 4 3 14 33 30 34 39 6 24 20 |\
+ grep -v solution| \
+ awk '/^leafs visited:/ {printf("\0")} /^leafs visited:/,/^$$/ {next} 1'|\
+ sort -z|\
+ tr '\0' '\n\n' |\
+ diff --color -u $(TESTS_DIR)/reference-output - \
+ && echo "-------- TEST2 SUCCESSFUL! --------" \
+ || echo "-------- TEST2 FAILED! --------"
+
+test2: magichex
+ @echo "Running test2: $(BIN_DIR)/magichex 3 2"
+ @$(BIN_DIR)/magichex 3 2 |\
+ grep -v solution| \
+ awk '/^leafs visited:/ {printf("\0")} /^leafs visited:/,/^$$/ {next} 1'|\
+ sort -z|\
+ tr '\0' '\n\n' |\
+ diff --color -u $(TESTS_DIR)/reference-output-3-2 - \
+ && echo "-------- TEST2 SUCCESSFUL! --------" \
+ || echo "-------- TEST2 FAILED! --------"
+
+test3: magichex
+ @echo "Running test3: $(BIN_DIR)/magichex 3 0"
+ @$(BIN_DIR)/magichex 3 0 |\
+ grep -v solution| \
+ awk '/^leafs visited:/ {printf("\0")} /^leafs visited:/,/^$$/ {next} 1'|\
+ sort -z|\
+ tr '\0' '\n\n' |\
+ diff --color -u $(TESTS_DIR)/reference-output-3-0 - \
+ && echo "-------- TEST2 SUCCESSFUL! --------" \
+ || echo "-------- TEST2 FAILED! --------"
+
+profile-with-test: magichex
+ perf stat -e cycles:u -e instructions:u -e branches:u -e branch-misses:u -e L1-dcache-load-misses:u $(BIN_DIR)/magichex 4 3 14 33 30 34 39 6 24 20 |\
+ grep -v solution| \
+ awk '/^leafs visited:/ {printf("\0")} /^leafs visited:/,/^$$/ {next} 1'|\
+ sort -z|\
+ tr '\0' '\n\n' |\
+ diff --color -u $(TESTS_DIR)/reference-output - \
+ && echo "-------- TEST SUCCESSFUL! --------" \
+ || echo "-------- TEST FAILED! --------"
+
+profile: magichex
+ perf stat -e cycles:u -e instructions:u -e branches:u -e branch-misses:u -e L1-dcache-load-misses:u $(BIN_DIR)/magichex 4 3 14 33 30 34 39 6 24 20
+
+clean:
+ rm -f $(BIN_DIR)/magichex $(BUILD_DIR)/*.o
diff --git a/README.md b/README.md
@@ -1 +1,42 @@
-# 2023W-EFFPROG-
\ No newline at end of file
+# 2023W-EFFPROG - magichex
+
+
+## Building the program
+```
+make
+```
+
+The executable will be located in `./bin/magichex`
+
+## Testing the program against reference output
+
+```
+make test
+```
+
+Will execute `magichex` three times with some predefined parameters and compare its
+outputs with some reference output.
+
+The test cases can also be executed one at a time by calling
+
+```
+make test1
+```
+```
+make test2
+```
+```
+make test3
+```
+
+## Profiling
+
+There are two pre-defined targets to run `perf` on `magichex`
+
+```
+make profile
+```
+
+```
+make profile-with-test
+```+
\ No newline at end of file
diff --git a/magichex/src/magichex.c b/magichex/src/magichex.c
@@ -0,0 +1,347 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+
+typedef struct var Var;
+
+/* constraint variable; if lo==hi, this is the variable's value */
+typedef struct var {
+ long id; /* variable id; id<0 if the variable is not part of the hexagon */
+ long lo; /* lower bound */
+ long hi; /* upper bound */
+} Var;
+
+/* representation of a hexagon of order n: (2n-1)^2 square array
+ for a hexagon of order 2:
+ A B
+ C D E
+ F G
+ the representation is:
+ A B .
+ C D E
+ . F G
+ The . slots have lo>hi.
+
+ The variable array is organized as a single-dimension array with accesses
+ vs[y*r+x]
+ This allows to access the diagonal with stride 2*order
+
+ Variable names n, r, H, S according to German Wikipedia Article
+ Instead of "i", the deviation variable is called "d" (d=0 means
+ that the sum=0; to have the lowest value 1, d=2)
+
+ n is the order (number of elements of a side of the hexagon).
+ r = 2n-1 (length of the middle row/diagonals)
+ H = 3n^2-3n+1 (number of variables)
+ M = dH (sum of each row/diagonal)
+ lowest value = dr - (H-1)/2
+ highest value = dr + (H-1)/2
+*/
+
+unsigned long solutions = 0; /* counter of solutions */
+unsigned long leafs = 0; /* counter of leaf nodes visited in the search tree */
+
+long min(long a, long b)
+{
+ return (a<b)?a:b;
+}
+
+long max(long a, long b)
+{
+ return (a>b)?a:b;
+}
+
+
+/* unless otherwise noted, the following functions return
+
+ 0 if there is no solution (i.e., the action eliminates all values
+ from a variable),
+
+ 1 if there was a change
+
+ 2 if there was no change
+*/
+
+
+int sethi(Var *v, long x) {
+ assert(v->id >= 0);
+ if (x < v->hi) {
+ v->hi = x;
+ if (v->lo <= v->hi)
+ return 1;
+ else
+ return 0;
+ }
+ return 2;
+}
+
+int setlo(Var *v, long x) {
+ assert(v->id >= 0);
+ if (x > v->lo) {
+ v->lo = x;
+ if (v->lo <= v->hi)
+ return 1;
+ else
+ return 0;
+ }
+ return 2;
+}
+
+/* returns 0 if there is no solution, 1 if one of the variables has changed */
+int lessthan(Var *v1, Var *v2)
+{
+ assert(v1->id >= 0);
+ assert(v2->id >= 0);
+ int f = sethi(v1, v2->hi-1);
+ if (f < 2)
+ return f;
+ return (setlo(v2, v1->lo+1));
+}
+
+int sum(Var vs[], unsigned long nv, unsigned long stride, long sum,
+ Var *vsstart, Var *vsend)
+{
+ unsigned long i;
+ long hi = sum;
+ long lo = sum;
+ Var *vp;
+#if 0
+ printf("sum(vsstart+%ld, %lu, %lu, %ld, vsstart, vsstart+%ld) ",vs-vsstart,nv,stride,sum,vsend-vsstart); fflush(stdout);
+ for (i=0, vp=vs; i<nv; i++, vp+=stride) {
+ assert(vp>=vsstart);
+ assert(vp<vsend);
+ assert(vp->id >= 0);
+ printf("v%ld ",vp->id);
+ }
+ printf("\n");
+#endif
+ for (i=0, vp=vs; i<nv; i++, vp+=stride) {
+ assert(vp>=vsstart);
+ assert(vp<vsend);
+ assert(vp->id >= 0);
+ hi -= vp->lo;
+ lo -= vp->hi;
+ }
+ /* hi is the upper bound of sum-sum(vs), lo the lower bound */
+ for (i=0, vp=vs; i<nv; i++, vp+=stride) {
+ int f = sethi(vp,hi+vp->lo); /* readd vp->lo to get an upper bound of vp */
+ assert(vp>=vsstart);
+ assert(vp<vsend);
+ assert(vp->id >= 0);
+ if (f < 2)
+ return f;
+ f = setlo(vp,lo+vp->hi); /* likewise, readd vp->hi */
+ if (f < 2)
+ return f;
+ }
+ return 2;
+}
+
+/* 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 */
+int solve(unsigned long n, long d, Var vs[])
+{
+ 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 vs[i] has value x, occupation[x-o]==i,
+ if no vs[*] has value x, occupation[x-o]==H*/
+ unsigned long corners[] = {0, n-1, (n-1)*r+0, (n-1)*r+r-1, (r-1)*r+n-1, (r-1)*r+r-1};
+ unsigned long i;
+ //printf("(re)start\n");
+ /* deal with the alldifferent constraint */
+ for (i=0; i<H; i++)
+ occupation[i] = r*r;
+ restart:
+ for (i=0; i<r*r; i++) {
+ Var *v = &vs[i];
+ if (v->lo == v->hi && occupation[v->lo-o] != i) {
+ if (occupation[v->lo-o] < r*r)
+ return 0; /* another variable has the same value */
+ occupation[v->lo-o] = i; /* occupy v->lo */
+ goto restart;
+ }
+ }
+ /* now propagate the alldifferent results to the bounds */
+ for (i=0; i<r*r; i++) {
+ Var *v = &vs[i];
+ if (v->lo < v->hi) {
+ if (occupation[v->lo-o] < r*r) {
+ v->lo++;
+ goto restart;
+ }
+ if (occupation[v->hi-o] < r*r) {
+ v->hi--;
+ goto restart;
+ }
+ }
+ }
+ /* the < constraints; all other corners are smaller than the first
+ one (eliminate rotational symmetry) */
+ for (i=1; i<sizeof(corners)/sizeof(corners[0]); i++) {
+ int f = lessthan(&vs[corners[0]],&vs[corners[i]]);
+ if (f==0) return 0;
+ if (f==1) goto restart;
+ }
+ /* eliminate the mirror symmetry between the corners to the right
+ and left of the first corner */
+ {
+ int f = lessthan(&vs[corners[2]],&vs[corners[1]]);
+ if (f==0) return 0;
+ if (f==1) goto restart;
+ }
+ /* sum constraints: each line and diagonal sums up to M */
+ /* line sum constraints */
+ for (i=0; i<r; i++) {
+ int f;
+ /* line */
+ f = sum(vs+r*i+max(0,i+1-n), min(i+n,r+n-i-1), 1, M, vs, vs+r*r);
+ if (f==0) return 0;
+ if (f==1) goto restart;
+ /* column (diagonal down-left in the hexagon) */
+ f = sum(vs+i+max(0,i+1-n)*r, min(i+n,r+n-i-1), r, M, vs, vs+r*r);
+ if (f==0) return 0;
+ if (f==1) goto restart;
+ /* diagonal (down-right) */
+ f = sum(vs-n+1+i+max(0,n-i-1)*(r+1), min(i+n,r+n-i-1), r+1, M, vs, vs+r*r);
+ if (f==0) return 0;
+ if (f==1) goto restart;
+ }
+ return 1;
+}
+
+void printhexagon(unsigned long n, Var vs[])
+{
+ unsigned long i,j;
+ unsigned r=2*n-1;
+ for (i=0; i<r; i++) {
+ unsigned long l=0;
+ unsigned long h=r;
+ if (i+1>n)
+ l = i+1-n;
+ if (i+1<n)
+ h = n+i;
+ for (j=h-l; j<r; j++)
+ printf(" ");
+ for (j=l; j<h; j++) {
+ assert(i<r);
+ assert(j<r);
+ Var *v=&vs[i*r+j];
+ assert(v->lo <= v->hi);
+#if 0
+ printf("%6ld ",v->id);
+#else
+ if (v->lo < v->hi)
+ printf("%4ld-%-3ld",v->lo,v->hi);
+ else
+ printf("%6ld ",v->lo);
+#endif
+ }
+ printf("\n");
+ }
+}
+
+/* assign values to vs[index] and all later variables in vs such that
+ the constraints hold */
+void labeling(unsigned long n, long d, Var vs[], unsigned long index)
+{
+ long i;
+ unsigned long r = 2*n-1;
+ Var *vp = vs+index;
+ if (index >= r*r) {
+ printhexagon(n,vs);
+ solutions++;
+ leafs++;
+ printf("leafs visited: %lu\n\n",leafs);
+ return;
+ }
+ if (vp->id < 0)
+ return labeling(n,d,vs,index+1);
+ for (i = vp->lo; i <= vp->hi; i++) {
+ Var newvs[r*r];
+ Var* newvp=newvs+index;
+ memmove(newvs,vs,r*r*sizeof(Var));
+ newvp->lo = i;
+ newvp->hi = i;
+#if 0
+ for (Var *v = newvs; v<=newvp; v++) {
+ if (v->id >= 0) {
+ assert(v->lo == v->hi);
+ printf(" %ld",v->lo); fflush(stdout);
+ }
+ }
+ printf("\n");
+#endif
+ if (solve(n,d,newvs))
+ labeling(n,d,newvs,index+1);
+ else
+ leafs++;
+ }
+}
+
+Var *makehexagon(unsigned long n, long d)
+{
+ unsigned long i,j;
+ unsigned long r = 2*n-1;
+ unsigned long H = 3*n*n-3*n+1;
+
+ Var *vs = calloc(r*r,sizeof(Var));
+ unsigned long id = 0;
+ for (i=0; i<r*r; i++) {
+ Var *v = &vs[i];
+ v->id = -1;
+ v->lo = 1;
+ v->hi = 0;
+ }
+ for (i=0; i<r; i++) {
+ unsigned long l=0;
+ unsigned long h=r;
+ if (i+1>n)
+ l = i+1-n;
+ if (i+1<n)
+ h = n+i;
+ for (j=l; j<h; j++) {
+ assert(i<r);
+ assert(j<r);
+ Var *v=&vs[i*r+j];
+ assert(v->lo>v->hi);
+ v->id = id++;
+ v->lo = d*r - (H-1)/2;
+ v->hi = d*r + (H-1)/2;
+ }
+ }
+ return vs;
+}
+
+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);
+ }
+ n = strtoul(argv[1],NULL,10);
+ if (n<1) {
+ fprintf(stderr, "order must be >=1\n");
+ exit(1);
+ }
+ d = strtol(argv[2],NULL,10);
+ Var *vs = makehexagon(n,d);
+ for (i=3; i<argc; i++) {
+ while (vs[j].id < 0)
+ j++;
+ vs[j].lo = vs[j].hi = strtol(argv[i],NULL,10);
+ j++;
+ }
+ labeling(n,d,vs,0);
+ printf("%lu solution(s), %lu leafs visited\n",solutions, leafs);
+ //(void)solve(n, d, vs);
+ //printhexagon(n, vs);
+ return 0;
+}
diff --git a/magichex/tests/reference-output b/magichex/tests/reference-output
@@ -0,0 +1,320 @@
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 11 15 10 21 28
+ 32 23 5 4 17 3 27
+ 38 12 8 7 9 37
+ 25 19 13 36 18
+ 16 31 35 29
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 13 23 5 17 27
+ 32 21 8 3 4 15 28
+ 38 16 7 12 9 29
+ 10 11 19 35 36
+ 31 37 25 18
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 13 3 4 29 36
+ 32 21 15 7 12 5 19
+ 38 16 11 9 10 27
+ 23 17 8 35 28
+ 18 31 25 37
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 16 7 3 23 36
+ 32 25 17 4 5 9 19
+ 31 12 13 15 11 29
+ 21 10 8 37 35
+ 27 38 18 28
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 16 7 3 23 36
+ 32 25 17 4 5 9 19
+ 31 12 13 8 18 29
+ 21 10 15 37 28
+ 27 38 11 35
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 18 5 3 21 38
+ 32 25 10 8 7 12 17
+ 29 19 15 11 9 28
+ 23 4 13 36 35
+ 27 37 16 31
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 26 8 15 11 13 38
+ 32 29 7 5 9 12 17
+ 35 10 4 23 3 36
+ 25 18 16 21 31
+ 19 28 37 27
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 27 15 11 8 18 32
+ 31 19 12 4 5 17 23
+ 38 21 7 3 16 26
+ 13 9 28 36 25
+ 29 35 10 37
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 27 16 3 7 32 26
+ 31 18 8 11 4 10 29
+ 38 21 13 5 15 19
+ 25 9 12 37 28
+ 17 36 23 35
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 27 26 3 4 15 36
+ 31 17 5 12 16 11 19
+ 29 21 10 7 9 35
+ 28 8 13 37 25
+ 23 38 18 32
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 27 5 12 4 26 37
+ 31 29 13 7 3 10 18
+ 38 9 16 8 15 25
+ 23 11 17 28 32
+ 19 35 21 36
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 27 8 17 11 16 32
+ 31 28 5 13 4 7 23
+ 36 9 3 15 10 38
+ 26 12 19 25 29
+ 18 35 37 21
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 31 15 12 9 26 18
+ 27 19 11 3 4 10 37
+ 38 5 7 8 28 25
+ 29 21 16 32 13
+ 17 35 23 36
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 31 18 3 10 17 32
+ 27 28 12 8 4 9 23
+ 26 5 7 13 25 35
+ 37 11 19 29 15
+ 21 36 16 38
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 31 21 11 8 4 36
+ 27 16 3 9 5 32 19
+ 35 17 7 15 12 25
+ 26 10 28 18 29
+ 23 37 13 38
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 31 23 3 9 16 29
+ 27 28 5 7 8 10 26
+ 21 11 12 13 19 35
+ 38 4 15 36 18
+ 25 37 17 32
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 31 25 9 10 19 17
+ 27 18 3 4 5 16 38
+ 29 13 8 7 28 26
+ 32 12 21 35 11
+ 23 37 15 36
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 31 28 3 4 16 29
+ 27 23 7 5 13 10 26
+ 21 9 12 15 19 35
+ 38 11 8 36 18
+ 25 37 17 32
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 12 15 7 28 17
+ 26 25 3 4 5 10 38
+ 35 18 8 16 11 23
+ 21 9 13 37 31
+ 29 27 36 19
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 16 3 10 23 27
+ 26 25 12 4 7 9 28
+ 31 5 15 13 18 29
+ 37 11 8 36 19
+ 17 38 21 35
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 16 5 7 15 36
+ 26 35 3 9 11 8 19
+ 21 12 10 17 13 38
+ 37 4 18 29 23
+ 27 28 25 31
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 25 8 3 5 38
+ 26 16 4 10 11 27 17
+ 31 9 7 23 12 29
+ 36 19 15 13 28
+ 18 35 21 37
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 28 10 4 19 18
+ 26 15 5 8 13 7 37
+ 29 11 3 12 21 35
+ 31 17 9 38 16
+ 25 36 27 23
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 31 3 10 8 27
+ 26 16 4 5 15 17 28
+ 25 13 7 19 11 36
+ 37 12 9 35 18
+ 23 38 21 29
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 32 5 9 7 21 37
+ 26 36 3 11 4 13 18
+ 31 10 12 16 15 27
+ 35 8 23 17 28
+ 19 25 29 38
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 35 15 12 4 8 37
+ 23 19 7 5 11 28 18
+ 38 9 10 26 3 25
+ 29 17 13 16 36
+ 21 31 27 32
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 35 4 12 7 16 37
+ 23 32 5 11 3 19 18
+ 36 9 8 17 15 26
+ 31 10 28 13 29
+ 21 25 27 38
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 35 9 5 11 13 38
+ 23 32 16 4 7 12 17
+ 31 8 3 18 15 36
+ 28 10 25 27 21
+ 29 26 19 37
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 11 12 9 16 26
+ 21 23 7 10 4 17 29
+ 38 13 8 19 5 28
+ 25 3 15 32 36
+ 27 35 31 18
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 11 9 3 15 36
+ 21 29 5 13 16 8 19
+ 32 12 4 18 7 38
+ 31 10 17 25 28
+ 27 23 35 26
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 12 5 3 18 36
+ 21 31 4 8 17 11 19
+ 29 10 16 15 9 32
+ 38 7 13 28 25
+ 23 26 27 35
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 13 11 8 25 17
+ 21 23 7 9 3 10 38
+ 36 4 5 12 28 26
+ 35 16 18 27 15
+ 19 31 29 32
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 16 4 5 11 38
+ 21 31 9 3 12 18 17
+ 25 8 13 23 10 32
+ 36 7 15 26 27
+ 29 28 19 35
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 18 11 4 13 28
+ 21 19 8 7 17 12 27
+ 35 9 5 3 23 36
+ 29 15 25 32 10
+ 26 31 16 38
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 18 8 4 12 32
+ 21 28 9 10 7 13 23
+ 26 5 11 17 16 36
+ 35 3 15 31 27
+ 29 38 19 25
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 19 13 12 3 27
+ 21 17 4 7 8 26 28
+ 36 9 5 11 18 32
+ 31 10 29 25 16
+ 23 38 15 35
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 27 3 7 5 32
+ 21 16 9 4 13 25 23
+ 29 10 8 18 15 31
+ 35 12 17 28 19
+ 26 36 11 38
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 8 13 4 17 32
+ 21 26 12 3 10 16 23
+ 38 7 18 11 9 28
+ 25 5 15 35 31
+ 27 36 19 29
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 8 5 15 18 28
+ 21 26 9 13 4 11 27
+ 38 7 3 19 12 32
+ 36 10 17 25 23
+ 16 31 35 29
+
+ 14 33 30 34
+ 39 6 24 20 22
+ 37 9 8 7 18 32
+ 21 27 10 15 3 12 23
+ 36 4 11 13 16 31
+ 35 5 17 26 28
+ 19 38 25 29
+
diff --git a/magichex/tests/reference-output-3-0 b/magichex/tests/reference-output-3-0
@@ -0,0 +1,156 @@
+ -5 2 3
+ 9 -7 6 -8
+ -4 -2 0 1 5
+ 7 -6 8 -9
+ -3 -1 4
+
+ -5 2 3
+ 9 -8 6 -7
+ -4 -1 0 1 4
+ 7 -6 8 -9
+ -3 -2 5
+
+ -5 3 2
+ 9 -8 6 -7
+ -4 -2 1 0 5
+ 7 -6 8 -9
+ -3 -1 4
+
+ -5 4 1
+ 9 0 -2 -7
+ -4 -3 -6 7 6
+ -1 2 8 -9
+ 5 -8 3
+
+ -5 7 -2
+ 9 0 -6 -3
+ -4 -8 -1 8 5
+ 1 6 2 -9
+ 3 -7 4
+
+ -5 8 -3
+ 9 -1 -6 -2
+ -4 -8 0 7 5
+ 1 6 2 -9
+ 3 -7 4
+
+ -5 8 -3
+ 9 -2 -6 -1
+ -4 -7 0 7 4
+ 1 6 2 -9
+ 3 -8 5
+
+ -6 7 -1
+ 9 -7 2 -4
+ -3 -8 6 0 5
+ 8 -2 3 -9
+ -5 1 4
+
+ -7 1 6
+ 9 -4 3 -8
+ -2 -5 0 5 2
+ 8 -3 4 -9
+ -6 -1 7
+
+ -7 2 5
+ 3 6 -8 -1
+ 4 -9 0 9 -4
+ 1 8 -6 -3
+ -5 -2 7
+
+ -7 2 5
+ 6 8 -5 -9
+ 1 -2 -6 3 4
+ -8 -1 9 0
+ 7 -3 -4
+
+ -7 3 4
+ 8 1 -9 0
+ -1 2 6 -3 -4
+ -6 -8 5 9
+ 7 -2 -5
+
+ -7 3 4
+ 9 -8 5 -6
+ -2 -1 0 1 2
+ 6 -5 8 -9
+ -4 -3 7
+
+ -8 1 7
+ 6 3 -4 -5
+ 2 -9 0 9 -2
+ 5 4 -3 -6
+ -7 -1 8
+
+ -8 -1 9
+ 7 4 -5 -6
+ 1 -9 3 8 -3
+ 6 0 -4 -2
+ -7 2 5
+
+ -8 2 6
+ 9 -5 3 -7
+ -1 -4 0 4 1
+ 7 -3 5 -9
+ -6 -2 8
+
+ -8 3 5
+ 7 4 -7 -4
+ 1 2 0 -2 -1
+ -9 -6 9 6
+ 8 -3 -5
+
+ -8 3 5
+ 7 -9 6 -4
+ 1 2 0 -2 -1
+ 4 -6 9 -7
+ -5 -3 8
+
+ -8 3 5
+ 9 6 -9 -6
+ -1 -2 0 2 1
+ -7 -4 7 4
+ 8 -3 -5
+
+ -8 3 5
+ 9 -7 4 -6
+ -1 -2 0 2 1
+ 6 -4 7 -9
+ -5 -3 8
+
+ -8 5 3
+ 7 0 -6 -1
+ 1 -9 2 8 -2
+ 4 6 -3 -7
+ -5 -4 9
+
+ -9 1 8
+ 3 4 -5 -2
+ 6 -7 0 7 -6
+ 2 5 -4 -3
+ -8 -1 9
+
+ -9 1 8
+ 6 5 -4 -7
+ 3 -8 -3 9 -1
+ 2 4 0 -6
+ -5 -2 7
+
+ -9 3 6
+ 7 -8 5 -4
+ 2 1 0 -1 -2
+ 4 -5 8 -7
+ -6 -3 9
+
+ -9 4 5
+ 7 3 -6 -4
+ 2 -8 -2 9 -1
+ 1 6 0 -7
+ -3 -5 8
+
+ -9 5 4
+ 6 2 -7 -1
+ 3 -8 0 8 -3
+ 1 7 -2 -6
+ -4 -5 9
+
diff --git a/magichex/tests/reference-output-3-2 b/magichex/tests/reference-output-3-2
@@ -0,0 +1,6 @@
+ 3 17 18
+ 19 7 1 11
+ 16 2 5 6 9
+ 12 4 8 14
+ 10 13 15
+
