X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/e1a449049f516296fe30b2286cd4a55a12cadbb2..fb86a8e006a25ad515f2a506528edb617f136cec:/bridges.c diff --git a/bridges.c b/bridges.c index 694f011..8f8ff75 100644 --- a/bridges.c +++ b/bridges.c @@ -77,7 +77,8 @@ struct game_params { 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; }; @@ -513,7 +514,6 @@ static int island_impossible(struct island *is, int strict) { int curr = island_countbridges(is), nspc = is->count - curr, nsurrspc; int i, poss; - grid_type v; struct island *is_orth; if (nspc < 0) { @@ -533,7 +533,6 @@ static int island_impossible(struct island *is, int strict) 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; @@ -542,9 +541,24 @@ static int island_impossible(struct island *is, int strict) 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", @@ -868,17 +882,20 @@ static void map_update_possibles(game_state *state) /* 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++) { @@ -888,6 +905,7 @@ static void map_update_possibles(game_state *state) 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; @@ -908,17 +926,20 @@ static void map_update_possibles(game_state *state) 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++) { @@ -928,6 +949,7 @@ static void map_update_possibles(game_state *state) 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; @@ -1393,15 +1415,18 @@ static int solve_island_subgroup(struct island *is, int direction, int n) 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. */ @@ -1492,14 +1517,96 @@ static int solve_island_stage3(struct island *is, int *didsth_r) 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; } @@ -2244,6 +2351,8 @@ static game_state *execute_move(game_state *state, char *move) 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; @@ -2253,6 +2362,8 @@ static game_state *execute_move(game_state *state, char *move) 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; @@ -2261,6 +2372,8 @@ static game_state *execute_move(game_state *state, char *move) 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); @@ -2473,7 +2586,7 @@ static void dsf_debug_draw(drawing *dr, #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, @@ -2550,7 +2663,7 @@ static void island_redraw(drawing *dr, 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), @@ -2694,6 +2807,11 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, 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; @@ -2714,7 +2832,7 @@ static void game_print(drawing *dr, game_state *state, int ts) 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 */ @@ -2724,6 +2842,7 @@ static void game_print(drawing *dr, game_state *state, int ts) /* 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++) { @@ -2733,27 +2852,21 @@ static void game_print(drawing *dr, game_state *state, int ts) 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; @@ -2802,6 +2915,7 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, FALSE, game_print_size, game_print, FALSE, /* wants_statusbar */ FALSE, game_timing_state,