--- /dev/null
+This subdirectory contains puzzle implementations which are
+half-written, fundamentally flawed, or in other ways unready to be
+shipped as part of the polished Puzzles collection.
+
+Those puzzles which have .R files can be built as part of the
+Puzzles collection by symlinking their source files into the parent
+directory and re-running mkfiles.pl. Anything without a .R file
+isn't even finished enough to do that, and you should read the
+source file itself to find out the status.
--- /dev/null
+/*
+ * This program implements a breadth-first search which
+ * exhaustively solves the Countdown numbers game, and related
+ * games with slightly different rule sets such as `Flippo'.
+ *
+ * Currently it is simply a standalone command-line utility to
+ * which you provide a set of numbers and it tells you everything
+ * it can make together with how many different ways it can be
+ * made. I would like ultimately to turn it into the generator for
+ * a Puzzles puzzle, but I haven't even started on writing a
+ * Puzzles user interface yet.
+ */
+
+/*
+ * TODO:
+ *
+ * - start thinking about difficulty ratings
+ * + anything involving associative operations will be flagged
+ * as many-paths because of the associative options (e.g.
+ * 2*3*4 can be (2*3)*4 or 2*(3*4), or indeed (2*4)*3). This
+ * is probably a _good_ thing, since those are unusually
+ * easy.
+ * + tree-structured calculations ((a*b)/(c+d)) have multiple
+ * paths because the independent branches of the tree can be
+ * evaluated in either order, whereas straight-line
+ * calculations with no branches will be considered easier.
+ * Can we do anything about this? It's certainly not clear to
+ * me that tree-structure calculations are _easier_, although
+ * I'm also not convinced they're harder.
+ * + I think for a realistic difficulty assessment we must also
+ * consider the `obviousness' of the arithmetic operations in
+ * some heuristic sense, and also (in Countdown) how many
+ * numbers ended up being used.
+ * - actually try some generations
+ * - at this point we're probably ready to start on the Puzzles
+ * integration.
+ */
+
+#include <stdio.h>
+#include <limits.h>
+#include <assert.h>
+
+#include "puzzles.h"
+#include "tree234.h"
+
+/*
+ * To search for numbers we can make, we employ a breadth-first
+ * search across the space of sets of input numbers. That is, for
+ * example, we start with the set (3,6,25,50,75,100); we apply
+ * moves which involve combining two numbers (e.g. adding the 50
+ * and the 75 takes us to the set (3,6,25,100,125); and then we see
+ * if we ever end up with a set containing (say) 952.
+ *
+ * If the rules are changed so that all the numbers must be used,
+ * this is easy to adjust to: we simply see if we end up with a set
+ * containing _only_ (say) 952.
+ *
+ * Obviously, we can vary the rules about permitted arithmetic
+ * operations simply by altering the set of valid moves in the bfs.
+ * However, there's one common rule in this sort of puzzle which
+ * takes a little more thought, and that's _concatenation_. For
+ * example, if you are given (say) four 4s and required to make 10,
+ * you are permitted to combine two of the 4s into a 44 to begin
+ * with, making (44-4)/4 = 10. However, you are generally not
+ * allowed to concatenate two numbers that _weren't_ both in the
+ * original input set (you couldn't multiply two 4s to get 16 and
+ * then concatenate a 4 on to it to make 164), so concatenation is
+ * not an operation which is valid in all situations.
+ *
+ * We could enforce this restriction by storing a flag alongside
+ * each number indicating whether or not it's an original number;
+ * the rules being that concatenation of two numbers is only valid
+ * if they both have the original flag, and that its output _also_
+ * has the original flag (so that you can concatenate three 4s into
+ * a 444), but that applying any other arithmetic operation clears
+ * the original flag on the output. However, we can get marginally
+ * simpler than that by observing that since concatenation has to
+ * happen to a number before any other operation, we can simply
+ * place all the concatenations at the start of the search. In
+ * other words, we have a global flag on an entire number _set_
+ * which indicates whether we are still permitted to perform
+ * concatenations; if so, we can concatenate any of the numbers in
+ * that set. Performing any other operation clears the flag.
+ */
+
+#define SETFLAG_CONCAT 1 /* we can do concatenation */
+
+struct sets;
+
+struct set {
+ int *numbers; /* rationals stored as n,d pairs */
+ short nnumbers; /* # of rationals, so half # of ints */
+ short flags; /* SETFLAG_CONCAT only, at present */
+ struct set *prev; /* index of ancestor set in set list */
+ unsigned char pa, pb, po, pr; /* operation that got here from prev */
+ int npaths; /* number of ways to reach this set */
+};
+
+struct output {
+ int number;
+ struct set *set;
+ int index; /* which number in the set is it? */
+ int npaths; /* number of ways to reach this */
+};
+
+#define SETLISTLEN 1024
+#define NUMBERLISTLEN 32768
+#define OUTPUTLISTLEN 1024
+struct operation;
+struct sets {
+ struct set **setlists;
+ int nsets, nsetlists, setlistsize;
+ tree234 *settree;
+ int **numberlists;
+ int nnumbers, nnumberlists, numberlistsize;
+ struct output **outputlists;
+ int noutputs, noutputlists, outputlistsize;
+ tree234 *outputtree;
+ const struct operation *const *ops;
+};
+
+#define OPFLAG_NEEDS_CONCAT 1
+#define OPFLAG_KEEPS_CONCAT 2
+
+struct operation {
+ /*
+ * Most operations should be shown in the output working, but
+ * concatenation should not; we just take the result of the
+ * concatenation and assume that it's obvious how it was
+ * derived.
+ */
+ int display;
+
+ /*
+ * Text display of the operator.
+ */
+ char *text;
+
+ /*
+ * Flags dictating when the operator can be applied.
+ */
+ int flags;
+
+ /*
+ * Priority of the operator (for avoiding unnecessary
+ * parentheses when formatting it into a string).
+ */
+ int priority;
+
+ /*
+ * Associativity of the operator. Bit 0 means we need parens
+ * when the left operand of one of these operators is another
+ * instance of it, e.g. (2^3)^4. Bit 1 means we need parens
+ * when the right operand is another instance of the same
+ * operator, e.g. 2-(3-4). Thus:
+ *
+ * - this field is 0 for a fully associative operator, since
+ * we never need parens.
+ * - it's 1 for a right-associative operator.
+ * - it's 2 for a left-associative operator.
+ * - it's 3 for a _non_-associative operator (which always
+ * uses parens just to be sure).
+ */
+ int assoc;
+
+ /*
+ * Whether the operator is commutative. Saves time in the
+ * search if we don't have to try it both ways round.
+ */
+ int commutes;
+
+ /*
+ * Function which implements the operator. Returns TRUE on
+ * success, FALSE on failure. Takes two rationals and writes
+ * out a third.
+ */
+ int (*perform)(int *a, int *b, int *output);
+};
+
+struct rules {
+ const struct operation *const *ops;
+ int use_all;
+};
+
+#define MUL(r, a, b) do { \
+ (r) = (a) * (b); \
+ if ((b) && (a) && (r) / (b) != (a)) return FALSE; \
+} while (0)
+
+#define ADD(r, a, b) do { \
+ (r) = (a) + (b); \
+ if ((a) > 0 && (b) > 0 && (r) < 0) return FALSE; \
+ if ((a) < 0 && (b) < 0 && (r) > 0) return FALSE; \
+} while (0)
+
+#define OUT(output, n, d) do { \
+ int g = gcd((n),(d)); \
+ if ((d) < 0) g = -g; \
+ (output)[0] = (n)/g; \
+ (output)[1] = (d)/g; \
+ assert((output)[1] > 0); \
+} while (0)
+
+static int gcd(int x, int y)
+{
+ while (x != 0 && y != 0) {
+ int t = x;
+ x = y;
+ y = t % y;
+ }
+
+ return abs(x + y); /* i.e. whichever one isn't zero */
+}
+
+static int perform_add(int *a, int *b, int *output)
+{
+ int at, bt, tn, bn;
+ /*
+ * a0/a1 + b0/b1 = (a0*b1 + b0*a1) / (a1*b1)
+ */
+ MUL(at, a[0], b[1]);
+ MUL(bt, b[0], a[1]);
+ ADD(tn, at, bt);
+ MUL(bn, a[1], b[1]);
+ OUT(output, tn, bn);
+ return TRUE;
+}
+
+static int perform_sub(int *a, int *b, int *output)
+{
+ int at, bt, tn, bn;
+ /*
+ * a0/a1 - b0/b1 = (a0*b1 - b0*a1) / (a1*b1)
+ */
+ MUL(at, a[0], b[1]);
+ MUL(bt, b[0], a[1]);
+ ADD(tn, at, -bt);
+ MUL(bn, a[1], b[1]);
+ OUT(output, tn, bn);
+ return TRUE;
+}
+
+static int perform_mul(int *a, int *b, int *output)
+{
+ int tn, bn;
+ /*
+ * a0/a1 * b0/b1 = (a0*b0) / (a1*b1)
+ */
+ MUL(tn, a[0], b[0]);
+ MUL(bn, a[1], b[1]);
+ OUT(output, tn, bn);
+ return TRUE;
+}
+
+static int perform_div(int *a, int *b, int *output)
+{
+ int tn, bn;
+
+ /*
+ * Division by zero is outlawed.
+ */
+ if (b[0] == 0)
+ return FALSE;
+
+ /*
+ * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
+ */
+ MUL(tn, a[0], b[1]);
+ MUL(bn, a[1], b[0]);
+ OUT(output, tn, bn);
+ return TRUE;
+}
+
+static int perform_exact_div(int *a, int *b, int *output)
+{
+ int tn, bn;
+
+ /*
+ * Division by zero is outlawed.
+ */
+ if (b[0] == 0)
+ return FALSE;
+
+ /*
+ * a0/a1 / b0/b1 = (a0*b1) / (a1*b0)
+ */
+ MUL(tn, a[0], b[1]);
+ MUL(bn, a[1], b[0]);
+ OUT(output, tn, bn);
+
+ /*
+ * Exact division means we require the result to be an integer.
+ */
+ return (output[1] == 1);
+}
+
+static int perform_concat(int *a, int *b, int *output)
+{
+ int t1, t2, p10;
+
+ /*
+ * We can't concatenate anything which isn't an integer.
+ */
+ if (a[1] != 1 || b[1] != 1)
+ return FALSE;
+
+ /*
+ * For concatenation, we can safely assume leading zeroes
+ * aren't an issue. It isn't clear whether they `should' be
+ * allowed, but it turns out not to matter: concatenating a
+ * leading zero on to a number in order to harmlessly get rid
+ * of the zero is never necessary because unwanted zeroes can
+ * be disposed of by adding them to something instead. So we
+ * disallow them always.
+ *
+ * The only other possibility is that you might want to
+ * concatenate a leading zero on to something and then
+ * concatenate another non-zero digit on to _that_ (to make,
+ * for example, 106); but that's also unnecessary, because you
+ * can make 106 just as easily by concatenating the 0 on to the
+ * _end_ of the 1 first.
+ */
+ if (a[0] == 0)
+ return FALSE;
+
+ /*
+ * Find the smallest power of ten strictly greater than b. This
+ * is the power of ten by which we'll multiply a.
+ *
+ * Special case: we must multiply a by at least 10, even if b
+ * is zero.
+ */
+ p10 = 10;
+ while (p10 <= (INT_MAX/10) && p10 <= b[0])
+ p10 *= 10;
+ if (p10 > INT_MAX/10)
+ return FALSE; /* integer overflow */
+ MUL(t1, p10, a[0]);
+ ADD(t2, t1, b[0]);
+ OUT(output, t2, 1);
+ return TRUE;
+}
+
+const static struct operation op_add = {
+ TRUE, "+", 0, 10, 0, TRUE, perform_add
+};
+const static struct operation op_sub = {
+ TRUE, "-", 0, 10, 2, FALSE, perform_sub
+};
+const static struct operation op_mul = {
+ TRUE, "*", 0, 20, 0, TRUE, perform_mul
+};
+const static struct operation op_div = {
+ TRUE, "/", 0, 20, 2, FALSE, perform_div
+};
+const static struct operation op_xdiv = {
+ TRUE, "/", 0, 20, 2, FALSE, perform_exact_div
+};
+const static struct operation op_concat = {
+ FALSE, "", OPFLAG_NEEDS_CONCAT | OPFLAG_KEEPS_CONCAT,
+ 1000, 0, FALSE, perform_concat
+};
+
+/*
+ * In Countdown, divisions resulting in fractions are disallowed.
+ * http://www.askoxford.com/wordgames/countdown/rules/
+ */
+const static struct operation *const ops_countdown[] = {
+ &op_add, &op_mul, &op_sub, &op_xdiv, NULL
+};
+const static struct rules rules_countdown = {
+ ops_countdown, FALSE
+};
+
+/*
+ * A slightly different rule set which handles the reasonably well
+ * known puzzle of making 24 using two 3s and two 8s. For this we
+ * need rational rather than integer division.
+ */
+const static struct operation *const ops_3388[] = {
+ &op_add, &op_mul, &op_sub, &op_div, NULL
+};
+const static struct rules rules_3388 = {
+ ops_3388, TRUE
+};
+
+/*
+ * A still more permissive rule set usable for the four-4s problem
+ * and similar things. Permits concatenation.
+ */
+const static struct operation *const ops_four4s[] = {
+ &op_add, &op_mul, &op_sub, &op_div, &op_concat, NULL
+};
+const static struct rules rules_four4s = {
+ ops_four4s, TRUE
+};
+
+#define ratcmp(a,op,b) ( (long long)(a)[0] * (b)[1] op \
+ (long long)(b)[0] * (a)[1] )
+
+static int addtoset(struct set *set, int newnumber[2])
+{
+ int i, j;
+
+ /* Find where we want to insert the new number */
+ for (i = 0; i < set->nnumbers &&
+ ratcmp(set->numbers+2*i, <, newnumber); i++);
+
+ /* Move everything else up */
+ for (j = set->nnumbers; j > i; j--) {
+ set->numbers[2*j] = set->numbers[2*j-2];
+ set->numbers[2*j+1] = set->numbers[2*j-1];
+ }
+
+ /* Insert the new number */
+ set->numbers[2*i] = newnumber[0];
+ set->numbers[2*i+1] = newnumber[1];
+
+ set->nnumbers++;
+
+ return i;
+}
+
+#define ensure(array, size, newlen, type) do { \
+ if ((newlen) > (size)) { \
+ (size) = (newlen) + 512; \
+ (array) = sresize((array), (size), type); \
+ } \
+} while (0)
+
+static int setcmp(void *av, void *bv)
+{
+ struct set *a = (struct set *)av;
+ struct set *b = (struct set *)bv;
+ int i;
+
+ if (a->nnumbers < b->nnumbers)
+ return -1;
+ else if (a->nnumbers > b->nnumbers)
+ return +1;
+
+ if (a->flags < b->flags)
+ return -1;
+ else if (a->flags > b->flags)
+ return +1;
+
+ for (i = 0; i < a->nnumbers; i++) {
+ if (ratcmp(a->numbers+2*i, <, b->numbers+2*i))
+ return -1;
+ else if (ratcmp(a->numbers+2*i, >, b->numbers+2*i))
+ return +1;
+ }
+
+ return 0;
+}
+
+static int outputcmp(void *av, void *bv)
+{
+ struct output *a = (struct output *)av;
+ struct output *b = (struct output *)bv;
+
+ if (a->number < b->number)
+ return -1;
+ else if (a->number > b->number)
+ return +1;
+
+ return 0;
+}
+
+static int outputfindcmp(void *av, void *bv)
+{
+ int *a = (int *)av;
+ struct output *b = (struct output *)bv;
+
+ if (*a < b->number)
+ return -1;
+ else if (*a > b->number)
+ return +1;
+
+ return 0;
+}
+
+static void addset(struct sets *s, struct set *set, struct set *prev)
+{
+ struct set *s2;
+ int npaths = (prev ? prev->npaths : 1);
+
+ assert(set == s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN);
+ s2 = add234(s->settree, set);
+ if (s2 == set) {
+ /*
+ * New set added to the tree.
+ */
+ set->prev = prev;
+ set->npaths = npaths;
+ s->nsets++;
+ s->nnumbers += 2 * set->nnumbers;
+ } else {
+ /*
+ * Rediscovered an existing set. Update its npaths only.
+ */
+ s2->npaths += npaths;
+ }
+}
+
+static struct set *newset(struct sets *s, int nnumbers, int flags)
+{
+ struct set *sn;
+
+ ensure(s->setlists, s->setlistsize, s->nsets/SETLISTLEN+1, struct set *);
+ while (s->nsetlists <= s->nsets / SETLISTLEN)
+ s->setlists[s->nsetlists++] = snewn(SETLISTLEN, struct set);
+ sn = s->setlists[s->nsets / SETLISTLEN] + s->nsets % SETLISTLEN;
+
+ if (s->nnumbers + nnumbers * 2 > s->nnumberlists * NUMBERLISTLEN)
+ s->nnumbers = s->nnumberlists * NUMBERLISTLEN;
+ ensure(s->numberlists, s->numberlistsize,
+ s->nnumbers/NUMBERLISTLEN+1, int *);
+ while (s->nnumberlists <= s->nnumbers / NUMBERLISTLEN)
+ s->numberlists[s->nnumberlists++] = snewn(NUMBERLISTLEN, int);
+ sn->numbers = s->numberlists[s->nnumbers / NUMBERLISTLEN] +
+ s->nnumbers % NUMBERLISTLEN;
+
+ /*
+ * Start the set off empty.
+ */
+ sn->nnumbers = 0;
+
+ sn->flags = flags;
+
+ return sn;
+}
+
+static int addoutput(struct sets *s, struct set *ss, int index, int *n)
+{
+ struct output *o, *o2;
+
+ /*
+ * Target numbers are always integers.
+ */
+ if (ss->numbers[2*index+1] != 1)
+ return FALSE;
+
+ ensure(s->outputlists, s->outputlistsize, s->noutputs/OUTPUTLISTLEN+1,
+ struct output *);
+ while (s->noutputlists <= s->noutputs / OUTPUTLISTLEN)
+ s->outputlists[s->noutputlists++] = snewn(OUTPUTLISTLEN,
+ struct output);
+ o = s->outputlists[s->noutputs / OUTPUTLISTLEN] +
+ s->noutputs % OUTPUTLISTLEN;
+
+ o->number = ss->numbers[2*index];
+ o->set = ss;
+ o->index = index;
+ o->npaths = ss->npaths;
+ o2 = add234(s->outputtree, o);
+ if (o2 != o) {
+ o2->npaths += o->npaths;
+ } else {
+ s->noutputs++;
+ }
+ *n = o->number;
+ return TRUE;
+}
+
+static struct sets *do_search(int ninputs, int *inputs,
+ const struct rules *rules, int *target)
+{
+ struct sets *s;
+ struct set *sn;
+ int qpos, i;
+ const struct operation *const *ops = rules->ops;
+
+ s = snew(struct sets);
+ s->setlists = NULL;
+ s->nsets = s->nsetlists = s->setlistsize = 0;
+ s->numberlists = NULL;
+ s->nnumbers = s->nnumberlists = s->numberlistsize = 0;
+ s->outputlists = NULL;
+ s->noutputs = s->noutputlists = s->outputlistsize = 0;
+ s->settree = newtree234(setcmp);
+ s->outputtree = newtree234(outputcmp);
+ s->ops = ops;
+
+ /*
+ * Start with the input set.
+ */
+ sn = newset(s, ninputs, SETFLAG_CONCAT);
+ for (i = 0; i < ninputs; i++) {
+ int newnumber[2];
+ newnumber[0] = inputs[i];
+ newnumber[1] = 1;
+ addtoset(sn, newnumber);
+ }
+ addset(s, sn, NULL);
+
+ /*
+ * Now perform the breadth-first search: keep looping over sets
+ * until we run out of steam.
+ */
+ qpos = 0;
+ while (qpos < s->nsets) {
+ struct set *ss = s->setlists[qpos / SETLISTLEN] + qpos % SETLISTLEN;
+ struct set *sn;
+ int i, j, k, m;
+
+ /*
+ * Record all the valid output numbers in this state. We
+ * can always do this if there's only one number in the
+ * state; otherwise, we can only do it if we aren't
+ * required to use all the numbers in coming to our answer.
+ */
+ if (ss->nnumbers == 1 || !rules->use_all) {
+ for (i = 0; i < ss->nnumbers; i++) {
+ int n;
+
+ if (addoutput(s, ss, i, &n) && target && n == *target)
+ return s;
+ }
+ }
+
+ /*
+ * Try every possible operation from this state.
+ */
+ for (k = 0; ops[k] && ops[k]->perform; k++) {
+ if ((ops[k]->flags & OPFLAG_NEEDS_CONCAT) &&
+ !(ss->flags & SETFLAG_CONCAT))
+ continue; /* can't use this operation here */
+ for (i = 0; i < ss->nnumbers; i++) {
+ for (j = 0; j < ss->nnumbers; j++) {
+ int n[2];
+
+ if (i == j)
+ continue; /* can't combine a number with itself */
+ if (i > j && ops[k]->commutes)
+ continue; /* no need to do this both ways round */
+ if (!ops[k]->perform(ss->numbers+2*i, ss->numbers+2*j, n))
+ continue; /* operation failed */
+
+ sn = newset(s, ss->nnumbers-1, ss->flags);
+
+ if (!(ops[k]->flags & OPFLAG_KEEPS_CONCAT))
+ sn->flags &= ~SETFLAG_CONCAT;
+
+ for (m = 0; m < ss->nnumbers; m++) {
+ if (m == i || m == j)
+ continue;
+ sn->numbers[2*sn->nnumbers] = ss->numbers[2*m];
+ sn->numbers[2*sn->nnumbers + 1] = ss->numbers[2*m + 1];
+ sn->nnumbers++;
+ }
+ sn->pa = i;
+ sn->pb = j;
+ sn->po = k;
+ sn->pr = addtoset(sn, n);
+ addset(s, sn, ss);
+ }
+ }
+ }
+
+ qpos++;
+ }
+
+ return s;
+}
+
+static void free_sets(struct sets *s)
+{
+ int i;
+
+ freetree234(s->settree);
+ freetree234(s->outputtree);
+ for (i = 0; i < s->nsetlists; i++)
+ sfree(s->setlists[i]);
+ sfree(s->setlists);
+ for (i = 0; i < s->nnumberlists; i++)
+ sfree(s->numberlists[i]);
+ sfree(s->numberlists);
+ for (i = 0; i < s->noutputlists; i++)
+ sfree(s->outputlists[i]);
+ sfree(s->outputlists);
+ sfree(s);
+}
+
+/*
+ * Construct a text formula for producing a given output.
+ */
+void mkstring_recurse(char **str, int *len,
+ struct sets *s, struct set *ss, int index,
+ int priority, int assoc, int child)
+{
+ if (ss->prev && index != ss->pr) {
+ int pi;
+
+ /*
+ * This number was passed straight down from this set's
+ * predecessor. Find its index in the previous set and
+ * recurse to there.
+ */
+ pi = index;
+ assert(pi != ss->pr);
+ if (pi > ss->pr)
+ pi--;
+ if (pi >= min(ss->pa, ss->pb)) {
+ pi++;
+ if (pi >= max(ss->pa, ss->pb))
+ pi++;
+ }
+ mkstring_recurse(str, len, s, ss->prev, pi, priority, assoc, child);
+ } else if (ss->prev && index == ss->pr &&
+ s->ops[ss->po]->display) {
+ /*
+ * This number was created by a displayed operator in the
+ * transition from this set to its predecessor. Hence we
+ * write an open paren, then recurse into the first
+ * operand, then write the operator, then the second
+ * operand, and finally close the paren.
+ */
+ char *op;
+ int parens, thispri, thisassoc;
+
+ /*
+ * Determine whether we need parentheses.
+ */
+ thispri = s->ops[ss->po]->priority;
+ thisassoc = s->ops[ss->po]->assoc;
+ parens = (thispri < priority ||
+ (thispri == priority && (assoc & child)));
+
+ if (parens) {
+ if (str)
+ *(*str)++ = '(';
+ if (len)
+ (*len)++;
+ }
+ mkstring_recurse(str, len, s, ss->prev, ss->pa, thispri, thisassoc, 1);
+ for (op = s->ops[ss->po]->text; *op; op++) {
+ if (str)
+ *(*str)++ = *op;
+ if (len)
+ (*len)++;
+ }
+ mkstring_recurse(str, len, s, ss->prev, ss->pb, thispri, thisassoc, 2);
+ if (parens) {
+ if (str)
+ *(*str)++ = ')';
+ if (len)
+ (*len)++;
+ }
+ } else {
+ /*
+ * This number is either an original, or something formed
+ * by a non-displayed operator (concatenation). Either way,
+ * we display it as is.
+ */
+ char buf[80], *p;
+ int blen;
+ blen = sprintf(buf, "%d", ss->numbers[2*index]);
+ if (ss->numbers[2*index+1] != 1)
+ blen += sprintf(buf+blen, "/%d", ss->numbers[2*index+1]);
+ assert(blen < lenof(buf));
+ for (p = buf; *p; p++) {
+ if (str)
+ *(*str)++ = *p;
+ if (len)
+ (*len)++;
+ }
+ }
+}
+char *mkstring(struct sets *s, struct output *o)
+{
+ int len;
+ char *str, *p;
+
+ len = 0;
+ mkstring_recurse(NULL, &len, s, o->set, o->index, 0, 0, 0);
+ str = snewn(len+1, char);
+ p = str;
+ mkstring_recurse(&p, NULL, s, o->set, o->index, 0, 0, 0);
+ assert(p - str <= len);
+ *p = '\0';
+ return str;
+}
+
+int main(int argc, char **argv)
+{
+ int doing_opts = TRUE;
+ const struct rules *rules = NULL;
+ char *pname = argv[0];
+ int got_target = FALSE, target = 0;
+ int numbers[10], nnumbers = 0;
+ int verbose = FALSE;
+ int pathcounts = FALSE;
+
+ struct output *o;
+ struct sets *s;
+ int i, start, limit;
+
+ while (--argc) {
+ char *p = *++argv;
+ int c;
+
+ if (doing_opts && *p == '-') {
+ p++;
+
+ if (!strcmp(p, "-")) {
+ doing_opts = FALSE;
+ continue;
+ } else while (*p) switch (c = *p++) {
+ case 'C':
+ rules = &rules_countdown;
+ break;
+ case 'B':
+ rules = &rules_3388;
+ break;
+ case 'D':
+ rules = &rules_four4s;
+ break;
+ case 'v':
+ verbose = TRUE;
+ break;
+ case 'p':
+ pathcounts = TRUE;
+ break;
+ case 't':
+ {
+ char *v;
+ if (*p) {
+ v = p;
+ p = NULL;
+ } else if (--argc) {
+ v = *++argv;
+ } else {
+ fprintf(stderr, "%s: option '-%c' expects an"
+ " argument\n", pname, c);
+ return 1;
+ }
+ switch (c) {
+ case 't':
+ got_target = TRUE;
+ target = atoi(v);
+ break;
+ }
+ }
+ break;
+ default:
+ fprintf(stderr, "%s: option '-%c' not"
+ " recognised\n", pname, c);
+ return 1;
+ }
+ } else {
+ if (nnumbers >= lenof(numbers)) {
+ fprintf(stderr, "%s: internal limit of %d numbers exceeded\n",
+ pname, lenof(numbers));
+ return 1;
+ } else {
+ numbers[nnumbers++] = atoi(p);
+ }
+ }
+ }
+
+ if (!rules) {
+ fprintf(stderr, "%s: no rule set specified; use -C,-B,-D\n", pname);
+ return 1;
+ }
+
+ if (!nnumbers) {
+ fprintf(stderr, "%s: no input numbers specified\n", pname);
+ return 1;
+ }
+
+ s = do_search(nnumbers, numbers, rules, (got_target ? &target : NULL));
+
+ if (got_target) {
+ o = findrelpos234(s->outputtree, &target, outputfindcmp,
+ REL234_LE, &start);
+ if (!o)
+ start = -1;
+ o = findrelpos234(s->outputtree, &target, outputfindcmp,
+ REL234_GE, &limit);
+ if (!o)
+ limit = -1;
+ assert(start != -1 || limit != -1);
+ if (start == -1)
+ start = limit;
+ else if (limit == -1)
+ limit = start;
+ limit++;
+ } else {
+ start = 0;
+ limit = count234(s->outputtree);
+ }
+
+ for (i = start; i < limit; i++) {
+ o = index234(s->outputtree, i);
+
+ printf("%d", o->number);
+
+ if (pathcounts)
+ printf(" [%d]", o->npaths);
+
+ if (got_target || verbose) {
+ char *p = mkstring(s, o);
+ printf(" = %s", p);
+ sfree(p);
+ }
+
+ printf("\n");
+ }
+
+ free_sets(s);
+
+ return 0;
+}
--- /dev/null
+/*
+ * Experimental grid generator for Nikoli's `Number Link' puzzle.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include "puzzles.h"
+
+/*
+ * 2005-07-08: This is currently a Path grid generator which will
+ * construct valid grids at a plausible speed. However, the grids
+ * are not of suitable quality to be used directly as puzzles.
+ *
+ * The basic strategy is to start with an empty grid, and
+ * repeatedly either (a) add a new path to it, or (b) extend one
+ * end of a path by one square in some direction and push other
+ * paths into new shapes in the process. The effect of this is that
+ * we are able to construct a set of paths which between them fill
+ * the entire grid.
+ *
+ * Quality issues: if we set the main loop to do (a) where possible
+ * and (b) only where necessary, we end up with a grid containing a
+ * few too many small paths, which therefore doesn't make for an
+ * interesting puzzle. If we reverse the priority so that we do (b)
+ * where possible and (a) only where necessary, we end up with some
+ * staggeringly interwoven grids with very very few separate paths,
+ * but the result of this is that there's invariably a solution
+ * other than the intended one which leaves many grid squares
+ * unfilled. There's also a separate problem which is that many
+ * grids have really boring and obvious paths in them, such as the
+ * entire bottom row of the grid being taken up by a single path.
+ *
+ * It's not impossible that a few tweaks might eliminate or reduce
+ * the incidence of boring paths, and might also find a happy
+ * medium between too many and too few. There remains the question
+ * of unique solutions, however. I fear there is no alternative but
+ * to write - somehow! - a solver.
+ *
+ * While I'm here, some notes on UI strategy for the parts of the
+ * puzzle implementation that _aren't_ the generator:
+ *
+ * - data model is to track connections between adjacent squares,
+ * so that you aren't limited to extending a path out from each
+ * number but can also mark sections of path which you know
+ * _will_ come in handy later.
+ *
+ * - user interface is to click in one square and drag to an
+ * adjacent one, thus creating a link between them. We can
+ * probably tolerate rapid mouse motion causing a drag directly
+ * to a square which is a rook move away, but any other rapid
+ * motion is ambiguous and probably the best option is to wait
+ * until the mouse returns to a square we know how to reach.
+ *
+ * - a drag causing the current path to backtrack has the effect
+ * of removing bits of it.
+ *
+ * - the UI should enforce at all times the constraint that at
+ * most two links can come into any square.
+ *
+ * - my Cunning Plan for actually implementing this: the game_ui
+ * contains a grid-sized array, which is copied from the current
+ * game_state on starting a drag. While a drag is active, the
+ * contents of the game_ui is adjusted with every mouse motion,
+ * and is displayed _in place_ of the game_state itself. On
+ * termination of a drag, the game_ui array is copied back into
+ * the new game_state (or rather, a string move is encoded which
+ * has precisely the set of link changes to cause that effect).
+ */
+
+/*
+ * Standard notation for directions.
+ */
+#define L 0
+#define U 1
+#define R 2
+#define D 3
+#define DX(dir) ( (dir)==L ? -1 : (dir)==R ? +1 : 0)
+#define DY(dir) ( (dir)==U ? -1 : (dir)==D ? +1 : 0)
+
+/*
+ * Perform a breadth-first search over a grid of squares with the
+ * colour of square (X,Y) given by grid[Y*w+X]. The search begins
+ * at (x,y), and finds all squares which are the same colour as
+ * (x,y) and reachable from it by orthogonal moves. On return:
+ * - dist[Y*w+X] gives the distance of (X,Y) from (x,y), or -1 if
+ * unreachable or a different colour
+ * - the returned value is the number of reachable squares,
+ * including (x,y) itself
+ * - list[0] up to list[returned value - 1] list those squares, in
+ * increasing order of distance from (x,y) (and in arbitrary
+ * order within that).
+ */
+static int bfs(int w, int h, int *grid, int x, int y, int *dist, int *list)
+{
+ int i, j, c, listsize, listdone;
+
+ /*
+ * Start by clearing the output arrays.
+ */
+ for (i = 0; i < w*h; i++)
+ dist[i] = list[i] = -1;
+
+ /*
+ * Set up the initial list.
+ */
+ listsize = 1;
+ listdone = 0;
+ list[0] = y*w+x;
+ dist[y*w+x] = 0;
+ c = grid[y*w+x];
+
+ /*
+ * Repeatedly process a square and add any extra squares to the
+ * end of list.
+ */
+ while (listdone < listsize) {
+ i = list[listdone++];
+ y = i / w;
+ x = i % w;
+ for (j = 0; j < 4; j++) {
+ int xx, yy, ii;
+
+ xx = x + DX(j);
+ yy = y + DY(j);
+ ii = yy*w+xx;
+
+ if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
+ grid[ii] == c && dist[ii] == -1) {
+ dist[ii] = dist[i] + 1;
+ assert(listsize < w*h);
+ list[listsize++] = ii;
+ }
+ }
+ }
+
+ return listsize;
+}
+
+struct genctx {
+ int w, h;
+ int *grid, *sparegrid, *sparegrid2, *sparegrid3;
+ int *dist, *list;
+
+ int npaths, pathsize;
+ int *pathends, *sparepathends; /* 2*npaths entries */
+ int *pathspare; /* npaths entries */
+ int *extends; /* 8*npaths entries */
+};
+
+static struct genctx *new_genctx(int w, int h)
+{
+ struct genctx *ctx = snew(struct genctx);
+ ctx->w = w;
+ ctx->h = h;
+ ctx->grid = snewn(w * h, int);
+ ctx->sparegrid = snewn(w * h, int);
+ ctx->sparegrid2 = snewn(w * h, int);
+ ctx->sparegrid3 = snewn(w * h, int);
+ ctx->dist = snewn(w * h, int);
+ ctx->list = snewn(w * h, int);
+ ctx->npaths = ctx->pathsize = 0;
+ ctx->pathends = ctx->sparepathends = ctx->pathspare = ctx->extends = NULL;
+ return ctx;
+}
+
+static void free_genctx(struct genctx *ctx)
+{
+ sfree(ctx->grid);
+ sfree(ctx->sparegrid);
+ sfree(ctx->sparegrid2);
+ sfree(ctx->sparegrid3);
+ sfree(ctx->dist);
+ sfree(ctx->list);
+ sfree(ctx->pathends);
+ sfree(ctx->sparepathends);
+ sfree(ctx->pathspare);
+ sfree(ctx->extends);
+}
+
+static int newpath(struct genctx *ctx)
+{
+ int n;
+
+ n = ctx->npaths++;
+ if (ctx->npaths > ctx->pathsize) {
+ ctx->pathsize += 16;
+ ctx->pathends = sresize(ctx->pathends, ctx->pathsize*2, int);
+ ctx->sparepathends = sresize(ctx->sparepathends, ctx->pathsize*2, int);
+ ctx->pathspare = sresize(ctx->pathspare, ctx->pathsize, int);
+ ctx->extends = sresize(ctx->extends, ctx->pathsize*8, int);
+ }
+ return n;
+}
+
+static int is_endpoint(struct genctx *ctx, int x, int y)
+{
+ int w = ctx->w, h = ctx->h, c;
+
+ assert(x >= 0 && x < w && y >= 0 && y < h);
+
+ c = ctx->grid[y*w+x];
+ if (c < 0)
+ return FALSE; /* empty square is not an endpoint! */
+ assert(c >= 0 && c < ctx->npaths);
+ if (ctx->pathends[c*2] == y*w+x || ctx->pathends[c*2+1] == y*w+x)
+ return TRUE;
+ return FALSE;
+}
+
+/*
+ * Tries to extend a path by one square in the given direction,
+ * pushing other paths around if necessary. Returns TRUE on success
+ * or FALSE on failure.
+ */
+static int extend_path(struct genctx *ctx, int path, int end, int direction)
+{
+ int w = ctx->w, h = ctx->h;
+ int x, y, xe, ye, cut;
+ int i, j, jp, n, first, last;
+
+ assert(path >= 0 && path < ctx->npaths);
+ assert(end == 0 || end == 1);
+
+ /*
+ * Find the endpoint of the path and the point we plan to
+ * extend it into.
+ */
+ y = ctx->pathends[path * 2 + end] / w;
+ x = ctx->pathends[path * 2 + end] % w;
+ assert(x >= 0 && x < w && y >= 0 && y < h);
+
+ xe = x + DX(direction);
+ ye = y + DY(direction);
+ if (xe < 0 || xe >= w || ye < 0 || ye >= h)
+ return FALSE; /* could not extend in this direction */
+
+ /*
+ * We don't extend paths _directly_ into endpoints of other
+ * paths, although we don't mind too much if a knock-on effect
+ * of an extension is to push part of another path into a third
+ * path's endpoint.
+ */
+ if (is_endpoint(ctx, xe, ye))
+ return FALSE;
+
+ /*
+ * We can't extend a path back the way it came.
+ */
+ if (ctx->grid[ye*w+xe] == path)
+ return FALSE;
+
+ /*
+ * Paths may not double back on themselves. Check if the new
+ * point is adjacent to any point of this path other than (x,y).
+ */
+ for (j = 0; j < 4; j++) {
+ int xf, yf;
+
+ xf = xe + DX(j);
+ yf = ye + DY(j);
+
+ if (xf >= 0 && xf < w && yf >= 0 && yf < h &&
+ (xf != x || yf != y) && ctx->grid[yf*w+xf] == path)
+ return FALSE;
+ }
+
+ /*
+ * Now we're convinced it's valid to _attempt_ the extension.
+ * It may still fail if we run out of space to push other paths
+ * into.
+ *
+ * So now we can set up our temporary data structures. We will
+ * need:
+ *
+ * - a spare copy of the grid on which to gradually move paths
+ * around (sparegrid)
+ *
+ * - a second spare copy with which to remember how paths
+ * looked just before being cut (sparegrid2). FIXME: is
+ * sparegrid2 necessary? right now it's never different from
+ * grid itself
+ *
+ * - a third spare copy with which to do the internal
+ * calculations involved in reconstituting a cut path
+ * (sparegrid3)
+ *
+ * - something to track which paths currently need
+ * reconstituting after being cut, and which have already
+ * been cut (pathspare)
+ *
+ * - a spare copy of pathends to store the altered states in
+ * (sparepathends)
+ */
+ memcpy(ctx->sparegrid, ctx->grid, w*h*sizeof(int));
+ memcpy(ctx->sparegrid2, ctx->grid, w*h*sizeof(int));
+ memcpy(ctx->sparepathends, ctx->pathends, ctx->npaths*2*sizeof(int));
+ for (i = 0; i < ctx->npaths; i++)
+ ctx->pathspare[i] = 0; /* 0=untouched, 1=broken, 2=fixed */
+
+ /*
+ * Working in sparegrid, actually extend the path. If it cuts
+ * another, begin a loop in which we restore any cut path by
+ * moving it out of the way.
+ */
+ cut = ctx->sparegrid[ye*w+xe];
+ ctx->sparegrid[ye*w+xe] = path;
+ ctx->sparepathends[path*2+end] = ye*w+xe;
+ ctx->pathspare[path] = 2; /* this one is sacrosanct */
+ if (cut >= 0) {
+ assert(cut >= 0 && cut < ctx->npaths);
+ ctx->pathspare[cut] = 1; /* broken */
+
+ while (1) {
+ for (i = 0; i < ctx->npaths; i++)
+ if (ctx->pathspare[i] == 1)
+ break;
+ if (i == ctx->npaths)
+ break; /* we're done */
+
+ /*
+ * Path i needs restoring. So walk along its original
+ * track (as given in sparegrid2) and see where it's
+ * been cut. Where it has, surround the cut points in
+ * the same colour, without overwriting already-fixed
+ * paths.
+ */
+ memcpy(ctx->sparegrid3, ctx->sparegrid, w*h*sizeof(int));
+ n = bfs(w, h, ctx->sparegrid2,
+ ctx->pathends[i*2] % w, ctx->pathends[i*2] / w,
+ ctx->dist, ctx->list);
+ first = last = -1;
+if (ctx->sparegrid3[ctx->pathends[i*2]] != i ||
+ ctx->sparegrid3[ctx->pathends[i*2+1]] != i) return FALSE;/* FIXME */
+ for (j = 0; j < n; j++) {
+ jp = ctx->list[j];
+ assert(ctx->dist[jp] == j);
+ assert(ctx->sparegrid2[jp] == i);
+
+ /*
+ * Wipe out the original path in sparegrid.
+ */
+ if (ctx->sparegrid[jp] == i)
+ ctx->sparegrid[jp] = -1;
+
+ /*
+ * Be prepared to shorten the path at either end if
+ * the endpoints have been stomped on.
+ */
+ if (ctx->sparegrid3[jp] == i) {
+ if (first < 0)
+ first = jp;
+ last = jp;
+ }
+
+ if (ctx->sparegrid3[jp] != i) {
+ int jx = jp % w, jy = jp / w;
+ int dx, dy;
+ for (dy = -1; dy <= +1; dy++)
+ for (dx = -1; dx <= +1; dx++) {
+ int newp, newv;
+ if (!dy && !dx)
+ continue; /* central square */
+ if (jx+dx < 0 || jx+dx >= w ||
+ jy+dy < 0 || jy+dy >= h)
+ continue; /* out of range */
+ newp = (jy+dy)*w+(jx+dx);
+ newv = ctx->sparegrid3[newp];
+ if (newv >= 0 && (newv == i ||
+ ctx->pathspare[newv] == 2))
+ continue; /* can't use this square */
+ ctx->sparegrid3[newp] = i;
+ }
+ }
+ }
+
+ if (first < 0 || last < 0)
+ return FALSE; /* path is completely wiped out! */
+
+ /*
+ * Now we've covered sparegrid3 in possible squares for
+ * the new layout of path i. Find the actual layout
+ * we're going to use by bfs: we want the shortest path
+ * from one endpoint to the other.
+ */
+ n = bfs(w, h, ctx->sparegrid3, first % w, first / w,
+ ctx->dist, ctx->list);
+ if (ctx->dist[last] < 2) {
+ /*
+ * Either there is no way to get between the path's
+ * endpoints, or the remaining endpoints simply
+ * aren't far enough apart to make the path viable
+ * any more. This means the entire push operation
+ * has failed.
+ */
+ return FALSE;
+ }
+
+ /*
+ * Write the new path into sparegrid. Also save the new
+ * endpoint locations, in case they've changed.
+ */
+ jp = last;
+ j = ctx->dist[jp];
+ while (1) {
+ int d;
+
+ if (ctx->sparegrid[jp] >= 0) {
+ if (ctx->pathspare[ctx->sparegrid[jp]] == 2)
+ return FALSE; /* somehow we've hit a fixed path */
+ ctx->pathspare[ctx->sparegrid[jp]] = 1; /* broken */
+ }
+ ctx->sparegrid[jp] = i;
+
+ if (j == 0)
+ break;
+
+ /*
+ * Now look at the neighbours of jp to find one
+ * which has dist[] one less.
+ */
+ for (d = 0; d < 4; d++) {
+ int jx = (jp % w) + DX(d), jy = (jp / w) + DY(d);
+ if (jx >= 0 && jx < w && jy >= 0 && jy < w &&
+ ctx->dist[jy*w+jx] == j-1) {
+ jp = jy*w+jx;
+ j--;
+ break;
+ }
+ }
+ assert(d < 4);
+ }
+
+ ctx->sparepathends[i*2] = first;
+ ctx->sparepathends[i*2+1] = last;
+//printf("new ends of path %d: %d,%d\n", i, first, last);
+ ctx->pathspare[i] = 2; /* fixed */
+ }
+ }
+
+ /*
+ * If we got here, the extension was successful!
+ */
+ memcpy(ctx->grid, ctx->sparegrid, w*h*sizeof(int));
+ memcpy(ctx->pathends, ctx->sparepathends, ctx->npaths*2*sizeof(int));
+ return TRUE;
+}
+
+/*
+ * Tries to add a new path to the grid.
+ */
+static int add_path(struct genctx *ctx, random_state *rs)
+{
+ int w = ctx->w, h = ctx->h;
+ int i, ii, n;
+
+ /*
+ * Our strategy is:
+ * - randomly choose an empty square in the grid
+ * - do a BFS from that point to find a long path starting
+ * from it
+ * - if we run out of viable empty squares, return failure.
+ */
+
+ /*
+ * Use `sparegrid' to collect a list of empty squares.
+ */
+ n = 0;
+ for (i = 0; i < w*h; i++)
+ if (ctx->grid[i] == -1)
+ ctx->sparegrid[n++] = i;
+
+ /*
+ * Shuffle the grid.
+ */
+ for (i = n; i-- > 1 ;) {
+ int k = random_upto(rs, i+1);
+ if (k != i) {
+ int t = ctx->sparegrid[i];
+ ctx->sparegrid[i] = ctx->sparegrid[k];
+ ctx->sparegrid[k] = t;
+ }
+ }
+
+ /*
+ * Loop over it trying to add paths. This looks like a
+ * horrifying N^4 algorithm (that is, (w*h)^2), but I predict
+ * that in fact the worst case will very rarely arise because
+ * when there's lots of grid space an attempt will succeed very
+ * quickly.
+ */
+ for (ii = 0; ii < n; ii++) {
+ int i = ctx->sparegrid[ii];
+ int y = i / w, x = i % w, nsq;
+ int r, c, j;
+
+ /*
+ * BFS from here to find long paths.
+ */
+ nsq = bfs(w, h, ctx->grid, x, y, ctx->dist, ctx->list);
+
+ /*
+ * If there aren't any long enough, give up immediately.
+ */
+ assert(nsq > 0); /* must be the start square at least! */
+ if (ctx->dist[ctx->list[nsq-1]] < 3)
+ continue;
+
+ /*
+ * Find the first viable endpoint in ctx->list (i.e. the
+ * first point with distance at least three). I could
+ * binary-search for this, but that would be O(log N)
+ * whereas in fact I can get a constant time bound by just
+ * searching up from the start - after all, there can be at
+ * most 13 points at _less_ than distance 3 from the
+ * starting one!
+ */
+ for (j = 0; j < nsq; j++)
+ if (ctx->dist[ctx->list[j]] >= 3)
+ break;
+ assert(j < nsq); /* we tested above that there was one */
+
+ /*
+ * Now we know that any element of `list' between j and nsq
+ * would be valid in principle. However, we want a few long
+ * paths rather than many small ones, so select only those
+ * elements which are either the maximum length or one
+ * below it.
+ */
+ while (ctx->dist[ctx->list[j]] + 1 < ctx->dist[ctx->list[nsq-1]])
+ j++;
+ r = j + random_upto(rs, nsq - j);
+ j = ctx->list[r];
+
+ /*
+ * And that's our endpoint. Mark the new path on the grid.
+ */
+ c = newpath(ctx);
+ ctx->pathends[c*2] = i;
+ ctx->pathends[c*2+1] = j;
+ ctx->grid[j] = c;
+ while (j != i) {
+ int d, np, index, pts[4];
+ np = 0;
+ for (d = 0; d < 4; d++) {
+ int xn = (j % w) + DX(d), yn = (j / w) + DY(d);
+ if (xn >= 0 && xn < w && yn >= 0 && yn < w &&
+ ctx->dist[yn*w+xn] == ctx->dist[j] - 1)
+ pts[np++] = yn*w+xn;
+ }
+ if (np > 1)
+ index = random_upto(rs, np);
+ else
+ index = 0;
+ j = pts[index];
+ ctx->grid[j] = c;
+ }
+
+ return TRUE;
+ }
+
+ return FALSE;
+}
+
+/*
+ * The main grid generation loop.
+ */
+static void gridgen_mainloop(struct genctx *ctx, random_state *rs)
+{
+ int w = ctx->w, h = ctx->h;
+ int i, n;
+
+ /*
+ * The generation algorithm doesn't always converge. Loop round
+ * until it does.
+ */
+ while (1) {
+ for (i = 0; i < w*h; i++)
+ ctx->grid[i] = -1;
+ ctx->npaths = 0;
+
+ while (1) {
+ /*
+ * See if the grid is full.
+ */
+ for (i = 0; i < w*h; i++)
+ if (ctx->grid[i] < 0)
+ break;
+ if (i == w*h)
+ return;
+
+#ifdef GENERATION_DIAGNOSTICS
+ {
+ int x, y;
+ for (y = 0; y < h; y++) {
+ printf("|");
+ for (x = 0; x < w; x++) {
+ if (ctx->grid[y*w+x] >= 0)
+ printf("%2d", ctx->grid[y*w+x]);
+ else
+ printf(" .");
+ }
+ printf(" |\n");
+ }
+ }
+#endif
+ /*
+ * Try adding a path.
+ */
+ if (add_path(ctx, rs)) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("added path\n");
+#endif
+ continue;
+ }
+
+ /*
+ * Try extending a path. First list all the possible
+ * extensions.
+ */
+ for (i = 0; i < ctx->npaths * 8; i++)
+ ctx->extends[i] = i;
+ n = i;
+
+ /*
+ * Then shuffle the list.
+ */
+ for (i = n; i-- > 1 ;) {
+ int k = random_upto(rs, i+1);
+ if (k != i) {
+ int t = ctx->extends[i];
+ ctx->extends[i] = ctx->extends[k];
+ ctx->extends[k] = t;
+ }
+ }
+
+ /*
+ * Now try each one in turn until one works.
+ */
+ for (i = 0; i < n; i++) {
+ int p, d, e;
+ p = ctx->extends[i];
+ d = p % 4;
+ p /= 4;
+ e = p % 2;
+ p /= 2;
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("trying to extend path %d end %d (%d,%d) in dir %d\n", p, e,
+ ctx->pathends[p*2+e] % w,
+ ctx->pathends[p*2+e] / w, d);
+#endif
+ if (extend_path(ctx, p, e, d)) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("extended path %d end %d (%d,%d) in dir %d\n", p, e,
+ ctx->pathends[p*2+e] % w,
+ ctx->pathends[p*2+e] / w, d);
+#endif
+ break;
+ }
+ }
+
+ if (i < n)
+ continue;
+
+ break;
+ }
+ }
+}
+
+/*
+ * Wrapper function which deals with the boring bits such as
+ * removing the solution from the generated grid, shuffling the
+ * numeric labels and creating/disposing of the context structure.
+ */
+static int *gridgen(int w, int h, random_state *rs)
+{
+ struct genctx *ctx;
+ int *ret;
+ int i;
+
+ ctx = new_genctx(w, h);
+
+ gridgen_mainloop(ctx, rs);
+
+ /*
+ * There is likely to be an ordering bias in the numbers
+ * (longer paths on lower numbers due to there having been more
+ * grid space when laying them down). So we must shuffle the
+ * numbers. We use ctx->pathspare for this.
+ *
+ * This is also as good a time as any to shift to numbering
+ * from 1, for display to the user.
+ */
+ for (i = 0; i < ctx->npaths; i++)
+ ctx->pathspare[i] = i+1;
+ for (i = ctx->npaths; i-- > 1 ;) {
+ int k = random_upto(rs, i+1);
+ if (k != i) {
+ int t = ctx->pathspare[i];
+ ctx->pathspare[i] = ctx->pathspare[k];
+ ctx->pathspare[k] = t;
+ }
+ }
+
+ /* FIXME: remove this at some point! */
+ {
+ int y, x;
+ for (y = 0; y < h; y++) {
+ printf("|");
+ for (x = 0; x < w; x++) {
+ assert(ctx->grid[y*w+x] >= 0);
+ printf("%2d", ctx->pathspare[ctx->grid[y*w+x]]);
+ }
+ printf(" |\n");
+ }
+ printf("\n");
+ }
+
+ /*
+ * Clear the grid, and write in just the endpoints.
+ */
+ for (i = 0; i < w*h; i++)
+ ctx->grid[i] = 0;
+ for (i = 0; i < ctx->npaths; i++) {
+ ctx->grid[ctx->pathends[i*2]] =
+ ctx->grid[ctx->pathends[i*2+1]] = ctx->pathspare[i];
+ }
+
+ ret = ctx->grid;
+ ctx->grid = NULL;
+
+ free_genctx(ctx);
+
+ return ret;
+}
+
+#ifdef TEST_GEN
+
+#define TEST_GENERAL
+
+int main(void)
+{
+ int w = 10, h = 8;
+ random_state *rs = random_init("12345", 5);
+ int x, y, i, *grid;
+
+ for (i = 0; i < 10; i++) {
+ grid = gridgen(w, h, rs);
+
+ for (y = 0; y < h; y++) {
+ printf("|");
+ for (x = 0; x < w; x++) {
+ if (grid[y*w+x] > 0)
+ printf("%2d", grid[y*w+x]);
+ else
+ printf(" .");
+ }
+ printf(" |\n");
+ }
+ printf("\n");
+
+ sfree(grid);
+ }
+
+ return 0;
+}
+#endif
+
+#ifdef TEST_GENERAL
+#include <stdarg.h>
+
+void fatal(char *fmt, ...)
+{
+ va_list ap;
+
+ fprintf(stderr, "fatal error: ");
+
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+
+ fprintf(stderr, "\n");
+ exit(1);
+}
+#endif
--- /dev/null
+# -*- makefile -*-
+
+PEARL = pearl dsf
+
+pearl : [X] GTK COMMON PEARL
+
+pearl : [G] WINDOWS COMMON PEARL
+
+ALL += PEARL
+
+!begin gtk
+GAMES += pearl
+!end
+
+!begin >list.c
+ A(pearl) \
+!end
--- /dev/null
+/*
+ * pearl.c: Nikoli's `Masyu' puzzle. Currently this is a blank
+ * puzzle file with nothing but a test solver-generator.
+ */
+
+/*
+ * TODO:
+ *
+ * - The generation method appears to be fundamentally flawed. I
+ * think generating a random loop and then choosing a clue set
+ * is simply not a viable approach, because on a test run of
+ * 10,000 attempts, it generated _six_ viable puzzles. All the
+ * rest of the randomly generated loops failed to be soluble
+ * even given a maximal clue set. Also, the vast majority of the
+ * clues were white circles (straight clues); black circles
+ * (corners) seem very uncommon.
+ * + So what can we do? One possible approach would be to
+ * adjust the random loop generation so that it created loops
+ * which were in some heuristic sense more likely to be
+ * viable Masyu puzzles. Certainly a good start on that would
+ * be to arrange that black clues actually _came up_ slightly
+ * more often, but I have no idea whether that would be
+ * sufficient.
+ * + A second option would be to throw the entire mechanism out
+ * and instead write a different generator from scratch which
+ * evolves the solution along with the puzzle: place a few
+ * clues, nail down a bit of the loop, place another clue,
+ * nail down some more, etc. It's unclear whether this can
+ * sensibly be done, though.
+ *
+ * - Puzzle playing UI and everything else apart from the
+ * generator...
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+
+#define NOCLUE 0
+#define CORNER 1
+#define STRAIGHT 2
+
+#define R 1
+#define U 2
+#define L 4
+#define D 8
+
+#define DX(d) ( ((d)==R) - ((d)==L) )
+#define DY(d) ( ((d)==D) - ((d)==U) )
+
+#define F(d) (((d << 2) | (d >> 2)) & 0xF)
+#define C(d) (((d << 3) | (d >> 1)) & 0xF)
+#define A(d) (((d << 1) | (d >> 3)) & 0xF)
+
+#define LR (L | R)
+#define RL (R | L)
+#define UD (U | D)
+#define DU (D | U)
+#define LU (L | U)
+#define UL (U | L)
+#define LD (L | D)
+#define DL (D | L)
+#define RU (R | U)
+#define UR (U | R)
+#define RD (R | D)
+#define DR (D | R)
+#define BLANK 0
+#define UNKNOWN 15
+
+#define bLR (1 << LR)
+#define bRL (1 << RL)
+#define bUD (1 << UD)
+#define bDU (1 << DU)
+#define bLU (1 << LU)
+#define bUL (1 << UL)
+#define bLD (1 << LD)
+#define bDL (1 << DL)
+#define bRU (1 << RU)
+#define bUR (1 << UR)
+#define bRD (1 << RD)
+#define bDR (1 << DR)
+#define bBLANK (1 << BLANK)
+
+enum {
+ COL_BACKGROUND,
+ NCOLOURS
+};
+
+struct game_params {
+ int FIXME;
+};
+
+struct game_state {
+ int FIXME;
+};
+
+static game_params *default_params(void)
+{
+ game_params *ret = snew(game_params);
+
+ ret->FIXME = 0;
+
+ return ret;
+}
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{
+ return FALSE;
+}
+
+static void free_params(game_params *params)
+{
+ sfree(params);
+}
+
+static game_params *dup_params(game_params *params)
+{
+ game_params *ret = snew(game_params);
+ *ret = *params; /* structure copy */
+ return ret;
+}
+
+static void decode_params(game_params *params, char const *string)
+{
+}
+
+static char *encode_params(game_params *params, int full)
+{
+ return dupstr("FIXME");
+}
+
+static config_item *game_configure(game_params *params)
+{
+ return NULL;
+}
+
+static game_params *custom_params(config_item *cfg)
+{
+ return NULL;
+}
+
+static char *validate_params(game_params *params, int full)
+{
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Solver.
+ */
+
+int pearl_solve(int w, int h, char *clues, char *result)
+{
+ int W = 2*w+1, H = 2*h+1;
+ short *workspace;
+ int *dsf, *dsfsize;
+ int x, y, b, d;
+ int ret = -1;
+
+ /*
+ * workspace[(2*y+1)*W+(2*x+1)] indicates the possible nature
+ * of the square (x,y), as a logical OR of bitfields.
+ *
+ * workspace[(2*y)*W+(2*x+1)], for x odd and y even, indicates
+ * whether the horizontal edge between (x,y) and (x+1,y) is
+ * connected (1), disconnected (2) or unknown (3).
+ *
+ * workspace[(2*y+1)*W+(2*x)], indicates the same about the
+ * vertical edge between (x,y) and (x,y+1).
+ *
+ * Initially, every square is considered capable of being in
+ * any of the seven possible states (two straights, four
+ * corners and empty), except those corresponding to clue
+ * squares which are more restricted.
+ *
+ * Initially, all edges are unknown, except the ones around the
+ * grid border which are known to be disconnected.
+ */
+ workspace = snewn(W*H, short);
+ for (x = 0; x < W*H; x++)
+ workspace[x] = 0;
+ /* Square states */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ switch (clues[y*w+x]) {
+ case CORNER:
+ workspace[(2*y+1)*W+(2*x+1)] = bLU|bLD|bRU|bRD;
+ break;
+ case STRAIGHT:
+ workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD;
+ break;
+ default:
+ workspace[(2*y+1)*W+(2*x+1)] = bLR|bUD|bLU|bLD|bRU|bRD|bBLANK;
+ break;
+ }
+ /* Horizontal edges */
+ for (y = 0; y <= h; y++)
+ for (x = 0; x < w; x++)
+ workspace[(2*y)*W+(2*x+1)] = (y==0 || y==h ? 2 : 3);
+ /* Vertical edges */
+ for (y = 0; y < h; y++)
+ for (x = 0; x <= w; x++)
+ workspace[(2*y+1)*W+(2*x)] = (x==0 || x==w ? 2 : 3);
+
+ /*
+ * We maintain a dsf of connected squares, together with a
+ * count of the size of each equivalence class.
+ */
+ dsf = snewn(w*h, int);
+ dsfsize = snewn(w*h, int);
+
+ /*
+ * Now repeatedly try to find something we can do.
+ */
+ while (1) {
+
+#ifdef SOLVER_DIAGNOSTICS
+ for (y = 0; y < H; y++) {
+ for (x = 0; x < W; x++)
+ printf("%*x", (x&1) ? 5 : 2, workspace[y*W+x]);
+ printf("\n");
+ }
+#endif
+
+ int done_something = FALSE;
+
+ /*
+ * Go through the square state words, and discard any
+ * square state which is inconsistent with known facts
+ * about the edges around the square.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {
+ for (b = 0; b < 0xD; b++)
+ if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
+ /*
+ * If any edge of this square is known to
+ * be connected when state b would require
+ * it disconnected, or vice versa, discard
+ * the state.
+ */
+ for (d = 1; d <= 8; d += d) {
+ int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
+ if (workspace[ey*W+ex] ==
+ ((b & d) ? 2 : 1)) {
+ workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<b);
+#ifdef SOLVER_DIAGNOSTICS
+ printf("edge (%d,%d)-(%d,%d) rules out state"
+ " %d for square (%d,%d)\n",
+ ex/2, ey/2, (ex+1)/2, (ey+1)/2,
+ b, x, y);
+#endif
+ done_something = TRUE;
+ break;
+ }
+ }
+ }
+
+ /*
+ * Consistency check: each square must have at
+ * least one state left!
+ */
+ if (!workspace[(2*y+1)*W+(2*x+1)]) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("edge check at (%d,%d): inconsistency\n", x, y);
+ ret = 0;
+ goto cleanup;
+#endif
+ }
+ }
+
+ /*
+ * Now go through the states array again, and nail down any
+ * unknown edge if one of its neighbouring squares makes it
+ * known.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {
+ int edgeor = 0, edgeand = 15;
+
+ for (b = 0; b < 0xD; b++)
+ if (workspace[(2*y+1)*W+(2*x+1)] & (1<<b)) {
+ edgeor |= b;
+ edgeand &= b;
+ }
+
+ /*
+ * Now any bit clear in edgeor marks a disconnected
+ * edge, and any bit set in edgeand marks a
+ * connected edge.
+ */
+
+ /* First check consistency: neither bit is both! */
+ if (edgeand & ~edgeor) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("square check at (%d,%d): inconsistency\n", x, y);
+ ret = 0;
+ goto cleanup;
+#endif
+ }
+
+ for (d = 1; d <= 8; d += d) {
+ int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
+
+ if (!(edgeor & d) && workspace[ey*W+ex] == 3) {
+ workspace[ey*W+ex] = 2;
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("possible states of square (%d,%d) force edge"
+ " (%d,%d)-(%d,%d) to be disconnected\n",
+ x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
+#endif
+ } else if ((edgeand & d) && workspace[ey*W+ex] == 3) {
+ workspace[ey*W+ex] = 1;
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("possible states of square (%d,%d) force edge"
+ " (%d,%d)-(%d,%d) to be connected\n",
+ x, y, ex/2, ey/2, (ex+1)/2, (ey+1)/2);
+#endif
+ }
+ }
+ }
+
+ if (done_something)
+ continue;
+
+ /*
+ * Now for longer-range clue-based deductions (using the
+ * rules that a corner clue must connect to two straight
+ * squares, and a straight clue must connect to at least
+ * one corner square).
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ switch (clues[y*w+x]) {
+ case CORNER:
+ for (d = 1; d <= 8; d += d) {
+ int ex = 2*x+1 + DX(d), ey = 2*y+1 + DY(d);
+ int fx = ex + DX(d), fy = ey + DY(d);
+ int type = d | F(d);
+
+ if (workspace[ey*W+ex] == 1) {
+ /*
+ * If a corner clue is connected on any
+ * edge, then we can immediately nail
+ * down the square beyond that edge as
+ * being a straight in the appropriate
+ * direction.
+ */
+ if (workspace[fy*W+fx] != (1<<type)) {
+ workspace[fy*W+fx] = (1<<type);
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("corner clue at (%d,%d) forces square "
+ "(%d,%d) into state %d\n", x, y,
+ fx/2, fy/2, type);
+#endif
+
+ }
+ } else if (workspace[ey*W+ex] == 3) {
+ /*
+ * Conversely, if a corner clue is
+ * separated by an unknown edge from a
+ * square which _cannot_ be a straight
+ * in the appropriate direction, we can
+ * mark that edge as disconnected.
+ */
+ if (!(workspace[fy*W+fx] & (1<<type))) {
+ workspace[ey*W+ex] = 2;
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("corner clue at (%d,%d), plus square "
+ "(%d,%d) not being state %d, "
+ "disconnects edge (%d,%d)-(%d,%d)\n",
+ x, y, fx/2, fy/2, type,
+ ex/2, ey/2, (ex+1)/2, (ey+1)/2);
+#endif
+
+ }
+ }
+ }
+
+
+ break;
+ case STRAIGHT:
+ /*
+ * If a straight clue is between two squares
+ * neither of which is capable of being a
+ * corner connected to it, then the straight
+ * clue cannot point in that direction.
+ */
+ for (d = 1; d <= 2; d += d) {
+ int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
+ int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
+ int type = d | F(d);
+
+ if (!(workspace[(2*y+1)*W+(2*x+1)] & (1<<type)))
+ continue;
+
+ if (!(workspace[fy*W+fx] & ((1<<(F(d)|A(d))) |
+ (1<<(F(d)|C(d))))) &&
+ !(workspace[gy*W+gx] & ((1<<( d |A(d))) |
+ (1<<( d |C(d)))))) {
+ workspace[(2*y+1)*W+(2*x+1)] &= ~(1<<type);
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("straight clue at (%d,%d) cannot corner at "
+ "(%d,%d) or (%d,%d) so is not state %d\n",
+ x, y, fx/2, fy/2, gx/2, gy/2, type);
+#endif
+ }
+
+ }
+
+ /*
+ * If a straight clue with known direction is
+ * connected on one side to a known straight,
+ * then on the other side it must be a corner.
+ */
+ for (d = 1; d <= 8; d += d) {
+ int fx = 2*x+1 + 2*DX(d), fy = 2*y+1 + 2*DY(d);
+ int gx = 2*x+1 - 2*DX(d), gy = 2*y+1 - 2*DY(d);
+ int type = d | F(d);
+
+ if (workspace[(2*y+1)*W+(2*x+1)] != (1<<type))
+ continue;
+
+ if (!(workspace[fy*W+fx] &~ (bLR|bUD)) &&
+ (workspace[gy*W+gx] &~ (bLU|bLD|bRU|bRD))) {
+ workspace[gy*W+gx] &= (bLU|bLD|bRU|bRD);
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("straight clue at (%d,%d) connecting to "
+ "straight at (%d,%d) makes (%d,%d) a "
+ "corner\n", x, y, fx/2, fy/2, gx/2, gy/2);
+#endif
+ }
+
+ }
+ break;
+ }
+
+ if (done_something)
+ continue;
+
+ /*
+ * Now detect shortcut loops.
+ */
+
+ {
+ int nonblanks, loopclass;
+
+ dsf_init(dsf, w*h);
+ for (x = 0; x < w*h; x++)
+ dsfsize[x] = 1;
+
+ /*
+ * First go through the edge entries and update the dsf
+ * of which squares are connected to which others. We
+ * also track the number of squares in each equivalence
+ * class, and count the overall number of
+ * known-non-blank squares.
+ *
+ * In the process of doing this, we must notice if a
+ * loop has already been formed. If it has, we blank
+ * out any square which isn't part of that loop
+ * (failing a consistency check if any such square does
+ * not have BLANK as one of its remaining options) and
+ * exit the deduction loop with success.
+ */
+ nonblanks = 0;
+ loopclass = -1;
+ for (y = 1; y < H-1; y++)
+ for (x = 1; x < W-1; x++)
+ if ((y ^ x) & 1) {
+ /*
+ * (x,y) are the workspace coordinates of
+ * an edge field. Compute the normal-space
+ * coordinates of the squares it connects.
+ */
+ int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
+ int bx = x/2, by = y/2, bc = by*w+bx;
+
+ /*
+ * If the edge is connected, do the dsf
+ * thing.
+ */
+ if (workspace[y*W+x] == 1) {
+ int ae, be;
+
+ ae = dsf_canonify(dsf, ac);
+ be = dsf_canonify(dsf, bc);
+
+ if (ae == be) {
+ /*
+ * We have a loop!
+ */
+ if (loopclass != -1) {
+ /*
+ * In fact, we have two
+ * separate loops, which is
+ * doom.
+ */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("two loops found in grid!\n");
+#endif
+ ret = 0;
+ goto cleanup;
+ }
+ loopclass = ae;
+ } else {
+ /*
+ * Merge the two equivalence
+ * classes.
+ */
+ int size = dsfsize[ae] + dsfsize[be];
+ dsf_merge(dsf, ac, bc);
+ ae = dsf_canonify(dsf, ac);
+ dsfsize[ae] = size;
+ }
+ }
+ } else if ((y & x) & 1) {
+ /*
+ * (x,y) are the workspace coordinates of a
+ * square field. If the square is
+ * definitely not blank, count it.
+ */
+ if (!(workspace[y*W+x] & bBLANK))
+ nonblanks++;
+ }
+
+ /*
+ * If we discovered an existing loop above, we must now
+ * blank every square not part of it, and exit the main
+ * deduction loop.
+ */
+ if (loopclass != -1) {
+#ifdef SOLVER_DIAGNOSTICS
+ printf("loop found in grid!\n");
+#endif
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ if (dsf_canonify(dsf, y*w+x) != loopclass) {
+ if (workspace[(y*2+1)*W+(x*2+1)] & bBLANK) {
+ workspace[(y*2+1)*W+(x*2+1)] = bBLANK;
+ } else {
+ /*
+ * This square is not part of the
+ * loop, but is known non-blank. We
+ * have goofed.
+ */
+#ifdef SOLVER_DIAGNOSTICS
+ printf("non-blank square (%d,%d) found outside"
+ " loop!\n", x, y);
+#endif
+ ret = 0;
+ goto cleanup;
+ }
+ }
+ /*
+ * And we're done.
+ */
+ ret = 1;
+ break;
+ }
+
+ /*
+ * Now go through the workspace again and mark any edge
+ * which would cause a shortcut loop (i.e. would
+ * connect together two squares in the same equivalence
+ * class, and that equivalence class does not contain
+ * _all_ the known-non-blank squares currently in the
+ * grid) as disconnected. Also, mark any _square state_
+ * which would cause a shortcut loop as disconnected.
+ */
+ for (y = 1; y < H-1; y++)
+ for (x = 1; x < W-1; x++)
+ if ((y ^ x) & 1) {
+ /*
+ * (x,y) are the workspace coordinates of
+ * an edge field. Compute the normal-space
+ * coordinates of the squares it connects.
+ */
+ int ax = (x-1)/2, ay = (y-1)/2, ac = ay*w+ax;
+ int bx = x/2, by = y/2, bc = by*w+bx;
+
+ /*
+ * If the edge is currently unknown, and
+ * sits between two squares in the same
+ * equivalence class, and the size of that
+ * class is less than nonblanks, then
+ * connecting this edge would be a shortcut
+ * loop and so we must not do so.
+ */
+ if (workspace[y*W+x] == 3) {
+ int ae, be;
+
+ ae = dsf_canonify(dsf, ac);
+ be = dsf_canonify(dsf, bc);
+
+ if (ae == be) {
+ /*
+ * We have a loop. Is it a shortcut?
+ */
+ if (dsfsize[ae] < nonblanks) {
+ /*
+ * Yes! Mark this edge disconnected.
+ */
+ workspace[y*W+x] = 2;
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("edge (%d,%d)-(%d,%d) would create"
+ " a shortcut loop, hence must be"
+ " disconnected\n", x/2, y/2,
+ (x+1)/2, (y+1)/2);
+#endif
+ }
+ }
+ }
+ } else if ((y & x) & 1) {
+ /*
+ * (x,y) are the workspace coordinates of a
+ * square field. Go through its possible
+ * (non-blank) states and see if any gives
+ * rise to a shortcut loop.
+ *
+ * This is slightly fiddly, because we have
+ * to check whether this square is already
+ * part of the same equivalence class as
+ * the things it's joining.
+ */
+ int ae = dsf_canonify(dsf, (y/2)*w+(x/2));
+
+ for (b = 2; b < 0xD; b++)
+ if (workspace[y*W+x] & (1<<b)) {
+ /*
+ * Find the equivalence classes of
+ * the two squares this one would
+ * connect if it were in this
+ * state.
+ */
+ int e = -1;
+
+ for (d = 1; d <= 8; d += d) if (b & d) {
+ int xx = x/2 + DX(d), yy = y/2 + DY(d);
+ int ee = dsf_canonify(dsf, yy*w+xx);
+
+ if (e == -1)
+ ee = e;
+ else if (e != ee)
+ e = -2;
+ }
+
+ if (e >= 0) {
+ /*
+ * This square state would form
+ * a loop on equivalence class
+ * e. Measure the size of that
+ * loop, and see if it's a
+ * shortcut.
+ */
+ int loopsize = dsfsize[e];
+ if (e != ae)
+ loopsize++;/* add the square itself */
+ if (loopsize < nonblanks) {
+ /*
+ * It is! Mark this square
+ * state invalid.
+ */
+ workspace[y*W+x] &= ~(1<<b);
+ done_something = TRUE;
+#ifdef SOLVER_DIAGNOSTICS
+ printf("square (%d,%d) would create a "
+ "shortcut loop in state %d, "
+ "hence cannot be\n",
+ x/2, y/2, b);
+#endif
+ }
+ }
+ }
+ }
+ }
+
+ if (done_something)
+ continue;
+
+ /*
+ * If we reach here, there is nothing left we can do.
+ * Return 2 for ambiguous puzzle.
+ */
+ ret = 2;
+ goto cleanup;
+ }
+
+ /*
+ * If we reach _here_, it's by `break' out of the main loop,
+ * which means we've successfully achieved a solution. This
+ * means that we expect every square to be nailed down to
+ * exactly one possibility. Transcribe those possibilities into
+ * the result array.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {
+ for (b = 0; b < 0xD; b++)
+ if (workspace[(2*y+1)*W+(2*x+1)] == (1<<b)) {
+ result[y*w+x] = b;
+ break;
+ }
+ assert(b < 0xD); /* we should have had a break by now */
+ }
+
+ cleanup:
+ sfree(dsfsize);
+ sfree(dsf);
+ sfree(workspace);
+ assert(ret >= 0);
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Loop generator.
+ */
+
+void pearl_loopgen(int w, int h, char *grid, random_state *rs)
+{
+ int *options, *mindist, *maxdist, *list;
+ int x, y, d, total, n, area, limit;
+
+ /*
+ * We're eventually going to have to return a w-by-h array
+ * containing line segment data. However, it's more convenient
+ * while actually generating the loop to consider the problem
+ * as a (w-1) by (h-1) array in which some squares are `inside'
+ * and some `outside'.
+ *
+ * I'm going to use the top left corner of my return array in
+ * the latter manner until the end of the function.
+ */
+
+ /*
+ * To begin with, all squares are outside (0), except for one
+ * randomly selected one which is inside (1).
+ */
+ memset(grid, 0, w*h);
+ x = random_upto(rs, w-1);
+ y = random_upto(rs, h-1);
+ grid[y*w+x] = 1;
+
+ /*
+ * I'm also going to need an array to store the possible
+ * options for the next extension of the grid.
+ */
+ options = snewn(w*h, int);
+ for (x = 0; x < w*h; x++)
+ options[x] = 0;
+
+ /*
+ * And some arrays and a list for breadth-first searching.
+ */
+ mindist = snewn(w*h, int);
+ maxdist = snewn(w*h, int);
+ list = snewn(w*h, int);
+
+ /*
+ * Now we repeatedly scan the grid for feasible squares into
+ * which we can extend our loop, pick one, and do it.
+ */
+ area = 1;
+
+ while (1) {
+#ifdef LOOPGEN_DIAGNOSTICS
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++)
+ printf("%d", grid[y*w+x]);
+ printf("\n");
+ }
+ printf("\n");
+#endif
+
+ /*
+ * Our primary aim in growing this loop is to make it
+ * reasonably _dense_ in the target rectangle. That is, we
+ * want the maximum over all squares of the minimum
+ * distance from that square to the loop to be small.
+ *
+ * Therefore, we start with a breadth-first search of the
+ * grid to find those minimum distances.
+ */
+ {
+ int head = 0, tail = 0;
+ int i;
+
+ for (i = 0; i < w*h; i++) {
+ mindist[i] = -1;
+ if (grid[i]) {
+ mindist[i] = 0;
+ list[tail++] = i;
+ }
+ }
+
+ while (head < tail) {
+ i = list[head++];
+ y = i / w;
+ x = i % w;
+ for (d = 1; d <= 8; d += d) {
+ int xx = x + DX(d), yy = y + DY(d);
+ if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
+ mindist[yy*w+xx] < 0) {
+ mindist[yy*w+xx] = mindist[i] + 1;
+ list[tail++] = yy*w+xx;
+ }
+ }
+ }
+
+ /*
+ * Having done the BFS, we now backtrack along its path
+ * to determine the most distant square that each
+ * square is on the shortest path to. This tells us
+ * which of the loop extension candidates (all of which
+ * are squares marked 1) is most desirable to extend
+ * into in terms of minimising the maximum distance
+ * from any empty square to the nearest loop square.
+ */
+ for (head = tail; head-- > 0 ;) {
+ int max;
+
+ i = list[head];
+ y = i / w;
+ x = i % w;
+
+ max = mindist[i];
+
+ for (d = 1; d <= 8; d += d) {
+ int xx = x + DX(d), yy = y + DY(d);
+ if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
+ mindist[yy*w+xx] > mindist[i] &&
+ maxdist[yy*w+xx] > max) {
+ max = maxdist[yy*w+xx];
+ }
+ }
+
+ maxdist[i] = max;
+ }
+ }
+
+ /*
+ * A square is a viable candidate for extension of our loop
+ * if and only if the following conditions are all met:
+ * - It is currently labelled 0.
+ * - At least one of its four orthogonal neighbours is
+ * labelled 1.
+ * - If you consider its eight orthogonal and diagonal
+ * neighbours to form a ring, that ring contains at most
+ * one contiguous run of 1s. (It must also contain at
+ * _least_ one, of course, but that's already guaranteed
+ * by the previous condition so there's no need to test
+ * it separately.)
+ */
+ total = 0;
+ for (y = 0; y < h-1; y++)
+ for (x = 0; x < w-1; x++) {
+ int ring[8];
+ int rx, neighbours, runs, dist;
+
+ dist = maxdist[y*w+x];
+ options[y*w+x] = 0;
+
+ if (grid[y*w+x])
+ continue; /* it isn't labelled 0 */
+
+ neighbours = 0;
+ for (rx = 0, d = 1; d <= 8; rx += 2, d += d) {
+ int x2 = x + DX(d), y2 = y + DY(d);
+ int x3 = x2 + DX(A(d)), y3 = y2 + DY(A(d));
+ int g2 = (x2 >= 0 && x2 < w && y2 >= 0 && y2 < h ?
+ grid[y2*w+x2] : 0);
+ int g3 = (x3 >= 0 && x3 < w && y3 >= 0 && y3 < h ?
+ grid[y3*w+x3] : 0);
+ ring[rx] = g2;
+ ring[rx+1] = g3;
+ if (g2)
+ neighbours++;
+ }
+
+ if (!neighbours)
+ continue; /* it doesn't have a 1 neighbour */
+
+ runs = 0;
+ for (rx = 0; rx < 8; rx++)
+ if (ring[rx] && !ring[(rx+1) & 7])
+ runs++;
+
+ if (runs > 1)
+ continue; /* too many runs of 1s */
+
+ /*
+ * Now we know this square is a viable extension
+ * candidate. Mark it.
+ *
+ * FIXME: probabilistic prioritisation based on
+ * perimeter perturbation? (Wow, must keep that
+ * phrase.)
+ */
+ options[y*w+x] = dist * (4-neighbours) * (4-neighbours);
+ total += options[y*w+x];
+ }
+
+ if (!total)
+ break; /* nowhere to go! */
+
+ /*
+ * Now pick a random one of the viable extension squares,
+ * and extend into it.
+ */
+ n = random_upto(rs, total);
+ for (y = 0; y < h-1; y++)
+ for (x = 0; x < w-1; x++) {
+ assert(n >= 0);
+ if (options[y*w+x] > n)
+ goto found; /* two-level break */
+ n -= options[y*w+x];
+ }
+ assert(!"We shouldn't ever get here");
+ found:
+ grid[y*w+x] = 1;
+ area++;
+
+ /*
+ * We terminate the loop when around 7/12 of the grid area
+ * is full, but we also require that the loop has reached
+ * all four edges.
+ */
+ limit = random_upto(rs, (w-1)*(h-1)) + 13*(w-1)*(h-1);
+ if (24 * area > limit) {
+ int l = FALSE, r = FALSE, u = FALSE, d = FALSE;
+ for (x = 0; x < w; x++) {
+ if (grid[0*w+x])
+ u = TRUE;
+ if (grid[(h-2)*w+x])
+ d = TRUE;
+ }
+ for (y = 0; y < h; y++) {
+ if (grid[y*w+0])
+ l = TRUE;
+ if (grid[y*w+(w-2)])
+ r = TRUE;
+ }
+ if (l && r && u && d)
+ break;
+ }
+ }
+
+ sfree(list);
+ sfree(maxdist);
+ sfree(mindist);
+ sfree(options);
+
+#ifdef LOOPGEN_DIAGNOSTICS
+ printf("final loop:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++)
+ printf("%d", grid[y*w+x]);
+ printf("\n");
+ }
+ printf("\n");
+#endif
+
+ /*
+ * Now convert this array of 0s and 1s into an array of path
+ * components.
+ */
+ for (y = h; y-- > 0 ;) {
+ for (x = w; x-- > 0 ;) {
+ /*
+ * Examine the four grid squares of which (x,y) are in
+ * the bottom right, to determine the output for this
+ * square.
+ */
+ int ul = (x > 0 && y > 0 ? grid[(y-1)*w+(x-1)] : 0);
+ int ur = (y > 0 ? grid[(y-1)*w+x] : 0);
+ int dl = (x > 0 ? grid[y*w+(x-1)] : 0);
+ int dr = grid[y*w+x];
+ int type = 0;
+
+ if (ul != ur) type |= U;
+ if (dl != dr) type |= D;
+ if (ul != dl) type |= L;
+ if (ur != dr) type |= R;
+
+ assert((bLR|bUD|bLU|bLD|bRU|bRD|bBLANK) & (1 << type));
+
+ grid[y*w+x] = type;
+
+ }
+ }
+
+#if defined LOOPGEN_DIAGNOSTICS && !defined GENERATION_DIAGNOSTICS
+ printf("as returned:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ int type = grid[y*w+x];
+ char s[5], *p = s;
+ if (type & L) *p++ = 'L';
+ if (type & R) *p++ = 'R';
+ if (type & U) *p++ = 'U';
+ if (type & D) *p++ = 'D';
+ *p = '\0';
+ printf("%3s", s);
+ }
+ printf("\n");
+ }
+ printf("\n");
+#endif
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ char *grid, *clues;
+ int *clueorder;
+ int w = 10, h = 10;
+ int x, y, d, ret, i;
+
+#if 0
+ clues = snewn(7*7, char);
+ memcpy(clues,
+ "\0\1\0\0\2\0\0"
+ "\0\0\0\2\0\0\0"
+ "\0\0\0\2\0\0\1"
+ "\2\0\0\2\0\0\0"
+ "\2\0\0\0\0\0\1"
+ "\0\0\1\0\0\2\0"
+ "\0\0\2\0\0\0\0", 7*7);
+ grid = snewn(7*7, char);
+ printf("%d\n", pearl_solve(7, 7, clues, grid));
+#elif 0
+ clues = snewn(10*10, char);
+ memcpy(clues,
+ "\0\0\2\0\2\0\0\0\0\0"
+ "\0\0\0\0\2\0\0\0\1\0"
+ "\0\0\1\0\1\0\2\0\0\0"
+ "\0\0\0\2\0\0\2\0\0\0"
+ "\1\0\0\0\0\2\0\0\0\2"
+ "\0\0\2\0\0\0\0\2\0\0"
+ "\0\0\1\0\0\0\2\0\0\0"
+ "\2\0\0\0\1\0\0\0\0\2"
+ "\0\0\0\0\0\0\2\2\0\0"
+ "\0\0\1\0\0\0\0\0\0\1", 10*10);
+ grid = snewn(10*10, char);
+ printf("%d\n", pearl_solve(10, 10, clues, grid));
+#elif 0
+ clues = snewn(10*10, char);
+ memcpy(clues,
+ "\0\0\0\0\0\0\1\0\0\0"
+ "\0\1\0\1\2\0\0\0\0\2"
+ "\0\0\0\0\0\0\0\0\0\1"
+ "\2\0\0\1\2\2\1\0\0\0"
+ "\1\0\0\0\0\0\0\1\0\0"
+ "\0\0\2\0\0\0\0\0\0\2"
+ "\0\0\0\2\1\2\1\0\0\2"
+ "\2\0\0\0\0\0\0\0\0\0"
+ "\2\0\0\0\0\1\1\0\2\0"
+ "\0\0\0\2\0\0\0\0\0\0", 10*10);
+ grid = snewn(10*10, char);
+ printf("%d\n", pearl_solve(10, 10, clues, grid));
+#endif
+
+ grid = snewn(w*h, char);
+ clues = snewn(w*h, char);
+ clueorder = snewn(w*h, int);
+
+ while (1) {
+ pearl_loopgen(w, h, grid, rs);
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("grid array:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ int type = grid[y*w+x];
+ char s[5], *p = s;
+ if (type & L) *p++ = 'L';
+ if (type & R) *p++ = 'R';
+ if (type & U) *p++ = 'U';
+ if (type & D) *p++ = 'D';
+ *p = '\0';
+ printf("%2s ", s);
+ }
+ printf("\n");
+ }
+ printf("\n");
+#endif
+
+ /*
+ * Set up the maximal clue array.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {
+ int type = grid[y*w+x];
+
+ clues[y*w+x] = NOCLUE;
+
+ if ((bLR|bUD) & (1 << type)) {
+ /*
+ * This is a straight; see if it's a viable
+ * candidate for a straight clue. It qualifies if
+ * at least one of the squares it connects to is a
+ * corner.
+ */
+ for (d = 1; d <= 8; d += d) if (type & d) {
+ int xx = x + DX(d), yy = y + DY(d);
+ assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
+ if ((bLU|bLD|bRU|bRD) & (1 << grid[yy*w+xx]))
+ break;
+ }
+ if (d <= 8) /* we found one */
+ clues[y*w+x] = STRAIGHT;
+ } else if ((bLU|bLD|bRU|bRD) & (1 << type)) {
+ /*
+ * This is a corner; see if it's a viable candidate
+ * for a corner clue. It qualifies if all the
+ * squares it connects to are straights.
+ */
+ for (d = 1; d <= 8; d += d) if (type & d) {
+ int xx = x + DX(d), yy = y + DY(d);
+ assert(xx >= 0 && xx < w && yy >= 0 && yy < h);
+ if (!((bLR|bUD) & (1 << grid[yy*w+xx])))
+ break;
+ }
+ if (d > 8) /* we didn't find a counterexample */
+ clues[y*w+x] = CORNER;
+ }
+ }
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("clue array:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+#endif
+
+ /*
+ * See if we can solve the puzzle just like this.
+ */
+ ret = pearl_solve(w, h, clues, grid);
+ assert(ret > 0); /* shouldn't be inconsistent! */
+ if (ret != 1)
+ continue; /* go round and try again */
+
+ /*
+ * Now shuffle the grid points and gradually remove the
+ * clues to find a minimal set which still leaves the
+ * puzzle soluble.
+ */
+ for (i = 0; i < w*h; i++)
+ clueorder[i] = i;
+ shuffle(clueorder, w*h, sizeof(*clueorder), rs);
+ for (i = 0; i < w*h; i++) {
+ int clue;
+
+ y = clueorder[i] / w;
+ x = clueorder[i] % w;
+
+ if (clues[y*w+x] == 0)
+ continue;
+
+ clue = clues[y*w+x];
+ clues[y*w+x] = 0; /* try removing this clue */
+
+ ret = pearl_solve(w, h, clues, grid);
+ assert(ret > 0);
+ if (ret != 1)
+ clues[y*w+x] = clue; /* oops, put it back again */
+ }
+
+#ifdef FINISHED_PUZZLE
+ printf("clue array:\n");
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ printf("%c", " *O"[(unsigned char)clues[y*w+x]]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+#endif
+
+ break; /* got it */
+ }
+
+ sfree(grid);
+ sfree(clues);
+ sfree(clueorder);
+
+ return dupstr("FIXME");
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{
+ return NULL;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{
+ game_state *state = snew(game_state);
+
+ state->FIXME = 0;
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{
+ game_state *ret = snew(game_state);
+
+ ret->FIXME = state->FIXME;
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{
+ sfree(state);
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *aux, char **error)
+{
+ return NULL;
+}
+
+static char *game_text_format(game_state *state)
+{
+ return NULL;
+}
+
+static game_ui *new_ui(game_state *state)
+{
+ return NULL;
+}
+
+static void free_ui(game_ui *ui)
+{
+}
+
+static char *encode_ui(game_ui *ui)
+{
+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{
+}
+
+struct game_drawstate {
+ int tilesize;
+ int FIXME;
+};
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{
+ return NULL;
+}
+
+static game_state *execute_move(game_state *state, char *move)
+{
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{
+ *x = *y = 10 * tilesize; /* FIXME */
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{
+ ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+ float *ret = snewn(3 * NCOLOURS, float);
+
+ frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{
+ struct game_drawstate *ds = snew(struct game_drawstate);
+
+ ds->tilesize = 0;
+ ds->FIXME = 0;
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+ sfree(ds);
+}
+
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
+{
+ /*
+ * The initial contents of the window are not guaranteed and
+ * can vary with front ends. To be on the safe side, all games
+ * should start by drawing a big background-colour rectangle
+ * covering the whole window.
+ */
+ draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{
+ return 0.0F;
+}
+
+static float game_flash_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{
+ return 0.0F;
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{
+ return TRUE;
+}
+
+static void game_print_size(game_params *params, float *x, float *y)
+{
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{
+}
+
+#ifdef COMBINED
+#define thegame pearl
+#endif
+
+const struct game thegame = {
+ "Pearl", NULL,
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ FALSE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ FALSE, solve_game,
+ FALSE, game_text_format,
+ new_ui,
+ free_ui,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
+ 20 /* FIXME */, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ FALSE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ 0, /* flags */
+};
--- /dev/null
+# -*- makefile -*-
+
+sokoban : [X] GTK COMMON sokoban
+
+sokoban : [G] WINDOWS COMMON sokoban
+
+ALL += sokoban
+
+!begin gtk
+GAMES += sokoban
+!end
+
+!begin >list.c
+ A(sokoban) \
+!end
--- /dev/null
+/*
+ * sokoban.c: An implementation of the well-known Sokoban barrel-
+ * pushing game. Random generation is too simplistic to be
+ * credible, but the rest of the gameplay works well enough to use
+ * it with hand-written level descriptions.
+ */
+
+/*
+ * TODO:
+ *
+ * - I think it would be better to ditch the `prev' array, and
+ * instead make the `dist' array strictly monotonic (by having
+ * each distance be something like I*A+S, where A is the grid
+ * area, I the number of INITIAL squares trampled on, and S the
+ * number of harmless spaces moved through). This would permit
+ * the path-tracing when a pull is actually made to choose
+ * randomly from all the possible shortest routes, which would
+ * be superior in terms of eliminating directional bias.
+ * + So when tracing the path back to the current px,py, we
+ * look at all four adjacent squares, find the minimum
+ * distance, check that it's _strictly smaller_ than that of
+ * the current square, and restrict our choice to precisely
+ * those squares with that minimum distance.
+ * + The other place `prev' is currently used is in the check
+ * for consistency of a pull. We would have to replace the
+ * check for whether prev[ny*w+nx]==oy*w+ox with a check that
+ * made sure there was at least one adjacent square with a
+ * smaller distance which _wasn't_ oy*w+ox. Then when we did
+ * the path-tracing we'd also have to take this special case
+ * into account.
+ *
+ * - More discriminating choice of pull. (Snigger.)
+ * + favour putting targets in clumps
+ * + try to shoot for a reasonably consistent number of barrels
+ * (adjust willingness to generate a new barrel depending on
+ * how many are already present)
+ * + adjust willingness to break new ground depending on how
+ * much is already broken
+ *
+ * - generation time parameters:
+ * + enable NetHack mode (and find a better place for the hole)
+ * + decide how many of the remaining Is should be walls
+ *
+ * - at the end of generation, randomly position the starting
+ * player coordinates, probably by (somehow) reusing the same
+ * bfs currently inside the loop.
+ *
+ * - possible backtracking?
+ *
+ * - IWBNI we could spot completely unreachable bits of level at
+ * the outside, and not bother drawing grid lines for them. The
+ * NH levels currently look a bit weird with grid lines on the
+ * outside of the boundary.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include <ctype.h>
+#include <math.h>
+
+#include "puzzles.h"
+
+/*
+ * Various subsets of these constants are used during game
+ * generation, game play, game IDs and the game_drawstate.
+ */
+#define INITIAL 'i' /* used only in game generation */
+#define SPACE 's'
+#define WALL 'w'
+#define PIT 'p'
+#define DEEP_PIT 'd'
+#define TARGET 't'
+#define BARREL 'b'
+#define BARRELTARGET 'f' /* target is 'f'illed */
+#define PLAYER 'u' /* yo'u'; used in game IDs */
+#define PLAYERTARGET 'v' /* bad letter: v is to u as t is to s */
+#define INVALID '!' /* used in drawstate to force redraw */
+/*
+ * We also support the use of any capital letter as a barrel, which
+ * will be displayed with that letter as a label. (This facilitates
+ * people distributing annotated game IDs for particular Sokoban
+ * levels, so they can accompany them with verbal instructions
+ * about pushing particular barrels in particular ways.) Therefore,
+ * to find out whether something is a barrel, we need a test
+ * function which does a bit more than just comparing to BARREL.
+ *
+ * When resting on target squares, capital-letter barrels are
+ * replaced with their control-character value (A -> ^A).
+ */
+#define IS_PLAYER(c) ( (c)==PLAYER || (c)==PLAYERTARGET )
+#define IS_BARREL(c) ( (c)==BARREL || (c)==BARRELTARGET || \
+ ((c)>='A' && (c)<='Z') || ((c)>=1 && (c)<=26) )
+#define IS_ON_TARGET(c) ( (c)==TARGET || (c)==BARRELTARGET || \
+ (c)==PLAYERTARGET || ((c)>=1 && (c)<=26) )
+#define TARGETISE(b) ( (b)==BARREL ? BARRELTARGET : (b)-('A'-1) )
+#define DETARGETISE(b) ( (b)==BARRELTARGET ? BARREL : (b)+('A'-1) )
+#define BARREL_LABEL(b) ( (b)>='A'&&(b)<='Z' ? (b) : \
+ (b)>=1 && (b)<=26 ? (b)+('A'-1) : 0 )
+
+#define DX(d) (d == 0 ? -1 : d == 2 ? +1 : 0);
+#define DY(d) (d == 1 ? -1 : d == 3 ? +1 : 0);
+
+#define FLASH_LENGTH 0.3F
+
+enum {
+ COL_BACKGROUND,
+ COL_TARGET,
+ COL_PIT,
+ COL_DEEP_PIT,
+ COL_BARREL,
+ COL_PLAYER,
+ COL_TEXT,
+ COL_GRID,
+ COL_OUTLINE,
+ COL_HIGHLIGHT,
+ COL_LOWLIGHT,
+ COL_WALL,
+ NCOLOURS
+};
+
+struct game_params {
+ int w, h;
+ /*
+ * FIXME: a parameter involving degree of filling in?
+ */
+};
+
+struct game_state {
+ game_params p;
+ unsigned char *grid;
+ int px, py;
+ int completed;
+};
+
+static game_params *default_params(void)
+{
+ game_params *ret = snew(game_params);
+
+ ret->w = 12;
+ ret->h = 10;
+
+ return ret;
+}
+
+static void free_params(game_params *params)
+{
+ sfree(params);
+}
+
+static game_params *dup_params(game_params *params)
+{
+ game_params *ret = snew(game_params);
+ *ret = *params; /* structure copy */
+ return ret;
+}
+
+static const struct game_params sokoban_presets[] = {
+ { 12, 10 },
+ { 16, 12 },
+ { 20, 16 },
+};
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{
+ game_params p, *ret;
+ char *retname;
+ char namebuf[80];
+
+ if (i < 0 || i >= lenof(sokoban_presets))
+ return FALSE;
+
+ p = sokoban_presets[i];
+ ret = dup_params(&p);
+ sprintf(namebuf, "%dx%d", ret->w, ret->h);
+ retname = dupstr(namebuf);
+
+ *params = ret;
+ *name = retname;
+ return TRUE;
+}
+
+static void decode_params(game_params *params, char const *string)
+{
+ params->w = params->h = atoi(string);
+ while (*string && isdigit((unsigned char)*string)) string++;
+ if (*string == 'x') {
+ string++;
+ params->h = atoi(string);
+ }
+}
+
+static char *encode_params(game_params *params, int full)
+{
+ char data[256];
+
+ sprintf(data, "%dx%d", params->w, params->h);
+
+ return dupstr(data);
+}
+
+static config_item *game_configure(game_params *params)
+{
+ config_item *ret;
+ char buf[80];
+
+ ret = snewn(3, config_item);
+
+ ret[0].name = "Width";
+ ret[0].type = C_STRING;
+ sprintf(buf, "%d", params->w);
+ ret[0].sval = dupstr(buf);
+ ret[0].ival = 0;
+
+ ret[1].name = "Height";
+ ret[1].type = C_STRING;
+ sprintf(buf, "%d", params->h);
+ ret[1].sval = dupstr(buf);
+ ret[1].ival = 0;
+
+ ret[2].name = NULL;
+ ret[2].type = C_END;
+ ret[2].sval = NULL;
+ ret[2].ival = 0;
+
+ return ret;
+}
+
+static game_params *custom_params(config_item *cfg)
+{
+ game_params *ret = snew(game_params);
+
+ ret->w = atoi(cfg[0].sval);
+ ret->h = atoi(cfg[1].sval);
+
+ return ret;
+}
+
+static char *validate_params(game_params *params, int full)
+{
+ if (params->w < 4 || params->h < 4)
+ return "Width and height must both be at least 4";
+
+ return NULL;
+}
+
+/* ----------------------------------------------------------------------
+ * Game generation mechanism.
+ *
+ * To generate a Sokoban level, we begin with a completely blank
+ * grid and make valid inverse moves. Grid squares can be in a
+ * number of states. The states are:
+ *
+ * - INITIAL: this square has not as yet been touched by any
+ * inverse move, which essentially means we haven't decided what
+ * it is yet.
+ *
+ * - SPACE: this square is a space.
+ *
+ * - TARGET: this square is a space which is also the target for a
+ * barrel.
+ *
+ * - BARREL: this square contains a barrel.
+ *
+ * - BARRELTARGET: this square contains a barrel _on_ a target.
+ *
+ * - WALL: this square is a wall.
+ *
+ * - PLAYER: this square contains the player.
+ *
+ * - PLAYERTARGET: this square contains the player on a target.
+ *
+ * We begin with every square of the in state INITIAL, apart from a
+ * solid ring of WALLs around the edge. We randomly position the
+ * PLAYER somewhere. Thereafter our valid moves are:
+ *
+ * - to move the PLAYER in one direction _pulling_ a barrel after
+ * us. For this to work, we must have SPACE or INITIAL in the
+ * direction we're moving, and BARREL or BARRELTARGET in the
+ * direction we're moving away from. We leave SPACE or TARGET
+ * respectively in the vacated square.
+ *
+ * - to create a new barrel by transforming an INITIAL square into
+ * BARRELTARGET.
+ *
+ * - to move the PLAYER freely through SPACE and TARGET squares,
+ * leaving SPACE or TARGET where it started.
+ *
+ * - to move the player through INITIAL squares, carving a tunnel
+ * of SPACEs as it goes.
+ *
+ * We try to avoid destroying INITIAL squares wherever possible (if
+ * there's a path to where we want to be using only SPACE, then we
+ * should always use that). At the end of generation, every square
+ * still in state INITIAL is one which was not required at any
+ * point during generation, which means we can randomly choose
+ * whether to make it SPACE or WALL.
+ *
+ * It's unclear as yet what the right strategy for wall placement
+ * should be. Too few WALLs will yield many alternative solutions
+ * to the puzzle, whereas too many might rule out so many
+ * possibilities that the intended solution becomes obvious.
+ */
+
+static void sokoban_generate(int w, int h, unsigned char *grid, int moves,
+ int nethack, random_state *rs)
+{
+ struct pull {
+ int ox, oy, nx, ny, score;
+ };
+
+ struct pull *pulls;
+ int *dist, *prev, *heap;
+ int x, y, px, py, i, j, d, heapsize, npulls;
+
+ pulls = snewn(w * h * 4, struct pull);
+ dist = snewn(w * h, int);
+ prev = snewn(w * h, int);
+ heap = snewn(w * h, int);
+
+ /*
+ * Configure the initial grid.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ grid[y*w+x] = (x == 0 || y == 0 || x == w-1 || y == h-1 ?
+ WALL : INITIAL);
+ if (nethack)
+ grid[1] = DEEP_PIT;
+
+ /*
+ * Place the player.
+ */
+ i = random_upto(rs, (w-2) * (h-2));
+ x = 1 + i % (w-2);
+ y = 1 + i / (w-2);
+ grid[y*w+x] = SPACE;
+ px = x;
+ py = y;
+
+ /*
+ * Now loop around making random inverse Sokoban moves. In this
+ * loop we aim to make one actual barrel-pull per iteration,
+ * plus as many free moves as are necessary to get into
+ * position for that pull.
+ */
+ while (moves-- >= 0) {
+ /*
+ * First enumerate all the viable barrel-pulls we can
+ * possibly make, counting two pulls of the same barrel in
+ * different directions as different. We also include pulls
+ * we can perform by creating a new barrel. Each pull is
+ * marked with the amount of violence it would have to do
+ * to the grid.
+ */
+ npulls = 0;
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ for (d = 0; d < 4; d++) {
+ int dx = DX(d);
+ int dy = DY(d);
+ int nx = x + dx, ny = y + dy;
+ int npx = nx + dx, npy = ny + dy;
+ int score = 0;
+
+ /*
+ * The candidate move is to put the player at
+ * (nx,ny), and move him to (npx,npy), pulling
+ * a barrel at (x,y) to (nx,ny). So first we
+ * must check that all those squares are within
+ * the boundaries of the grid. For this it is
+ * sufficient to check npx,npy.
+ */
+ if (npx < 0 || npx >= w || npy < 0 || npy >= h)
+ continue;
+
+ /*
+ * (x,y) must either be a barrel, or a square
+ * which we can convert into a barrel.
+ */
+ switch (grid[y*w+x]) {
+ case BARREL: case BARRELTARGET:
+ break;
+ case INITIAL:
+ if (nethack)
+ continue;
+ score += 10 /* new_barrel_score */;
+ break;
+ case DEEP_PIT:
+ if (!nethack)
+ continue;
+ break;
+ default:
+ continue;
+ }
+
+ /*
+ * (nx,ny) must either be a space, or a square
+ * which we can convert into a space.
+ */
+ switch (grid[ny*w+nx]) {
+ case SPACE: case TARGET:
+ break;
+ case INITIAL:
+ score += 3 /* new_space_score */;
+ break;
+ default:
+ continue;
+ }
+
+ /*
+ * (npx,npy) must also either be a space, or a
+ * square which we can convert into a space.
+ */
+ switch (grid[npy*w+npx]) {
+ case SPACE: case TARGET:
+ break;
+ case INITIAL:
+ score += 3 /* new_space_score */;
+ break;
+ default:
+ continue;
+ }
+
+ /*
+ * That's sufficient to tag this as a possible
+ * pull right now. We still don't know if we
+ * can reach the required player position, but
+ * that's a job for the subsequent BFS phase to
+ * tell us.
+ */
+ pulls[npulls].ox = x;
+ pulls[npulls].oy = y;
+ pulls[npulls].nx = nx;
+ pulls[npulls].ny = ny;
+ pulls[npulls].score = score;
+#ifdef GENERATION_DIAGNOSTICS
+ printf("found potential pull: (%d,%d)-(%d,%d) cost %d\n",
+ pulls[npulls].ox, pulls[npulls].oy,
+ pulls[npulls].nx, pulls[npulls].ny,
+ pulls[npulls].score);
+#endif
+ npulls++;
+ }
+#ifdef GENERATION_DIAGNOSTICS
+ printf("found %d potential pulls\n", npulls);
+#endif
+
+ /*
+ * If there are no pulls available at all, we give up.
+ *
+ * (FIXME: or perhaps backtrack?)
+ */
+ if (npulls == 0)
+ break;
+
+ /*
+ * Now we do a BFS from our current position, to find all
+ * the squares we can get the player into.
+ *
+ * This BFS is unusually tricky. We want to give a positive
+ * distance only to squares which we have to carve through
+ * INITIALs to get to, which means we can't just stick
+ * every square we reach on the end of our to-do list.
+ * Instead, we must maintain our list as a proper priority
+ * queue.
+ */
+ for (i = 0; i < w*h; i++)
+ dist[i] = prev[i] = -1;
+
+ heap[0] = py*w+px;
+ heapsize = 1;
+ dist[py*w+px] = 0;
+
+#define PARENT(n) ( ((n)-1)/2 )
+#define LCHILD(n) ( 2*(n)+1 )
+#define RCHILD(n) ( 2*(n)+2 )
+#define SWAP(i,j) do { int swaptmp = (i); (i) = (j); (j) = swaptmp; } while (0)
+
+ while (heapsize > 0) {
+ /*
+ * Pull the smallest element off the heap: it's at
+ * position 0. Move the arbitrary element from the very
+ * end of the heap into position 0.
+ */
+ y = heap[0] / w;
+ x = heap[0] % w;
+
+ heapsize--;
+ heap[0] = heap[heapsize];
+
+ /*
+ * Now repeatedly move that arbitrary element down the
+ * heap by swapping it with the more suitable of its
+ * children.
+ */
+ i = 0;
+ while (1) {
+ int lc, rc;
+
+ lc = LCHILD(i);
+ rc = RCHILD(i);
+
+ if (lc >= heapsize)
+ break; /* we've hit bottom */
+
+ if (rc >= heapsize) {
+ /*
+ * Special case: there is only one child to
+ * check.
+ */
+ if (dist[heap[i]] > dist[heap[lc]])
+ SWAP(heap[i], heap[lc]);
+
+ /* _Now_ we've hit bottom. */
+ break;
+ } else {
+ /*
+ * The common case: there are two children and
+ * we must check them both.
+ */
+ if (dist[heap[i]] > dist[heap[lc]] ||
+ dist[heap[i]] > dist[heap[rc]]) {
+ /*
+ * Pick the more appropriate child to swap with
+ * (i.e. the one which would want to be the
+ * parent if one were above the other - as one
+ * is about to be).
+ */
+ if (dist[heap[lc]] > dist[heap[rc]]) {
+ SWAP(heap[i], heap[rc]);
+ i = rc;
+ } else {
+ SWAP(heap[i], heap[lc]);
+ i = lc;
+ }
+ } else {
+ /* This element is in the right place; we're done. */
+ break;
+ }
+ }
+ }
+
+ /*
+ * OK, that's given us (x,y) for this phase of the
+ * search. Now try all directions from here.
+ */
+
+ for (d = 0; d < 4; d++) {
+ int dx = DX(d);
+ int dy = DY(d);
+ int nx = x + dx, ny = y + dy;
+ if (nx < 0 || nx >= w || ny < 0 || ny >= h)
+ continue;
+ if (grid[ny*w+nx] != SPACE && grid[ny*w+nx] != TARGET &&
+ grid[ny*w+nx] != INITIAL)
+ continue;
+ if (dist[ny*w+nx] == -1) {
+ dist[ny*w+nx] = dist[y*w+x] + (grid[ny*w+nx] == INITIAL);
+ prev[ny*w+nx] = y*w+x;
+
+ /*
+ * Now insert ny*w+nx at the end of the heap,
+ * and move it down to its appropriate resting
+ * place.
+ */
+ i = heapsize;
+ heap[heapsize++] = ny*w+nx;
+
+ /*
+ * Swap element n with its parent repeatedly to
+ * preserve the heap property.
+ */
+
+ while (i > 0) {
+ int p = PARENT(i);
+
+ if (dist[heap[p]] > dist[heap[i]]) {
+ SWAP(heap[p], heap[i]);
+ i = p;
+ } else
+ break;
+ }
+ }
+ }
+ }
+
+#undef PARENT
+#undef LCHILD
+#undef RCHILD
+#undef SWAP
+
+#ifdef GENERATION_DIAGNOSTICS
+ printf("distance map:\n");
+ for (i = 0; i < h; i++) {
+ for (j = 0; j < w; j++) {
+ int d = dist[i*w+j];
+ int c;
+ if (d < 0)
+ c = '#';
+ else if (d >= 36)
+ c = '!';
+ else if (d >= 10)
+ c = 'A' - 10 + d;
+ else
+ c = '0' + d;
+ putchar(c);
+ }
+ putchar('\n');
+ }
+#endif
+
+ /*
+ * Now we can go back through the `pulls' array, adjusting
+ * the score for each pull depending on how hard it is to
+ * reach its starting point, and also throwing out any
+ * whose starting points are genuinely unreachable even
+ * with the possibility of carving through INITIAL squares.
+ */
+ for (i = j = 0; i < npulls; i++) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf("potential pull (%d,%d)-(%d,%d)",
+ pulls[i].ox, pulls[i].oy,
+ pulls[i].nx, pulls[i].ny);
+#endif
+ x = pulls[i].nx;
+ y = pulls[i].ny;
+ if (dist[y*w+x] < 0) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf(" unreachable\n");
+#endif
+ continue; /* this pull isn't feasible at all */
+ } else {
+ /*
+ * Another nasty special case we have to check is
+ * whether the initial barrel location (ox,oy) is
+ * on the path used to reach the square. This can
+ * occur if that square is in state INITIAL: the
+ * pull is initially considered valid on the basis
+ * that the INITIAL can become BARRELTARGET, and
+ * it's also considered reachable on the basis that
+ * INITIAL can be turned into SPACE, but it can't
+ * be both at once.
+ *
+ * Fortunately, if (ox,oy) is on the path at all,
+ * it must be only one space from the end, so this
+ * is easy to spot and rule out.
+ */
+ if (prev[y*w+x] == pulls[i].oy*w+pulls[i].ox) {
+#ifdef GENERATION_DIAGNOSTICS
+ printf(" goes through itself\n");
+#endif
+ continue; /* this pull isn't feasible at all */
+ }
+ pulls[j] = pulls[i]; /* structure copy */
+ pulls[j].score += dist[y*w+x] * 3 /* new_space_score */;
+#ifdef GENERATION_DIAGNOSTICS
+ printf(" reachable at distance %d (cost now %d)\n",
+ dist[y*w+x], pulls[j].score);
+#endif
+ j++;
+ }
+ }
+ npulls = j;
+
+ /*
+ * Again, if there are no pulls available at all, we give
+ * up.
+ *
+ * (FIXME: or perhaps backtrack?)
+ */
+ if (npulls == 0)
+ break;
+
+ /*
+ * Now choose which pull to make. On the one hand we should
+ * prefer pulls which do less damage to the INITIAL squares
+ * (thus, ones for which we can already get into position
+ * via existing SPACEs, and for which the barrel already
+ * exists and doesn't have to be invented); on the other,
+ * we want to avoid _always_ preferring such pulls, on the
+ * grounds that that will lead to levels without very much
+ * stuff in.
+ *
+ * When creating new barrels, we prefer creations which are
+ * next to existing TARGET squares.
+ *
+ * FIXME: for the moment I'll make this very simple indeed.
+ */
+ i = random_upto(rs, npulls);
+
+ /*
+ * Actually make the pull, including carving a path to get
+ * to the site if necessary.
+ */
+ x = pulls[i].nx;
+ y = pulls[i].ny;
+ while (prev[y*w+x] >= 0) {
+ int p;
+
+ if (grid[y*w+x] == INITIAL)
+ grid[y*w+x] = SPACE;
+
+ p = prev[y*w+x];
+ y = p / w;
+ x = p % w;
+ }
+ px = 2*pulls[i].nx - pulls[i].ox;
+ py = 2*pulls[i].ny - pulls[i].oy;
+ if (grid[py*w+px] == INITIAL)
+ grid[py*w+px] = SPACE;
+ if (grid[pulls[i].ny*w+pulls[i].nx] == TARGET)
+ grid[pulls[i].ny*w+pulls[i].nx] = BARRELTARGET;
+ else
+ grid[pulls[i].ny*w+pulls[i].nx] = BARREL;
+ if (grid[pulls[i].oy*w+pulls[i].ox] == BARREL)
+ grid[pulls[i].oy*w+pulls[i].ox] = SPACE;
+ else if (grid[pulls[i].oy*w+pulls[i].ox] != DEEP_PIT)
+ grid[pulls[i].oy*w+pulls[i].ox] = TARGET;
+ }
+
+ sfree(heap);
+ sfree(prev);
+ sfree(dist);
+ sfree(pulls);
+
+ if (grid[py*w+px] == TARGET)
+ grid[py*w+px] = PLAYERTARGET;
+ else
+ grid[py*w+px] = PLAYER;
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ int w = params->w, h = params->h;
+ char *desc;
+ int desclen, descpos, descsize, prev, count;
+ unsigned char *grid;
+ int i, j;
+
+ /*
+ * FIXME: perhaps some more interesting means of choosing how
+ * many moves to try?
+ */
+ grid = snewn(w*h, unsigned char);
+ sokoban_generate(w, h, grid, w*h, FALSE, rs);
+
+ desclen = descpos = descsize = 0;
+ desc = NULL;
+ prev = -1;
+ count = 0;
+ for (i = 0; i < w*h; i++) {
+ if (descsize < desclen + 40) {
+ descsize = desclen + 100;
+ desc = sresize(desc, descsize, char);
+ desc[desclen] = '\0';
+ }
+ switch (grid[i]) {
+ case INITIAL:
+ j = 'w'; /* FIXME: make some of these 's'? */
+ break;
+ case SPACE:
+ j = 's';
+ break;
+ case WALL:
+ j = 'w';
+ break;
+ case TARGET:
+ j = 't';
+ break;
+ case BARREL:
+ j = 'b';
+ break;
+ case BARRELTARGET:
+ j = 'f';
+ break;
+ case DEEP_PIT:
+ j = 'd';
+ break;
+ case PLAYER:
+ j = 'u';
+ break;
+ case PLAYERTARGET:
+ j = 'v';
+ break;
+ default:
+ j = '?';
+ break;
+ }
+ assert(j != '?');
+ if (j != prev) {
+ desc[desclen++] = j;
+ descpos = desclen;
+ prev = j;
+ count = 1;
+ } else {
+ count++;
+ desclen = descpos + sprintf(desc+descpos, "%d", count);
+ }
+ }
+
+ sfree(grid);
+
+ return desc;
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{
+ int w = params->w, h = params->h;
+ int area = 0;
+ int nplayers = 0;
+
+ while (*desc) {
+ int c = *desc++;
+ int n = 1;
+ if (*desc && isdigit((unsigned char)*desc)) {
+ n = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ }
+
+ area += n;
+
+ if (c == PLAYER || c == PLAYERTARGET)
+ nplayers += n;
+ else if (c == INITIAL || c == SPACE || c == WALL || c == TARGET ||
+ c == PIT || c == DEEP_PIT || IS_BARREL(c))
+ /* ok */;
+ else
+ return "Invalid character in game description";
+ }
+
+ if (area > w*h)
+ return "Too much data in game description";
+ if (area < w*h)
+ return "Too little data in game description";
+ if (nplayers < 1)
+ return "No starting player position specified";
+ if (nplayers > 1)
+ return "More than one starting player position specified";
+
+ return NULL;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{
+ int w = params->w, h = params->h;
+ game_state *state = snew(game_state);
+ int i;
+
+ state->p = *params; /* structure copy */
+ state->grid = snewn(w*h, unsigned char);
+ state->px = state->py = -1;
+ state->completed = FALSE;
+
+ i = 0;
+
+ while (*desc) {
+ int c = *desc++;
+ int n = 1;
+ if (*desc && isdigit((unsigned char)*desc)) {
+ n = atoi(desc);
+ while (*desc && isdigit((unsigned char)*desc)) desc++;
+ }
+
+ if (c == PLAYER || c == PLAYERTARGET) {
+ state->py = i / w;
+ state->px = i % w;
+ c = IS_ON_TARGET(c) ? TARGET : SPACE;
+ }
+
+ while (n-- > 0)
+ state->grid[i++] = c;
+ }
+
+ assert(i == w*h);
+ assert(state->px != -1 && state->py != -1);
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{
+ int w = state->p.w, h = state->p.h;
+ game_state *ret = snew(game_state);
+
+ ret->p = state->p; /* structure copy */
+ ret->grid = snewn(w*h, unsigned char);
+ memcpy(ret->grid, state->grid, w*h);
+ ret->px = state->px;
+ ret->py = state->py;
+ ret->completed = state->completed;
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{
+ sfree(state->grid);
+ sfree(state);
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *aux, char **error)
+{
+ return NULL;
+}
+
+static char *game_text_format(game_state *state)
+{
+ return NULL;
+}
+
+static game_ui *new_ui(game_state *state)
+{
+ return NULL;
+}
+
+static void free_ui(game_ui *ui)
+{
+}
+
+static char *encode_ui(game_ui *ui)
+{
+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{
+}
+
+struct game_drawstate {
+ game_params p;
+ int tilesize;
+ int started;
+ unsigned short *grid;
+};
+
+#define PREFERRED_TILESIZE 32
+#define TILESIZE (ds->tilesize)
+#define BORDER (TILESIZE)
+#define HIGHLIGHT_WIDTH (TILESIZE / 10)
+#define COORD(x) ( (x) * TILESIZE + BORDER )
+#define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 )
+
+/*
+ * I'm going to need to do most of the move-type analysis in both
+ * interpret_move and execute_move, so I'll abstract it out into a
+ * subfunction. move_type() returns -1 for an illegal move, 0 for a
+ * movement, and 1 for a push.
+ */
+int move_type(game_state *state, int dx, int dy)
+{
+ int w = state->p.w, h = state->p.h;
+ int px = state->px, py = state->py;
+ int nx, ny, nbx, nby;
+
+ assert(dx >= -1 && dx <= +1);
+ assert(dy >= -1 && dy <= +1);
+ assert(dx || dy);
+
+ nx = px + dx;
+ ny = py + dy;
+
+ /*
+ * Disallow any move that goes off the grid.
+ */
+ if (nx < 0 || nx >= w || ny < 0 || ny >= h)
+ return -1;
+
+ /*
+ * Examine the target square of the move to see whether it's a
+ * space, a barrel, or a wall.
+ */
+
+ if (state->grid[ny*w+nx] == WALL ||
+ state->grid[ny*w+nx] == PIT ||
+ state->grid[ny*w+nx] == DEEP_PIT)
+ return -1; /* this one's easy; just disallow it */
+
+ if (IS_BARREL(state->grid[ny*w+nx])) {
+ /*
+ * This is a push move. For a start, that means it must not
+ * be diagonal.
+ */
+ if (dy && dx)
+ return -1;
+
+ /*
+ * Now find the location of the third square involved in
+ * the push, and stop if it's off the edge.
+ */
+ nbx = nx + dx;
+ nby = ny + dy;
+ if (nbx < 0 || nbx >= w || nby < 0 || nby >= h)
+ return -1;
+
+ /*
+ * That third square must be able to accept a barrel.
+ */
+ if (state->grid[nby*w+nbx] == SPACE ||
+ state->grid[nby*w+nbx] == TARGET ||
+ state->grid[nby*w+nbx] == PIT ||
+ state->grid[nby*w+nbx] == DEEP_PIT) {
+ /*
+ * The push is valid.
+ */
+ return 1;
+ } else {
+ return -1;
+ }
+ } else {
+ /*
+ * This is just an ordinary move. We've already checked the
+ * target square, so the only thing left to check is that a
+ * diagonal move has a space on one side to have notionally
+ * gone through.
+ */
+ if (dx && dy &&
+ state->grid[(py+dy)*w+px] != SPACE &&
+ state->grid[(py+dy)*w+px] != TARGET &&
+ state->grid[py*w+(px+dx)] != SPACE &&
+ state->grid[py*w+(px+dx)] != TARGET)
+ return -1;
+
+ /*
+ * Otherwise, the move is valid.
+ */
+ return 0;
+ }
+}
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{
+ int dx, dy;
+ char *move;
+
+ /*
+ * Diagonal movement is supported as it is in NetHack: it's
+ * for movement only (never pushing), and one of the two
+ * squares adjacent to both the source and destination
+ * squares must be free to move through. In other words, it
+ * is only a shorthand for two orthogonal moves and cannot
+ * change the nature of the actual puzzle game.
+ */
+ if (button == CURSOR_UP || button == (MOD_NUM_KEYPAD | '8'))
+ dx = 0, dy = -1;
+ else if (button == CURSOR_DOWN || button == (MOD_NUM_KEYPAD | '2'))
+ dx = 0, dy = +1;
+ else if (button == CURSOR_LEFT || button == (MOD_NUM_KEYPAD | '4'))
+ dx = -1, dy = 0;
+ else if (button == CURSOR_RIGHT || button == (MOD_NUM_KEYPAD | '6'))
+ dx = +1, dy = 0;
+ else if (button == (MOD_NUM_KEYPAD | '7'))
+ dx = -1, dy = -1;
+ else if (button == (MOD_NUM_KEYPAD | '9'))
+ dx = +1, dy = -1;
+ else if (button == (MOD_NUM_KEYPAD | '1'))
+ dx = -1, dy = +1;
+ else if (button == (MOD_NUM_KEYPAD | '3'))
+ dx = +1, dy = +1;
+ else
+ return NULL;
+
+ if (move_type(state, dx, dy) < 0)
+ return NULL;
+
+ move = snewn(2, char);
+ move[1] = '\0';
+ move[0] = '5' - 3*dy + dx;
+ return move;
+}
+
+static game_state *execute_move(game_state *state, char *move)
+{
+ int w = state->p.w, h = state->p.h;
+ int px = state->px, py = state->py;
+ int dx, dy, nx, ny, nbx, nby, type, m, i, freebarrels, freetargets;
+ game_state *ret;
+
+ if (*move < '1' || *move == '5' || *move > '9' || move[1])
+ return NULL; /* invalid move string */
+
+ m = *move - '0';
+ dx = (m + 2) % 3 - 1;
+ dy = 2 - (m + 2) / 3;
+ type = move_type(state, dx, dy);
+ if (type < 0)
+ return NULL;
+
+ ret = dup_game(state);
+
+ nx = px + dx;
+ ny = py + dy;
+ nbx = nx + dx;
+ nby = ny + dy;
+
+ if (type) {
+ int b;
+
+ /*
+ * Push.
+ */
+ b = ret->grid[ny*w+nx];
+ if (IS_ON_TARGET(b)) {
+ ret->grid[ny*w+nx] = TARGET;
+ b = DETARGETISE(b);
+ } else
+ ret->grid[ny*w+nx] = SPACE;
+
+ if (ret->grid[nby*w+nbx] == PIT)
+ ret->grid[nby*w+nbx] = SPACE;
+ else if (ret->grid[nby*w+nbx] == DEEP_PIT)
+ /* do nothing - the pit eats the barrel and remains there */;
+ else if (ret->grid[nby*w+nbx] == TARGET)
+ ret->grid[nby*w+nbx] = TARGETISE(b);
+ else
+ ret->grid[nby*w+nbx] = b;
+ }
+
+ ret->px = nx;
+ ret->py = ny;
+
+ /*
+ * Check for completion. This is surprisingly complicated,
+ * given the presence of pits and deep pits, and also the fact
+ * that some Sokoban levels with pits have fewer pits than
+ * barrels (due to providing spares, e.g. NetHack's). I think
+ * the completion condition in fact must be that the game
+ * cannot become any _more_ complete. That is, _either_ there
+ * are no remaining barrels not on targets, _or_ there is a
+ * good reason why any such barrels cannot be placed. The only
+ * available good reason is that there are no remaining pits,
+ * no free target squares, and no deep pits at all.
+ */
+ if (!ret->completed) {
+ freebarrels = FALSE;
+ freetargets = FALSE;
+ for (i = 0; i < w*h; i++) {
+ int v = ret->grid[i];
+
+ if (IS_BARREL(v) && !IS_ON_TARGET(v))
+ freebarrels = TRUE;
+ if (v == DEEP_PIT || v == PIT ||
+ (!IS_BARREL(v) && IS_ON_TARGET(v)))
+ freetargets = TRUE;
+ }
+
+ if (!freebarrels || !freetargets)
+ ret->completed = TRUE;
+ }
+
+ return ret;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{
+ /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+ struct { int tilesize; } ads, *ds = &ads;
+ ads.tilesize = tilesize;
+
+ *x = 2 * BORDER + 1 + params->w * TILESIZE;
+ *y = 2 * BORDER + 1 + params->h * TILESIZE;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{
+ ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{
+ float *ret = snewn(3 * NCOLOURS, float);
+ int i;
+
+ game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
+
+ ret[COL_OUTLINE * 3 + 0] = 0.0F;
+ ret[COL_OUTLINE * 3 + 1] = 0.0F;
+ ret[COL_OUTLINE * 3 + 2] = 0.0F;
+
+ ret[COL_PLAYER * 3 + 0] = 0.0F;
+ ret[COL_PLAYER * 3 + 1] = 1.0F;
+ ret[COL_PLAYER * 3 + 2] = 0.0F;
+
+ ret[COL_BARREL * 3 + 0] = 0.6F;
+ ret[COL_BARREL * 3 + 1] = 0.3F;
+ ret[COL_BARREL * 3 + 2] = 0.0F;
+
+ ret[COL_TARGET * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
+ ret[COL_TARGET * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
+ ret[COL_TARGET * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
+
+ ret[COL_PIT * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0] / 2;
+ ret[COL_PIT * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1] / 2;
+ ret[COL_PIT * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2] / 2;
+
+ ret[COL_DEEP_PIT * 3 + 0] = 0.0F;
+ ret[COL_DEEP_PIT * 3 + 1] = 0.0F;
+ ret[COL_DEEP_PIT * 3 + 2] = 0.0F;
+
+ ret[COL_TEXT * 3 + 0] = 1.0F;
+ ret[COL_TEXT * 3 + 1] = 1.0F;
+ ret[COL_TEXT * 3 + 2] = 1.0F;
+
+ ret[COL_GRID * 3 + 0] = ret[COL_LOWLIGHT * 3 + 0];
+ ret[COL_GRID * 3 + 1] = ret[COL_LOWLIGHT * 3 + 1];
+ ret[COL_GRID * 3 + 2] = ret[COL_LOWLIGHT * 3 + 2];
+
+ ret[COL_OUTLINE * 3 + 0] = 0.0F;
+ ret[COL_OUTLINE * 3 + 1] = 0.0F;
+ ret[COL_OUTLINE * 3 + 2] = 0.0F;
+
+ for (i = 0; i < 3; i++) {
+ ret[COL_WALL * 3 + i] = (3 * ret[COL_BACKGROUND * 3 + i] +
+ 1 * ret[COL_HIGHLIGHT * 3 + i]) / 4;
+ }
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{
+ int w = state->p.w, h = state->p.h;
+ struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
+
+ ds->tilesize = 0;
+ ds->p = state->p; /* structure copy */
+ ds->grid = snewn(w*h, unsigned short);
+ for (i = 0; i < w*h; i++)
+ ds->grid[i] = INVALID;
+ ds->started = FALSE;
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{
+ sfree(ds->grid);
+ sfree(ds);
+}
+
+static void draw_tile(drawing *dr, game_drawstate *ds, int x, int y, int v)
+{
+ int tx = COORD(x), ty = COORD(y);
+ int bg = (v & 0x100 ? COL_HIGHLIGHT : COL_BACKGROUND);
+
+ v &= 0xFF;
+
+ clip(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1);
+ draw_rect(dr, tx+1, ty+1, TILESIZE-1, TILESIZE-1, bg);
+
+ if (v == WALL) {
+ int coords[6];
+
+ coords[0] = tx + TILESIZE;
+ coords[1] = ty + TILESIZE;
+ coords[2] = tx + TILESIZE;
+ coords[3] = ty + 1;
+ coords[4] = tx + 1;
+ coords[5] = ty + TILESIZE;
+ draw_polygon(dr, coords, 3, COL_LOWLIGHT, COL_LOWLIGHT);
+
+ coords[0] = tx + 1;
+ coords[1] = ty + 1;
+ draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
+
+ draw_rect(dr, tx + 1 + HIGHLIGHT_WIDTH, ty + 1 + HIGHLIGHT_WIDTH,
+ TILESIZE - 2*HIGHLIGHT_WIDTH,
+ TILESIZE - 2*HIGHLIGHT_WIDTH, COL_WALL);
+ } else if (v == PIT) {
+ draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
+ TILESIZE*3/7, COL_PIT, COL_OUTLINE);
+ } else if (v == DEEP_PIT) {
+ draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
+ TILESIZE*3/7, COL_DEEP_PIT, COL_OUTLINE);
+ } else {
+ if (IS_ON_TARGET(v)) {
+ draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
+ TILESIZE*3/7, COL_TARGET, COL_OUTLINE);
+ }
+ if (IS_PLAYER(v)) {
+ draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
+ TILESIZE/3, COL_PLAYER, COL_OUTLINE);
+ } else if (IS_BARREL(v)) {
+ char str[2];
+
+ draw_circle(dr, tx + TILESIZE/2, ty + TILESIZE/2,
+ TILESIZE/3, COL_BARREL, COL_OUTLINE);
+ str[1] = '\0';
+ str[0] = BARREL_LABEL(v);
+ if (str[0]) {
+ draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2,
+ FONT_VARIABLE, TILESIZE/2,
+ ALIGN_VCENTRE | ALIGN_HCENTRE, COL_TEXT, str);
+ }
+ }
+ }
+
+ unclip(dr);
+ draw_update(dr, tx, ty, TILESIZE, TILESIZE);
+}
+
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
+{
+ int w = state->p.w, h = state->p.h /*, wh = w*h */;
+ int x, y;
+ int flashtype;
+
+ if (flashtime &&
+ !((int)(flashtime * 3 / FLASH_LENGTH) % 2))
+ flashtype = 0x100;
+ else
+ flashtype = 0;
+
+ /*
+ * Initialise a fresh drawstate.
+ */
+ if (!ds->started) {
+ int wid, ht;
+
+ /*
+ * Blank out the window initially.
+ */
+ game_compute_size(&ds->p, TILESIZE, &wid, &ht);
+ draw_rect(dr, 0, 0, wid, ht, COL_BACKGROUND);
+ draw_update(dr, 0, 0, wid, ht);
+
+ /*
+ * Draw the grid lines.
+ */
+ for (y = 0; y <= h; y++)
+ draw_line(dr, COORD(0), COORD(y), COORD(w), COORD(y),
+ COL_LOWLIGHT);
+ for (x = 0; x <= w; x++)
+ draw_line(dr, COORD(x), COORD(0), COORD(x), COORD(h),
+ COL_LOWLIGHT);
+
+ ds->started = TRUE;
+ }
+
+ /*
+ * Draw the grid contents.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {
+ int v = state->grid[y*w+x];
+ if (y == state->py && x == state->px) {
+ if (v == TARGET)
+ v = PLAYERTARGET;
+ else {
+ assert(v == SPACE);
+ v = PLAYER;
+ }
+ }
+
+ v |= flashtype;
+
+ if (ds->grid[y*w+x] != v) {
+ draw_tile(dr, ds, x, y, v);
+ ds->grid[y*w+x] = v;
+ }
+ }
+
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{
+ return 0.0F;
+}
+
+static float game_flash_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{
+ if (!oldstate->completed && newstate->completed)
+ return FLASH_LENGTH;
+ else
+ return 0.0F;
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{
+ return TRUE;
+}
+
+static void game_print_size(game_params *params, float *x, float *y)
+{
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{
+}
+
+#ifdef COMBINED
+#define thegame sokoban
+#endif
+
+const struct game thegame = {
+ "Sokoban", NULL,
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ FALSE, solve_game,
+ FALSE, game_text_format,
+ new_ui,
+ free_ui,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
+ PREFERRED_TILESIZE, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ FALSE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ 0, /* flags */
+};
~mdw / sgt / puzzles / commitdiff