*
* Things still to do:
*
- * * write a recursive solver?
+ * - The solver's algorithmic design is not really ideal. It makes
+ * use of the same data representation as gameplay uses, which
+ * often looks like a tempting reuse of code but isn't always a
+ * good idea. In this case, it's unpleasant that each edge of the
+ * graph ends up represented as multiple squares on a grid, with
+ * flags indicating when edges and non-edges cross; that's useful
+ * when the result can be directly translated into positions of
+ * graphics on the display, but in purely internal work it makes
+ * even simple manipulations during solving more painful than they
+ * should be, and complex ones have no choice but to modify the
+ * data structures temporarily, test things, and put them back. I
+ * envisage a complete solver rewrite along the following lines:
+ * + We have a collection of vertices (islands) and edges
+ * (potential bridge locations, i.e. pairs of horizontal or
+ * vertical islands with no other island in between).
+ * + Each edge has an associated list of edges that cross it, and
+ * hence with which it is mutually exclusive.
+ * + For each edge, we track the min and max number of bridges we
+ * currently think possible.
+ * + For each vertex, we track the number of _liberties_ it has,
+ * i.e. its clue number minus the min bridge count for each edge
+ * out of it.
+ * + We also maintain a dsf that identifies sets of vertices which
+ * are connected components of the puzzle so far, and for each
+ * equivalence class we track the total number of liberties for
+ * that component. (The dsf mechanism will also already track
+ * the size of each component, i.e. number of islands.)
+ * + So incrementing the min for an edge requires processing along
+ * the lines of:
+ * - set the max for all edges crossing that one to zero
+ * - decrement the liberty count for the vertex at each end,
+ * and also for each vertex's equivalence class (NB they may
+ * be the same class)
+ * - unify the two equivalence classes if they're not already,
+ * and if so, set the liberty count for the new class to be
+ * the sum of the previous two.
+ * + Decrementing the max is much easier, however.
+ * + With this data structure the really fiddly stuff in stage3()
+ * becomes more or less trivial, because it's now a quick job to
+ * find out whether an island would form an isolated subgraph if
+ * connected to a given subset of its neighbours:
+ * - identify the connected components containing the test
+ * vertex and its putative new neighbours (but be careful not
+ * to count a component more than once if two or more of the
+ * vertices involved are already in the same one)
+ * - find the sum of those components' liberty counts, and also
+ * the total number of islands involved
+ * - if the total liberty count of the connected components is
+ * exactly equal to twice the number of edges we'd be adding
+ * (of course each edge destroys two liberties, one at each
+ * end) then these components would become a subgraph with
+ * zero liberties if connected together.
+ * - therefore, if that subgraph also contains fewer than the
+ * total number of islands, it's disallowed.
+ * - As mentioned in stage3(), once we've identified such a
+ * disallowed pattern, we have two choices for what to do
+ * with it: if the candidate set of neighbours has size 1 we
+ * can reduce the max for the edge to that one neighbour,
+ * whereas if its complement has size 1 we can increase the
+ * min for the edge to the _omitted_ neighbour.
+ *
+ * - write a recursive solver?
*/
#include <stdio.h>
}
}
-static int game_can_format_as_text_now(game_params *params)
+static int game_can_format_as_text_now(const game_params *params)
{
return TRUE;
}
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
{
int x, y, len, nl;
char *ret, *p;
sfree(params);
}
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* structure copy */
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char buf[80];
return dupstr(buf);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[80];
return ret;
}
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
if (params->w < 3 || params->h < 3)
return "Width and height must be at least 3";
return ret;
}
-static char *game_state_diff(game_state *src, game_state *dest)
+static char *game_state_diff(const game_state *src, const game_state *dest)
{
int movesize = 256, movelen = 0;
char *move = snewn(movesize, char), buf[80];
idx = x;
s = e = -1;
bl = 0;
+ maxb = state->params.maxb; /* placate optimiser */
/* Unset possible flags until we find an island. */
for (y = 0; y < state->h; y++) {
is_s = IDX(state, gridi, idx);
idx = y*w;
s = e = -1;
bl = 0;
+ maxb = state->params.maxb; /* placate optimiser */
for (x = 0; x < state->w; x++) {
is_s = IDX(state, gridi, idx);
if (is_s) {
return 1;
}
-static int solve_island_subgroup(struct island *is, int direction, int n)
+static int solve_island_subgroup(struct island *is, int direction)
{
struct island *is_join;
int nislands, *dsf = is->state->solver->dsf;
debug(("..checking subgroups.\n"));
/* if is isn't full, return 0. */
- if (n < is->count) {
+ if (island_countbridges(is) < is->count) {
debug(("...orig island (%d,%d) not full.\n", is->x, is->y));
return 0;
}
/* we have a full subgroup that isn't the whole set.
* This isn't allowed. */
debug(("island at (%d,%d) makes full subgroup, disallowing.\n",
- is->x, is->y, n));
+ is->x, is->y));
return 1;
} else {
debug(("...has finished puzzle.\n"));
if (missing <= 0) return 1;
for (i = 0; i < is->adj.npoints; i++) {
- /* We only do right- or down-pointing bridges. */
- if (is->adj.points[i].dx == -1 ||
- is->adj.points[i].dy == -1) continue;
-
x = is->adj.points[i].x;
y = is->adj.points[i].y;
spc = island_adjspace(is, 1, missing, i);
solve_join(is, i, n, 0);
map_update_possibles(is->state);
- if (solve_island_subgroup(is, i, n) ||
+ if (solve_island_subgroup(is, i) ||
solve_island_impossible(is->state)) {
maxb = n-1;
debug(("island at (%d,%d) d(%d,%d) new max of %d bridges:\n",
}
map_update_possibles(is->state);
- if (solve_island_subgroup(is, -1, n))
+ if (solve_island_subgroup(is, -1))
got = 1;
for (j = 0; j < is->adj.npoints; j++)
/* --- New game functions --- */
-static game_state *new_state(game_params *params)
+static game_state *new_state(const game_params *params)
{
game_state *ret = snew(game_state);
int wh = params->w * params->h, i;
return ret;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
game_state *ret = snew(game_state);
int wh = state->w*state->h;
#define ORDER(a,b) do { if (a < b) { int tmp=a; int a=b; int b=tmp; } } while(0)
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params, random_state *rs,
char **aux, int interactive)
{
game_state *tobuild = NULL;
return ret;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int i, wh = params->w * params->h;
return NULL;
}
-static game_state *new_game_sub(game_params *params, char *desc)
+static game_state *new_game_sub(const game_params *params, const char *desc)
{
game_state *state = new_state(params);
int x, y, run = 0;
return state;
}
-static game_state *new_game(midend *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+ const char *desc)
{
return new_game_sub(params, desc);
}
return "";
}
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ui = snew(game_ui);
ui_cancel_drag(ui);
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+ const game_state *newstate)
{
}
int show_hints;
};
-static char *update_drag_dst(game_state *state, game_ui *ui, game_drawstate *ds,
- int nx, int ny)
+static char *update_drag_dst(const game_state *state, game_ui *ui,
+ const game_drawstate *ds, int nx, int ny)
{
int ox, oy, dx, dy, i, currl, maxb;
struct island *is;
return "";
}
-static char *finish_drag(game_state *state, game_ui *ui)
+static char *finish_drag(const game_state *state, game_ui *ui)
{
char buf[80];
return dupstr(buf);
}
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
- int x, int y, int button)
+static char *interpret_move(const game_state *state, game_ui *ui,
+ const game_drawstate *ds,
+ int x, int y, int button)
{
int gx = FROMCOORD(x), gy = FROMCOORD(y);
char buf[80], *ret;
return NULL;
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
game_state *ret = dup_game(state);
int x1, y1, x2, y2, nl, n;
return NULL;
}
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+ const char *aux, char **error)
{
char *ret;
game_state *solved;
* Drawing routines.
*/
-static void game_compute_size(game_params *params, int tilesize,
- int *x, int *y)
+static void game_compute_size(const game_params *params, int tilesize,
+ int *x, int *y)
{
/* Ick: fake up `ds->tilesize' for macro expansion purposes */
struct { int tilesize; } ads, *ds = &ads;
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
return ret;
}
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
struct game_drawstate *ds = snew(struct game_drawstate);
int wh = state->w*state->h;
draw_line(dr, ox+off, oy, ox, oy+off, col);
}
-static int between_island(game_state *state, int sx, int sy, int dx, int dy)
+static int between_island(const game_state *state, int sx, int sy,
+ int dx, int dy)
{
int x = sx - dx, y = sy - dy;
return 0;
}
-static void lines_lvlh(game_state *state, game_ui *ui, int x, int y, grid_type v,
- int *lv_r, int *lh_r)
+static void lines_lvlh(const game_state *state, const game_ui *ui,
+ int x, int y, grid_type v, int *lv_r, int *lh_r)
{
int lh = 0, lv = 0;
}
static void dsf_debug_draw(drawing *dr,
- game_state *state, game_drawstate *ds,
+ const game_state *state, game_drawstate *ds,
int x, int y)
{
#ifdef DRAW_DSF
#endif
}
-static void lines_redraw(drawing *dr,
- game_state *state, game_drawstate *ds, game_ui *ui,
+static void lines_redraw(drawing *dr, const game_state *state,
+ game_drawstate *ds, const game_ui *ui,
int x, int y, grid_type v, int lv, int lh)
{
int ox = COORD(x), oy = COORD(y);
(((is)->count < 10) ? (TILE_SIZE*7)/10 : (TILE_SIZE*5)/10)
static void island_redraw(drawing *dr,
- game_state *state, game_drawstate *ds,
+ const game_state *state, game_drawstate *ds,
struct island *is, grid_type v)
{
/* These overlap the edges of their squares, which is why they're drawn later.
draw_update(dr, ox - orad, oy - orad, updatesz, updatesz);
}
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
+static void game_redraw(drawing *dr, game_drawstate *ds,
+ const game_state *oldstate, const game_state *state,
+ int dir, const game_ui *ui,
+ float animtime, float flashtime)
{
int x, y, force = 0, i, j, redraw, lv, lh;
grid_type v, dsv, flash = 0;
}
}
-static float game_anim_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_anim_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
return 0.0F;
}
-static float game_flash_length(game_state *oldstate, game_state *newstate,
- int dir, game_ui *ui)
+static float game_flash_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
if (!oldstate->completed && newstate->completed &&
!oldstate->solved && !newstate->solved)
return 0.0F;
}
-static int game_status(game_state *state)
+static int game_status(const game_state *state)
{
return state->completed ? +1 : 0;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_timing_state(const game_state *state, game_ui *ui)
{
return TRUE;
}
-static void game_print_size(game_params *params, float *x, float *y)
+static void game_print_size(const game_params *params, float *x, float *y)
{
int pw, ph;
*y = ph / 100.0F;
}
-static void game_print(drawing *dr, game_state *state, int ts)
+static void game_print(drawing *dr, const game_state *state, int ts)
{
int ink = print_mono_colour(dr, 0);
int paper = print_mono_colour(dr, 1);