summaryrefslogtreecommitdiffstats
path: root/apps/plugins
diff options
context:
space:
mode:
authorFranklin Wei <git@fwei.tk>2019-05-15 18:16:27 -0400
committerFranklin Wei <git@fwei.tk>2019-05-15 18:16:27 -0400
commitf940276fd9bc38ae34d4119fd1d983171a627400 (patch)
tree117a191e61c070548b4c55b35f6d1159f98f03f9 /apps/plugins
parent4ed57276542124a22c26ebb1d307996fc3a7556c (diff)
downloadrockbox-f940276fd9bc38ae34d4119fd1d983171a627400.tar.gz
rockbox-f940276fd9bc38ae34d4119fd1d983171a627400.tar.bz2
rockbox-f940276fd9bc38ae34d4119fd1d983171a627400.zip
puzzles: resync with upstream
This brings the puzzles source to upstream commit e2135d5. (I've made my own changes on top of that.) This brings in a couple bugfixes and a new solver for Dominosa. Change-Id: I11d46b43171787832330a5e2e0d2f353f36f727d
Diffstat (limited to 'apps/plugins')
-rw-r--r--apps/plugins/puzzles/SOURCES1
-rwxr-xr-xapps/plugins/puzzles/src/benchmark.pl2
-rw-r--r--apps/plugins/puzzles/src/dominosa.R5
-rw-r--r--apps/plugins/puzzles/src/dominosa.c2688
-rw-r--r--apps/plugins/puzzles/src/emccpre.js39
-rw-r--r--apps/plugins/puzzles/src/findloop.c31
-rw-r--r--apps/plugins/puzzles/src/galaxies.c56
-rw-r--r--apps/plugins/puzzles/src/midend.c7
-rw-r--r--apps/plugins/puzzles/src/pegs.c6
-rw-r--r--apps/plugins/puzzles/src/puzzles.h26
-rw-r--r--apps/plugins/puzzles/src/sort.c160
11 files changed, 2525 insertions, 496 deletions
diff --git a/apps/plugins/puzzles/SOURCES b/apps/plugins/puzzles/SOURCES
index c9611548f9..5301ceef3d 100644
--- a/apps/plugins/puzzles/SOURCES
+++ b/apps/plugins/puzzles/SOURCES
@@ -19,6 +19,7 @@ src/misc.c
src/penrose.c
src/printing.c
src/random.c
+src/sort.c
src/tdq.c
src/tree234.c
src/version.c
diff --git a/apps/plugins/puzzles/src/benchmark.pl b/apps/plugins/puzzles/src/benchmark.pl
index 98763859e8..7ac48abc25 100755
--- a/apps/plugins/puzzles/src/benchmark.pl
+++ b/apps/plugins/puzzles/src/benchmark.pl
@@ -9,7 +9,7 @@ my @presets = ();
my %presets = ();
my $maxval = 0;
-while (<>) {
+while (<<>>) {
chomp;
if (/^(.*)(#.*): ([\d\.]+)$/) {
push @presets, $1 unless defined $presets{$1};
diff --git a/apps/plugins/puzzles/src/dominosa.R b/apps/plugins/puzzles/src/dominosa.R
index 99218366e6..b85e7dc1e0 100644
--- a/apps/plugins/puzzles/src/dominosa.R
+++ b/apps/plugins/puzzles/src/dominosa.R
@@ -1,6 +1,6 @@
# -*- makefile -*-
-DOMINOSA_EXTRA = laydomino
+DOMINOSA_EXTRA = laydomino dsf sort findloop
dominosa : [X] GTK COMMON dominosa DOMINOSA_EXTRA dominosa-icon|no-icon
@@ -8,6 +8,9 @@ dominosa : [G] WINDOWS COMMON dominosa DOMINOSA_EXTRA dominosa.res|noicon.res
ALL += dominosa[COMBINED] DOMINOSA_EXTRA
+dominosasolver : [U] dominosa[STANDALONE_SOLVER] DOMINOSA_EXTRA STANDALONE
+dominosasolver : [C] dominosa[STANDALONE_SOLVER] DOMINOSA_EXTRA STANDALONE
+
!begin am gtk
GAMES += dominosa
!end
diff --git a/apps/plugins/puzzles/src/dominosa.c b/apps/plugins/puzzles/src/dominosa.c
index 5f035e9250..67a1d69c91 100644
--- a/apps/plugins/puzzles/src/dominosa.c
+++ b/apps/plugins/puzzles/src/dominosa.c
@@ -5,65 +5,41 @@
*/
/*
- * TODO:
- *
- * - improve solver so as to use more interesting forms of
- * deduction
+ * Further possible deduction types in the solver:
*
- * * rule out a domino placement if it would divide an unfilled
- * region such that at least one resulting region had an odd
- * area
- * + Tarjan's bridge-finding algorithm would be a way to find
- * domino placements that split a connected region in two:
- * form the graph whose vertices are unpaired squares and
- * whose edges are potential (not placed but also not ruled
- * out) dominoes covering two of them, and any bridge in that
- * graph is a candidate.
- * + Then, finding any old spanning forest of the unfilled
- * squares should be sufficient to determine the area parity
- * of the region that any such placement would cut off.
+ * * possibly an advanced form of deduce_parity via 2-connectedness.
+ * We currently deal with areas of the graph with exactly one way
+ * in and out; but if you have an area with exactly _two_ routes in
+ * and out of it, then you can at least decide on the _relative_
+ * parity of the two (either 'these two edges both bisect dominoes
+ * or neither do', or 'exactly one of these edges bisects a
+ * domino'). And occasionally that can be enough to let you rule
+ * out one of the two remaining choices.
+ * + For example, if both those edges bisect a domino, then those
+ * two dominoes would also be both the same.
+ * + Or perhaps between them they rule out all possibilities for
+ * some other square.
+ * + Or perhaps they themselves would be duplicates!
+ * + Or perhaps, on purely geometric grounds, they would box in a
+ * square to the point where it ended up having to be an
+ * isolated singleton.
+ * + The tricky part of this is how you do the graph theory.
+ * Perhaps a modified form of Tarjan's bridge-finding algorithm
+ * would work, but I haven't thought through the details.
*
- * * set analysis
- * + look at all unclaimed squares containing a given number
- * + for each one, find the set of possible numbers that it
- * can connect to (i.e. each neighbouring tile such that
- * the placement between it and that neighbour has not yet
- * been ruled out)
- * + now proceed similarly to Solo set analysis: try to find
- * a subset of the squares such that the union of their
- * possible numbers is the same size as the subset. If so,
- * rule out those possible numbers for all other squares.
- * * important wrinkle: the double dominoes complicate
- * matters. Connecting a number to itself uses up _two_
- * of the unclaimed squares containing a number. Thus,
- * when finding the initial subset we must never
- * include two adjacent squares; and also, when ruling
- * things out after finding the subset, we must be
- * careful that we don't rule out precisely the domino
- * placement that was _included_ in our set!
- *
- * * playing off the two ends of one potential domino, by
- * considering the alternatives to that domino that each end
- * might otherwise be part of.
- * + if not playing this domino would require each end to be
- * part of an identical domino, play it. (e.g. the middle of
- * 5-4-4-5)
- * + if not playing this domino would guarantee that the two
- * ends between them used up all of some other square's
- * choices, play it. (e.g. the middle of 2-3-3-1 if another 3
- * cell can only link to a 2 or a 1)
- *
- * * identify 'forcing chains', in the sense of any path of cells
- * each of which has only two possible dominoes to be part of,
- * and each of those rules out one of the choices for the next
- * cell. Such a chain has the property that either all the odd
- * dominoes are placed, or all the even ones are placed; so if
- * either set of those introduces a conflict (e.g. a dupe within
- * the chain, or using up all of some other square's choices),
- * then the whole set can be ruled out, and the other set played
- * immediately.
- * + this is of course a generalisation of the previous idea,
- * which is simply a forcing chain of length 3.
+ * * possibly an advanced version of set analysis which doesn't have
+ * to start from squares all having the same number? For example,
+ * if you have three mutually non-adjacent squares labelled 1,2,3
+ * such that the numbers adjacent to each are precisely the other
+ * two, then set analysis can work just fine in principle, and
+ * tells you that those three squares must overlap the three
+ * dominoes 1-2, 2-3 and 1-3 in some order, so you can rule out any
+ * placements of those elsewhere.
+ * + the difficulty with this is how you avoid it going painfully
+ * exponential-time. You can't iterate over all the subsets, so
+ * you'd need some kind of more sophisticated directed search.
+ * + and the adjacency allowance has to be similarly accounted
+ * for, which could get tricky to keep track of.
*/
#include <stdio.h>
@@ -84,6 +60,26 @@
#define FLASH_TIME 0.13F
+/*
+ * Difficulty levels. I do some macro ickery here to ensure that my
+ * enum and the various forms of my name list always match up.
+ */
+#define DIFFLIST(X) \
+ X(TRIVIAL,Trivial,t) \
+ X(BASIC,Basic,b) \
+ X(HARD,Hard,h) \
+ X(EXTREME,Extreme,e) \
+ X(AMBIGUOUS,Ambiguous,a) \
+ /* end of list */
+#define ENUM(upper,title,lower) DIFF_ ## upper,
+#define TITLE(upper,title,lower) #title,
+#define ENCODE(upper,title,lower) #lower
+#define CONFIG(upper,title,lower) ":" #title
+enum { DIFFLIST(ENUM) DIFFCOUNT };
+static char const *const dominosa_diffnames[] = { DIFFLIST(TITLE) };
+static char const dominosa_diffchars[] = DIFFLIST(ENCODE);
+#define DIFFCONFIG DIFFLIST(CONFIG)
+
enum {
COL_BACKGROUND,
COL_TEXT,
@@ -98,7 +94,7 @@ enum {
struct game_params {
int n;
- bool unique;
+ int diff;
};
struct game_numbers {
@@ -125,35 +121,41 @@ static game_params *default_params(void)
game_params *ret = snew(game_params);
ret->n = 6;
- ret->unique = true;
+ ret->diff = DIFF_BASIC;
return ret;
}
-static bool game_fetch_preset(int i, char **name, game_params **params)
+static const struct game_params dominosa_presets[] = {
+ { 3, DIFF_TRIVIAL },
+ { 4, DIFF_TRIVIAL },
+ { 5, DIFF_TRIVIAL },
+ { 6, DIFF_TRIVIAL },
+ { 4, DIFF_BASIC },
+ { 5, DIFF_BASIC },
+ { 6, DIFF_BASIC },
+ { 7, DIFF_BASIC },
+ { 8, DIFF_BASIC },
+ { 9, DIFF_BASIC },
+ { 6, DIFF_HARD },
+ { 6, DIFF_EXTREME },
+};
+
+static bool game_fetch_preset(int i, char **name, game_params **params_out)
{
- game_params *ret;
- int n;
+ game_params *params;
char buf[80];
- switch (i) {
- case 0: n = 3; break;
- case 1: n = 4; break;
- case 2: n = 5; break;
- case 3: n = 6; break;
- case 4: n = 7; break;
- case 5: n = 8; break;
- case 6: n = 9; break;
- default: return false;
- }
+ if (i < 0 || i >= lenof(dominosa_presets))
+ return false;
- sprintf(buf, "Up to double-%d", n);
- *name = dupstr(buf);
+ params = snew(game_params);
+ *params = dominosa_presets[i]; /* structure copy */
- *params = ret = snew(game_params);
- ret->n = n;
- ret->unique = true;
+ sprintf(buf, "Order %d, %s", params->n, dominosa_diffnames[params->diff]);
+ *name = dupstr(buf);
+ *params_out = params;
return true;
}
@@ -171,18 +173,36 @@ static game_params *dup_params(const game_params *params)
static void decode_params(game_params *params, char const *string)
{
- params->n = atoi(string);
- while (*string && isdigit((unsigned char)*string)) string++;
- if (*string == 'a')
- params->unique = false;
+ const char *p = string;
+
+ params->n = atoi(p);
+ while (*p && isdigit((unsigned char)*p)) p++;
+
+ while (*p) {
+ char c = *p++;
+ if (c == 'a') {
+ /* Legacy encoding from before the difficulty system */
+ params->diff = DIFF_AMBIGUOUS;
+ } else if (c == 'd') {
+ int i;
+ params->diff = DIFFCOUNT+1; /* ...which is invalid */
+ if (*p) {
+ for (i = 0; i < DIFFCOUNT; i++) {
+ if (*p == dominosa_diffchars[i])
+ params->diff = i;
+ }
+ p++;
+ }
+ }
+ }
}
static char *encode_params(const game_params *params, bool full)
{
char buf[80];
- sprintf(buf, "%d", params->n);
- if (full && !params->unique)
- strcat(buf, "a");
+ int len = sprintf(buf, "%d", params->n);
+ if (full)
+ len += sprintf(buf + len, "d%c", dominosa_diffchars[params->diff]);
return dupstr(buf);
}
@@ -198,9 +218,10 @@ static config_item *game_configure(const game_params *params)
sprintf(buf, "%d", params->n);
ret[0].u.string.sval = dupstr(buf);
- ret[1].name = "Ensure unique solution";
- ret[1].type = C_BOOLEAN;
- ret[1].u.boolean.bval = params->unique;
+ ret[1].name = "Difficulty";
+ ret[1].type = C_CHOICES;
+ ret[1].u.choices.choicenames = DIFFCONFIG;
+ ret[1].u.choices.selected = params->diff;
ret[2].name = NULL;
ret[2].type = C_END;
@@ -213,7 +234,7 @@ static game_params *custom_params(const config_item *cfg)
game_params *ret = snew(game_params);
ret->n = atoi(cfg[0].u.string.sval);
- ret->unique = cfg[1].u.boolean.bval;
+ ret->diff = cfg[1].u.choices.selected;
return ret;
}
@@ -222,6 +243,8 @@ static const char *validate_params(const game_params *params, bool full)
{
if (params->n < 1)
return "Maximum face number must be at least one";
+ if (params->diff >= DIFFCOUNT)
+ return "Unknown difficulty rating";
return NULL;
}
@@ -229,361 +252,1993 @@ static const char *validate_params(const game_params *params, bool full)
* Solver.
*/
-static int find_overlaps(int w, int h, int placement, int *set)
+#ifdef STANDALONE_SOLVER
+#define SOLVER_DIAGNOSTICS
+bool solver_diagnostics = false;
+#elif defined SOLVER_DIAGNOSTICS
+const bool solver_diagnostics = true;
+#endif
+
+struct solver_domino;
+struct solver_placement;
+
+/*
+ * Information about a particular domino.
+ */
+struct solver_domino {
+ /* The numbers on the domino, and its index in the dominoes array. */
+ int lo, hi, index;
+
+ /* List of placements not yet ruled out for this domino. */
+ int nplacements;
+ struct solver_placement **placements;
+
+#ifdef SOLVER_DIAGNOSTICS
+ /* A textual name we can easily reuse in solver diagnostics. */
+ char *name;
+#endif
+};
+
+/*
+ * Information about a particular 'placement' (i.e. specific location
+ * that a domino might go in).
+ */
+struct solver_placement {
+ /* The index of this placement in sc->placements. */
+ int index;
+
+ /* The two squares that make up this placement. */
+ struct solver_square *squares[2];
+
+ /* The domino that has to go in this position, if any. */
+ struct solver_domino *domino;
+
+ /* The index of this placement in each square's placements array,
+ * and in that of the domino. */
+ int spi[2], dpi;
+
+ /* Whether this is still considered a possible placement. */
+ bool active;
+
+ /* Other domino placements that overlap with this one. (Maximum 6:
+ * three overlapping each square of the placement.) */
+ int noverlaps;
+ struct solver_placement *overlaps[6];
+
+#ifdef SOLVER_DIAGNOSTICS
+ /* A textual name we can easily reuse in solver diagnostics. */
+ char *name;
+#endif
+};
+
+/*
+ * Information about a particular solver square.
+ */
+struct solver_square {
+ /* The coordinates of the square, and its index in a normal grid array. */
+ int x, y, index;
+
+ /* List of domino placements not yet ruled out for this square. */
+ int nplacements;
+ struct solver_placement *placements[4];
+
+ /* The number in the square. */
+ int number;
+
+#ifdef SOLVER_DIAGNOSTICS
+ /* A textual name we can easily reuse in solver diagnostics. */
+ char *name;
+#endif
+};
+
+struct solver_scratch {
+ int n, dc, pc, w, h, wh;
+ int max_diff_used;
+ struct solver_domino *dominoes;
+ struct solver_placement *placements;
+ struct solver_square *squares;
+ struct solver_placement **domino_placement_lists;
+ struct solver_square **squares_by_number;
+ struct findloopstate *fls;
+ bool squares_by_number_initialised;
+ int *wh_scratch, *pc_scratch, *pc_scratch2, *dc_scratch;
+};
+
+static struct solver_scratch *solver_make_scratch(int n)
{
- int x, y, n;
+ int dc = DCOUNT(n), w = n+2, h = n+1, wh = w*h;
+ int pc = (w-1)*h + w*(h-1);
+ struct solver_scratch *sc = snew(struct solver_scratch);
+ int hi, lo, di, x, y, pi, si;
+
+ sc->n = n;
+ sc->dc = dc;
+ sc->pc = pc;
+ sc->w = w;
+ sc->h = h;
+ sc->wh = wh;
+
+ sc->dominoes = snewn(dc, struct solver_domino);
+ sc->placements = snewn(pc, struct solver_placement);
+ sc->squares = snewn(wh, struct solver_square);
+ sc->domino_placement_lists = snewn(pc, struct solver_placement *);
+ sc->fls = findloop_new_state(wh);
+
+ for (di = hi = 0; hi <= n; hi++) {
+ for (lo = 0; lo <= hi; lo++) {
+ assert(di == DINDEX(hi, lo));
+ sc->dominoes[di].hi = hi;
+ sc->dominoes[di].lo = lo;
+ sc->dominoes[di].index = di;
- n = 0; /* number of returned placements */
+#ifdef SOLVER_DIAGNOSTICS
+ {
+ char buf[128];
+ sprintf(buf, "%d-%d", hi, lo);
+ sc->dominoes[di].name = dupstr(buf);
+ }
+#endif
- x = placement / 2;
- y = x / w;
- x %= w;
+ di++;
+ }
+ }
- if (placement & 1) {
- /*
- * Horizontal domino, indexed by its left end.
- */
- if (x > 0)
- set[n++] = placement-2; /* horizontal domino to the left */
- if (y > 0)
- set[n++] = placement-2*w-1;/* vertical domino above left side */
- if (y+1 < h)
- set[n++] = placement-1; /* vertical domino below left side */
- if (x+2 < w)
- set[n++] = placement+2; /* horizontal domino to the right */
- if (y > 0)
- set[n++] = placement-2*w+2-1;/* vertical domino above right side */
- if (y+1 < h)
- set[n++] = placement+2-1; /* vertical domino below right side */
- } else {
- /*
- * Vertical domino, indexed by its top end.
- */
- if (y > 0)
- set[n++] = placement-2*w; /* vertical domino above */
- if (x > 0)
- set[n++] = placement-2+1; /* horizontal domino left of top */
- if (x+1 < w)
- set[n++] = placement+1; /* horizontal domino right of top */
- if (y+2 < h)
- set[n++] = placement+2*w; /* vertical domino below */
- if (x > 0)
- set[n++] = placement-2+2*w+1;/* horizontal domino left of bottom */
- if (x+1 < w)
- set[n++] = placement+2*w+1;/* horizontal domino right of bottom */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ struct solver_square *sq = &sc->squares[y*w+x];
+ sq->x = x;
+ sq->y = y;
+ sq->index = y * w + x;
+ sq->nplacements = 0;
+
+#ifdef SOLVER_DIAGNOSTICS
+ {
+ char buf[128];
+ sprintf(buf, "(%d,%d)", x, y);
+ sq->name = dupstr(buf);
+ }
+#endif
+ }
}
- return n;
+ pi = 0;
+ for (y = 0; y < h-1; y++) {
+ for (x = 0; x < w; x++) {
+ assert(pi < pc);
+ sc->placements[pi].squares[0] = &sc->squares[y*w+x];
+ sc->placements[pi].squares[1] = &sc->squares[(y+1)*w+x];
+#ifdef SOLVER_DIAGNOSTICS
+ {
+ char buf[128];
+ sprintf(buf, "(%d,%d-%d)", x, y, y+1);
+ sc->placements[pi].name = dupstr(buf);
+ }
+#endif
+ pi++;
+ }
+ }
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w-1; x++) {
+ assert(pi < pc);
+ sc->placements[pi].squares[0] = &sc->squares[y*w+x];
+ sc->placements[pi].squares[1] = &sc->squares[y*w+(x+1)];
+#ifdef SOLVER_DIAGNOSTICS
+ {
+ char buf[128];
+ sprintf(buf, "(%d-%d,%d)", x, x+1, y);
+ sc->placements[pi].name = dupstr(buf);
+ }
+#endif
+ pi++;
+ }
+ }
+ assert(pi == pc);
+
+ /* Set up the full placement lists for all squares, temporarily,
+ * so as to use them to calculate the overlap lists */
+ for (si = 0; si < wh; si++)
+ sc->squares[si].nplacements = 0;
+ for (pi = 0; pi < pc; pi++) {
+ struct solver_placement *p = &sc->placements[pi];
+ for (si = 0; si < 2; si++) {
+ struct solver_square *sq = p->squares[si];
+ p->spi[si] = sq->nplacements;
+ sq->placements[sq->nplacements++] = p;
+ }
+ }
+
+ /* Actually calculate the overlap lists */
+ for (pi = 0; pi < pc; pi++) {
+ struct solver_placement *p = &sc->placements[pi];
+ p->noverlaps = 0;
+ for (si = 0; si < 2; si++) {
+ struct solver_square *sq = p->squares[si];
+ int j;
+ for (j = 0; j < sq->nplacements; j++) {
+ struct solver_placement *q = sq->placements[j];
+ if (q != p)
+ p->overlaps[p->noverlaps++] = q;
+ }
+ }
+ }
+
+ /* Fill in the index field of the placements */
+ for (pi = 0; pi < pc; pi++)
+ sc->placements[pi].index = pi;
+
+ /* Lazily initialised by particular solver techniques that might
+ * never be needed */
+ sc->squares_by_number = NULL;
+ sc->squares_by_number_initialised = false;
+ sc->wh_scratch = NULL;
+ sc->pc_scratch = sc->pc_scratch2 = NULL;
+ sc->dc_scratch = NULL;
+
+ return sc;
+}
+
+static void solver_free_scratch(struct solver_scratch *sc)
+{
+#ifdef SOLVER_DIAGNOSTICS
+ {
+ int i;
+ for (i = 0; i < sc->dc; i++)
+ sfree(sc->dominoes[i].name);
+ for (i = 0; i < sc->pc; i++)
+ sfree(sc->placements[i].name);
+ for (i = 0; i < sc->wh; i++)
+ sfree(sc->squares[i].name);
+ }
+#endif
+ sfree(sc->dominoes);
+ sfree(sc->placements);
+ sfree(sc->squares);
+ sfree(sc->domino_placement_lists);
+ sfree(sc->squares_by_number);
+ findloop_free_state(sc->fls);
+ sfree(sc->wh_scratch);
+ sfree(sc->pc_scratch);
+ sfree(sc->pc_scratch2);
+ sfree(sc->dc_scratch);
+ sfree(sc);
+}
+
+static void solver_setup_grid(struct solver_scratch *sc, const int *numbers)
+{
+ int i, j;
+
+ for (i = 0; i < sc->wh; i++) {
+ sc->squares[i].nplacements = 0;
+ sc->squares[i].number = numbers[sc->squares[i].index];
+ }
+
+ for (i = 0; i < sc->pc; i++) {
+ struct solver_placement *p = &sc->placements[i];
+ int di = DINDEX(p->squares[0]->number, p->squares[1]->number);
+ p->domino = &sc->dominoes[di];
+ }
+
+ for (i = 0; i < sc->dc; i++)
+ sc->dominoes[i].nplacements = 0;
+ for (i = 0; i < sc->pc; i++)
+ sc->placements[i].domino->nplacements++;
+ for (i = j = 0; i < sc->dc; i++) {
+ sc->dominoes[i].placements = sc->domino_placement_lists + j;
+ j += sc->dominoes[i].nplacements;
+ sc->dominoes[i].nplacements = 0;
+ }
+ for (i = 0; i < sc->pc; i++) {
+ struct solver_placement *p = &sc->placements[i];
+ p->dpi = p->domino->nplacements;
+ p->domino->placements[p->domino->nplacements++] = p;
+ p->active = true;
+ }
+
+ for (i = 0; i < sc->wh; i++)
+ sc->squares[i].nplacements = 0;
+ for (i = 0; i < sc->pc; i++) {
+ struct solver_placement *p = &sc->placements[i];
+ for (j = 0; j < 2; j++) {
+ struct solver_square *sq = p->squares[j];
+ p->spi[j] = sq->nplacements;
+ sq->placements[sq->nplacements++] = p;
+ }
+ }
+
+ sc->max_diff_used = DIFF_TRIVIAL;
+ sc->squares_by_number_initialised = false;
+}
+
+/* Given two placements p,q that overlap, returns si such that
+ * p->squares[si] is the square also in q */
+static int common_square_index(struct solver_placement *p,
+ struct solver_placement *q)
+{
+ return (p->squares[0] == q->squares[0] ||
+ p->squares[0] == q->squares[1]) ? 0 : 1;
+}
+
+/* Sort function used to set up squares_by_number */
+static int squares_by_number_cmpfn(const void *av, const void *bv)
+{
+ struct solver_square *a = *(struct solver_square *const *)av;
+ struct solver_square *b = *(struct solver_square *const *)bv;
+ return (a->number < b->number ? -1 : a->number > b->number ? +1 :
+ a->index < b->index ? -1 : a->index > b->index ? +1 : 0);
+}
+
+static void rule_out_placement(
+ struct solver_scratch *sc, struct solver_placement *p)
+{
+ struct solver_domino *d = p->domino;
+ int i, j, si;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics)
+ printf(" ruling out placement %s for domino %s\n", p->name, d->name);
+#endif
+
+ p->active = false;
+
+ i = p->dpi;
+ assert(d->placements[i] == p);
+ if (--d->nplacements != i) {
+ d->placements[i] = d->placements[d->nplacements];
+ d->placements[i]->dpi = i;
+ }
+
+ for (si = 0; si < 2; si++) {
+ struct solver_square *sq = p->squares[si];
+ i = p->spi[si];
+ assert(sq->placements[i] == p);
+ if (--sq->nplacements != i) {
+ sq->placements[i] = sq->placements[sq->nplacements];
+ j = (sq->placements[i]->squares[0] == sq ? 0 : 1);
+ sq->placements[i]->spi[j] = i;
+ }
+ }
}
/*
- * Returns 0, 1 or 2 for number of solutions. 2 means `any number
- * more than one', or more accurately `we were unable to prove
- * there was only one'.
- *
- * Outputs in a `placements' array, indexed the same way as the one
- * within this function (see below); entries in there are <0 for a
- * placement ruled out, 0 for an uncertain placement, and 1 for a
- * definite one.
+ * If a domino has only one placement remaining, rule out all other
+ * placements that overlap it.
*/
-static int solver(int w, int h, int n, int *grid, int *output)
+static bool deduce_domino_single_placement(struct solver_scratch *sc, int di)
{
- int wh = w*h, dc = DCOUNT(n);
- int *placements, *heads;
- int i, j, x, y, ret;
+ struct solver_domino *d = &sc->dominoes[di];
+ struct solver_placement *p, *q;
+ int oi;
+ bool done_something = false;
+
+ if (d->nplacements != 1)
+ return false;
+ p = d->placements[0];
+
+ for (oi = 0; oi < p->noverlaps; oi++) {
+ q = p->overlaps[oi];
+ if (q->active) {
+ if (!done_something) {
+ done_something = true;
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics)
+ printf("domino %s has unique placement %s\n",
+ d->name, p->name);
+#endif
+ }
+ rule_out_placement(sc, q);
+ }
+ }
+
+ return done_something;
+}
+
+/*
+ * If a square has only one placement remaining, rule out all other
+ * placements of its domino.
+ */
+static bool deduce_square_single_placement(struct solver_scratch *sc, int si)
+{
+ struct solver_square *sq = &sc->squares[si];
+ struct solver_placement *p;
+ struct solver_domino *d;
+
+ if (sq->nplacements != 1)
+ return false;
+ p = sq->placements[0];
+ d = p->domino;
+
+ if (d->nplacements <= 1)
+ return false; /* we already knew everything this would tell us */
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics)
+ printf("square %s has unique placement %s (domino %s)\n",
+ sq->name, p->name, p->domino->name);
+#endif
+
+ while (d->nplacements > 1)
+ rule_out_placement(
+ sc, d->placements[0] == p ? d->placements[1] : d->placements[0]);
+
+ return true;
+}
+
+/*
+ * If all placements for a square involve the same domino, rule out
+ * all other placements of that domino.
+ */
+static bool deduce_square_single_domino(struct solver_scratch *sc, int si)
+{
+ struct solver_square *sq = &sc->squares[si];
+ struct solver_domino *d;
+ int i;
/*
- * This array has one entry for every possible domino
- * placement. Vertical placements are indexed by their top
- * half, at (y*w+x)*2; horizontal placements are indexed by
- * their left half at (y*w+x)*2+1.
- *
- * This array is used to link domino placements together into
- * linked lists, so that we can track all the possible
- * placements of each different domino. It's also used as a
- * quick means of looking up an individual placement to see
- * whether we still think it's possible. Actual values stored
- * in this array are -2 (placement not possible at all), -1
- * (end of list), or the array index of the next item.
- *
- * Oh, and -3 for `not even valid', used for array indices
- * which don't even represent a plausible placement.
+ * We only bother with this if the square has at least _two_
+ * placements. If it only has one, then a simpler deduction will
+ * have handled it already, or will do so the next time round the
+ * main solver loop - and we should let the simpler deduction do
+ * it, because that will give a less overblown diagnostic.
*/
- placements = snewn(2*wh, int);
- for (i = 0; i < 2*wh; i++)
- placements[i] = -3; /* not even valid */
+ if (sq->nplacements < 2)
+ return false;
+
+ d = sq->placements[0]->domino;
+ for (i = 1; i < sq->nplacements; i++)
+ if (sq->placements[i]->domino != d)
+ return false; /* not all the same domino */
+
+ if (d->nplacements <= sq->nplacements)
+ return false; /* no other placements of d to rule out */
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics)
+ printf("square %s can only contain domino %s\n", sq->name, d->name);
+#endif
+
+ for (i = d->nplacements; i-- > 0 ;) {
+ struct solver_placement *p = d->placements[i];
+ if (p->squares[0] != sq && p->squares[1] != sq)
+ rule_out_placement(sc, p);
+ }
+
+ return true;
+}
+
+/*
+ * If any placement is overlapped by _all_ possible placements of a
+ * given domino, rule that placement out.
+ */
+static bool deduce_domino_must_overlap(struct solver_scratch *sc, int di)
+{
+ struct solver_domino *d = &sc->dominoes[di];
+ struct solver_placement *intersection[6], *p;
+ int nintersection = 0;
+ int i, j, k;
/*
- * This array has one entry for every domino, and it is an
- * index into `placements' denoting the head of the placement
- * list for that domino.
+ * As in deduce_square_single_domino, we only bother with this
+ * deduction if the domino has at least two placements.
*/
- heads = snewn(dc, int);
- for (i = 0; i < dc; i++)
- heads[i] = -1;
+ if (d->nplacements < 2)
+ return false;
+
+ /* Initialise our set of overlapped placements with all the active
+ * ones overlapped by placements[0]. */
+ p = d->placements[0];
+ for (i = 0; i < p->noverlaps; i++)
+ if (p->overlaps[i]->active)
+ intersection[nintersection++] = p->overlaps[i];
+
+ /* Now loop over the other placements of d, winnowing that set. */
+ for (j = 1; j < d->nplacements; j++) {
+ int old_n;
+
+ p = d->placements[j];
+
+ old_n = nintersection;
+ nintersection = 0;
+
+ for (k = 0; k < old_n; k++) {
+ for (i = 0; i < p->noverlaps; i++)
+ if (p->overlaps[i] == intersection[k])
+ goto found;
+ /* If intersection[k] isn't in p->overlaps, exclude it
+ * from our set of placements overlapped by everything */
+ continue;
+ found:
+ intersection[nintersection++] = intersection[k];
+ }
+ }
+
+ if (nintersection == 0)
+ return false; /* no new exclusions */
+
+ for (i = 0; i < nintersection; i++) {
+ p = intersection[i];
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ printf("placement %s of domino %s overlaps all placements "
+ "of domino %s:", p->name, p->domino->name, d->name);
+ for (j = 0; j < d->nplacements; j++)
+ printf(" %s", d->placements[j]->name);
+ printf("\n");
+ }
+#endif
+ rule_out_placement(sc, p);
+ }
+
+ return true;
+}
+
+/*
+ * If a placement of domino D overlaps the only remaining placement
+ * for some square S which is not also for domino D, then placing D
+ * here would require another copy of it in S, so we can rule it out.
+ */
+static bool deduce_local_duplicate(struct solver_scratch *sc, int pi)
+{
+ struct solver_placement *p = &sc->placements[pi];
+ struct solver_domino *d = p->domino;
+ int i, j;
+
+ if (!p->active)
+ return false;
+
+ for (i = 0; i < p->noverlaps; i++) {
+ struct solver_placement *q = p->overlaps[i];
+ struct solver_square *sq;
+
+ if (!q->active)
+ continue;
+
+ /* Find the square of q that _isn't_ part of p */
+ sq = q->squares[1 - common_square_index(q, p)];
+
+ for (j = 0; j < sq->nplacements; j++)
+ if (sq->placements[j] != q && sq->placements[j]->domino != d)
+ goto no;
+
+ /* If we get here, every possible placement for sq is either q
+ * itself, or another copy of d. Success! We can rule out p. */
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ printf("placement %s of domino %s would force another copy of %s "
+ "in square %s\n", p->name, d->name, d->name, sq->name);
+ }
+#endif
+
+ rule_out_placement(sc, p);
+ return true;
+
+ no:;
+ }
+
+ return false;
+}
+
+/*
+ * If placement P overlaps one placement for each of two squares S,T
+ * such that all the remaining placements for both S and T are the
+ * same domino D (and none of those placements joins S and T to each
+ * other), then P can't be placed, because it would leave S,T each
+ * having to be a copy of D, i.e. duplicates.
+ */
+static bool deduce_local_duplicate_2(struct solver_scratch *sc, int pi)
+{
+ struct solver_placement *p = &sc->placements[pi];
+ int i, j, k;
+
+ if (!p->active)
+ return false;
/*
- * Set up the initial possibility lists by scanning the grid.
+ * Iterate over pairs of placements qi,qj overlapping p.
*/
- for (y = 0; y < h-1; y++)
- for (x = 0; x < w; x++) {
- int di = DINDEX(grid[y*w+x], grid[(y+1)*w+x]);
- placements[(y*w+x)*2] = heads[di];
- heads[di] = (y*w+x)*2;
+ for (i = 0; i < p->noverlaps; i++) {
+ struct solver_placement *qi = p->overlaps[i];
+ struct solver_square *sqi;
+ struct solver_domino *di = NULL;
+
+ if (!qi->active)
+ continue;
+
+ /* Find the square of qi that _isn't_ part of p */
+ sqi = qi->squares[1 - common_square_index(qi, p)];
+
+ /*
+ * Identify the unique domino involved in all possible
+ * placements of sqi other than qi. If there isn't a unique
+ * one (either too many or too few), move on and try the next
+ * qi.
+ */
+ for (k = 0; k < sqi->nplacements; k++) {
+ struct solver_placement *pk = sqi->placements[k];
+ if (sqi->placements[k] == qi)
+ continue; /* not counting qi itself */
+ if (!di)
+ di = pk->domino;
+ else if (di != pk->domino)
+ goto done_qi;
}
- for (y = 0; y < h; y++)
- for (x = 0; x < w-1; x++) {
- int di = DINDEX(grid[y*w+x], grid[y*w+(x+1)]);
- placements[(y*w+x)*2+1] = heads[di];
- heads[di] = (y*w+x)*2+1;
+ if (!di)
+ goto done_qi;
+
+ /*
+ * Now find an appropriate qj != qi.
+ */
+ for (j = 0; j < p->noverlaps; j++) {
+ struct solver_placement *qj = p->overlaps[j];
+ struct solver_square *sqj;
+ bool found_di = false;
+
+ if (j == i || !qj->active)
+ continue;
+
+ sqj = qj->squares[1 - common_square_index(qj, p)];
+
+ /*
+ * As above, we want the same domino di to be the only one
+ * sqj can be if placement qj is ruled out. But also we
+ * need no placement of sqj to overlap sqi.
+ */
+ for (k = 0; k < sqj->nplacements; k++) {
+ struct solver_placement *pk = sqj->placements[k];
+ if (pk == qj)
+ continue; /* not counting qj itself */
+ if (pk->domino != di)
+ goto done_qj; /* found a different domino */
+ if (pk->squares[0] == sqi || pk->squares[1] == sqi)
+ goto done_qj; /* sqi,sqj can be joined to each other */
+ found_di = true;
+ }
+ if (!found_di)
+ goto done_qj;
+
+ /* If we get here, then every placement for either of sqi
+ * and sqj is a copy of di, except for the ones that
+ * overlap p. Success! We can rule out p. */
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ printf("placement %s of domino %s would force squares "
+ "%s and %s to both be domino %s\n",
+ p->name, p->domino->name,
+ sqi->name, sqj->name, di->name);
+ }
+#endif
+ rule_out_placement(sc, p);
+ return true;
+
+ done_qj:;
}
+ done_qi:;
+ }
+
+ return false;
+}
+
+struct parity_findloop_ctx {
+ struct solver_scratch *sc;
+ struct solver_square *sq;
+ int i;
+};
+
+int parity_neighbour(int vertex, void *vctx)
+{
+ struct parity_findloop_ctx *ctx = (struct parity_findloop_ctx *)vctx;
+ struct solver_placement *p;
+
+ if (vertex >= 0) {
+ ctx->sq = &ctx->sc->squares[vertex];
+ ctx->i = 0;
+ } else {
+ assert(ctx->sq);
+ }
+
+ if (ctx->i >= ctx->sq->nplacements) {
+ ctx->sq = NULL;
+ return -1;
+ }
+
+ p = ctx->sq->placements[ctx->i++];
+ return p->squares[0]->index + p->squares[1]->index - ctx->sq->index;
+}
+
+/*
+ * Look for dominoes whose placement would disconnect the unfilled
+ * area of the grid into pieces with odd area. Such a domino can't be
+ * placed, because then the area on each side of it would be
+ * untileable.
+ */
+static bool deduce_parity(struct solver_scratch *sc)
+{
+ struct parity_findloop_ctx pflctx;
+ bool done_something = false;
+ int pi;
+
+ /*
+ * Run findloop, aka Tarjan's bridge-finding algorithm, on the
+ * graph whose vertices are squares, with two vertices separated
+ * by an edge iff some not-yet-ruled-out domino placement covers
+ * them both. (So each edge itself corresponds to a domino
+ * placement.)
+ *
+ * The effect is that any bridge in this graph is a domino whose
+ * placement would separate two previously connected areas of the
+ * unfilled squares of the grid.
+ *
+ * Placing that domino would not just disconnect those areas from
+ * each other, but also use up one square of each. So if we want
+ * to avoid leaving two odd areas after placing the domino, it
+ * follows that we want to avoid the bridge having an _even_
+ * number of vertices on each side.
+ */
+ pflctx.sc = sc;
+ findloop_run(sc->fls, sc->wh, parity_neighbour, &pflctx);
+
+ for (pi = 0; pi < sc->pc; pi++) {
+ struct solver_placement *p = &sc->placements[pi];
+ int size0, size1;
+
+ if (!p->active)
+ continue;
+ if (!findloop_is_bridge(
+ sc->fls, p->squares[0]->index, p->squares[1]->index,
+ &size0, &size1))
+ continue;
+ /* To make a deduction, size0 and size1 must both be even,
+ * i.e. after placing this domino decrements each by 1 they
+ * would both become odd and untileable areas. */
+ if ((size0 | size1) & 1)
+ continue;
+
#ifdef SOLVER_DIAGNOSTICS
- printf("before solver:\n");
- for (i = 0; i <= n; i++)
- for (j = 0; j <= i; j++) {
- int k, m;
- m = 0;
- printf("%2d [%d %d]:", DINDEX(i, j), i, j);
- for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
- printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');
- printf("\n");
+ if (solver_diagnostics) {
+ printf("placement %s of domino %s would create two odd-sized "
+ "areas\n", p->name, p->domino->name);
}
#endif
+ rule_out_placement(sc, p);
+ done_something = true;
+ }
- while (1) {
- bool done_something = false;
+ return done_something;
+}
+/*
+ * Try to find a set of squares all containing the same number, such
+ * that the set of possible dominoes for all the squares in that set
+ * is small enough to let us rule out placements of those dominoes
+ * elsewhere.
+ */
+static bool deduce_set(struct solver_scratch *sc, bool doubles)
+{
+ struct solver_square **sqs, **sqp, **sqe;
+ int num, nsq, i, j;
+ unsigned long domino_sets[16], adjacent[16];
+ struct solver_domino *ds[16];
+ bool done_something = false;
+
+ if (!sc->squares_by_number)
+ sc->squares_by_number = snewn(sc->wh, struct solver_square *);
+ if (!sc->wh_scratch)
+ sc->wh_scratch = snewn(sc->wh, int);
+
+ if (!sc->squares_by_number_initialised) {
/*
- * For each domino, look at its possible placements, and
- * for each placement consider the placements (of any
- * domino) it overlaps. Any placement overlapped by all
- * placements of this domino can be ruled out.
- *
- * Each domino placement overlaps only six others, so we
- * need not do serious set theory to work this out.
+ * If this is the first call to this function for a given
+ * grid, start by sorting the squares by their containing
+ * number.
*/
- for (i = 0; i < dc; i++) {
- int permset[6], permlen = 0, p;
-
+ for (i = 0; i < sc->wh; i++)
+ sc->squares_by_number[i] = &sc->squares[i];
+ qsort(sc->squares_by_number, sc->wh, sizeof(*sc->squares_by_number),
+ squares_by_number_cmpfn);
+ }
- if (heads[i] == -1) { /* no placement for this domino */
- ret = 0; /* therefore puzzle is impossible */
- goto done;
- }
- for (j = heads[i]; j >= 0; j = placements[j]) {
- assert(placements[j] != -2);
+ sqp = sc->squares_by_number;
+ sqe = sc->squares_by_number + sc->wh;
+ for (num = 0; num <= sc->n; num++) {
+ unsigned long squares;
+ unsigned long squares_done;
- if (j == heads[i]) {
- permlen = find_overlaps(w, h, j, permset);
- } else {
- int tempset[6], templen, m, n, k;
+ /* Find the bounds of the subinterval of squares_by_number
+ * containing squares with this particular number. */
+ sqs = sqp;
+ while (sqp < sqe && (*sqp)->number == num)
+ sqp++;
+ nsq = sqp - sqs;
+
+ /*
+ * Now sqs[0], ..., sqs[nsq-1] are the squares containing 'num'.
+ */
+
+ if (nsq > lenof(domino_sets)) {
+ /*
+ * Abort this analysis if we're trying to enumerate all
+ * the subsets of a too-large base set.
+ *
+ * This _shouldn't_ happen, at the time of writing this
+ * code, because the largest puzzle we support is only
+ * supposed to have 10 instances of each number, and part
+ * of our input grid validation checks that each number
+ * does appear the right number of times. But just in case
+ * weird test input makes its way to this function, or the
+ * puzzle sizes are expanded later, it's easy enough to
+ * just rule out doing this analysis for overlarge sets of
+ * numbers.
+ */
+ continue;
+ }
+
+ /*
+ * Index the squares in wh_scratch, which we're using as a
+ * lookup table to map the official index of a square back to
+ * its value in our local indexing scheme.
+ */
+ for (i = 0; i < nsq; i++)
+ sc->wh_scratch[sqs[i]->index] = i;
+
+ /*
+ * For each square, make a bit mask of the dominoes that can
+ * overlap it, by finding the number at the other end of each
+ * one.
+ *
+ * Also, for each square, make a bit mask of other squares in
+ * the current list that might occupy the _same_ domino
+ * (because a possible placement of a double overlaps both).
+ * We'll need that for evaluating whether sets are properly
+ * exhaustive.
+ */
+ for (i = 0; i < nsq; i++)
+ adjacent[i] = 0;
- templen = find_overlaps(w, h, j, tempset);
+ for (i = 0; i < nsq; i++) {
+ struct solver_square *sq = sqs[i];
+ unsigned long mask = 0;
+ for (j = 0; j < sq->nplacements; j++) {
+ struct solver_placement *p = sq->placements[j];
+ int othernum = p->domino->lo + p->domino->hi - num;
+ mask |= 1UL << othernum;
+ ds[othernum] = p->domino; /* so we can find them later */
+
+ if (othernum == num) {
/*
- * Pathetically primitive set intersection
- * algorithm, which I'm only getting away with
- * because I know my sets are bounded by a very
- * small size.
+ * Special case: this is a double, so it gives
+ * rise to entries in adjacent[].
*/
- for (m = n = 0; m < permlen; m++) {
- for (k = 0; k < templen; k++)
- if (tempset[k] == permset[m])
- break;
- if (k < templen)
- permset[n++] = permset[m];
- }
- permlen = n;
+ int i2 = sc->wh_scratch[p->squares[0]->index +
+ p->squares[1]->index - sq->index];
+ adjacent[i] |= 1UL << i2;
+ adjacent[i2] |= 1UL << i;
}
}
- for (p = 0; p < permlen; p++) {
- j = permset[p];
- if (placements[j] != -2) {
- int p1, p2, di;
- done_something = true;
+ domino_sets[i] = mask;
+
+ }
+
+ squares_done = 0;
+
+ for (squares = 0; squares < (1UL << nsq); squares++) {
+ unsigned long dominoes = 0;
+ int bitpos, nsquares, ndominoes;
+ bool got_adj_squares = false;
+ bool reported = false;
+ bool rule_out_nondoubles;
+ int min_nused_for_double;
+#ifdef SOLVER_DIAGNOSTICS
+ const char *rule_out_text;
+#endif
+
+ /*
+ * We don't do set analysis on the same square of the grid
+ * more than once in this loop. Otherwise you generate
+ * pointlessly overcomplicated diagnostics for simpler
+ * follow-up deductions. For example, suppose squares
+ * {A,B} must go with dominoes {X,Y}. So you rule out X,Y
+ * elsewhere, and then it turns out square C (from which
+ * one of those was eliminated) has only one remaining
+ * possibility Z. What you _don't_ want to do is
+ * triumphantly report a second case of set elimination
+ * where you say 'And also, squares {A,B,C} have to be
+ * {X,Y,Z}!' You'd prefer to give 'now C has to be Z' as a
+ * separate deduction later, more simply phrased.
+ */
+ if (squares & squares_done)
+ continue;
+
+ nsquares = 0;
+
+ /* Make the set of dominoes that these squares can inhabit. */
+ for (bitpos = 0; bitpos < nsq; bitpos++) {
+ if (!(1 & (squares >> bitpos)))
+ continue; /* this bit isn't set in the mask */
+
+ if (adjacent[bitpos] & squares)
+ got_adj_squares = true;
+ dominoes |= domino_sets[bitpos];
+ nsquares++;
+ }
+
+ /* Count them. */
+ ndominoes = 0;
+ for (bitpos = 0; bitpos < nsq; bitpos++)
+ ndominoes += 1 & (dominoes >> bitpos);
+
+ /*
+ * Do the two sets have the right relative size?
+ */
+ if (!got_adj_squares) {
+ /*
+ * The normal case, in which every possible domino
+ * placement involves at most _one_ of these squares.
+ *
+ * This is exactly analogous to the set analysis
+ * deductions in many other puzzles: if our N squares
+ * between them have to account for N distinct
+ * dominoes, with exactly one of those dominoes to
+ * each square, then all those dominoes correspond to
+ * all those squares and we can rule out any
+ * placements of the same dominoes appearing
+ * elsewhere.
+ */
+ if (ndominoes != nsquares)
+ continue;
+ rule_out_nondoubles = true;
+ min_nused_for_double = 1;
+#ifdef SOLVER_DIAGNOSTICS
+ rule_out_text = "all of them elsewhere";
+#endif
+ } else {
+ if (!doubles)
+ continue; /* not at this difficulty level */
+
+ /*
+ * But in Dominosa, there's a special case if _two_
+ * squares in this set can possibly both be covered by
+ * the same double domino. (I.e. if they are adjacent,
+ * and moreover, the double-domino placement
+ * containing both is not yet ruled out.)
+ *
+ * In that situation, the simple argument doesn't hold
+ * up, because the N squares might be covered by N-1
+ * dominoes - or, put another way, if you list the
+ * containing domino for each of the squares, they
+ * might not be all distinct.
+ *
+ * In that situation, we can still do something, but
+ * the details vary, and there are two further cases.
+ */
+ if (ndominoes == nsquares-1) {
/*
- * Rule out this placement. First find what
- * domino it is...
+ * Suppose there is one _more_ square in our set
+ * than there are dominoes it can involve. For
+ * example, suppose we had four '0' squares which
+ * between them could contain only the 0-0, 0-1
+ * and 0-2 dominoes.
+ *
+ * Then that can only work at all if the 0-0
+ * covers two of those squares - and in that
+ * situation that _must_ be what's happened.
+ *
+ * So we can rule out the 0-1 and 0-2 dominoes (in
+ * this example) in any placement that doesn't use
+ * one of the squares in this set. And we can rule
+ * out a placement of the 0-0 even if it uses
+ * _one_ square from this set: in this situation,
+ * we have to insist on it using _two_.
*/
- p1 = j / 2;
- p2 = (j & 1) ? p1 + 1 : p1 + w;
- di = DINDEX(grid[p1], grid[p2]);
+ rule_out_nondoubles = true;
+ min_nused_for_double = 2;
#ifdef SOLVER_DIAGNOSTICS
- printf("considering domino %d: ruling out placement %d"
- " for %d\n", i, j, di);
+ rule_out_text = "all of them elsewhere "
+ "(including the double if it fails to use both)";
#endif
-
+ } else if (ndominoes == nsquares) {
+ /*
+ * A restricted form of the deduction is still
+ * possible if we have the same number of dominoes
+ * as squares.
+ *
+ * If we have _three_ '0' squares none of which
+ * can be any domino other than 0-0, 0-1 and 0-2,
+ * and there's still a possibility of an 0-0
+ * domino using up two of them, then we can't rule
+ * out 0-1 or 0-2 anywhere else, because it's
+ * possible that these three squares only use two
+ * of the dominoes between them.
+ *
+ * But we _can_ rule out the double 0-0, in any
+ * placement that uses _none_ of our three
+ * squares. Because we do know that _at least one_
+ * of our squares must be involved in the 0-0, or
+ * else the three of them would only have the
+ * other two dominoes left.
+ */
+ rule_out_nondoubles = false;
+ min_nused_for_double = 1;
+#ifdef SOLVER_DIAGNOSTICS
+ rule_out_text = "the double elsewhere";
+#endif
+ } else {
/*
- * ... then walk that domino's placement list,
- * removing this placement when we find it.
+ * If none of those cases has happened, then our
+ * set admits no deductions at all.
*/
- if (heads[di] == j)
- heads[di] = placements[j];
- else {
- int k = heads[di];
- while (placements[k] != -1 && placements[k] != j)
- k = placements[k];
- assert(placements[k] == j);
- placements[k] = placements[j];
+ continue;
+ }
+ }
+
+ /* Skip sets of size 1, or whose complement has size 1.
+ * Those can be handled by a simpler analysis, and should
+ * be, for more sensible solver diagnostics. */
+ if (ndominoes <= 1 || ndominoes >= nsq-1)
+ continue;
+
+ /*
+ * We've found a set! That means we can rule out any
+ * placement of any domino in that set which would leave
+ * the squares in the set with too few dominoes between
+ * them.
+ *
+ * We may or may not actually end up ruling anything out
+ * here. But even if we don't, we should record that these
+ * squares form a self-contained set, so that we don't
+ * pointlessly report a superset of them later which could
+ * instead be reported as just the other ones.
+ *
+ * Or rather, we do that for the main cases that let us
+ * rule out lots of dominoes. We only do this with the
+ * borderline case where we can only rule out a double if
+ * we _actually_ rule something out. Otherwise we'll never
+ * even _find_ a larger set with the same number of
+ * dominoes!
+ */
+ if (rule_out_nondoubles)
+ squares_done |= squares;
+
+ for (bitpos = 0; bitpos < nsq; bitpos++) {
+ struct solver_domino *d;
+
+ if (!(1 & (dominoes >> bitpos)))
+ continue;
+ d = ds[bitpos];
+
+ for (i = d->nplacements; i-- > 0 ;) {
+ struct solver_placement *p = d->placements[i];
+ int si, nused;
+
+ /* Count how many of our squares this placement uses. */
+ for (si = nused = 0; si < 2; si++) {
+ struct solver_square *sq2 = p->squares[si];
+ if (sq2->number == num &&
+ (1 & (squares >> sc->wh_scratch[sq2->index])))
+ nused++;
+ }
+
+ /* See if that's too many to rule it out. */
+ if (d->lo == d->hi) {
+ if (nused >= min_nused_for_double)
+ continue;
+ } else {
+ if (nused > 0 || !rule_out_nondoubles)
+ continue;
+ }
+
+ if (!reported) {
+ reported = true;
+ done_something = true;
+
+ /* In case we didn't do this above */
+ squares_done |= squares;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ int b;
+ const char *sep;
+ printf("squares {");
+ for (sep = "", b = 0; b < nsq; b++)
+ if (1 & (squares >> b)) {
+ printf("%s%s", sep, sqs[b]->name);
+ sep = ",";
+ }
+ printf("} can contain only dominoes {");
+ for (sep = "", b = 0; b < nsq; b++)
+ if (1 & (dominoes >> b)) {
+ printf("%s%s", sep, ds[b]->name);
+ sep = ",";
+ }
+ printf("}, so rule out %s", rule_out_text);
+ printf("\n");
+ }
+#endif
}
- placements[j] = -2;
+
+ rule_out_placement(sc, p);
}
}
}
+ }
+
+ return done_something;
+}
+
+static int forcing_chain_dup_cmp(const void *av, const void *bv, void *ctx)
+{
+ struct solver_scratch *sc = (struct solver_scratch *)ctx;
+ int a = *(const int *)av, b = *(const int *)bv;
+ int ac, bc;
+
+ ac = sc->pc_scratch[a];
+ bc = sc->pc_scratch[b];
+ if (ac != bc) return ac > bc ? +1 : -1;
+
+ ac = sc->placements[a].domino->index;
+ bc = sc->placements[b].domino->index;
+ if (ac != bc) return ac > bc ? +1 : -1;
+
+ return 0;
+}
+
+static int forcing_chain_sq_cmp(const void *av, const void *bv, void *ctx)
+{
+ struct solver_scratch *sc = (struct solver_scratch *)ctx;
+ int a = *(const int *)av, b = *(const int *)bv;
+ int ac, bc;
+
+ ac = sc->placements[a].domino->index;
+ bc = sc->placements[b].domino->index;
+ if (ac != bc) return ac > bc ? +1 : -1;
+
+ ac = sc->pc_scratch[a];
+ bc = sc->pc_scratch[b];
+ if (ac != bc) return ac > bc ? +1 : -1;
+
+ return 0;
+}
+
+static bool deduce_forcing_chain(struct solver_scratch *sc)
+{
+ int si, pi, di, j, k, m;
+ bool done_something = false;
+
+ if (!sc->wh_scratch)
+ sc->wh_scratch = snewn(sc->wh, int);
+ if (!sc->pc_scratch)
+ sc->pc_scratch = snewn(sc->pc, int);
+ if (!sc->pc_scratch2)
+ sc->pc_scratch2 = snewn(sc->pc, int);
+ if (!sc->dc_scratch)
+ sc->dc_scratch = snewn(sc->dc, int);
+
+ /*
+ * Start by identifying chains of placements which must all occur
+ * together if any of them occurs. We do this by making
+ * pc_scratch2 an edsf binding the placements into an equivalence
+ * class for each entire forcing chain, with the two possible sets
+ * of dominoes for the chain listed as inverses.
+ */
+ dsf_init(sc->pc_scratch2, sc->pc);
+ for (si = 0; si < sc->wh; si++) {
+ struct solver_square *sq = &sc->squares[si];
+ if (sq->nplacements == 2)
+ edsf_merge(sc->pc_scratch2,
+ sq->placements[0]->index,
+ sq->placements[1]->index, true);
+ }
+ /*
+ * Now read out the whole dsf into pc_scratch, flattening its
+ * structured data into a simple integer id per chain of dominoes
+ * that must occur together.
+ *
+ * The integer ids have the property that any two that differ only
+ * in the lowest bit (i.e. of the form {2n,2n+1}) represent
+ * complementary chains, each of which rules out the other.
+ */
+ for (pi = 0; pi < sc->pc; pi++) {
+ bool inv;
+ int c = edsf_canonify(sc->pc_scratch2, pi, &inv);
+ sc->pc_scratch[pi] = c * 2 + (inv ? 1 : 0);
+ }
+
+ /*
+ * Identify chains that contain a duplicate domino, and rule them
+ * out. We do this by making a list of the placement indices in
+ * pc_scratch2, sorted by (chain id, domino id), so that dupes
+ * become adjacent.
+ */
+ for (pi = 0; pi < sc->pc; pi++)
+ sc->pc_scratch2[pi] = pi;
+ arraysort(sc->pc_scratch2, sc->pc, forcing_chain_dup_cmp, sc);
+
+ for (j = 0; j < sc->pc ;) {
+ struct solver_domino *duplicated_domino = NULL;
+
/*
- * For each square, look at the available placements
- * involving that square. If all of them are for the same
- * domino, then rule out any placements for that domino
- * _not_ involving this square.
+ * This loop iterates once per contiguous segment of the same
+ * value in pc_scratch2, i.e. once per chain.
*/
- for (i = 0; i < wh; i++) {
- int list[4], k, n, adi;
-
- x = i % w;
- y = i / w;
-
- j = 0;
- if (x > 0)
- list[j++] = 2*(i-1)+1;
- if (x+1 < w)
- list[j++] = 2*i+1;
- if (y > 0)
- list[j++] = 2*(i-w);
- if (y+1 < h)
- list[j++] = 2*i;
-
- for (n = k = 0; k < j; k++)
- if (placements[list[k]] >= -1)
- list[n++] = list[k];
-
- adi = -1;
-
- for (j = 0; j < n; j++) {
- int p1, p2, di;
- k = list[j];
-
- p1 = k / 2;
- p2 = (k & 1) ? p1 + 1 : p1 + w;
- di = DINDEX(grid[p1], grid[p2]);
-
- if (adi == -1)
- adi = di;
- if (adi != di)
- break;
+ int ci = sc->pc_scratch[sc->pc_scratch2[j]];
+ int climit, cstart = j;
+ while (j < sc->pc && sc->pc_scratch[sc->pc_scratch2[j]] == ci)
+ j++;
+ climit = j;
+
+ /*
+ * Now look for a duplicate domino within that chain.
+ */
+ for (k = cstart; k + 1 < climit; k++) {
+ struct solver_placement *p = &sc->placements[sc->pc_scratch2[k]];
+ struct solver_placement *q = &sc->placements[sc->pc_scratch2[k+1]];
+ if (p->domino == q->domino) {
+ duplicated_domino = p->domino;
+ break;
}
+ }
- if (j == n) {
- int nn;
+ if (!duplicated_domino)
+ continue;
- assert(adi >= 0);
- /*
- * We've found something. All viable placements
- * involving this square are for domino `adi'. If
- * the current placement list for that domino is
- * longer than n, reduce it to precisely this
- * placement list and we've done something.
- */
- nn = 0;
- for (k = heads[adi]; k >= 0; k = placements[k])
- nn++;
- if (nn > n) {
- done_something = true;
#ifdef SOLVER_DIAGNOSTICS
- printf("considering square %d,%d: reducing placements "
- "of domino %d\n", x, y, adi);
+ if (solver_diagnostics) {
+ printf("domino %s occurs more than once in forced chain:",
+ duplicated_domino->name);
+ for (k = cstart; k < climit; k++)
+ printf(" %s", sc->placements[sc->pc_scratch2[k]].name);
+ printf("\n");
+ }
#endif
+
+ for (k = cstart; k < climit; k++)
+ rule_out_placement(sc, &sc->placements[sc->pc_scratch2[k]]);
+
+ done_something = true;
+ }
+
+ if (done_something)
+ return true;
+
+ /*
+ * A second way in which a whole forcing chain can be ruled out is
+ * if it contains all the dominoes that can occupy some other
+ * square, so that if the domnioes in the chain were all laid, the
+ * other square would be left without any choices.
+ *
+ * To detect this, we sort the placements again, this time by
+ * (domino index, chain index), so that we can easily find a
+ * sorted list of chains per domino. That allows us to iterate
+ * over the squares and check for a chain id common to all the
+ * placements of that square.
+ */
+ for (pi = 0; pi < sc->pc; pi++)
+ sc->pc_scratch2[pi] = pi;
+ arraysort(sc->pc_scratch2, sc->pc, forcing_chain_sq_cmp, sc);
+
+ /* Store a lookup table of the first entry in pc_scratch2
+ * corresponding to each domino. */
+ for (di = j = 0; j < sc->pc; j++) {
+ while (di <= sc->placements[sc->pc_scratch2[j]].domino->index) {
+ assert(di < sc->dc);
+ sc->dc_scratch[di++] = j;
+ }
+ }
+ assert(di == sc->dc);
+
+ for (si = 0; si < sc->wh; si++) {
+ struct solver_square *sq = &sc->squares[si];
+ int listpos = 0, listsize = 0, listout = 0;
+ int exclude[4];
+ int n_exclude;
+
+ if (sq->nplacements < 2)
+ continue; /* too simple to be worth trying */
+
+ /*
+ * Start by checking for chains this square can actually form
+ * part of. We won't consider those. (The aim is to find a
+ * completely _different_ square whose placements are all
+ * ruled out by a chain.)
+ */
+ assert(sq->nplacements <= lenof(exclude));
+ for (j = n_exclude = 0; j < sq->nplacements; j++)
+ exclude[n_exclude++] = sc->pc_scratch[sq->placements[j]->index];
+
+ for (j = 0; j < sq->nplacements; j++) {
+ struct solver_domino *d = sq->placements[j]->domino;
+
+ listout = listpos = 0;
+
+ for (k = sc->dc_scratch[d->index];
+ k < sc->pc && sc->placements[sc->pc_scratch2[k]].domino == d;
+ k++) {
+ int chain = sc->pc_scratch[sc->pc_scratch2[k]];
+ bool keep;
+
+ if (!sc->placements[sc->pc_scratch2[k]].active)
+ continue;
+
+ if (j == 0) {
+ keep = true;
+ } else {
+ while (listpos < listsize &&
+ sc->wh_scratch[listpos] < chain)
+ listpos++;
+ keep = (listpos < listsize &&
+ sc->wh_scratch[listpos] == chain);
+ }
+
+ for (m = 0; m < n_exclude; m++)
+ if (chain == exclude[m])
+ keep = false;
+
+ if (keep)
+ sc->wh_scratch[listout++] = chain;
+ }
+
+ listsize = listout;
+ if (listsize == 0)
+ break; /* ruled out all chains; terminate loop early */
+ }
+
+ for (listpos = 0; listpos < listsize; listpos++) {
+ int chain = sc->wh_scratch[listpos];
+
+ /*
+ * We've found a chain we can rule out.
+ */
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ printf("all choices for square %s would be ruled out "
+ "by forced chain:", sq->name);
+ for (pi = 0; pi < sc->pc; pi++)
+ if (sc->pc_scratch[pi] == chain)
+ printf(" %s", sc->placements[pi].name);
+ printf("\n");
+ }
+#endif
+
+ for (pi = 0; pi < sc->pc; pi++)
+ if (sc->pc_scratch[pi] == chain)
+ rule_out_placement(sc, &sc->placements[pi]);
+
+ done_something = true;
+ }
+ }
+
+ /*
+ * Another thing you can do with forcing chains, besides ruling
+ * out a whole one at a time, is to look at each pair of chains
+ * that overlap each other. Each such pair gives you two sets of
+ * domino placements, such that if either set is not placed, then
+ * the other one must be.
+ *
+ * This means that any domino which has a placement in _both_
+ * chains of a pair must occupy one of those two placements, i.e.
+ * we can rule that domino out anywhere else it might appear.
+ */
+ for (di = 0; di < sc->dc; di++) {
+ struct solver_domino *d = &sc->dominoes[di];
+
+ if (d->nplacements <= 2)
+ continue; /* not enough placements to rule one out */
+
+ for (j = 0; j+1 < d->nplacements; j++) {
+ int ij = d->placements[j]->index;
+ int cj = sc->pc_scratch[ij];
+ for (k = j+1; k < d->nplacements; k++) {
+ int ik = d->placements[k]->index;
+ int ck = sc->pc_scratch[ik];
+ if ((cj ^ ck) == 1) {
/*
- * Set all other placements on the list to
- * impossible.
+ * Placements j,k of domino d are in complementary
+ * chains, so we can rule out all the others.
*/
- k = heads[adi];
- while (k >= 0) {
- int tmp = placements[k];
- placements[k] = -2;
- k = tmp;
+ int i;
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ printf("domino %s occurs in both complementary "
+ "forced chains:", d->name);
+ for (i = 0; i < sc->pc; i++)
+ if (sc->pc_scratch[i] == cj)
+ printf(" %s", sc->placements[i].name);
+ printf(" and");
+ for (i = 0; i < sc->pc; i++)
+ if (sc->pc_scratch[i] == ck)
+ printf(" %s", sc->placements[i].name);
+ printf("\n");
}
- /*
- * Set up the new list.
- */
- heads[adi] = list[0];
- for (k = 0; k < n; k++)
- placements[list[k]] = (k+1 == n ? -1 : list[k+1]);
+#endif
+
+ for (i = d->nplacements; i-- > 0 ;)
+ if (i != j && i != k)
+ rule_out_placement(sc, d->placements[i]);
+
+ done_something = true;
+ goto done_this_domino;
}
}
}
- if (!done_something)
- break;
+ done_this_domino:;
}
+ return done_something;
+}
+
+/*
+ * Run the solver until it can't make any more progress.
+ *
+ * Return value is:
+ * 0 = no solution exists (puzzle clues are unsatisfiable)
+ * 1 = unique solution found (success!)
+ * 2 = multiple possibilities remain (puzzle is ambiguous or solver is not
+ * smart enough)
+ */
+static int run_solver(struct solver_scratch *sc, int max_diff_allowed)
+{
+ int di, si, pi;
+ bool done_something;
+
#ifdef SOLVER_DIAGNOSTICS
- printf("after solver:\n");
- for (i = 0; i <= n; i++)
- for (j = 0; j <= i; j++) {
- int k, m;
- m = 0;
- printf("%2d [%d %d]:", DINDEX(i, j), i, j);
- for (k = heads[DINDEX(i,j)]; k >= 0; k = placements[k])
- printf(" %3d [%d,%d,%c]", k, k/2%w, k/2/w, k%2?'h':'v');
+ if (solver_diagnostics) {
+ int di, j;
+ printf("Initial possible placements:\n");
+ for (di = 0; di < sc->dc; di++) {
+ struct solver_domino *d = &sc->dominoes[di];
+ printf(" %s:", d->name);
+ for (j = 0; j < d->nplacements; j++)
+ printf(" %s", d->placements[j]->name);
printf("\n");
}
+ }
#endif
- ret = 1;
- for (i = 0; i < wh*2; i++) {
- if (placements[i] == -2) {
- if (output)
- output[i] = -1; /* ruled out */
- } else if (placements[i] != -3) {
- int p1, p2, di;
-
- p1 = i / 2;
- p2 = (i & 1) ? p1 + 1 : p1 + w;
- di = DINDEX(grid[p1], grid[p2]);
-
- if (i == heads[di] && placements[i] == -1) {
- if (output)
- output[i] = 1; /* certain */
- } else {
- if (output)
- output[i] = 0; /* uncertain */
- ret = 2;
+ do {
+ done_something = false;
+
+ for (di = 0; di < sc->dc; di++)
+ if (deduce_domino_single_placement(sc, di))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_TRIVIAL);
+ continue;
+ }
+
+ for (si = 0; si < sc->wh; si++)
+ if (deduce_square_single_placement(sc, si))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_TRIVIAL);
+ continue;
+ }
+
+ if (max_diff_allowed <= DIFF_TRIVIAL)
+ continue;
+
+ for (si = 0; si < sc->wh; si++)
+ if (deduce_square_single_domino(sc, si))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
+ continue;
+ }
+
+ for (di = 0; di < sc->dc; di++)
+ if (deduce_domino_must_overlap(sc, di))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
+ continue;
+ }
+
+ for (pi = 0; pi < sc->pc; pi++)
+ if (deduce_local_duplicate(sc, pi))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
+ continue;
+ }
+
+ for (pi = 0; pi < sc->pc; pi++)
+ if (deduce_local_duplicate_2(sc, pi))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
+ continue;
+ }
+
+ if (deduce_parity(sc))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_BASIC);
+ continue;
+ }
+
+ if (max_diff_allowed <= DIFF_BASIC)
+ continue;
+
+ if (deduce_set(sc, false))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_HARD);
+ continue;
+ }
+
+ if (max_diff_allowed <= DIFF_HARD)
+ continue;
+
+ if (deduce_set(sc, true))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME);
+ continue;
+ }
+
+ if (deduce_forcing_chain(sc))
+ done_something = true;
+ if (done_something) {
+ sc->max_diff_used = max(sc->max_diff_used, DIFF_EXTREME);
+ continue;
+ }
+
+ } while (done_something);
+
+#ifdef SOLVER_DIAGNOSTICS
+ if (solver_diagnostics) {
+ int di, j;
+ printf("Final possible placements:\n");
+ for (di = 0; di < sc->dc; di++) {
+ struct solver_domino *d = &sc->dominoes[di];
+ printf(" %s:", d->name);
+ for (j = 0; j < d->nplacements; j++)
+ printf(" %s", d->placements[j]->name);
+ printf("\n");
+ }
+ }
+#endif
+
+ for (di = 0; di < sc->dc; di++)
+ if (sc->dominoes[di].nplacements == 0)
+ return 0;
+ for (di = 0; di < sc->dc; di++)
+ if (sc->dominoes[di].nplacements > 1)
+ return 2;
+ return 1;
+}
+
+/* ----------------------------------------------------------------------
+ * Functions for generating a candidate puzzle (before we run the
+ * solver to check it's soluble at the right difficulty level).
+ */
+
+struct alloc_val;
+struct alloc_loc;
+
+struct alloc_scratch {
+ /* Game parameters. */
+ int n, w, h, wh, dc;
+
+ /* The domino layout. Indexed by squares in the usual y*w+x raster
+ * order: layout[i] gives the index of the other square in the
+ * same domino as square i. */
+ int *layout;
+
+ /* The output array, containing a number in every square. */
+ int *numbers;
+
+ /* List of domino values (i.e. number pairs), indexed by DINDEX. */
+ struct alloc_val *vals;
+
+ /* List of domino locations, indexed arbitrarily. */
+ struct alloc_loc *locs;
+
+ /* Preallocated scratch spaces. */
+ int *wh_scratch; /* size wh */
+ int *wh2_scratch; /* size 2*wh */
+};
+
+struct alloc_val {
+ int lo, hi;
+ bool confounder;
+};
+
+struct alloc_loc {
+ int sq[2];
+};
+
+static struct alloc_scratch *alloc_make_scratch(int n)
+{
+ struct alloc_scratch *as = snew(struct alloc_scratch);
+ int lo, hi;
+
+ as->n = n;
+ as->w = n+2;
+ as->h = n+1;
+ as->wh = as->w * as->h;
+ as->dc = DCOUNT(n);
+
+ as->layout = snewn(as->wh, int);
+ as->numbers = snewn(as->wh, int);
+ as->vals = snewn(as->dc, struct alloc_val);
+ as->locs = snewn(as->dc, struct alloc_loc);
+ as->wh_scratch = snewn(as->wh, int);
+ as->wh2_scratch = snewn(as->wh * 2, int);
+
+ for (hi = 0; hi <= n; hi++)
+ for (lo = 0; lo <= hi; lo++) {
+ struct alloc_val *v = &as->vals[DINDEX(hi, lo)];
+ v->lo = lo;
+ v->hi = hi;
+ }
+
+ return as;
+}
+
+static void alloc_free_scratch(struct alloc_scratch *as)
+{
+ sfree(as->layout);
+ sfree(as->numbers);
+ sfree(as->vals);
+ sfree(as->locs);
+ sfree(as->wh_scratch);
+ sfree(as->wh2_scratch);
+ sfree(as);
+}
+
+static void alloc_make_layout(struct alloc_scratch *as, random_state *rs)
+{
+ int i, pos;
+
+ domino_layout_prealloc(as->w, as->h, rs,
+ as->layout, as->wh_scratch, as->wh2_scratch);
+
+ for (i = pos = 0; i < as->wh; i++) {
+ if (as->layout[i] > i) {
+ struct alloc_loc *loc;
+ assert(pos < as->dc);
+
+ loc = &as->locs[pos++];
+ loc->sq[0] = i;
+ loc->sq[1] = as->layout[i];
+ }
+ }
+ assert(pos == as->dc);
+}
+
+static void alloc_trivial(struct alloc_scratch *as, random_state *rs)
+{
+ int i;
+ for (i = 0; i < as->dc; i++)
+ as->wh_scratch[i] = i;
+ shuffle(as->wh_scratch, as->dc, sizeof(*as->wh_scratch), rs);
+
+ for (i = 0; i < as->dc; i++) {
+ struct alloc_val *val = &as->vals[as->wh_scratch[i]];
+ struct alloc_loc *loc = &as->locs[i];
+ int which_lo = random_upto(rs, 2), which_hi = 1 - which_lo;
+ as->numbers[loc->sq[which_lo]] = val->lo;
+ as->numbers[loc->sq[which_hi]] = val->hi;
+ }
+}
+
+/*
+ * Given a domino location in the form of two square indices, compute
+ * the square indices of the domino location that would lie on one
+ * side of it. Returns false if the location would be outside the
+ * grid, or if it isn't actually a domino in the layout.
+ */
+static bool alloc_find_neighbour(
+ struct alloc_scratch *as, int p0, int p1, int *n0, int *n1)
+{
+ int x0 = p0 % as->w, y0 = p0 / as->w, x1 = p1 % as->w, y1 = p1 / as->w;
+ int dy = y1-y0, dx = x1-x0;
+ int nx0 = x0 + dy, ny0 = y0 - dx, nx1 = x1 + dy, ny1 = y1 - dx;
+ int np0, np1;
+
+ if (!(nx0 >= 0 && nx0 < as->w && ny0 >= 0 && ny0 < as->h &&
+ nx1 >= 1 && nx1 < as->w && ny1 >= 1 && ny1 < as->h))
+ return false; /* out of bounds */
+
+ np0 = ny0 * as->w + nx0;
+ np1 = ny1 * as->w + nx1;
+ if (as->layout[np0] != np1)
+ return false; /* not a domino */
+
+ *n0 = np0;
+ *n1 = np1;
+ return true;
+}
+
+static bool alloc_try_unique(struct alloc_scratch *as, random_state *rs)
+{
+ int i;
+ for (i = 0; i < as->dc; i++)
+ as->wh_scratch[i] = i;
+ shuffle(as->wh_scratch, as->dc, sizeof(*as->wh_scratch), rs);
+ for (i = 0; i < as->dc; i++)
+ as->wh2_scratch[i] = i;
+ shuffle(as->wh2_scratch, as->dc, sizeof(*as->wh2_scratch), rs);
+
+ for (i = 0; i < as->wh; i++)
+ as->numbers[i] = -1;
+
+ for (i = 0; i < as->dc; i++) {
+ struct alloc_val *val = &as->vals[as->wh_scratch[i]];
+ struct alloc_loc *loc = &as->locs[as->wh2_scratch[i]];
+ int which_lo, which_hi;
+ bool can_lo_0 = true, can_lo_1 = true;
+ int n0, n1;
+
+ /*
+ * This is basically the same strategy as alloc_trivial:
+ * simply iterate through the locations and values in random
+ * relative order and pair them up. But we make sure to avoid
+ * the most common, and also simplest, cause of a non-unique
+ * solution:two dominoes side by side, sharing a number at
+ * opposite ends. Any section of that form automatically leads
+ * to an alternative solution:
+ *
+ * +-------+ +---+---+
+ * | 1 2 | | 1 | 2 |
+ * +-------+ <-> | | |
+ * | 2 3 | | 2 | 3 |
+ * +-------+ +---+---+
+ *
+ * So as we place each domino, we check for a neighbouring
+ * domino on each side, and if there is one, rule out any
+ * placement of _this_ domino that places a number diagonally
+ * opposite the same number in the neighbour.
+ *
+ * Sometimes this can fail completely, if a domino on each
+ * side is already placed and between them they rule out all
+ * placements of this one. But it happens rarely enough that
+ * it's fine to just abort and try the layout again.
+ */
+
+ if (alloc_find_neighbour(as, loc->sq[0], loc->sq[1], &n0, &n1) &&
+ (as->numbers[n0] == val->hi || as->numbers[n1] == val->lo))
+ can_lo_0 = false;
+ if (alloc_find_neighbour(as, loc->sq[1], loc->sq[0], &n0, &n1) &&
+ (as->numbers[n0] == val->hi || as->numbers[n1] == val->lo))
+ can_lo_1 = false;
+
+ if (!can_lo_0 && !can_lo_1)
+ return false; /* layout failed */
+ else if (can_lo_0 && can_lo_1)
+ which_lo = random_upto(rs, 2);
+ else
+ which_lo = can_lo_0 ? 0 : 1;
+
+ which_hi = 1 - which_lo;
+ as->numbers[loc->sq[which_lo]] = val->lo;
+ as->numbers[loc->sq[which_hi]] = val->hi;
+ }
+
+ return true;
+}
+
+static bool alloc_try_hard(struct alloc_scratch *as, random_state *rs)
+{
+ int i, x, y, hi, lo, vals, locs, confounders_needed;
+ bool ok;
+
+ for (i = 0; i < as->wh; i++)
+ as->numbers[i] = -1;
+
+ /*
+ * Shuffle the location indices.
+ */
+ for (i = 0; i < as->dc; i++)
+ as->wh2_scratch[i] = i;
+ shuffle(as->wh2_scratch, as->dc, sizeof(*as->wh2_scratch), rs);
+
+ /*
+ * Start by randomly placing the double dominoes, to give a
+ * starting instance of every number to try to put other things
+ * next to.
+ */
+ for (i = 0; i <= as->n; i++)
+ as->wh_scratch[i] = DINDEX(i, i);
+ shuffle(as->wh_scratch, i, sizeof(*as->wh_scratch), rs);
+ for (i = 0; i <= as->n; i++) {
+ struct alloc_loc *loc = &as->locs[as->wh2_scratch[i]];
+ as->numbers[loc->sq[0]] = as->numbers[loc->sq[1]] = i;
+ }
+
+ /*
+ * Find all the dominoes that don't yet have a _wrong_ placement
+ * somewhere in the grid.
+ */
+ for (i = 0; i < as->dc; i++)
+ as->vals[i].confounder = false;
+ for (y = 0; y < as->h; y++) {
+ for (x = 0; x < as->w; x++) {
+ int p = y * as->w + x;
+ if (as->numbers[p] == -1)
+ continue;
+
+ if (x+1 < as->w) {
+ int p1 = y * as->w + (x+1);
+ if (as->layout[p] != p1 && as->numbers[p1] != -1)
+ as->vals[DINDEX(as->numbers[p], as->numbers[p1])]
+ .confounder = true;
+ }
+ if (y+1 < as->h) {
+ int p1 = (y+1) * as->w + x;
+ if (as->layout[p] != p1 && as->numbers[p1] != -1)
+ as->vals[DINDEX(as->numbers[p], as->numbers[p1])]
+ .confounder = true;
}
}
}
- done:
+ for (i = confounders_needed = 0; i < as->dc; i++)
+ if (!as->vals[i].confounder)
+ confounders_needed++;
+
/*
- * Free working data.
+ * Make a shuffled list of all the unplaced dominoes, and go
+ * through it trying to find a placement for each one that also
+ * fills in at least one of the needed confounders.
*/
- sfree(placements);
- sfree(heads);
+ vals = 0;
+ for (hi = 0; hi <= as->n; hi++)
+ for (lo = 0; lo < hi; lo++)
+ as->wh_scratch[vals++] = DINDEX(hi, lo);
+ shuffle(as->wh_scratch, vals, sizeof(*as->wh_scratch), rs);
+
+ locs = as->dc;
+
+ while (vals > 0) {
+ int valpos, valout, oldvals = vals;
+
+ for (valpos = valout = 0; valpos < vals; valpos++) {
+ int validx = as->wh_scratch[valpos];
+ struct alloc_val *val = &as->vals[validx];
+ struct alloc_loc *loc;
+ int locpos, si, which_lo;
+
+ for (locpos = 0; locpos < locs; locpos++) {
+ int locidx = as->wh2_scratch[locpos];
+ int wi, flip;
+
+ loc = &as->locs[locidx];
+ if (as->numbers[loc->sq[0]] != -1)
+ continue; /* this location is already filled */
+
+ flip = random_upto(rs, 2);
+
+ /* Try this location both ways round. */
+ for (wi = 0; wi < 2; wi++) {
+ int n0, n1;
+
+ which_lo = wi ^ flip;
+
+ /* First, do the same check as in alloc_try_unique, to
+ * avoid making an obviously insoluble puzzle. */
+ if (alloc_find_neighbour(as, loc->sq[which_lo],
+ loc->sq[1-which_lo], &n0, &n1) &&
+ (as->numbers[n0] == val->hi ||
+ as->numbers[n1] == val->lo))
+ break; /* can't place it this way round */
+
+ if (confounders_needed == 0)
+ goto place_ok;
+
+ /* Look to see if we're adding at least one
+ * previously absent confounder. */
+ for (si = 0; si < 2; si++) {
+ int x = loc->sq[si] % as->w, y = loc->sq[si] / as->w;
+ int n = (si == which_lo ? val->lo : val->hi);
+ int d;
+ for (d = 0; d < 4; d++) {
+ int dx = d==0 ? +1 : d==2 ? -1 : 0;
+ int dy = d==1 ? +1 : d==3 ? -1 : 0;
+ int x1 = x+dx, y1 = y+dy, p1 = y1 * as->w + x1;
+ if (x1 >= 0 && x1 < as->w &&
+ y1 >= 0 && y1 < as->h &&
+ as->numbers[p1] != -1 &&
+ !(as->vals[DINDEX(n, as->numbers[p1])]
+ .confounder)) {
+ /*
+ * Place this domino.
+ */
+ goto place_ok;
+ }
+ }
+ }
+ }
+ }
- return ret;
-}
+ /* If we get here without executing 'goto place_ok', we
+ * didn't find anywhere useful to put this domino. Put it
+ * back on the list for the next pass. */
+ as->wh_scratch[valout++] = validx;
+ continue;
+
+ place_ok:;
+
+ /* We've found a domino to place. Place it, and fill in
+ * all the confounders it adds. */
+ as->numbers[loc->sq[which_lo]] = val->lo;
+ as->numbers[loc->sq[1 - which_lo]] = val->hi;
+
+ for (si = 0; si < 2; si++) {
+ int p = loc->sq[si];
+ int n = as->numbers[p];
+ int x = p % as->w, y = p / as->w;
+ int d;
+ for (d = 0; d < 4; d++) {
+ int dx = d==0 ? +1 : d==2 ? -1 : 0;
+ int dy = d==1 ? +1 : d==3 ? -1 : 0;
+ int x1 = x+dx, y1 = y+dy, p1 = y1 * as->w + x1;
+
+ if (x1 >= 0 && x1 < as->w && y1 >= 0 && y1 < as->h &&
+ p1 != loc->sq[1-si] && as->numbers[p1] != -1) {
+ int di = DINDEX(n, as->numbers[p1]);
+ if (!as->vals[di].confounder)
+ confounders_needed--;
+ as->vals[di].confounder = true;
+ }
+ }
+ }
+ }
-/* ----------------------------------------------------------------------
- * End of solver code.
- */
+ vals = valout;
+
+ if (oldvals == vals)
+ break;
+ }
+
+ ok = true;
+
+ for (i = 0; i < as->dc; i++)
+ if (!as->vals[i].confounder)
+ ok = false;
+ for (i = 0; i < as->wh; i++)
+ if (as->numbers[i] == -1)
+ ok = false;
+
+ return ok;
+}
static char *new_game_desc(const game_params *params, random_state *rs,
char **aux, bool interactive)
{
- int n = params->n, w = n+2, h = n+1, wh = w*h;
- int *grid, *grid2, *list;
+ int n = params->n, w = n+2, h = n+1, wh = w*h, diff = params->diff;
+ struct solver_scratch *sc;
+ struct alloc_scratch *as;
int i, j, k, len;
char *ret;
+#ifndef OMIT_DIFFICULTY_CAP
+ /*
+ * Cap the difficulty level for small puzzles which would
+ * otherwise become impossible to generate.
+ *
+ * Under an #ifndef, to make it easy to remove this cap for the
+ * purpose of re-testing what it ought to be.
+ */
+ if (diff != DIFF_AMBIGUOUS) {
+ if (n == 1 && diff > DIFF_TRIVIAL)
+ diff = DIFF_TRIVIAL;
+ if (n == 2 && diff > DIFF_BASIC)
+ diff = DIFF_BASIC;
+ }
+#endif /* OMIT_DIFFICULTY_CAP */
+
/*
* Allocate space in which to lay the grid out.
*/
- grid = snewn(wh, int);
- grid2 = snewn(wh, int);
- list = snewn(2*wh, int);
+ sc = solver_make_scratch(n);
+ as = alloc_make_scratch(n);
/*
* I haven't been able to think of any particularly clever
@@ -614,91 +2269,75 @@ static char *new_game_desc(const game_params *params, random_state *rs,
* and 26 respectively, which is a lot more sensible.
*/
- do {
- domino_layout_prealloc(w, h, rs, grid, grid2, list);
+ while (1) {
+ alloc_make_layout(as, rs);
+
+ if (diff == DIFF_AMBIGUOUS) {
+ /* Just assign numbers to each domino completely at random. */
+ alloc_trivial(as, rs);
+ } else if (diff < DIFF_HARD) {
+ /* Try to rule out the most common case of a non-unique solution */
+ if (!alloc_try_unique(as, rs))
+ continue;
+ } else {
+ /*
+ * For Hard puzzles and above, we'd like there not to be
+ * any easy toehold to start with.
+ *
+ * Mostly, that's arranged by alloc_try_hard, which will
+ * ensure that no domino starts off with only one
+ * potential placement. But a few other deductions
+ * possible at Basic level can still sneak through the
+ * cracks - for example, if the only two placements of one
+ * domino overlap in a square, and you therefore rule out
+ * some other domino that can use that square, you might
+ * then find that _that_ domino now has only one
+ * placement, and you've made a start.
+ *
+ * Of course, the main difficulty-level check will still
+ * guarantee that you have to do a harder deduction
+ * _somewhere_ in the grid. But it's more elegant if
+ * there's nowhere obvious to get started at all.
+ */
+ int di;
+ bool ok;
- /*
- * Now we have a complete layout covering the whole
- * rectangle with dominoes. So shuffle the actual domino
- * values and fill the rectangle with numbers.
- */
- k = 0;
- for (i = 0; i <= params->n; i++)
- for (j = 0; j <= i; j++) {
- list[k++] = i;
- list[k++] = j;
- }
- shuffle(list, k/2, 2*sizeof(*list), rs);
- j = 0;
- for (i = 0; i < wh; i++)
- if (grid[i] > i) {
- /* Optionally flip the domino round. */
- int flip = -1;
+ if (!alloc_try_hard(as, rs))
+ continue;
- if (params->unique) {
- int t1, t2;
- /*
- * If we're after a unique solution, we can do
- * something here to improve the chances. If
- * we're placing a domino so that it forms a
- * 2x2 rectangle with one we've already placed,
- * and if that domino and this one share a
- * number, we can try not to put them so that
- * the identical numbers are diagonally
- * separated, because that automatically causes
- * non-uniqueness:
- *
- * +---+ +-+-+
- * |2 3| |2|3|
- * +---+ -> | | |
- * |4 2| |4|2|
- * +---+ +-+-+
- */
- t1 = i;
- t2 = grid[i];
- if (t2 == t1 + w) { /* this domino is vertical */
- if (t1 % w > 0 &&/* and not on the left hand edge */
- grid[t1-1] == t2-1 &&/* alongside one to left */
- (grid2[t1-1] == list[j] || /* and has a number */
- grid2[t1-1] == list[j+1] || /* in common */
- grid2[t2-1] == list[j] ||
- grid2[t2-1] == list[j+1])) {
- if (grid2[t1-1] == list[j] ||
- grid2[t2-1] == list[j+1])
- flip = 0;
- else
- flip = 1;
- }
- } else { /* this domino is horizontal */
- if (t1 / w > 0 &&/* and not on the top edge */
- grid[t1-w] == t2-w &&/* alongside one above */
- (grid2[t1-w] == list[j] || /* and has a number */
- grid2[t1-w] == list[j+1] || /* in common */
- grid2[t2-w] == list[j] ||
- grid2[t2-w] == list[j+1])) {
- if (grid2[t1-w] == list[j] ||
- grid2[t2-w] == list[j+1])
- flip = 0;
- else
- flip = 1;
- }
- }
- }
+ solver_setup_grid(sc, as->numbers);
+ if (run_solver(sc, DIFF_BASIC) < 2)
+ continue;
- if (flip < 0)
- flip = random_upto(rs, 2);
+ ok = true;
+ for (di = 0; di < sc->dc; di++)
+ if (sc->dominoes[di].nplacements <= 1) {
+ ok = false;
+ break;
+ }
- grid2[i] = list[j + flip];
- grid2[grid[i]] = list[j + 1 - flip];
- j += 2;
+ if (!ok) {
+ continue;
}
- assert(j == k);
- } while (params->unique && solver(w, h, n, grid2, NULL) > 1);
+ }
+
+ if (diff != DIFF_AMBIGUOUS) {
+ int solver_result;
+ solver_setup_grid(sc, as->numbers);
+ solver_result = run_solver(sc, diff);
+ if (solver_result > 1)
+ continue; /* puzzle couldn't be solved at this difficulty */
+ if (sc->max_diff_used < diff)
+ continue; /* puzzle _could_ be solved at easier difficulty */
+ }
+
+ break;
+ }
#ifdef GENERATION_DIAGNOSTICS
for (j = 0; j < h; j++) {
for (i = 0; i < w; i++) {
- putchar('0' + grid2[j*w+i]);
+ putchar('0' + as->numbers[j*w+i]);
}
putchar('\n');
}
@@ -738,7 +2377,7 @@ static char *new_game_desc(const game_params *params, random_state *rs,
ret = snewn(len+1, char);
j = 0;
for (i = 0; i < wh; i++) {
- k = grid2[i];
+ k = as->numbers[i];
if (k < 10)
ret[j++] = '0' + k;
else
@@ -755,7 +2394,7 @@ static char *new_game_desc(const game_params *params, random_state *rs,
char *auxinfo = snewn(wh+1, char);
for (i = 0; i < wh; i++) {
- int v = grid[i];
+ int v = as->layout[i];
auxinfo[i] = (v == i+1 ? 'L' : v == i-1 ? 'R' :
v == i+w ? 'T' : v == i-w ? 'B' : '.');
}
@@ -764,9 +2403,8 @@ static char *new_game_desc(const game_params *params, random_state *rs,
*aux = auxinfo;
}
- sfree(list);
- sfree(grid2);
- sfree(grid);
+ solver_free_scratch(sc);
+ alloc_free_scratch(as);
return ret;
}
@@ -898,14 +2536,62 @@ static void free_game(game_state *state)
sfree(state);
}
+static char *solution_move_string(struct solver_scratch *sc)
+{
+ char *ret;
+ int retlen, retsize;
+ int i, pass;
+
+ /*
+ * First make a pass putting in edges for -1, then make a pass
+ * putting in dominoes for +1.
+ */
+ retsize = 256;
+ ret = snewn(retsize, char);
+ retlen = sprintf(ret, "S");
+
+ for (pass = 0; pass < 2; pass++) {
+ char type = "ED"[pass];
+
+ for (i = 0; i < sc->pc; i++) {
+ struct solver_placement *p = &sc->placements[i];
+ char buf[80];
+ int extra;
+
+ if (pass == 0) {
+ /* Emit a barrier if this placement is ruled out for
+ * the domino. */
+ if (p->active)
+ continue;
+ } else {
+ /* Emit a domino if this placement is the only one not
+ * ruled out. */
+ if (!p->active || p->domino->nplacements > 1)
+ continue;
+ }
+
+ extra = sprintf(buf, ";%c%d,%d", type,
+ p->squares[0]->index, p->squares[1]->index);
+
+ if (retlen + extra + 1 >= retsize) {
+ retsize = retlen + extra + 256;
+ ret = sresize(ret, retsize, char);
+ }
+ strcpy(ret + retlen, buf);
+ retlen += extra;
+ }
+ }
+
+ return ret;
+}
+
static char *solve_game(const game_state *state, const game_state *currstate,
const char *aux, const char **error)
{
int n = state->params.n, w = n+2, h = n+1, wh = w*h;
- int *placements;
char *ret;
int retlen, retsize;
- int i, v;
+ int i;
char buf[80];
int extra;
@@ -931,38 +2617,11 @@ static char *solve_game(const game_state *state, const game_state *currstate,
}
} else {
-
- placements = snewn(wh*2, int);
- for (i = 0; i < wh*2; i++)
- placements[i] = -3;
- solver(w, h, n, state->numbers->numbers, placements);
-
- /*
- * First make a pass putting in edges for -1, then make a pass
- * putting in dominoes for +1.
- */
- retsize = 256;
- ret = snewn(retsize, char);
- retlen = sprintf(ret, "S");
-
- for (v = -1; v <= +1; v += 2)
- for (i = 0; i < wh*2; i++)
- if (placements[i] == v) {
- int p1 = i / 2;
- int p2 = (i & 1) ? p1+1 : p1+w;
-
- extra = sprintf(buf, ";%c%d,%d",
- (int)(v==-1 ? 'E' : 'D'), p1, p2);
-
- if (retlen + extra + 1 >= retsize) {
- retsize = retlen + extra + 256;
- ret = sresize(ret, retsize, char);
- }
- strcpy(ret + retlen, buf);
- retlen += extra;
- }
-
- sfree(placements);
+ struct solver_scratch *sc = solver_make_scratch(n);
+ solver_setup_grid(sc, state->numbers->numbers);
+ run_solver(sc, DIFFCOUNT);
+ ret = solution_move_string(sc);
+ solver_free_scratch(sc);
}
return ret;
@@ -1770,5 +3429,98 @@ const struct game thegame = {
0, /* flags */
};
+#ifdef STANDALONE_SOLVER
+
+int main(int argc, char **argv)
+{
+ game_params *p;
+ game_state *s, *s2;
+ char *id = NULL, *desc;
+ int maxdiff = DIFFCOUNT;
+ const char *err;
+ bool grade = false, diagnostics = false;
+ struct solver_scratch *sc;
+ int retd;
+
+ while (--argc > 0) {
+ char *p = *++argv;
+ if (!strcmp(p, "-v")) {
+ diagnostics = true;
+ } else if (!strcmp(p, "-g")) {
+ grade = true;
+ } else if (!strncmp(p, "-d", 2) && p[2] && !p[3]) {
+ int i;
+ bool bad = true;
+ for (i = 0; i < lenof(dominosa_diffchars); i++)
+ if (dominosa_diffchars[i] != DIFF_AMBIGUOUS &&
+ dominosa_diffchars[i] == p[2]) {
+ bad = false;
+ maxdiff = i;
+ break;
+ }
+ if (bad) {
+ fprintf(stderr, "%s: unrecognised difficulty `%c'\n",
+ argv[0], p[2]);
+ return 1;
+ }
+ } else if (*p == '-') {
+ fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p);
+ return 1;
+ } else {
+ id = p;
+ }
+ }
+
+ if (!id) {
+ fprintf(stderr, "usage: %s [-v | -g] <game_id>\n", argv[0]);
+ return 1;
+ }
+
+ desc = strchr(id, ':');
+ if (!desc) {
+ fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+ return 1;
+ }
+ *desc++ = '\0';
+
+ p = default_params();
+ decode_params(p, id);
+ err = validate_desc(p, desc);
+ if (err) {
+ fprintf(stderr, "%s: %s\n", argv[0], err);
+ return 1;
+ }
+ s = new_game(NULL, p, desc);
+
+ solver_diagnostics = diagnostics;
+ sc = solver_make_scratch(p->n);
+ solver_setup_grid(sc, s->numbers->numbers);
+ retd = run_solver(sc, maxdiff);
+ if (retd == 0) {
+ printf("Puzzle is inconsistent\n");
+ } else if (grade) {
+ printf("Difficulty rating: %s\n",
+ dominosa_diffnames[sc->max_diff_used]);
+ } else {
+ char *move, *text;
+ move = solution_move_string(sc);
+ s2 = execute_move(s, move);
+ text = game_text_format(s2);
+ sfree(move);
+ fputs(text, stdout);
+ sfree(text);
+ free_game(s2);
+ if (retd > 1)
+ printf("Could not deduce a unique solution\n");
+ }
+ solver_free_scratch(sc);
+ free_game(s);
+ free_params(p);
+
+ return 0;
+}
+
+#endif
+
/* vim: set shiftwidth=4 :set textwidth=80: */
diff --git a/apps/plugins/puzzles/src/emccpre.js b/apps/plugins/puzzles/src/emccpre.js
index 5082555617..56f69721f7 100644
--- a/apps/plugins/puzzles/src/emccpre.js
+++ b/apps/plugins/puzzles/src/emccpre.js
@@ -212,28 +212,51 @@ function initPuzzle() {
// button down (our puzzles don't want those events).
mousedown = Module.cwrap('mousedown', 'void',
['number', 'number', 'number']);
- buttons_down = 0;
+
+ button_phys2log = [null, null, null];
+ buttons_down = function() {
+ var i, toret = 0;
+ for (i = 0; i < 3; i++)
+ if (button_phys2log[i] !== null)
+ toret |= 1 << button_phys2log[i];
+ return toret;
+ };
+
onscreen_canvas.onmousedown = function(event) {
+ if (event.button >= 3)
+ return;
+
var xy = relative_mouse_coords(event, onscreen_canvas);
- mousedown(xy.x, xy.y, event.button);
- buttons_down |= 1 << event.button;
+ var logbutton = event.button;
+ if (event.shiftKey)
+ logbutton = 1; // Shift-click overrides to middle button
+ else if (event.ctrlKey)
+ logbutton = 2; // Ctrl-click overrides to right button
+
+ mousedown(xy.x, xy.y, logbutton);
+ button_phys2log[event.button] = logbutton;
+
onscreen_canvas.setCapture(true);
};
mousemove = Module.cwrap('mousemove', 'void',
['number', 'number', 'number']);
onscreen_canvas.onmousemove = function(event) {
- if (buttons_down) {
+ var down = buttons_down();
+ if (down) {
var xy = relative_mouse_coords(event, onscreen_canvas);
- mousemove(xy.x, xy.y, buttons_down);
+ mousemove(xy.x, xy.y, down);
}
};
mouseup = Module.cwrap('mouseup', 'void',
['number', 'number', 'number']);
onscreen_canvas.onmouseup = function(event) {
- if (buttons_down & (1 << event.button)) {
- buttons_down ^= 1 << event.button;
+ if (event.button >= 3)
+ return;
+
+ if (button_phys2log[event.button] !== null) {
var xy = relative_mouse_coords(event, onscreen_canvas);
- mouseup(xy.x, xy.y, event.button);
+ mouseup(xy.x, xy.y, button_phys2log[event.button]);
+ button_phys2log[event.button] = null;
}
};
diff --git a/apps/plugins/puzzles/src/findloop.c b/apps/plugins/puzzles/src/findloop.c
index ffda12d716..4ebdea1f85 100644
--- a/apps/plugins/puzzles/src/findloop.c
+++ b/apps/plugins/puzzles/src/findloop.c
@@ -14,7 +14,7 @@
#include "puzzles.h"
struct findloopstate {
- int parent, child, sibling;
+ int parent, child, sibling, component_root;
bool visited;
int index, minindex, maxindex;
int minreachable, maxreachable;
@@ -57,6 +57,33 @@ bool findloop_is_loop_edge(struct findloopstate *pv, int u, int v)
return !(pv[u].bridge == v || pv[v].bridge == u);
}
+static bool findloop_is_bridge_oneway(
+ struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)
+{
+ int r, total, below;
+
+ if (pv[u].bridge != v)
+ return false;
+
+ r = pv[u].component_root;
+ total = pv[r].maxindex - pv[r].minindex + 1;
+ below = pv[u].maxindex - pv[u].minindex + 1;
+
+ if (u_vertices)
+ *u_vertices = below;
+ if (v_vertices)
+ *v_vertices = total - below;
+
+ return true;
+}
+
+bool findloop_is_bridge(
+ struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices)
+{
+ return (findloop_is_bridge_oneway(pv, u, v, u_vertices, v_vertices) ||
+ findloop_is_bridge_oneway(pv, v, u, v_vertices, u_vertices));
+}
+
bool findloop_run(struct findloopstate *pv, int nvertices,
neighbour_fn_t neighbour, void *ctx)
{
@@ -94,6 +121,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices,
*/
pv[v].sibling = pv[root].child;
pv[root].child = v;
+ pv[v].component_root = v;
debug(("%d is new child of root\n", v));
u = v;
@@ -116,6 +144,7 @@ bool findloop_run(struct findloopstate *pv, int nvertices,
pv[w].child = -1;
pv[w].sibling = pv[u].child;
pv[w].parent = u;
+ pv[w].component_root = pv[u].component_root;
pv[u].child = w;
}
diff --git a/apps/plugins/puzzles/src/galaxies.c b/apps/plugins/puzzles/src/galaxies.c
index 0cc3198ae0..fe7cd24ecf 100644
--- a/apps/plugins/puzzles/src/galaxies.c
+++ b/apps/plugins/puzzles/src/galaxies.c
@@ -346,29 +346,44 @@ static void add_assoc(const game_state *state, space *tile, space *dot) {
tile->x, tile->y, dot->x, dot->y, dot->nassoc));*/
}
-static void add_assoc_with_opposite(game_state *state, space *tile, space *dot) {
+static bool ok_to_add_assoc_with_opposite_internal(
+ const game_state *state, space *tile, space *opposite)
+{
int *colors;
- space *opposite = space_opposite_dot(state, tile, dot);
+ bool toret;
- if (opposite == NULL) {
- return;
- }
- if (opposite->flags & F_DOT) {
- return;
- }
+ if (tile->flags & F_DOT)
+ return false;
+ if (opposite == NULL)
+ return false;
+ if (opposite->flags & F_DOT)
+ return false;
+ toret = true;
colors = snewn(state->w * state->h, int);
check_complete(state, NULL, colors);
- if (colors[(tile->y - 1)/2 * state->w + (tile->x - 1)/2]) {
- sfree(colors);
- return;
- }
- if (colors[(opposite->y - 1)/2 * state->w + (opposite->x - 1)/2]) {
- sfree(colors);
- return;
- }
+
+ if (colors[(tile->y - 1)/2 * state->w + (tile->x - 1)/2])
+ toret = false;
+ if (colors[(opposite->y - 1)/2 * state->w + (opposite->x - 1)/2])
+ toret = false;
sfree(colors);
+ return toret;
+}
+
+static bool ok_to_add_assoc_with_opposite(
+ const game_state *state, space *tile, space *dot)
+{
+ space *opposite = space_opposite_dot(state, tile, dot);
+ return ok_to_add_assoc_with_opposite_internal(state, tile, opposite);
+}
+
+static void add_assoc_with_opposite(game_state *state, space *tile, space *dot) {
+ space *opposite = space_opposite_dot(state, tile, dot);
+
+ assert(ok_to_add_assoc_with_opposite_internal(state, tile, opposite));
+
remove_assoc_with_opposite(state, tile);
add_assoc(state, tile, dot);
remove_assoc_with_opposite(state, opposite);
@@ -2596,8 +2611,15 @@ static char *interpret_move(const game_state *state, game_ui *ui,
*/
if (INUI(state, px, py)) {
sp = &SPACE(state, px, py);
+ dot = &SPACE(state, ui->dotx, ui->doty);
- if (!(sp->flags & F_DOT))
+ /*
+ * Exception: if it's not actually legal to add an arrow
+ * and its opposite at this position, we don't try,
+ * because otherwise we'd append an empty entry to the
+ * undo chain.
+ */
+ if (ok_to_add_assoc_with_opposite(state, sp, dot))
sprintf(buf + strlen(buf), "%sA%d,%d,%d,%d",
sep, px, py, ui->dotx, ui->doty);
}
diff --git a/apps/plugins/puzzles/src/midend.c b/apps/plugins/puzzles/src/midend.c
index 036c8569c7..a8dd179690 100644
--- a/apps/plugins/puzzles/src/midend.c
+++ b/apps/plugins/puzzles/src/midend.c
@@ -171,6 +171,8 @@ midend *midend_new(frontend *fe, const game *ourgame,
me->params = ourgame->default_params();
me->game_id_change_notify_function = NULL;
me->game_id_change_notify_ctx = NULL;
+ me->encoded_presets = NULL;
+ me->n_encoded_presets = 0;
/*
* Allow environment-based changing of the default settings by
@@ -261,8 +263,13 @@ static void midend_free_preset_menu(midend *me, struct preset_menu *menu)
void midend_free(midend *me)
{
+ int i;
+
midend_free_game(me);
+ for (i = 0; i < me->n_encoded_presets; i++)
+ sfree(me->encoded_presets[i]);
+ sfree(me->encoded_presets);
if (me->drawing)
drawing_free(me->drawing);
random_free(me->random);
diff --git a/apps/plugins/puzzles/src/pegs.c b/apps/plugins/puzzles/src/pegs.c
index 32673d56e7..db9caf298f 100644
--- a/apps/plugins/puzzles/src/pegs.c
+++ b/apps/plugins/puzzles/src/pegs.c
@@ -792,6 +792,12 @@ static void game_changed_state(game_ui *ui, const game_state *oldstate,
* unoccupied.
*/
ui->dragging = false;
+
+ /*
+ * Also, cancel a keyboard-driven jump if one is half way to being
+ * input.
+ */
+ ui->cur_jumping = false;
}
#define PREFERRED_TILE_SIZE 33
diff --git a/apps/plugins/puzzles/src/puzzles.h b/apps/plugins/puzzles/src/puzzles.h
index 48d3d83b6e..1732abe3e9 100644
--- a/apps/plugins/puzzles/src/puzzles.h
+++ b/apps/plugins/puzzles/src/puzzles.h
@@ -595,6 +595,32 @@ bool findloop_run(struct findloopstate *state, int nvertices,
bool findloop_is_loop_edge(struct findloopstate *state, int u, int v);
/*
+ * Alternative query function, which returns true if the u-v edge is a
+ * _bridge_, i.e. a non-loop edge, i.e. an edge whose removal would
+ * disconnect a currently connected component of the graph.
+ *
+ * If the return value is true, then the numbers of vertices that
+ * would be in the new components containing u and v are written into
+ * u_vertices and v_vertices respectively.
+ */
+bool findloop_is_bridge(
+ struct findloopstate *pv, int u, int v, int *u_vertices, int *v_vertices);
+
+/*
+ * Helper function to sort an array. Differs from standard qsort in
+ * that it takes a context parameter that is passed to the compare
+ * function.
+ *
+ * I wrap it in a macro so that you only need to give the element
+ * count of the array. The element size is determined by sizeof.
+ */
+typedef int (*arraysort_cmpfn_t)(const void *av, const void *bv, void *ctx);
+void arraysort_fn(void *array, size_t nmemb, size_t size,
+ arraysort_cmpfn_t cmp, void *ctx);
+#define arraysort(array, nmemb, cmp, ctx) \
+ arraysort_fn(array, nmemb, sizeof(*(array)), cmp, ctx)
+
+/*
* Data structure containing the function calls and data specific
* to a particular game. This is enclosed in a data structure so
* that a particular platform can choose, if it wishes, to compile
diff --git a/apps/plugins/puzzles/src/sort.c b/apps/plugins/puzzles/src/sort.c
new file mode 100644
index 0000000000..d1897b6fdf
--- /dev/null
+++ b/apps/plugins/puzzles/src/sort.c
@@ -0,0 +1,160 @@
+/*
+ * Implement arraysort() defined in puzzles.h.
+ *
+ * Strategy: heapsort.
+ */
+
+#include <stddef.h>
+#include <string.h>
+
+#include "puzzles.h"
+
+static void memswap(void *av, void *bv, size_t size)
+{
+ char t[4096];
+ char *a = (char *)av, *b = (char *)bv;
+
+ while (size > 0) {
+ size_t thissize = size < sizeof(t) ? size : sizeof(t);
+
+ memcpy(t, a, thissize);
+ memcpy(a, b, thissize);
+ memcpy(b, t, thissize);
+
+ size -= thissize;
+ a += thissize;
+ b += thissize;
+ }
+}
+
+#define PTR(i) ((char *)array + size * (i))
+#define SWAP(i,j) memswap(PTR(i), PTR(j), size)
+#define CMP(i,j) cmp(PTR(i), PTR(j), ctx)
+
+#define LCHILD(i) (2*(i)+1)
+#define RCHILD(i) (2*(i)+2)
+#define PARENT(i) (((i)-1)/2)
+
+static void downheap(void *array, size_t nmemb, size_t size,
+ arraysort_cmpfn_t cmp, void *ctx, size_t i)
+{
+ while (LCHILD(i) < nmemb) {
+ /* Identify the smallest element out of i and its children. */
+ size_t j = i;
+ if (CMP(j, LCHILD(i)) < 0)
+ j = LCHILD(i);
+ if (RCHILD(i) < nmemb &&
+ CMP(j, RCHILD(i)) < 0)
+ j = RCHILD(i);
+
+ if (j == i)
+ return; /* smallest element is already where it should be */
+
+ SWAP(j, i);
+ i = j;
+ }
+}
+
+void arraysort_fn(void *array, size_t nmemb, size_t size,
+ arraysort_cmpfn_t cmp, void *ctx)
+{
+ size_t i;
+
+ if (nmemb < 2)
+ return; /* trivial */
+
+ /*
+ * Stage 1: build the heap.
+ *
+ * Linear-time if we do it by downheaping the elements in
+ * decreasing order of index, instead of the more obvious approach
+ * of upheaping in increasing order. (Also, it means we don't need
+ * the upheap function at all.)
+ *
+ * We don't need to downheap anything in the second half of the
+ * array, because it can't have any children to swap with anyway.
+ */
+ for (i = PARENT(nmemb-1) + 1; i-- > 0 ;)
+ downheap(array, nmemb, size, cmp, ctx, i);
+
+ /*
+ * Stage 2: dismantle the heap by repeatedly swapping the root
+ * element (at index 0) into the last position and then
+ * downheaping the new root.
+ */
+ for (i = nmemb-1; i > 0; i--) {
+ SWAP(0, i);
+ downheap(array, i, size, cmp, ctx, 0);
+ }
+}
+
+#ifdef SORT_TEST
+
+#include <stdlib.h>
+#include <time.h>
+
+int testcmp(const void *av, const void *bv, void *ctx)
+{
+ int a = *(const int *)av, b = *(const int *)bv;
+ const int *keys = (const int *)ctx;
+ return keys[a] < keys[b] ? -1 : keys[a] > keys[b] ? +1 : 0;
+}
+
+int resetcmp(const void *av, const void *bv)
+{
+ int a = *(const int *)av, b = *(const int *)bv;
+ return a < b ? -1 : a > b ? +1 : 0;
+}
+
+int main(int argc, char **argv)
+{
+ typedef int Array[3723];
+ Array data, keys;
+ int iteration;
+ unsigned seed;
+
+ seed = (argc > 1 ? strtoul(argv[1], NULL, 0) : time(NULL));
+ printf("Random seed = %u\n", seed);
+ srand(seed);
+
+ for (iteration = 0; iteration < 10000; iteration++) {
+ int j;
+ const char *fail = NULL;
+
+ for (j = 0; j < lenof(data); j++) {
+ data[j] = j;
+ keys[j] = rand();
+ }
+
+ arraysort(data, lenof(data), testcmp, keys);
+
+ for (j = 1; j < lenof(data); j++) {
+ if (keys[data[j]] < keys[data[j-1]])
+ fail = "output misordered";
+ }
+ if (!fail) {
+ Array reset;
+ memcpy(reset, data, sizeof(data));
+ qsort(reset, lenof(reset), sizeof(*reset), resetcmp);
+ for (j = 0; j < lenof(reset); j++)
+ if (reset[j] != j)
+ fail = "output not permuted";
+ }
+
+ if (fail) {
+ printf("Failed at iteration %d: %s\n", iteration, fail);
+ printf("Key values:\n");
+ for (j = 0; j < lenof(keys); j++)
+ printf(" [%2d] %10d\n", j, keys[j]);
+ printf("Output sorted order:\n");
+ for (j = 0; j < lenof(data); j++)
+ printf(" [%2d] %10d\n", data[j], keys[data[j]]);
+ return 1;
+ }
+ }
+
+ printf("OK\n");
+ return 0;
+}
+
+#endif /* SORT_TEST */