typedef unsigned int grid_type; /* change me later if we invent > 16 bits of flags. */
struct solver_state {
- int *dsf, *tmpdsf;
+ int *dsf, *comptspaces;
+ int *tmpdsf, *tmpcompspaces;
int refcount;
};
{
int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc;
int i, poss;
- grid_type v;
struct island *is_orth;
if (nspc < 0) {
int ifree, dx = is->adj.points[i].dx;
if (!is->adj.points[i].off) continue;
- v = GRID(is->state, is->adj.points[i].x, is->adj.points[i].y);
poss = POSSIBLES(is->state, dx,
is->adj.points[i].x, is->adj.points[i].y);
if (poss == 0) continue;
assert(is_orth);
ifree = is_orth->count - island_countbridges(is_orth);
- if (ifree > 0)
- nsurrspc += min(ifree, MAXIMUM(is->state, dx,
- is->adj.points[i].x, is->adj.points[i].y));
+ if (ifree > 0) {
+ /*
+ * ifree is the number of bridges unfilled in the other
+ * island, which is clearly an upper bound on the number
+ * of extra bridges this island may run to it.
+ *
+ * Another upper bound is the number of bridges unfilled
+ * on the specific line between here and there. We must
+ * take the minimum of both.
+ */
+ int bmax = MAXIMUM(is->state, dx,
+ is->adj.points[i].x, is->adj.points[i].y);
+ int bcurr = GRIDCOUNT(is->state,
+ is->adj.points[i].x, is->adj.points[i].y,
+ dx ? G_LINEH : G_LINEV);
+ assert(bcurr <= bmax);
+ nsurrspc += min(ifree, bmax - bcurr);
+ }
}
if (nsurrspc < nspc) {
debug(("island at (%d,%d) impossible: surr. islands %d spc, need %d.\n",
/* Unset possible flags until we find an island. */
for (y = 0; y < state->h; y++) {
is_s = IDX(state, gridi, idx);
- if (is_s) break;
+ if (is_s) {
+ maxb = is_s->count;
+ break;
+ }
IDX(state, possv, idx) = 0;
idx += w;
}
for (; y < state->h; y++) {
+ maxb = min(maxb, IDX(state, maxv, idx));
is_f = IDX(state, gridi, idx);
if (is_f) {
assert(is_s);
- maxb = IDX(state, maxv, idx);
- np = min(maxb, min(is_s->count, is_f->count));
+ np = min(maxb, is_f->count);
if (s != -1) {
for (i = s; i <= e; i++) {
s = y+1;
bl = 0;
is_s = is_f;
+ maxb = is_s->count;
} else {
e = y;
if (IDX(state,grid,idx) & (G_LINEH|G_NOLINEV)) bl = 1;
bl = 0;
for (x = 0; x < state->w; x++) {
is_s = IDX(state, gridi, idx);
- if (is_s) break;
+ if (is_s) {
+ maxb = is_s->count;
+ break;
+ }
IDX(state, possh, idx) = 0;
idx += 1;
}
for (; x < state->w; x++) {
+ maxb = min(maxb, IDX(state, maxh, idx));
is_f = IDX(state, gridi, idx);
if (is_f) {
assert(is_s);
- maxb = IDX(state, maxh, idx);
- np = min(maxb, min(is_s->count, is_f->count));
+ np = min(maxb, is_f->count);
if (s != -1) {
for (i = s; i <= e; i++) {
s = x+1;
bl = 0;
is_s = is_f;
+ maxb = is_s->count;
} else {
e = x;
if (IDX(state,grid,idx) & (G_LINEV|G_NOLINEH)) bl = 1;
return 0;
}
- is_join = INDEX(state, gridi,
- ISLAND_ORTHX(is, direction),
- ISLAND_ORTHY(is, direction));
- assert(is_join);
+ if (direction >= 0) {
+ is_join = INDEX(state, gridi,
+ ISLAND_ORTHX(is, direction),
+ ISLAND_ORTHY(is, direction));
+ assert(is_join);
- /* if is_join isn't full, return 0. */
- if (island_countbridges(is_join) < is_join->count) {
- debug(("...dest island (%d,%d) not full.\n", is_join->x, is_join->y));
- return 0;
+ /* if is_join isn't full, return 0. */
+ if (island_countbridges(is_join) < is_join->count) {
+ debug(("...dest island (%d,%d) not full.\n",
+ is_join->x, is_join->y));
+ return 0;
+ }
}
/* Check group membership for is->dsf; if it's full return 1. */
if (maxb == 0) {
debug(("...adding NOLINE.\n"));
solve_join(is, i, -1, 0); /* we can't have any bridges here. */
- didsth = 1;
} else {
debug(("...setting maximum\n"));
solve_join(is, i, maxb, 1);
}
+ didsth = 1;
+ }
+ map_update_possibles(is->state);
+ }
+
+ for (i = 0; i < is->adj.npoints; i++) {
+ /*
+ * Now check to see if any currently empty direction must have
+ * at least one bridge in order to avoid forming an isolated
+ * subgraph. This differs from the check above in that it
+ * considers multiple target islands. For example:
+ *
+ * 2 2 4
+ * 1 3 2
+ * 3
+ * 4
+ *
+ * The example on the left can be handled by the above loop:
+ * it will observe that connecting the central 2 twice to the
+ * left would form an isolated subgraph, and hence it will
+ * restrict that 2 to at most one bridge in that direction.
+ * But the example on the right won't be handled by that loop,
+ * because the deduction requires us to imagine connecting the
+ * 3 to _both_ the 1 and 2 at once to form an isolated
+ * subgraph.
+ *
+ * This pass is necessary _as well_ as the above one, because
+ * neither can do the other's job. In the left one,
+ * restricting the direction which _would_ cause trouble can
+ * be done even if it's not yet clear which of the remaining
+ * directions has to have a compensatory bridge; whereas the
+ * pass below that can handle the right-hand example does need
+ * to know what direction to point the necessary bridge in.
+ *
+ * Neither pass can handle the most general case, in which we
+ * observe that an arbitrary subset of an island's neighbours
+ * would form an isolated subgraph with it if it connected
+ * maximally to them, and hence that at least one bridge must
+ * point to some neighbour outside that subset but we don't
+ * know which neighbour. To handle that, we'd have to have a
+ * richer data format for the solver, which could cope with
+ * recording the idea that at least one of two edges must have
+ * a bridge.
+ */
+ int got = 0;
+ int before[4];
+ int j;
+
+ spc = island_adjspace(is, 1, missing, i);
+ if (spc == 0) continue;
+
+ for (j = 0; j < is->adj.npoints; j++)
+ before[j] = GRIDCOUNT(is->state,
+ is->adj.points[j].x,
+ is->adj.points[j].y,
+ is->adj.points[j].dx ? G_LINEH : G_LINEV);
+ if (before[i] != 0) continue; /* this idea is pointless otherwise */
+
+ memcpy(ss->tmpdsf, ss->dsf, wh*sizeof(int));
+
+ for (j = 0; j < is->adj.npoints; j++) {
+ spc = island_adjspace(is, 1, missing, j);
+ if (spc == 0) continue;
+ if (j == i) continue;
+ solve_join(is, j, before[j] + spc, 0);
}
map_update_possibles(is->state);
+
+ if (solve_island_subgroup(is, -1, n))
+ got = 1;
+
+ for (j = 0; j < is->adj.npoints; j++)
+ solve_join(is, j, before[j], 0);
+ memcpy(ss->dsf, ss->tmpdsf, wh*sizeof(int));
+
+ if (got) {
+ debug(("island at (%d,%d) must connect in direction (%d,%d) to"
+ " avoid full subgroup.\n",
+ is->x, is->y, is->adj.points[i].dx, is->adj.points[i].dy));
+ solve_join(is, i, 1, 0);
+ didsth = 1;
+ }
+
+ map_update_possibles(is->state);
}
+
if (didsth) *didsth_r = didsth;
return 1;
}
if (sscanf(move, "%d,%d,%d,%d,%d%n",
&x1, &y1, &x2, &y2, &nl, &n) != 5)
goto badmove;
+ if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
+ goto badmove;
is1 = INDEX(ret, gridi, x1, y1);
is2 = INDEX(ret, gridi, x2, y2);
if (!is1 || !is2) goto badmove;
if (sscanf(move, "%d,%d,%d,%d%n",
&x1, &y1, &x2, &y2, &n) != 4)
goto badmove;
+ if (!INGRID(ret, x1, y1) || !INGRID(ret, x2, y2))
+ goto badmove;
is1 = INDEX(ret, gridi, x1, y1);
is2 = INDEX(ret, gridi, x2, y2);
if (!is1 || !is2) goto badmove;
if (sscanf(move, "%d,%d%n",
&x1, &y1, &n) != 2)
goto badmove;
+ if (!INGRID(ret, x1, y1))
+ goto badmove;
is1 = INDEX(ret, gridi, x1, y1);
if (!is1) goto badmove;
island_togglemark(is1);
#ifdef DRAW_DSF
int ts = TILE_SIZE/2;
int ox = COORD(x) + ts/2, oy = COORD(y) + ts/2;
- char str[10];
+ char str[32];
sprintf(str, "%d", dsf_canonify(state->solver->dsf, DINDEX(x,y)));
draw_text(dr, ox, oy, FONT_VARIABLE, ts,
int col = (v & G_ISSEL) ? COL_SELECTED : tcol;
int bg = (v & G_CURSOR) ? COL_CURSOR :
(v & G_MARK) ? COL_MARK : COL_BACKGROUND;
- char str[10];
+ char str[32];
#ifdef DRAW_GRID
draw_rect_outline(dr, COORD(is->x), COORD(is->y),
return 0.0F;
}
+static int game_status(game_state *state)
+{
+ return state->completed ? +1 : 0;
+}
+
static int game_timing_state(game_state *state, game_ui *ui)
{
return TRUE;
int ink = print_mono_colour(dr, 0);
int paper = print_mono_colour(dr, 1);
int x, y, cx, cy, i, nl;
- int loff = ts/8;
+ int loff;
grid_type grid;
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
/* I don't think this wants a border. */
/* Bridges */
+ loff = ts / (8 * sqrt((state->params.maxb - 1)));
print_line_width(dr, ts / 12);
for (x = 0; x < state->w; x++) {
for (y = 0; y < state->h; y++) {
if (grid & G_ISLAND) continue;
if (grid & G_LINEV) {
- if (nl > 1) {
- draw_line(dr, cx+ts/2-loff, cy, cx+ts/2-loff, cy+ts, ink);
- draw_line(dr, cx+ts/2+loff, cy, cx+ts/2+loff, cy+ts, ink);
- } else {
- draw_line(dr, cx+ts/2, cy, cx+ts/2, cy+ts, ink);
- }
+ for (i = 0; i < nl; i++)
+ draw_line(dr, cx+ts/2+(2*i-nl+1)*loff, cy,
+ cx+ts/2+(2*i-nl+1)*loff, cy+ts, ink);
}
if (grid & G_LINEH) {
- if (nl > 1) {
- draw_line(dr, cx, cy+ts/2-loff, cx+ts, cy+ts/2-loff, ink);
- draw_line(dr, cx, cy+ts/2+loff, cx+ts, cy+ts/2+loff, ink);
- } else {
- draw_line(dr, cx, cy+ts/2, cx+ts, cy+ts/2, ink);
- }
+ for (i = 0; i < nl; i++)
+ draw_line(dr, cx, cy+ts/2+(2*i-nl+1)*loff,
+ cx+ts, cy+ts/2+(2*i-nl+1)*loff, ink);
}
}
}
/* Islands */
for (i = 0; i < state->n_islands; i++) {
- char str[10];
+ char str[32];
struct island *is = &state->islands[i];
grid = GRID(state, is->x, is->y);
cx = COORD(is->x) + ts/2;
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
FALSE, /* wants_statusbar */
FALSE, game_timing_state,