ref: 1dfc38c2ec40e726d7dd764cd0176e3bdf5ff008
parent: 28aefee8fceeb8bd5ea6106eef986284583788dd
author: Simon Tatham <anakin@pobox.com>
date: Sun Mar 12 07:08:26 EDT 2023
Galaxies: new deduction by counting liberties of exclaves.
I've often noticed that Galaxies on 7x7 Unreasonable often generates
puzzles that _I_ don't feel as if I had to use recursion and
backtracking to solve, suggesting that there's an efficient mode of
reasoning available that the puzzle could be using and isn't.
One reason for this is that sometimes Galaxies gives up on trying to
generate an Unreasonable puzzle (if its MAXTRIES counter runs out) and
knowingly falls back to Normal. But that's not the only reason. The
other day I got the puzzle 7x7:gsjgzhfedwgzhd, which Galaxies's own
solver rates as Unreasonable, and I still think it should be Normal.
The full solution to that puzzle is this:
+-+-+-+-+-+-+-+
|y x| o | | |
+ +-+-+-+-+ +o+
| | | | o | |
+ + o + + +-+-+
| | | | | | |
+ +-+-+ +-+o+ +
| o |o| |o|
+ +-+-+ +-+-+ +
| | | | o | |
+ + o + +-+-+-+
| | | | |
+-+-+-+ + +o+ +
| o |x y| |
+-+-+-+-+-+-+-+
and Galaxies's Normal-mode solver gets stuck on it at the point where
it's managed to deduce that the tiles labelled 'x' can't possibly be
associated with any dot other than leftmost dot on the centre row, but
is then unable to figure out that the tiles labelled 'y' must also be
associated with that dot. But clearly they must, because they're boxed
in on all other sides (by the grid edge, and by tiles whose
associations are totally obvious), so if either 'x' tile is to find
_any_ path back to its home dot, it must go through the neighbouring
'y' tile.
So, this commit adds the missing deduction: we use a dsf to identify
'exclaves' (connected sets of tiles all associated to the same dot,
but which do not actually contain the dot), and for each exclave we
count its 'liberties' (unassociated tiles bordering the exclave, i.e.
which would extend the exclave if associated to the same dot). Any
exclave with only one liberty must extend into that tile, or else it
would be cut off completely from its home dot. In this case, each 'x'
tile is an exclave by itself, with 'y' its only liberty. (And once
that deduction is done, the pair {x,y} become a larger exclave, which
can be deduced in the same way to connect to the next tile.)
I think this is a deduction rule simple and obvious enough that it
should go in at Normal mode. I've been using it all along in my own
play, and was surprised to find the game wasn't already taking it into
account. In addition, in a quick cross-test of the two versions,
_most_ 7x7 Normal games generated by the modified Galaxies are still
rated as Normal by the old less powerful solver. So it doesn't extend
the difficulty of Normal mode by very much, if at all.
Another benefit is that this should make Normal puzzles more likely to
contain twisty regions of this type.
Also, of course, the usual effect of adding extra deductions at levels
below Unreasonable means that actually Unreasonable puzzles become
that much more tricky!
I have a couple of ideas for extending this technique to be more
powerful still (filled in as comments at the top of the file). For the
moment, I've just done the most obvious version. Perhaps the others
might need to go in at a higher difficulty level.
--- a/galaxies.c
+++ b/galaxies.c
@@ -13,10 +13,47 @@
* Edges have on/off state; obviously the actual edges of the
* board are fixed to on, and everything else starts as off.
*
- * TTD:
- * Cleverer solver
- * Think about how to display remote groups of tiles?
+ * Future solver directions:
*
+ * - Non-local version of the exclave extension? Suppose you have an
+ * exclave with multiple potential paths back home, but all of them
+ * go through the same tile somewhere in the middle of the path.
+ * Then _that_ critical square can be assigned to the home dot,
+ * even if we don't yet know the details of the path from it to
+ * either existing region.
+ *
+ * - Permit non-simply-connected puzzle instances in sub-Unreasonable
+ * mode? Even the simplest case 5x3:ubb is graded Unreasonable at
+ * present, because we have no solution technique short of
+ * recursion that can handle it.
+ *
+ * The reasoning a human uses for that puzzle is to observe that
+ * the centre left square has to connect to the centre dot, so it
+ * must have _some_ path back there. It could go round either side
+ * of the dot in the way. But _whichever_ way it goes, that rules
+ * out the left dot extending to the squares above and below it,
+ * because if it did that, that would block _both_ routes back to
+ * the centre.
+ *
+ * But the exclave-extending deduction we have at present is only
+ * capable of extending an exclave with _one_ liberty. This has
+ * two, so the only technique we have available is to try them one
+ * by one via recursion.
+ *
+ * My vague plan to fix this would be to re-run the exclave
+ * extension on a per-dot basis (probably after working out a
+ * non-local version as described above): instead of trying to find
+ * all exclaves at once, try it for one exclave at a time, or
+ * perhaps all exclaves relating to a particular home dot H. The
+ * point of this is that then you could spot pairs of squares with
+ * _two_ possible dots, one of which is H, and which are opposite
+ * to each other with respect to their other dot D (such as the
+ * squares above/below the left dot in this example). And then you
+ * merge those into one vertex of the connectivity graph, on the
+ * grounds that they're either both H or both D - and _then_ you
+ * have an exclave with only one path back home, and can make
+ * progress.
+ *
* Bugs:
*
* Notable puzzle IDs:
@@ -1682,7 +1719,8 @@
game_state *state;
int sz; /* state->sx * state->sy */
space **scratch; /* size sz */
-
+ int *dsf; /* size sz */
+ int *iscratch; /* size sz */
} solver_ctx;
static solver_ctx *new_solver(game_state *state)
@@ -1691,6 +1729,8 @@
sctx->state = state;
sctx->sz = state->sx*state->sy;
sctx->scratch = snewn(sctx->sz, space *);
+ sctx->dsf = snew_dsf(sctx->sz);
+ sctx->iscratch = snewn(sctx->sz, int);
return sctx;
}
@@ -1697,6 +1737,8 @@
static void free_solver(solver_ctx *sctx)
{sfree(sctx->scratch);
+ sfree(sctx->dsf);
+ sfree(sctx->iscratch);
sfree(sctx);
}
@@ -2150,6 +2192,177 @@
return foreach_tile(state, solver_expand_postcb, IMPOSSIBLE_QUITS, sctx);
}
+static int solver_extend_exclaves(game_state *state, solver_ctx *sctx)
+{+ int x, y, done_something = 0;
+
+ /*
+ * Make a dsf by unifying any two adjacent tiles associated with
+ * the same dot. This will identify separate connected components
+ * of the tiles belonging to a given dot. Any such component that
+ * doesn't contain its own dot is an 'exclave', and will need some
+ * kind of path of tiles to connect it back to the dot.
+ */
+ dsf_init(sctx->dsf, sctx->sz);
+ for (x = 1; x < state->sx; x += 2) {+ for (y = 1; y < state->sy; y += 2) {+ int dotx, doty;
+ space *tile, *othertile;
+
+ tile = &SPACE(state, x, y);
+ if (!(tile->flags & F_TILE_ASSOC))
+ continue; /* not associated with any dot */
+ dotx = tile->dotx;
+ doty = tile->doty;
+
+ if (INGRID(state, x+2, y)) {+ othertile = &SPACE(state, x+2, y);
+ if ((othertile->flags & F_TILE_ASSOC) &&
+ othertile->dotx == dotx && othertile->doty == doty)
+ dsf_merge(sctx->dsf, y*state->sx+x, y*state->sx+(x+2));
+ }
+
+ if (INGRID(state, x, y+2)) {+ othertile = &SPACE(state, x, y+2);
+ if ((othertile->flags & F_TILE_ASSOC) &&
+ othertile->dotx == dotx && othertile->doty == doty)
+ dsf_merge(sctx->dsf, y*state->sx+x, (y+2)*state->sx+x);
+ }
+ }
+ }
+
+ /*
+ * Go through the grid again, and count the 'liberties' of each
+ * connected component, in the Go sense, i.e. the number of
+ * currently unassociated squares adjacent to the component. The
+ * idea is that if an exclave has just one liberty, then that
+ * square _must_ extend the exclave, or else it will be completely
+ * cut off from connecting back to its home dot.
+ *
+ * We need to count each adjacent square just once, even if it
+ * borders the component on multiple edges. So we'll go through
+ * each unassociated square, check all four of its neighbours, and
+ * de-duplicate them.
+ *
+ * We'll store the count of liberties in the entry of iscratch
+ * corresponding to the square centre (i.e. with odd coordinates).
+ * Every time we find a liberty, we store its index in the square
+ * to the left of that, so that when a component has exactly one
+ * liberty we can remember what it was.
+ *
+ * Square centres that are not the canonical dsf element of a
+ * connected component will get their liberty count set to -1,
+ * which will allow us to identify them in the later loop (after
+ * we start making changes and need to spot that an associated
+ * square _now_ was not associated when the dsf was built).
+ */
+
+ /* Initialise iscratch */
+ for (x = 1; x < state->sx; x += 2) {+ for (y = 1; y < state->sy; y += 2) {+ int index = y * state->sx + x;
+ if (!(SPACE(state, x, y).flags & F_TILE_ASSOC) ||
+ dsf_canonify(sctx->dsf, index) != index) {+ sctx->iscratch[index] = -1; /* mark as not a component */
+ } else {+ sctx->iscratch[index] = 0; /* zero liberty count */
+ sctx->iscratch[index-1] = 0; /* initialise neighbour id */
+ }
+ }
+ }
+
+ /* Find each unassociated square and see what it's a liberty of */
+ for (x = 1; x < state->sx; x += 2) {+ for (y = 1; y < state->sy; y += 2) {+ int dx, dy, ni[4], nn, i;
+
+ if ((SPACE(state, x, y).flags & F_TILE_ASSOC))
+ continue; /* not an unassociated square */
+
+ /* Find distinct indices of adjacent components */
+ nn = 0;
+ for (dx = -1; dx <= 1; dx++) {+ for (dy = -1; dy <= 1; dy++) {+ if (dx != 0 && dy != 0) continue;
+ if (dx == 0 && dy == 0) continue;
+
+ if (INGRID(state, x+2*dx, y+2*dy) &&
+ (SPACE(state, x+2*dx, y+2*dy).flags & F_TILE_ASSOC)) {+ /* Find id of the component adjacent to x,y */
+ int nindex = (y+2*dy) * state->sx + (x+2*dx);
+ nindex = dsf_canonify(sctx->dsf, nindex);
+
+ /* See if we've seen it before in another direction */
+ for (i = 0; i < nn; i++)
+ if (ni[i] == nindex)
+ break;
+ if (i == nn) {+ /* No, it's new. Mark x,y as a liberty of it */
+ sctx->iscratch[nindex]++;
+ assert(nindex > 0);
+ sctx->iscratch[nindex-1] = y * state->sx + x;
+
+ /* And record this component as having been seen */
+ ni[nn++] = nindex;
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /*
+ * Now we have all the data we need to find exclaves with exactly
+ * one liberty. In each case, associate the unique liberty square
+ * with the same dot.
+ */
+ for (x = 1; x < state->sx; x += 2) {+ for (y = 1; y < state->sy; y += 2) {+ int index, dotx, doty, ex, ey, added;
+ space *tile;
+
+ index = y*state->sx+x;
+ if (sctx->iscratch[index] == -1)
+ continue; /* wasn't canonical when dsf was built */
+
+ tile = &SPACE(state, x, y);
+ if (!(tile->flags & F_TILE_ASSOC))
+ continue; /* not associated with any dot */
+ dotx = tile->dotx;
+ doty = tile->doty;
+
+ if (index == dsf_canonify(
+ sctx->dsf, (doty | 1) * state->sx + (dotx | 1)))
+ continue; /* not an exclave - contains its own dot */
+
+ if (sctx->iscratch[index] == 0) {+ solvep(("%*sExclave at %d,%d has no liberties!\n",+ solver_recurse_depth*4, "", x, y));
+ return -1;
+ }
+
+ if (sctx->iscratch[index] != 1)
+ continue; /* more than one liberty, can't be sure which */
+
+ assert(sctx->iscratch[index-1] != 0);
+ ex = sctx->iscratch[index-1] % state->sx;
+ ey = sctx->iscratch[index-1] / state->sx;
+ tile = &SPACE(state, ex, ey);
+ if (tile->flags & F_TILE_ASSOC)
+ continue; /* already done by earlier iteration of this loop */
+
+ added = solver_add_assoc(state, tile, dotx, doty,
+ "to connect exclave");
+ if (added < 0)
+ return -1;
+ if (added > 0)
+ done_something = 1;
+ }
+ }
+
+ return done_something;
+}
+
struct recurse_ctx {space *best;
int bestn;
@@ -2298,6 +2511,9 @@
CHECKRET(DIFF_NORMAL);
ret = solver_expand_dots(state, sctx);
+ CHECKRET(DIFF_NORMAL);
+
+ ret = solver_extend_exclaves(state, sctx);
CHECKRET(DIFF_NORMAL);
if (maxdiff <= DIFF_NORMAL)