X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/1515b973951ee7850936da493a95d467a83bd571..6bb2af847d3bad4f2a544ad7a428f7063fd1991a:/loopy.c diff --git a/loopy.c b/loopy.c index fbbbb2b..0dabaee 100644 --- a/loopy.c +++ b/loopy.c @@ -10,18 +10,61 @@ */ /* - * - * - 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 @@ -136,7 +179,7 @@ enum { DIFFLIST(ENUM) DIFF_MAX }; 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 { @@ -193,7 +236,7 @@ static void check_caches(const solver_state* sstate); 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])) /* Generates a (dynamically allocated) new grid, according to the * type and size requested in params. Does nothing if the grid is already @@ -421,6 +464,18 @@ static game_params *dup_params(game_params *params) } 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 }, @@ -434,6 +489,7 @@ static const game_params presets[] = { { 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) @@ -2981,7 +3037,8 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, 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++) { @@ -3014,7 +3071,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * 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++) { /* If we're changing state, AND * the previous state was a coloured line */ @@ -3143,12 +3200,15 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, * 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) { @@ -3248,14 +3308,14 @@ static void game_print(drawing *dr, game_state *state, int tilesize) dx = (dx * ds->tilesize) / thickness; dy = (dy * ds->tilesize) / thickness; - 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; + 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