*/
/*
- *
- * - There's an interesting deductive technique which makes use of topology
- * rather than just graph theory. Each _square_ in the grid is either inside
- * or outside the loop; you can tell that two squares are on the same side
- * of the loop if they're separated by an x (or, more generally, by a path
- * crossing no LINE_UNKNOWNs and an even number of LINE_YESes), and on the
- * opposite side of the loop if they're separated by a line (or an odd
- * number of LINE_YESes and no LINE_UNKNOWNs). Oh, and any square separated
- * from the outside of the grid by a LINE_YES or a LINE_NO is on the inside
- * or outside respectively. So if you can track this for all squares, you
- * figure out the state of the line between a pair once their relative
- * insideness is known.
+ * Possible future solver enhancements:
+ *
+ * - There's an interesting deductive technique which makes use
+ * of topology rather than just graph theory. Each _face_ in
+ * the grid is either inside or outside the loop; you can tell
+ * that two faces are on the same side of the loop if they're
+ * separated by a LINE_NO (or, more generally, by a path
+ * crossing no LINE_UNKNOWNs and an even number of LINE_YESes),
+ * and on the opposite side of the loop if they're separated by
+ * a LINE_YES (or an odd number of LINE_YESes and no
+ * LINE_UNKNOWNs). Oh, and any face separated from the outside
+ * of the grid by a LINE_YES or a LINE_NO is on the inside or
+ * outside respectively. So if you can track this for all
+ * faces, you figure out the state of the line between a pair
+ * once their relative insideness is known.
+ * + The way I envisage this working is simply to keep an edsf
+ * of all _faces_, which indicates whether they're on
+ * opposite sides of the loop from one another. We also
+ * include a special entry in the edsf for the infinite
+ * exterior "face".
+ * + So, the simple way to do this is to just go through the
+ * edges: every time we see an edge in a state other than
+ * LINE_UNKNOWN which separates two faces that aren't in the
+ * same edsf class, we can rectify that by merging the
+ * classes. Then, conversely, an edge in LINE_UNKNOWN state
+ * which separates two faces that _are_ in the same edsf
+ * class can immediately have its state determined.
+ * + But you can go one better, if you're prepared to loop
+ * over all _pairs_ of edges. Suppose we have edges A and B,
+ * which respectively separate faces A1,A2 and B1,B2.
+ * Suppose that A,B are in the same edge-edsf class and that
+ * A1,B1 (wlog) are in the same face-edsf class; then we can
+ * immediately place A2,B2 into the same face-edsf class (as
+ * each other, not as A1 and A2) one way round or the other.
+ * And conversely again, if A1,B1 are in the same face-edsf
+ * class and so are A2,B2, then we can put A,B into the same
+ * face-edsf class.
+ * * Of course, this deduction requires a quadratic-time
+ * loop over all pairs of edges in the grid, so it should
+ * be reserved until there's nothing easier left to be
+ * done.
+ *
+ * - The generalised grid support has made me (SGT) notice a
+ * possible extension to the loop-avoidance code. When you have
+ * a path of connected edges such that no other edges at all
+ * are incident on any vertex in the middle of the path - or,
+ * alternatively, such that any such edges are already known to
+ * be LINE_NO - then you know those edges are either all
+ * LINE_YES or all LINE_NO. Hence you can mentally merge the
+ * entire path into a single long curly edge for the purposes
+ * of loop avoidance, and look directly at whether or not the
+ * extreme endpoints of the path are connected by some other
+ * route. I find this coming up fairly often when I play on the
+ * octagonal grid setting, so it might be worth implementing in
+ * the solver.
*
* - (Just a speed optimisation.) Consider some todo list queue where every
* time we modify something we mark it for consideration by other bits of
* YES, NO or UNKNOWN */
char *lines;
+ unsigned char *line_errors;
+
int solved;
int cheated;
static char const *const diffnames[] = { DIFFLIST(TITLE) };
static char const diffchars[] = DIFFLIST(ENCODE);
#define DIFFCONFIG DIFFLIST(CONFIG)
-DIFFLIST(SOLVER_FN_DECL);
+DIFFLIST(SOLVER_FN_DECL)
static int (*(solver_fns[]))(solver_state *) = { DIFFLIST(SOLVER_FN) };
struct game_params {
grid *game_grid;
};
+/* line_drawstate is the same as line_state, but with the extra ERROR
+ * possibility. The drawing code copies line_state to line_drawstate,
+ * except in the case that the line is an error. */
enum line_state { LINE_YES, LINE_UNKNOWN, LINE_NO };
+enum line_drawstate { DS_LINE_YES, DS_LINE_UNKNOWN,
+ DS_LINE_NO, DS_LINE_ERROR };
#define OPP(line_state) \
(2 - line_state)
/* ------- List of grid generators ------- */
#define GRIDLIST(A) \
- A(Squares,grid_new_square) \
- A(Triangular,grid_new_triangular) \
- A(Honeycomb,grid_new_honeycomb) \
- A(Snub-Square,grid_new_snubsquare) \
- A(Cairo,grid_new_cairo) \
- A(Great-Hexagonal,grid_new_greathexagonal) \
- A(Octagonal,grid_new_octagonal) \
- A(Kites,grid_new_kites)
-
-#define GRID_NAME(title,fn) #title,
-#define GRID_CONFIG(title,fn) ":" #title
-#define GRID_FN(title,fn) &fn,
+ A(Squares,grid_new_square,3,3) \
+ A(Triangular,grid_new_triangular,3,3) \
+ A(Honeycomb,grid_new_honeycomb,3,3) \
+ A(Snub-Square,grid_new_snubsquare,3,3) \
+ A(Cairo,grid_new_cairo,3,4) \
+ A(Great-Hexagonal,grid_new_greathexagonal,3,3) \
+ A(Octagonal,grid_new_octagonal,3,3) \
+ A(Kites,grid_new_kites,3,3)
+
+#define GRID_NAME(title,fn,amin,omin) #title,
+#define GRID_CONFIG(title,fn,amin,omin) ":" #title
+#define GRID_FN(title,fn,amin,omin) &fn,
+#define GRID_SIZES(title,fn,amin,omin) \
+ {amin, omin, \
+ "Width and height for this grid type must both be at least " #amin, \
+ "At least one of width and height for this grid type must be at least " #omin,},
static char const *const gridnames[] = { GRIDLIST(GRID_NAME) };
#define GRID_CONFIGS GRIDLIST(GRID_CONFIG)
static grid * (*(grid_fns[]))(int w, int h) = { GRIDLIST(GRID_FN) };
-static const int NUM_GRID_TYPES = sizeof(grid_fns) / sizeof(grid_fns[0]);
+#define NUM_GRID_TYPES (sizeof(grid_fns) / sizeof(grid_fns[0]))
+static const struct {
+ int amin, omin;
+ char *aerr, *oerr;
+} grid_size_limits[] = { GRIDLIST(GRID_SIZES) };
/* Generates a (dynamically allocated) new grid, according to the
* type and size requested in params. Does nothing if the grid is already
ret->lines = snewn(state->game_grid->num_edges, char);
memcpy(ret->lines, state->lines, state->game_grid->num_edges);
+ ret->line_errors = snewn(state->game_grid->num_edges, unsigned char);
+ memcpy(ret->line_errors, state->line_errors, state->game_grid->num_edges);
+
ret->grid_type = state->grid_type;
return ret;
}
grid_free(state->game_grid);
sfree(state->clues);
sfree(state->lines);
+ sfree(state->line_errors);
sfree(state);
}
}
}
static const game_params presets[] = {
+#ifdef SMALL_SCREEN
+ { 7, 7, DIFF_EASY, 0, NULL },
+ { 7, 7, DIFF_NORMAL, 0, NULL },
+ { 7, 7, DIFF_HARD, 0, NULL },
+ { 7, 7, DIFF_HARD, 1, NULL },
+ { 7, 7, DIFF_HARD, 2, NULL },
+ { 5, 5, DIFF_HARD, 3, NULL },
+ { 7, 7, DIFF_HARD, 4, NULL },
+ { 5, 4, DIFF_HARD, 5, NULL },
+ { 5, 5, DIFF_HARD, 6, NULL },
+ { 5, 5, DIFF_HARD, 7, NULL },
+#else
{ 7, 7, DIFF_EASY, 0, NULL },
{ 10, 10, DIFF_EASY, 0, NULL },
{ 7, 7, DIFF_NORMAL, 0, NULL },
{ 5, 4, DIFF_HARD, 5, NULL },
{ 7, 7, DIFF_HARD, 6, NULL },
{ 5, 5, DIFF_HARD, 7, NULL },
+#endif
};
static int game_fetch_preset(int i, char **name, game_params **params)
static char *validate_params(game_params *params, int full)
{
- if (params->w < 3 || params->h < 3)
- return "Width and height must both be at least 3";
if (params->type < 0 || params->type >= NUM_GRID_TYPES)
return "Illegal grid type";
+ if (params->w < grid_size_limits[params->type].amin ||
+ params->h < grid_size_limits[params->type].amin)
+ return grid_size_limits[params->type].aerr;
+ if (params->w < grid_size_limits[params->type].omin &&
+ params->h < grid_size_limits[params->type].omin)
+ return grid_size_limits[params->type].oerr;
/*
* This shouldn't be able to happen at all, since decode_params
int *x, int *y)
{
grid *g;
+ int grid_width, grid_height, rendered_width, rendered_height;
+
params_generate_grid(params);
g = params->game_grid;
- int grid_width = g->highest_x - g->lowest_x;
- int grid_height = g->highest_y - g->lowest_y;
+ grid_width = g->highest_x - g->lowest_x;
+ grid_height = g->highest_y - g->lowest_y;
/* multiply first to minimise rounding error on integer division */
- int rendered_width = grid_width * tilesize / g->tilesize;
- int rendered_height = grid_height * tilesize / g->tilesize;
+ rendered_width = grid_width * tilesize / g->tilesize;
+ rendered_height = grid_height * tilesize / g->tilesize;
*x = rendered_width + 2 * BORDER(tilesize) + 1;
*y = rendered_height + 2 * BORDER(tilesize) + 1;
}
/* Fill in clues */
for (i = 0; i < g->num_faces; i++) {
+ int x1, x2, y1, y2;
+
f = g->faces + i;
assert(f->order == 4);
/* Cell coordinates, from (0,0) to (w-1,h-1) */
- int x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
- int x2 = (f->dots[2]->x - g->lowest_x) / cell_size;
- int y1 = (f->dots[0]->y - g->lowest_y) / cell_size;
- int y2 = (f->dots[2]->y - g->lowest_y) / cell_size;
+ x1 = (f->dots[0]->x - g->lowest_x) / cell_size;
+ x2 = (f->dots[2]->x - g->lowest_x) / cell_size;
+ y1 = (f->dots[0]->y - g->lowest_y) / cell_size;
+ y2 = (f->dots[2]->y - g->lowest_y) / cell_size;
/* Midpoint, in canvas coordinates */
x = x1 + x2;
y = y1 + y2;
g->refcount++;
state->clues = snewn(g->num_faces, signed char);
state->lines = snewn(g->num_edges, char);
+ state->line_errors = snewn(g->num_edges, unsigned char);
state->grid_type = params->type;
newboard_please:
memset(state->lines, LINE_UNKNOWN, g->num_edges);
+ memset(state->line_errors, 0, g->num_edges);
state->solved = state->cheated = FALSE;
int n;
const char *dp = desc;
grid *g;
+ int num_faces, num_edges;
+
params_generate_grid(params);
state->game_grid = g = params->game_grid;
g->refcount++;
- int num_faces = g->num_faces;
- int num_edges = g->num_edges;
+ num_faces = g->num_faces;
+ num_edges = g->num_edges;
state->clues = snewn(num_faces, signed char);
state->lines = snewn(num_edges, char);
+ state->line_errors = snewn(num_edges, unsigned char);
state->solved = state->cheated = FALSE;
}
memset(state->lines, LINE_UNKNOWN, num_edges);
-
+ memset(state->line_errors, 0, num_edges);
return state;
}
-enum { LOOP_NONE=0, LOOP_SOLN, LOOP_NOT_SOLN };
+/* Calculates the line_errors data, and checks if the current state is a
+ * solution */
+static int check_completion(game_state *state)
+{
+ grid *g = state->game_grid;
+ int *dsf;
+ int num_faces = g->num_faces;
+ int i;
+ int infinite_area, finite_area;
+ int loops_found = 0;
+ int found_edge_not_in_loop = FALSE;
+
+ memset(state->line_errors, 0, g->num_edges);
+
+ /* LL implementation of SGT's idea:
+ * A loop will partition the grid into an inside and an outside.
+ * If there is more than one loop, the grid will be partitioned into
+ * even more distinct regions. We can therefore track equivalence of
+ * faces, by saying that two faces are equivalent when there is a non-YES
+ * edge between them.
+ * We could keep track of the number of connected components, by counting
+ * the number of dsf-merges that aren't no-ops.
+ * But we're only interested in 3 separate cases:
+ * no loops, one loop, more than one loop.
+ *
+ * No loops: all faces are equivalent to the infinite face.
+ * One loop: only two equivalence classes - finite and infinite.
+ * >= 2 loops: there are 2 distinct finite regions.
+ *
+ * So we simply make two passes through all the edges.
+ * In the first pass, we dsf-merge the two faces bordering each non-YES
+ * edge.
+ * In the second pass, we look for YES-edges bordering:
+ * a) two non-equivalent faces.
+ * b) two non-equivalent faces, and one of them is part of a different
+ * finite area from the first finite area we've seen.
+ *
+ * An occurrence of a) means there is at least one loop.
+ * An occurrence of b) means there is more than one loop.
+ * Edges satisfying a) are marked as errors.
+ *
+ * While we're at it, we set a flag if we find a YES edge that is not
+ * part of a loop.
+ * This information will help decide, if there's a single loop, whether it
+ * is a candidate for being a solution (that is, all YES edges are part of
+ * this loop).
+ *
+ * If there is a candidate loop, we then go through all clues and check
+ * they are all satisfied. If so, we have found a solution and we can
+ * unmark all line_errors.
+ */
+
+ /* Infinite face is at the end - its index is num_faces.
+ * This macro is just to make this obvious! */
+ #define INF_FACE num_faces
+ dsf = snewn(num_faces + 1, int);
+ dsf_init(dsf, num_faces + 1);
+
+ /* First pass */
+ for (i = 0; i < g->num_edges; i++) {
+ grid_edge *e = g->edges + i;
+ int f1 = e->face1 ? e->face1 - g->faces : INF_FACE;
+ int f2 = e->face2 ? e->face2 - g->faces : INF_FACE;
+ if (state->lines[i] != LINE_YES)
+ dsf_merge(dsf, f1, f2);
+ }
+
+ /* Second pass */
+ infinite_area = dsf_canonify(dsf, INF_FACE);
+ finite_area = -1;
+ for (i = 0; i < g->num_edges; i++) {
+ grid_edge *e = g->edges + i;
+ int f1 = e->face1 ? e->face1 - g->faces : INF_FACE;
+ int can1 = dsf_canonify(dsf, f1);
+ int f2 = e->face2 ? e->face2 - g->faces : INF_FACE;
+ int can2 = dsf_canonify(dsf, f2);
+ if (state->lines[i] != LINE_YES) continue;
+
+ if (can1 == can2) {
+ /* Faces are equivalent, so this edge not part of a loop */
+ found_edge_not_in_loop = TRUE;
+ continue;
+ }
+ state->line_errors[i] = TRUE;
+ if (loops_found == 0) loops_found = 1;
+
+ /* Don't bother with further checks if we've already found 2 loops */
+ if (loops_found == 2) continue;
+
+ if (finite_area == -1) {
+ /* Found our first finite area */
+ if (can1 != infinite_area)
+ finite_area = can1;
+ else
+ finite_area = can2;
+ }
+
+ /* Have we found a second area? */
+ if (finite_area != -1) {
+ if (can1 != infinite_area && can1 != finite_area) {
+ loops_found = 2;
+ continue;
+ }
+ if (can2 != infinite_area && can2 != finite_area) {
+ loops_found = 2;
+ }
+ }
+ }
+
+/*
+ printf("loops_found = %d\n", loops_found);
+ printf("found_edge_not_in_loop = %s\n",
+ found_edge_not_in_loop ? "TRUE" : "FALSE");
+*/
+
+ sfree(dsf); /* No longer need the dsf */
+
+ /* Have we found a candidate loop? */
+ if (loops_found == 1 && !found_edge_not_in_loop) {
+ /* Yes, so check all clues are satisfied */
+ int found_clue_violation = FALSE;
+ for (i = 0; i < num_faces; i++) {
+ int c = state->clues[i];
+ if (c >= 0) {
+ if (face_order(state, i, LINE_YES) != c) {
+ found_clue_violation = TRUE;
+ break;
+ }
+ }
+ }
+
+ if (!found_clue_violation) {
+ /* The loop is good */
+ memset(state->line_errors, 0, g->num_edges);
+ return TRUE; /* No need to bother checking for dot violations */
+ }
+ }
+
+ /* Check for dot violations */
+ for (i = 0; i < g->num_dots; i++) {
+ int yes = dot_order(state, i, LINE_YES);
+ int unknown = dot_order(state, i, LINE_UNKNOWN);
+ if ((yes == 1 && unknown == 0) || (yes >= 3)) {
+ /* violation, so mark all YES edges as errors */
+ grid_dot *d = g->dots + i;
+ int j;
+ for (j = 0; j < d->order; j++) {
+ int e = d->edges[j] - g->edges;
+ if (state->lines[e] == LINE_YES)
+ state->line_errors[e] = TRUE;
+ }
+ }
+ }
+ return FALSE;
+}
/* ----------------------------------------------------------------------
* Solver logic
{
int i;
game_state *newstate = dup_game(state);
- grid *g = state->game_grid;
if (move[0] == 'S') {
move++;
/*
* Check for completion.
*/
- for (i = 0; i < g->num_edges; i++) {
- if (newstate->lines[i] == LINE_YES)
- break;
- }
- if (i < g->num_edges) {
- int looplen, count;
- grid_edge *start_edge = g->edges + i;
- grid_edge *e = start_edge;
- grid_dot *d = e->dot1;
- /*
- * We've found an edge i. Follow it round
- * to see if it's part of a loop.
- */
- looplen = 0;
- while (1) {
- int j;
- int order = dot_order(newstate, d - g->dots, LINE_YES);
- if (order != 2)
- goto completion_check_done;
-
- /* Find other edge around this dot */
- for (j = 0; j < d->order; j++) {
- grid_edge *e2 = d->edges[j];
- if (e2 != e && newstate->lines[e2 - g->edges] == LINE_YES)
- break;
- }
- assert(j != d->order); /* dot_order guarantees success */
-
- e = d->edges[j];
- d = (e->dot1 == d) ? e->dot2 : e->dot1;
- looplen++;
-
- if (e == start_edge)
- break;
- }
-
- /*
- * We've traced our way round a loop, and we know how many
- * line segments were involved. Count _all_ the line
- * segments in the grid, to see if the loop includes them
- * all.
- */
- count = 0;
- for (i = 0; i < g->num_edges; i++) {
- if (newstate->lines[i] == LINE_YES)
- count++;
- }
- assert(count >= looplen);
- if (count != looplen)
- goto completion_check_done;
-
- /*
- * The grid contains one closed loop and nothing else.
- * Check that all the clues are satisfied.
- */
- for (i = 0; i < g->num_faces; i++) {
- int c = newstate->clues[i];
- if (c >= 0) {
- if (face_order(newstate, i, LINE_YES) != c) {
- goto completion_check_done;
- }
- }
- }
-
- /*
- * Completed!
- */
+ if (check_completion(newstate))
newstate->solved = TRUE;
- }
- completion_check_done:
return newstate;
fail:
int grid_height = g->highest_y - g->lowest_y;
int w = grid_width * ds->tilesize / g->tilesize;
int h = grid_height * ds->tilesize / g->tilesize;
- draw_rect(dr, 0, 0, w + 2 * border, h + 2 * border, COL_BACKGROUND);
+ draw_rect(dr, 0, 0, w + 2 * border + 1, h + 2 * border + 1,
+ COL_BACKGROUND);
/* Draw clues */
for (i = 0; i < g->num_faces; i++) {
+ grid_face *f;
+ int x, y;
+
c[0] = CLUE2CHAR(state->clues[i]);
c[1] = '\0';
- int x, y;
- grid_face *f = g->faces + i;
+ f = g->faces + i;
face_text_pos(ds, g, f, &x, &y);
draw_text(dr, x, y, FONT_VARIABLE, ds->tilesize/2,
ALIGN_VCENTRE | ALIGN_HCENTRE, COL_FOREGROUND, c);
* bounding-box around the line, then flag all nearby objects for redraw.
*/
if (ds->started) {
- const char redraw_flag = 1<<7;
+ const char redraw_flag = (char)(1<<7);
for (i = 0; i < g->num_edges; i++) {
+ char prev_ds = (ds->lines[i] & ~redraw_flag);
+ char new_ds = state->lines[i];
+ if (state->line_errors[i])
+ new_ds = DS_LINE_ERROR;
+
/* If we're changing state, AND
* the previous state was a coloured line */
- if ((state->lines[i] != (ds->lines[i] & ~redraw_flag)) &&
- ((ds->lines[i] & ~redraw_flag) != LINE_NO)) {
+ if ((prev_ds != new_ds) && (prev_ds != LINE_NO)) {
grid_edge *e = g->edges + i;
int x1 = e->dot1->x;
int y1 = e->dot1->y;
}
}
- /* I've also had a request to colour lines red if they make a non-solution
- * loop, or if more than two lines go into any point. I think that would
- * be good some time. */
-
/* Lines */
for (i = 0; i < g->num_edges; i++) {
grid_edge *e = g->edges + i;
int x1, x2, y1, y2;
int xmin, ymin, xmax, ymax;
- int need_draw = (state->lines[i] != ds->lines[i]) ? TRUE : FALSE;
+ char new_ds, need_draw;
+ new_ds = state->lines[i];
+ if (state->line_errors[i])
+ new_ds = DS_LINE_ERROR;
+ need_draw = (new_ds != ds->lines[i]) ? TRUE : FALSE;
if (flash_changed && (state->lines[i] == LINE_YES))
need_draw = TRUE;
if (!ds->started)
need_draw = TRUE; /* draw everything at the start */
- ds->lines[i] = state->lines[i];
+ ds->lines[i] = new_ds;
if (!need_draw)
continue;
- if (state->lines[i] == LINE_UNKNOWN)
+ if (state->line_errors[i])
+ line_colour = COL_MISTAKE;
+ else if (state->lines[i] == LINE_UNKNOWN)
line_colour = COL_LINEUNKNOWN;
else if (state->lines[i] == LINE_NO)
line_colour = COL_BACKGROUND;
* direction to create a thin rectangle. */
int dx = (x1 > x2) ? -1 : ((x1 < x2) ? 1 : 0);
int dy = (y1 > y2) ? -1 : ((y1 < y2) ? 1 : 0);
- int points[] = {
- x1 + dy, y1 - dx,
- x1 - dy, y1 + dx,
- x2 - dy, y2 + dx,
- x2 + dy, y2 - dx
- };
+ int points[8];
+ points[0] = x1 + dy;
+ points[1] = y1 - dx;
+ points[2] = x1 - dy;
+ points[3] = y1 + dx;
+ points[4] = x2 - dy;
+ points[5] = y2 + dx;
+ points[6] = x2 + dy;
+ points[7] = y2 - dx;
draw_polygon(dr, points, 4, line_colour, line_colour);
}
if (ds->started) {
double d = sqrt(SQ((double)x1 - x2) + SQ((double)y1 - y2));
double dx = (x2 - x1) / d;
double dy = (y2 - y1) / d;
+ int points[8];
+
dx = (dx * ds->tilesize) / thickness;
dy = (dy * ds->tilesize) / thickness;
- int points[] = {
- x1 + dy, y1 - dx,
- x1 - dy, y1 + dx,
- x2 - dy, y2 + dx,
- x2 + dy, y2 - dx
- };
+ points[0] = x1 + (int)dy;
+ points[1] = y1 - (int)dx;
+ points[2] = x1 - (int)dy;
+ points[3] = y1 + (int)dx;
+ points[4] = x2 - (int)dy;
+ points[5] = y2 + (int)dx;
+ points[6] = x2 + (int)dy;
+ points[7] = y2 - (int)dx;
draw_polygon(dr, points, 4, ink, ink);
}
else
~mdw / sgt / puzzles / blobdiff