X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/756a9f15b5ddef732b54f6e2c1a2010655322a0e..1cea529f7dc604c05ae5d8a86c736e37fedd88aa:/map.c diff --git a/map.c b/map.c index e5edfd9..5d170d1 100644 --- a/map.c +++ b/map.c @@ -6,9 +6,7 @@ * TODO: * * - clue marking - * - more solver brains? * - better four-colouring algorithm? - * - pencil marks? */ #include @@ -21,6 +19,18 @@ #include "puzzles.h" /* + * In standalone solver mode, `verbose' is a variable which can be + * set by command-line option; in debugging mode it's simply always + * true. + */ +#if defined STANDALONE_SOLVER +#define SOLVER_DIAGNOSTICS +int verbose = FALSE; +#elif defined SOLVER_DIAGNOSTICS +#define verbose TRUE +#endif + +/* * I don't seriously anticipate wanting to change the number of * colours used in this game, but it doesn't cost much to use a * #define just in case :-) @@ -42,7 +52,9 @@ static float flash_length; */ #define DIFFLIST(A) \ A(EASY,Easy,e) \ - A(NORMAL,Normal,n) + A(NORMAL,Normal,n) \ + A(HARD,Hard,h) \ + A(RECURSE,Unreasonable,u) #define ENUM(upper,title,lower) DIFF_ ## upper, #define TITLE(upper,title,lower) #title, #define ENCODE(upper,title,lower) #lower @@ -73,13 +85,14 @@ struct map { int n; int ngraph; int *immutable; - int *edgex, *edgey; /* positions of a point on each edge */ + int *edgex, *edgey; /* position of a point on each edge */ + int *regionx, *regiony; /* position of a point in each region */ }; struct game_state { game_params p; struct map *map; - int *colouring; + int *colouring, *pencil; int completed, cheated; }; @@ -87,8 +100,13 @@ static game_params *default_params(void) { game_params *ret = snew(game_params); +#ifdef PORTRAIT_SCREEN + ret->w = 16; + ret->h = 18; +#else ret->w = 20; ret->h = 15; +#endif ret->n = 30; ret->diff = DIFF_NORMAL; @@ -96,9 +114,21 @@ static game_params *default_params(void) } static const struct game_params map_presets[] = { +#ifdef PORTRAIT_SCREEN + {16, 18, 30, DIFF_EASY}, + {16, 18, 30, DIFF_NORMAL}, + {16, 18, 30, DIFF_HARD}, + {16, 18, 30, DIFF_RECURSE}, + {25, 30, 75, DIFF_NORMAL}, + {25, 30, 75, DIFF_HARD}, +#else {20, 15, 30, DIFF_EASY}, {20, 15, 30, DIFF_NORMAL}, + {20, 15, 30, DIFF_HARD}, + {20, 15, 30, DIFF_RECURSE}, {30, 25, 75, DIFF_NORMAL}, + {30, 25, 75, DIFF_HARD}, +#endif }; static int game_fetch_preset(int i, char **name, game_params **params) @@ -786,9 +816,18 @@ static void fourcolour(int *graph, int n, int ngraph, int *colouring, struct solver_scratch { unsigned char *possible; /* bitmap of colours for each region */ + int *graph; int n; int ngraph; + + int *bfsqueue; + int *bfscolour; +#ifdef SOLVER_DIAGNOSTICS + int *bfsprev; +#endif + + int depth; }; static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) @@ -800,6 +839,12 @@ static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) sc->n = n; sc->ngraph = ngraph; sc->possible = snewn(n, unsigned char); + sc->depth = 0; + sc->bfsqueue = snewn(n, int); + sc->bfscolour = snewn(n, int); +#ifdef SOLVER_DIAGNOSTICS + sc->bfsprev = snewn(n, int); +#endif return sc; } @@ -807,33 +852,91 @@ static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) static void free_scratch(struct solver_scratch *sc) { sfree(sc->possible); + sfree(sc->bfsqueue); + sfree(sc->bfscolour); +#ifdef SOLVER_DIAGNOSTICS + sfree(sc->bfsprev); +#endif sfree(sc); } +/* + * Count the bits in a word. Only needs to cope with FOUR bits. + */ +static int bitcount(int word) +{ + assert(FOUR <= 4); /* or this needs changing */ + word = ((word & 0xA) >> 1) + (word & 0x5); + word = ((word & 0xC) >> 2) + (word & 0x3); + return word; +} + +#ifdef SOLVER_DIAGNOSTICS +static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' }; +#endif + static int place_colour(struct solver_scratch *sc, - int *colouring, int index, int colour) + int *colouring, int index, int colour +#ifdef SOLVER_DIAGNOSTICS + , char *verb +#endif + ) { int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph; int j, k; - if (!(sc->possible[index] & (1 << colour))) + if (!(sc->possible[index] & (1 << colour))) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*scannot place %c in region %d\n", 2*sc->depth, "", + colnames[colour], index); +#endif return FALSE; /* can't do it */ + } sc->possible[index] = 1 << colour; colouring[index] = colour; +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*s%s %c in region %d\n", 2*sc->depth, "", + verb, colnames[colour], index); +#endif + /* * Rule out this colour from all the region's neighbours. */ for (j = graph_vertex_start(graph, n, ngraph, index); j < ngraph && graph[j] < n*(index+1); j++) { k = graph[j] - index*n; +#ifdef SOLVER_DIAGNOSTICS + if (verbose && (sc->possible[k] & (1 << colour))) + printf("%*s ruling out %c in region %d\n", 2*sc->depth, "", + colnames[colour], k); +#endif sc->possible[k] &= ~(1 << colour); } return TRUE; } +#ifdef SOLVER_DIAGNOSTICS +static char *colourset(char *buf, int set) +{ + int i; + char *p = buf; + char *sep = ""; + + for (i = 0; i < FOUR; i++) + if (set & (1 << i)) { + p += sprintf(p, "%s%c", sep, colnames[i]); + sep = ","; + } + + return buf; +} +#endif + /* * Returns 0 for impossible, 1 for success, 2 for failure to * converge (i.e. puzzle is either ambiguous or just too @@ -845,20 +948,32 @@ static int map_solver(struct solver_scratch *sc, { int i; - /* - * Initialise scratch space. - */ - for (i = 0; i < n; i++) - sc->possible[i] = (1 << FOUR) - 1; + if (sc->depth == 0) { + /* + * Initialise scratch space. + */ + for (i = 0; i < n; i++) + sc->possible[i] = (1 << FOUR) - 1; - /* - * Place clues. - */ - for (i = 0; i < n; i++) - if (colouring[i] >= 0) { - if (!place_colour(sc, colouring, i, colouring[i])) - return 0; /* the clues aren't even consistent! */ - } + /* + * Place clues. + */ + for (i = 0; i < n; i++) + if (colouring[i] >= 0) { + if (!place_colour(sc, colouring, i, colouring[i] +#ifdef SOLVER_DIAGNOSTICS + , "initial clue:" +#endif + )) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*sinitial clue set is inconsistent\n", + 2*sc->depth, ""); +#endif + return 0; /* the clues aren't even consistent! */ + } + } + } /* * Now repeatedly loop until we find nothing further to do. @@ -876,17 +991,35 @@ static int map_solver(struct solver_scratch *sc, for (i = 0; i < n; i++) if (colouring[i] < 0) { int p = sc->possible[i]; - if (p == 0) + if (p == 0) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*sregion %d has no possible colours left\n", + 2*sc->depth, "", i); +#endif return 0; /* puzzle is inconsistent */ + } if ((p & (p-1)) == 0) { /* p is a power of two */ - int c; + int c, ret; for (c = 0; c < FOUR; c++) if (p == (1 << c)) break; assert(c < FOUR); - if (!place_colour(sc, colouring, i, c)) - return 0; /* found puzzle to be inconsistent */ + ret = place_colour(sc, colouring, i, c +#ifdef SOLVER_DIAGNOSTICS + , "placing" +#endif + ); + /* + * place_colour() can only fail if colour c was not + * even a _possibility_ for region i, and we're + * pretty sure it was because we checked before + * calling place_colour(). So we can safely assert + * here rather than having to return a nice + * friendly error code. + */ + assert(ret); done_something = TRUE; } } @@ -911,6 +1044,9 @@ static int map_solver(struct solver_scratch *sc, for (i = 0; i < ngraph; i++) { int j1 = graph[i] / n, j2 = graph[i] % n; int j, k, v, v2; +#ifdef SOLVER_DIAGNOSTICS + int started = FALSE; +#endif if (j1 > j2) continue; /* done it already, other way round */ @@ -946,24 +1082,311 @@ static int map_solver(struct solver_scratch *sc, k = graph[j] - j1*n; if (graph_adjacent(graph, n, ngraph, k, j2) && (sc->possible[k] & v)) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) { + char buf[80]; + if (!started) + printf("%*sadjacent regions %d,%d share colours" + " %s\n", 2*sc->depth, "", j1, j2, + colourset(buf, v)); + started = TRUE; + printf("%*s ruling out %s in region %d\n",2*sc->depth, + "", colourset(buf, sc->possible[k] & v), k); + } +#endif sc->possible[k] &= ~v; done_something = TRUE; } } } + if (done_something) + continue; + + if (difficulty < DIFF_HARD) + break; /* can't do anything harder */ + + /* + * Right; now we get creative. Now we're going to look for + * `forcing chains'. A forcing chain is a path through the + * graph with the following properties: + * + * (a) Each vertex on the path has precisely two possible + * colours. + * + * (b) Each pair of vertices which are adjacent on the + * path share at least one possible colour in common. + * + * (c) Each vertex in the middle of the path shares _both_ + * of its colours with at least one of its neighbours + * (not the same one with both neighbours). + * + * These together imply that at least one of the possible + * colour choices at one end of the path forces _all_ the + * rest of the colours along the path. In order to make + * real use of this, we need further properties: + * + * (c) Ruling out some colour C from the vertex at one end + * of the path forces the vertex at the other end to + * take colour C. + * + * (d) The two end vertices are mutually adjacent to some + * third vertex. + * + * (e) That third vertex currently has C as a possibility. + * + * If we can find all of that lot, we can deduce that at + * least one of the two ends of the forcing chain has + * colour C, and that therefore the mutually adjacent third + * vertex does not. + * + * To find forcing chains, we're going to start a bfs at + * each suitable vertex of the graph, once for each of its + * two possible colours. + */ + for (i = 0; i < n; i++) { + int c; + + if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2) + continue; + + for (c = 0; c < FOUR; c++) + if (sc->possible[i] & (1 << c)) { + int j, k, gi, origc, currc, head, tail; + /* + * Try a bfs from this vertex, ruling out + * colour c. + * + * Within this loop, we work in colour bitmaps + * rather than actual colours, because + * converting back and forth is a needless + * computational expense. + */ + + origc = 1 << c; + + for (j = 0; j < n; j++) { + sc->bfscolour[j] = -1; +#ifdef SOLVER_DIAGNOSTICS + sc->bfsprev[j] = -1; +#endif + } + head = tail = 0; + sc->bfsqueue[tail++] = i; + sc->bfscolour[i] = sc->possible[i] &~ origc; + + while (head < tail) { + j = sc->bfsqueue[head++]; + currc = sc->bfscolour[j]; + + /* + * Try neighbours of j. + */ + for (gi = graph_vertex_start(graph, n, ngraph, j); + gi < ngraph && graph[gi] < n*(j+1); gi++) { + k = graph[gi] - j*n; + + /* + * To continue with the bfs in vertex + * k, we need k to be + * (a) not already visited + * (b) have two possible colours + * (c) those colours include currc. + */ + + if (sc->bfscolour[k] < 0 && + colouring[k] < 0 && + bitcount(sc->possible[k]) == 2 && + (sc->possible[k] & currc)) { + sc->bfsqueue[tail++] = k; + sc->bfscolour[k] = + sc->possible[k] &~ currc; +#ifdef SOLVER_DIAGNOSTICS + sc->bfsprev[k] = j; +#endif + } + + /* + * One other possibility is that k + * might be the region in which we can + * make a real deduction: if it's + * adjacent to i, contains currc as a + * possibility, and currc is equal to + * the original colour we ruled out. + */ + if (currc == origc && + graph_adjacent(graph, n, ngraph, k, i) && + (sc->possible[k] & currc)) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) { + char buf[80], *sep = ""; + int r; + + printf("%*sforcing chain, colour %s, ", + 2*sc->depth, "", + colourset(buf, origc)); + for (r = j; r != -1; r = sc->bfsprev[r]) { + printf("%s%d", sep, r); + sep = "-"; + } + printf("\n%*s ruling out %s in region" + " %d\n", 2*sc->depth, "", + colourset(buf, origc), k); + } +#endif + sc->possible[k] &= ~origc; + done_something = TRUE; + } + } + } + + assert(tail <= n); + } + } + if (!done_something) break; } /* - * We've run out of things to deduce. See if we've got the lot. + * See if we've got a complete solution, and return if so. */ for (i = 0; i < n; i++) if (colouring[i] < 0) - return 2; + break; + if (i == n) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*sone solution found\n", 2*sc->depth, ""); +#endif + return 1; /* success! */ + } + + /* + * If recursion is not permissible, we now give up. + */ + if (difficulty < DIFF_RECURSE) { +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*sunable to proceed further without recursion\n", + 2*sc->depth, ""); +#endif + return 2; /* unable to complete */ + } + + /* + * Now we've got to do something recursive. So first hunt for a + * currently-most-constrained region. + */ + { + int best, bestc; + struct solver_scratch *rsc; + int *subcolouring, *origcolouring; + int ret, subret; + int we_already_got_one; + + best = -1; + bestc = FIVE; + + for (i = 0; i < n; i++) if (colouring[i] < 0) { + int p = sc->possible[i]; + enum { compile_time_assertion = 1 / (FOUR <= 4) }; + int c; + + /* Count the set bits. */ + c = (p & 5) + ((p >> 1) & 5); + c = (c & 3) + ((c >> 2) & 3); + assert(c > 1); /* or colouring[i] would be >= 0 */ + + if (c < bestc) { + best = i; + bestc = c; + } + } + + assert(best >= 0); /* or we'd be solved already */ - return 1; /* success! */ +#ifdef SOLVER_DIAGNOSTICS + if (verbose) + printf("%*srecursing on region %d\n", 2*sc->depth, "", best); +#endif + + /* + * Now iterate over the possible colours for this region. + */ + rsc = new_scratch(graph, n, ngraph); + rsc->depth = sc->depth + 1; + origcolouring = snewn(n, int); + memcpy(origcolouring, colouring, n * sizeof(int)); + subcolouring = snewn(n, int); + we_already_got_one = FALSE; + ret = 0; + + for (i = 0; i < FOUR; i++) { + if (!(sc->possible[best] & (1 << i))) + continue; + + memcpy(rsc->possible, sc->possible, n); + memcpy(subcolouring, origcolouring, n * sizeof(int)); + + place_colour(rsc, subcolouring, best, i +#ifdef SOLVER_DIAGNOSTICS + , "trying" +#endif + ); + + subret = map_solver(rsc, graph, n, ngraph, + subcolouring, difficulty); + +#ifdef SOLVER_DIAGNOSTICS + if (verbose) { + printf("%*sretracting %c in region %d; found %s\n", + 2*sc->depth, "", colnames[i], best, + subret == 0 ? "no solutions" : + subret == 1 ? "one solution" : "multiple solutions"); + } +#endif + + /* + * If this possibility turned up more than one valid + * solution, or if it turned up one and we already had + * one, we're definitely ambiguous. + */ + if (subret == 2 || (subret == 1 && we_already_got_one)) { + ret = 2; + break; + } + + /* + * If this possibility turned up one valid solution and + * it's the first we've seen, copy it into the output. + */ + if (subret == 1) { + memcpy(colouring, subcolouring, n * sizeof(int)); + we_already_got_one = TRUE; + ret = 1; + } + + /* + * Otherwise, this guess led to a contradiction, so we + * do nothing. + */ + } + + sfree(origcolouring); + sfree(subcolouring); + free_scratch(rsc); + +#ifdef SOLVER_DIAGNOSTICS + if (verbose && sc->depth == 0) { + printf("%*s%s found\n", + 2*sc->depth, "", + ret == 0 ? "no solutions" : + ret == 1 ? "one solution" : "multiple solutions"); + } +#endif + return ret; + } } /* ---------------------------------------------------------------------- @@ -1146,8 +1569,8 @@ static char *new_game_desc(game_params *params, random_state *rs, * Finally, check that the puzzle is _at least_ as hard as * required, and indeed that it isn't already solved. * (Calling map_solver with negative difficulty ensures the - * latter - if a solver which _does nothing_ can't solve - * it, it's too easy!) + * latter - if a solver which _does nothing_ can solve it, + * it's too easy!) */ memcpy(colouring2, colouring, n*sizeof(int)); if (map_solver(sc, graph, n, ngraph, colouring2, @@ -1155,7 +1578,7 @@ static char *new_game_desc(game_params *params, random_state *rs, /* * Drop minimum difficulty if necessary. */ - if (mindiff > 0 && (n < 9 || n > 3*wh/2)) { + if (mindiff > 0 && (n < 9 || n > 2*wh/3)) { if (tries-- <= 0) mindiff = 0; /* give up and go for Easy */ } @@ -1287,8 +1710,7 @@ static char *parse_edge_list(game_params *params, char **desc, int *map) int i, k, pos, state; char *p = *desc; - for (i = 0; i < wh; i++) - map[wh+i] = i; + dsf_init(map+wh, wh); pos = -1; state = 0; @@ -1367,9 +1789,9 @@ static char *validate_desc(game_params *params, char *desc) map = snewn(2*wh, int); ret = parse_edge_list(params, &desc, map); + sfree(map); if (ret) return ret; - sfree(map); if (*desc != ',') return "Expected comma before clue list"; @@ -1404,6 +1826,9 @@ static game_state *new_game(midend *me, game_params *params, char *desc) state->colouring = snewn(n, int); for (i = 0; i < n; i++) state->colouring[i] = -1; + state->pencil = snewn(n, int); + for (i = 0; i < n; i++) + state->pencil[i] = 0; state->completed = state->cheated = FALSE; @@ -1457,7 +1882,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) * outlines by the judicious use of diagonally divided squares. */ { - random_state *rs = random_init(desc, strlen(desc)); + random_state *rs = random_new(desc, strlen(desc)); int *squares = snewn(wh, int); int done_something; @@ -1508,34 +1933,37 @@ static game_state *new_game(midend *me, game_params *params, char *desc) /* * Analyse the map to find a canonical line segment - * corresponding to each edge. These are where we'll eventually - * put error markers. + * corresponding to each edge, and a canonical point + * corresponding to each region. The former are where we'll + * eventually put error markers; the latter are where we'll put + * per-region flags such as numbers (when in diagnostic mode). */ { int *bestx, *besty, *an, pass; float *ax, *ay, *best; - ax = snewn(state->map->ngraph, float); - ay = snewn(state->map->ngraph, float); - an = snewn(state->map->ngraph, int); - bestx = snewn(state->map->ngraph, int); - besty = snewn(state->map->ngraph, int); - best = snewn(state->map->ngraph, float); + ax = snewn(state->map->ngraph + n, float); + ay = snewn(state->map->ngraph + n, float); + an = snewn(state->map->ngraph + n, int); + bestx = snewn(state->map->ngraph + n, int); + besty = snewn(state->map->ngraph + n, int); + best = snewn(state->map->ngraph + n, float); - for (i = 0; i < state->map->ngraph; i++) { + for (i = 0; i < state->map->ngraph + n; i++) { bestx[i] = besty[i] = -1; - best[i] = 2*(w+h)+1; + best[i] = (float)(2*(w+h)+1); ax[i] = ay[i] = 0.0F; an[i] = 0; } /* * We make two passes over the map, finding all the line - * segments separating regions. In the first pass, we - * compute the _average_ x and y coordinate of all the line - * segments separating each pair of regions; in the second - * pass, for each such average point, we find the line - * segment closest to it and call that canonical. + * segments separating regions and all the suitable points + * within regions. In the first pass, we compute the + * _average_ x and y coordinate of all the points in a + * given class; in the second pass, for each such average + * point, we find the candidate closest to it and call that + * canonical. * * Line segments are considered to have coordinates in * their centre. Thus, at least one coordinate for any line @@ -1547,52 +1975,111 @@ static game_state *new_game(midend *me, game_params *params, char *desc) for (y = 0; y < h; y++) for (x = 0; x < w; x++) { - int ex[3], ey[3], ea[3], eb[3], en = 0; + int ex[4], ey[4], ea[4], eb[4], en = 0; /* * Look for an edge to the right of this * square, an edge below it, and an edge in the - * middle of it. + * middle of it. Also look to see if the point + * at the bottom right of this square is on an + * edge (and isn't a place where more than two + * regions meet). */ if (x+1 < w) { /* right edge */ ea[en] = state->map->map[RE * wh + y*w+x]; eb[en] = state->map->map[LE * wh + y*w+(x+1)]; - if (ea[en] != eb[en]) { - ex[en] = (x+1)*2; - ey[en] = y*2+1; - en++; - } + ex[en] = (x+1)*2; + ey[en] = y*2+1; + en++; } if (y+1 < h) { /* bottom edge */ ea[en] = state->map->map[BE * wh + y*w+x]; eb[en] = state->map->map[TE * wh + (y+1)*w+x]; - if (ea[en] != eb[en]) { - ex[en] = x*2+1; - ey[en] = (y+1)*2; - en++; - } + ex[en] = x*2+1; + ey[en] = (y+1)*2; + en++; } /* diagonal edge */ ea[en] = state->map->map[TE * wh + y*w+x]; eb[en] = state->map->map[BE * wh + y*w+x]; - if (ea[en] != eb[en]) { - ex[en] = x*2+1; - ey[en] = y*2+1; - en++; + ex[en] = x*2+1; + ey[en] = y*2+1; + en++; + + if (x+1 < w && y+1 < h) { + /* bottom right corner */ + int oct[8], othercol, nchanges; + oct[0] = state->map->map[RE * wh + y*w+x]; + oct[1] = state->map->map[LE * wh + y*w+(x+1)]; + oct[2] = state->map->map[BE * wh + y*w+(x+1)]; + oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)]; + oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)]; + oct[5] = state->map->map[RE * wh + (y+1)*w+x]; + oct[6] = state->map->map[TE * wh + (y+1)*w+x]; + oct[7] = state->map->map[BE * wh + y*w+x]; + + othercol = -1; + nchanges = 0; + for (i = 0; i < 8; i++) { + if (oct[i] != oct[0]) { + if (othercol < 0) + othercol = oct[i]; + else if (othercol != oct[i]) + break; /* three colours at this point */ + } + if (oct[i] != oct[(i+1) & 7]) + nchanges++; + } + + /* + * Now if there are exactly two regions at + * this point (not one, and not three or + * more), and only two changes around the + * loop, then this is a valid place to put + * an error marker. + */ + if (i == 8 && othercol >= 0 && nchanges == 2) { + ea[en] = oct[0]; + eb[en] = othercol; + ex[en] = (x+1)*2; + ey[en] = (y+1)*2; + en++; + } + + /* + * If there's exactly _one_ region at this + * point, on the other hand, it's a valid + * place to put a region centre. + */ + if (othercol < 0) { + ea[en] = eb[en] = oct[0]; + ex[en] = (x+1)*2; + ey[en] = (y+1)*2; + en++; + } } /* - * Now process the edges we've found, one by + * Now process the points we've found, one by * one. */ for (i = 0; i < en; i++) { int emin = min(ea[i], eb[i]); int emax = max(ea[i], eb[i]); - int gindex = - graph_edge_index(state->map->graph, n, - state->map->ngraph, emin, emax); + int gindex; + + if (emin != emax) { + /* Graph edge */ + gindex = + graph_edge_index(state->map->graph, n, + state->map->ngraph, emin, + emax); + } else { + /* Region number */ + gindex = state->map->ngraph + emin; + } assert(gindex >= 0); @@ -1604,7 +2091,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) */ ax[gindex] += ex[i]; ay[gindex] += ey[i]; - an[gindex] += 1.0F; + an[gindex] += 1; } else { /* * In pass 1, work out whether this @@ -1616,7 +2103,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) assert(an[gindex] > 0); dx = ex[i] - ax[gindex]; dy = ey[i] - ay[gindex]; - d = sqrt(dx*dx + dy*dy); + d = (float)sqrt(dx*dx + dy*dy); if (d < best[gindex]) { best[gindex] = d; bestx[gindex] = ex[i]; @@ -1627,7 +2114,7 @@ static game_state *new_game(midend *me, game_params *params, char *desc) } if (pass == 0) { - for (i = 0; i < state->map->ngraph; i++) + for (i = 0; i < state->map->ngraph + n; i++) if (an[i] > 0) { ax[i] /= an[i]; ay[i] /= an[i]; @@ -1635,8 +2122,15 @@ static game_state *new_game(midend *me, game_params *params, char *desc) } } - state->map->edgex = bestx; - state->map->edgey = besty; + state->map->edgex = snewn(state->map->ngraph, int); + state->map->edgey = snewn(state->map->ngraph, int); + memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int)); + memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int)); + + state->map->regionx = snewn(n, int); + state->map->regiony = snewn(n, int); + memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int)); + memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int)); for (i = 0; i < state->map->ngraph; i++) if (state->map->edgex[i] < 0) { @@ -1653,6 +2147,8 @@ static game_state *new_game(midend *me, game_params *params, char *desc) sfree(ay); sfree(an); sfree(best); + sfree(bestx); + sfree(besty); } return state; @@ -1665,6 +2161,8 @@ static game_state *dup_game(game_state *state) ret->p = state->p; ret->colouring = snewn(state->p.n, int); memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int)); + ret->pencil = snewn(state->p.n, int); + memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int)); ret->map = state->map; ret->map->refcount++; ret->completed = state->completed; @@ -1681,8 +2179,11 @@ static void free_game(game_state *state) sfree(state->map->immutable); sfree(state->map->edgex); sfree(state->map->edgey); + sfree(state->map->regionx); + sfree(state->map->regiony); sfree(state->map); } + sfree(state->pencil); sfree(state->colouring); sfree(state); } @@ -1747,14 +2248,31 @@ static char *solve_game(game_state *state, game_state *currstate, return dupstr(aux); } +static int game_can_format_as_text_now(game_params *params) +{ + return TRUE; +} + static char *game_text_format(game_state *state) { return NULL; } struct game_ui { - int drag_colour; /* -1 means no drag active */ + /* + * drag_colour: + * + * - -2 means no drag currently active. + * - >=0 means we're dragging a solid colour. + * - -1 means we're dragging a blank space, and drag_pencil + * might or might not add some pencil-mark stipples to that. + */ + int drag_colour; + int drag_pencil; int dragx, dragy; + int show_numbers; + + int cur_x, cur_y, cur_visible, cur_moved, cur_lastmove; }; static game_ui *new_ui(game_state *state) @@ -1762,6 +2280,10 @@ static game_ui *new_ui(game_state *state) game_ui *ui = snew(game_ui); ui->dragx = ui->dragy = -1; ui->drag_colour = -2; + ui->drag_pencil = 0; + ui->show_numbers = FALSE; + ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_moved = 0; + ui->cur_lastmove = 0; return ui; } @@ -1786,25 +2308,40 @@ static void game_changed_state(game_ui *ui, game_state *oldstate, struct game_drawstate { int tilesize; - unsigned short *drawn, *todraw; + unsigned long *drawn, *todraw; int started; int dragx, dragy, drag_visible; blitter *bl; }; /* Flags in `drawn'. */ -#define ERR_T 0x0100 -#define ERR_B 0x0200 -#define ERR_L 0x0400 -#define ERR_R 0x0800 -#define ERR_C 0x1000 -#define ERR_MASK 0x1F00 +#define ERR_BASE 0x00800000L +#define ERR_MASK 0xFF800000L +#define PENCIL_T_BASE 0x00080000L +#define PENCIL_T_MASK 0x00780000L +#define PENCIL_B_BASE 0x00008000L +#define PENCIL_B_MASK 0x00078000L +#define PENCIL_MASK 0x007F8000L +#define SHOW_NUMBERS 0x00004000L #define TILESIZE (ds->tilesize) #define BORDER (TILESIZE) #define COORD(x) ( (x) * TILESIZE + BORDER ) #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) + /* + * EPSILON_FOO are epsilons added to absolute cursor position by + * cursor movement, such that in pathological cases (e.g. a very + * small diamond-shaped area) it's relatively easy to select the + * region you wanted. + */ + +#define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \ + ((button) == CURSOR_LEFT) ? -1 : 0) +#define EPSILON_Y(button) (((button) == CURSOR_DOWN) ? +1 : \ + ((button) == CURSOR_UP) ? -1 : 0) + + static int region_from_coords(game_state *state, game_drawstate *ds, int x, int y) { @@ -1827,17 +2364,69 @@ static int region_from_coords(game_state *state, game_drawstate *ds, static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, int x, int y, int button) { - char buf[80]; + char *bufp, buf[256]; + int alt_button; + + /* + * Enable or disable numeric labels on regions. + */ + if (button == 'l' || button == 'L') { + ui->show_numbers = !ui->show_numbers; + return ""; + } + + if (IS_CURSOR_MOVE(button)) { + move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h, 0); + ui->cur_visible = 1; + ui->cur_moved = 1; + ui->cur_lastmove = button; + ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(button); + ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(button); + return ""; + } + if (IS_CURSOR_SELECT(button)) { + if (!ui->cur_visible) { + ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove); + ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove); + ui->cur_visible = 1; + return ""; + } + if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */ + int r = region_from_coords(state, ds, ui->dragx, ui->dragy); + if (r >= 0) { + ui->drag_colour = state->colouring[r]; + ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r]; + } else { + ui->drag_colour = -1; + ui->drag_pencil = 0; + } + ui->cur_moved = 0; + return ""; + } else { /* currently cursor-dragging; drop the colour in the new region. */ + x = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove); + y = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove); + alt_button = (button == CURSOR_SELECT2) ? 1 : 0; + /* Double-select removes current colour. */ + if (!ui->cur_moved) ui->drag_colour = -1; + goto drag_dropped; + } + } if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { int r = region_from_coords(state, ds, x, y); - if (r >= 0) + if (r >= 0) { ui->drag_colour = state->colouring[r]; - else + ui->drag_pencil = state->pencil[r]; + if (ui->drag_colour >= 0) + ui->drag_pencil = 0; /* should be already, but double-check */ + } else { ui->drag_colour = -1; + ui->drag_pencil = 0; + } ui->dragx = x; ui->dragy = y; + ui->cur_visible = 0; return ""; } @@ -1850,14 +2439,23 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) && ui->drag_colour > -2) { + alt_button = (button == RIGHT_RELEASE) ? 1 : 0; + goto drag_dropped; + } + + return NULL; + +drag_dropped: + { int r = region_from_coords(state, ds, x, y); int c = ui->drag_colour; + int p = ui->drag_pencil; + int oldp; /* * Cancel the drag, whatever happens. */ ui->drag_colour = -2; - ui->dragx = ui->dragy = -1; if (r < 0) return ""; /* drag into border; do nothing else */ @@ -1865,14 +2463,38 @@ static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds, if (state->map->immutable[r]) return ""; /* can't change this region */ - if (state->colouring[r] == c) + if (state->colouring[r] == c && state->pencil[r] == p) return ""; /* don't _need_ to change this region */ - sprintf(buf, "%c:%d", (int)(c < 0 ? 'C' : '0' + c), r); - return dupstr(buf); - } + if (alt_button) { + if (state->colouring[r] >= 0) { + /* Can't pencil on a coloured region */ + return ""; + } else if (c >= 0) { + /* Right-dragging from colour to blank toggles one pencil */ + p = state->pencil[r] ^ (1 << c); + c = -1; + } + /* Otherwise, right-dragging from blank to blank is equivalent + * to left-dragging. */ + } - return NULL; + bufp = buf; + oldp = state->pencil[r]; + if (c != state->colouring[r]) { + bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r); + if (c >= 0) + oldp = 0; + } + if (p != oldp) { + int i; + for (i = 0; i < FOUR; i++) + if ((oldp ^ p) & (1 << i)) + bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r); + } + + return dupstr(buf+1); /* ignore first semicolon */ + } } static game_state *execute_move(game_state *state, char *move) @@ -1882,12 +2504,30 @@ static game_state *execute_move(game_state *state, char *move) int c, k, adv, i; while (*move) { + int pencil = FALSE; + c = *move; + if (c == 'p') { + pencil = TRUE; + c = *++move; + } if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) && sscanf(move+1, ":%d%n", &k, &adv) == 1 && k >= 0 && k < state->p.n) { move += 1 + adv; - ret->colouring[k] = (c == 'C' ? -1 : c - '0'); + if (pencil) { + if (ret->colouring[k] >= 0) { + free_game(ret); + return NULL; + } + if (c == 'C') + ret->pencil[k] = 0; + else + ret->pencil[k] ^= 1 << (c - '0'); + } else { + ret->colouring[k] = (c == 'C' ? -1 : c - '0'); + ret->pencil[k] = 0; + } } else if (*move == 'S') { move++; ret->cheated = TRUE; @@ -1954,22 +2594,29 @@ static void game_set_size(drawing *dr, game_drawstate *ds, { ds->tilesize = tilesize; - if (ds->bl) - blitter_free(dr, ds->bl); + assert(!ds->bl); /* set_size is never called twice */ ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3); } const float map_colours[FOUR][3] = { +#ifdef VIVID_COLOURS + /* Use more vivid colours (e.g. on the Pocket PC) */ + {0.75F, 0.25F, 0.25F}, + {0.3F, 0.7F, 0.3F}, + {0.3F, 0.3F, 0.7F}, + {0.85F, 0.85F, 0.1F}, +#else {0.7F, 0.5F, 0.4F}, {0.8F, 0.7F, 0.4F}, {0.5F, 0.6F, 0.4F}, {0.55F, 0.45F, 0.35F}, +#endif }; const int map_hatching[FOUR] = { HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH }; -static float *game_colours(frontend *fe, game_state *state, int *ncolours) +static float *game_colours(frontend *fe, int *ncolours) { float *ret = snewn(3 * NCOLOURS, float); @@ -2002,10 +2649,10 @@ static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) int i; ds->tilesize = 0; - ds->drawn = snewn(state->p.w * state->p.h, unsigned short); + ds->drawn = snewn(state->p.w * state->p.h, unsigned long); for (i = 0; i < state->p.w * state->p.h; i++) - ds->drawn[i] = 0xFFFF; - ds->todraw = snewn(state->p.w * state->p.h, unsigned short); + ds->drawn[i] = 0xFFFFL; + ds->todraw = snewn(state->p.w * state->p.h, unsigned long); ds->started = FALSE; ds->bl = NULL; ds->drag_visible = FALSE; @@ -2049,20 +2696,25 @@ static void draw_error(drawing *dr, game_drawstate *ds, int x, int y) */ xext = TILESIZE/16; yext = TILESIZE*2/5 - (xext*2+2); - draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3+1), + draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3), COL_ERRTEXT); - draw_rect(dr, x-xext, y+yext-xext*2, xext*2+1, xext*2+1, COL_ERRTEXT); + draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT); } static void draw_square(drawing *dr, game_drawstate *ds, game_params *params, struct map *map, - int x, int y, int v) + int x, int y, unsigned long v) { int w = params->w, h = params->h, wh = w*h; - int tv, bv, errs; + int tv, bv, xo, yo, i, j, oldj; + unsigned long errs, pencil, show_numbers; errs = v & ERR_MASK; v &= ~ERR_MASK; + pencil = v & PENCIL_MASK; + v &= ~PENCIL_MASK; + show_numbers = v & SHOW_NUMBERS; + v &= ~SHOW_NUMBERS; tv = v / FIVE; bv = v % FIVE; @@ -2093,6 +2745,41 @@ static void draw_square(drawing *dr, game_drawstate *ds, } /* + * Draw `pencil marks'. Currently we arrange these in a square + * formation, which means we may be in trouble if the value of + * FOUR changes later... + */ + assert(FOUR == 4); + for (yo = 0; yo < 4; yo++) + for (xo = 0; xo < 4; xo++) { + int te = map->map[TE * wh + y*w+x]; + int e, ee, c; + + e = (yo < xo && yo < 3-xo ? TE : + yo > xo && yo > 3-xo ? BE : + xo < 2 ? LE : RE); + ee = map->map[e * wh + y*w+x]; + + if (xo != (yo * 2 + 1) % 5) + continue; + c = yo; + + if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c))) + continue; + + if (yo == xo && + (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x])) + continue; /* avoid TL-BR diagonal line */ + if (yo == 3-xo && + (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x])) + continue; /* avoid BL-TR diagonal line */ + + draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5, + COORD(y) + (yo+1)*TILESIZE/5, + TILESIZE/7, COL_0 + c, COL_0 + c); + } + + /* * Draw the grid lines, if required. */ if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x]) @@ -2107,16 +2794,37 @@ static void draw_square(drawing *dr, game_drawstate *ds, /* * Draw error markers. */ - if (errs & ERR_T) - draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y)); - if (errs & ERR_L) - draw_error(dr, ds, COORD(x), COORD(y)+TILESIZE/2); - if (errs & ERR_B) - draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y+1)); - if (errs & ERR_R) - draw_error(dr, ds, COORD(x+1), COORD(y)+TILESIZE/2); - if (errs & ERR_C) - draw_error(dr, ds, COORD(x)+TILESIZE/2, COORD(y)+TILESIZE/2); + for (yo = 0; yo < 3; yo++) + for (xo = 0; xo < 3; xo++) + if (errs & (ERR_BASE << (yo*3+xo))) + draw_error(dr, ds, + (COORD(x)*2+TILESIZE*xo)/2, + (COORD(y)*2+TILESIZE*yo)/2); + + /* + * Draw region numbers, if desired. + */ + if (show_numbers) { + oldj = -1; + for (i = 0; i < 2; i++) { + j = map->map[(i?BE:TE)*wh+y*w+x]; + if (oldj == j) + continue; + oldj = j; + + xo = map->regionx[j] - 2*x; + yo = map->regiony[j] - 2*y; + if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) { + char buf[80]; + sprintf(buf, "%d", j); + draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2, + (COORD(y)*2+TILESIZE*yo)/2, + FONT_VARIABLE, 3*TILESIZE/5, + ALIGN_HCENTRE|ALIGN_VCENTRE, + COL_GRID, buf); + } + } + } unclip(dr); @@ -2170,7 +2878,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, for (x = 0; x < w; x++) { int tv = state->colouring[state->map->map[TE * wh + y*w+x]]; int bv = state->colouring[state->map->map[BE * wh + y*w+x]]; - int v; + unsigned long v; if (tv < 0) tv = FOUR; @@ -2196,6 +2904,21 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, v = tv * FIVE + bv; + /* + * Add pencil marks. + */ + for (i = 0; i < FOUR; i++) { + if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 && + (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<colouring[state->map->map[BE * wh + y*w+x]] < 0 && + (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<show_numbers) + v |= SHOW_NUMBERS; + ds->todraw[y*w+x] = v; } @@ -2205,6 +2928,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, for (i = 0; i < state->map->ngraph; i++) { int v1 = state->map->graph[i] / n; int v2 = state->map->graph[i] % n; + int xo, yo; if (state->colouring[v1] < 0 || state->colouring[v2] < 0) continue; @@ -2214,15 +2938,21 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, x = state->map->edgex[i]; y = state->map->edgey[i]; - if (x % 2 && y % 2) { - ds->todraw[(y/2)*w+(x/2)] |= ERR_C; - } else if (x % 2) { - ds->todraw[(y/2-1)*w+(x/2)] |= ERR_B; - ds->todraw[(y/2)*w+(x/2)] |= ERR_T; - } else { - assert(y % 2); - ds->todraw[(y/2)*w+(x/2-1)] |= ERR_R; - ds->todraw[(y/2)*w+(x/2)] |= ERR_L; + xo = x % 2; x /= 2; + yo = y % 2; y /= 2; + + ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo); + if (xo == 0) { + assert(x > 0); + ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2); + } + if (yo == 0) { + assert(y > 0); + ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo); + } + if (xo == 0 && yo == 0) { + assert(x > 0 && y > 0); + ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2); } } @@ -2231,7 +2961,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, */ for (y = 0; y < h; y++) for (x = 0; x < w; x++) { - int v = ds->todraw[y*w+x]; + unsigned long v = ds->todraw[y*w+x]; if (ds->drawn[y*w+x] != v) { draw_square(dr, ds, &state->p, state->map, x, y, v); ds->drawn[y*w+x] = v; @@ -2241,13 +2971,31 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, /* * Draw the dragged colour blob if any. */ - if (ui->drag_colour > -2) { + if ((ui->drag_colour > -2) || ui->cur_visible) { + int bg, iscur = 0; + if (ui->drag_colour >= 0) + bg = COL_0 + ui->drag_colour; + else if (ui->drag_colour == -1) { + bg = COL_BACKGROUND; + } else { + int r = region_from_coords(state, ds, ui->dragx, ui->dragy); + int c = (r < 0) ? -1 : state->colouring[r]; + assert(ui->cur_visible); + /*bg = COL_GRID;*/ + bg = (c < 0) ? COL_BACKGROUND : COL_0 + c; + iscur = 1; + } + ds->dragx = ui->dragx - TILESIZE/2 - 2; ds->dragy = ui->dragy - TILESIZE/2 - 2; blitter_save(dr, ds->bl, ds->dragx, ds->dragy); - draw_circle(dr, ui->dragx, ui->dragy, TILESIZE/2, - (ui->drag_colour < 0 ? COL_BACKGROUND : - COL_0 + ui->drag_colour), COL_GRID); + draw_circle(dr, ui->dragx, ui->dragy, + iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID); + for (i = 0; i < FOUR; i++) + if (ui->drag_pencil & (1 << i)) + draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10, + ui->dragy + (i*2-3) * TILESIZE/10, + TILESIZE/8, COL_0 + i, COL_0 + i); draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); ds->drag_visible = TRUE; } @@ -2270,16 +3018,16 @@ static float game_flash_length(game_state *oldstate, game_state *newstate, flash_type = atoi(env); else flash_type = 0; - flash_length = (flash_type == 1 ? 0.50 : 0.30); + flash_length = (flash_type == 1 ? 0.50F : 0.30F); } return flash_length; } else return 0.0F; } -static int game_wants_statusbar(void) +static int game_status(game_state *state) { - return FALSE; + return state->completed ? +1 : 0; } static int game_timing_state(game_state *state, game_ui *ui) @@ -2297,8 +3045,8 @@ static void game_print_size(game_params *params, float *x, float *y) * given tile size and then scale. */ game_compute_size(params, 400, &pw, &ph); - *x = pw / 100.0; - *y = ph / 100.0; + *x = pw / 100.0F; + *y = ph / 100.0F; } static void game_print(drawing *dr, game_state *state, int tilesize) @@ -2310,12 +3058,14 @@ static void game_print(drawing *dr, game_state *state, int tilesize) /* Ick: fake up `ds->tilesize' for macro expansion purposes */ struct { int tilesize; } ads, *ds = &ads; + /* We can't call game_set_size() here because we don't want a blitter */ ads.tilesize = tilesize; ink = print_mono_colour(dr, 0); for (i = 0; i < FOUR; i++) - c[i] = print_rgb_colour(dr, map_hatching[i], map_colours[i][0], - map_colours[i][1], map_colours[i][2]); + c[i] = print_rgb_hatched_colour(dr, map_colours[i][0], + map_colours[i][1], map_colours[i][2], + map_hatching[i]); coordsize = 0; coords = NULL; @@ -2405,7 +3155,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) else d2 = i; } -/* printf("%% %d,%d r=%d: d1=%d d2=%d lastdir=%d\n", x, y, r, d1, d2, lastdir); */ + assert(d1 != -1 && d2 != -1); if (d1 == lastdir) d1 = d2; @@ -2443,7 +3193,7 @@ static void game_print(drawing *dr, game_state *state, int tilesize) #endif const struct game thegame = { - "Map", "games.map", + "Map", "games.map", "map", default_params, game_fetch_preset, decode_params, @@ -2458,7 +3208,7 @@ const struct game thegame = { dup_game, free_game, TRUE, solve_game, - FALSE, game_text_format, + FALSE, game_can_format_as_text_now, game_text_format, new_ui, free_ui, encode_ui, @@ -2473,8 +3223,114 @@ const struct game thegame = { game_redraw, game_anim_length, game_flash_length, + game_status, TRUE, TRUE, game_print_size, game_print, - game_wants_statusbar, + FALSE, /* wants_statusbar */ FALSE, game_timing_state, - 0, /* mouse_priorities */ + 0, /* flags */ }; + +#ifdef STANDALONE_SOLVER + +int main(int argc, char **argv) +{ + game_params *p; + game_state *s; + char *id = NULL, *desc, *err; + int grade = FALSE; + int ret, diff, really_verbose = FALSE; + struct solver_scratch *sc; + int i; + + while (--argc > 0) { + char *p = *++argv; + if (!strcmp(p, "-v")) { + really_verbose = TRUE; + } else if (!strcmp(p, "-g")) { + grade = TRUE; + } else if (*p == '-') { + fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); + return 1; + } else { + id = p; + } + } + + if (!id) { + fprintf(stderr, "usage: %s [-g | -v] \n", argv[0]); + return 1; + } + + desc = strchr(id, ':'); + if (!desc) { + fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); + return 1; + } + *desc++ = '\0'; + + p = default_params(); + decode_params(p, id); + err = validate_desc(p, desc); + if (err) { + fprintf(stderr, "%s: %s\n", argv[0], err); + return 1; + } + s = new_game(NULL, p, desc); + + sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph); + + /* + * When solving an Easy puzzle, we don't want to bother the + * user with Hard-level deductions. For this reason, we grade + * the puzzle internally before doing anything else. + */ + ret = -1; /* placate optimiser */ + for (diff = 0; diff < DIFFCOUNT; diff++) { + for (i = 0; i < s->map->n; i++) + if (!s->map->immutable[i]) + s->colouring[i] = -1; + ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph, + s->colouring, diff); + if (ret < 2) + break; + } + + if (diff == DIFFCOUNT) { + if (grade) + printf("Difficulty rating: harder than Hard, or ambiguous\n"); + else + printf("Unable to find a unique solution\n"); + } else { + if (grade) { + if (ret == 0) + printf("Difficulty rating: impossible (no solution exists)\n"); + else if (ret == 1) + printf("Difficulty rating: %s\n", map_diffnames[diff]); + } else { + verbose = really_verbose; + for (i = 0; i < s->map->n; i++) + if (!s->map->immutable[i]) + s->colouring[i] = -1; + ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph, + s->colouring, diff); + if (ret == 0) + printf("Puzzle is inconsistent\n"); + else { + int col = 0; + + for (i = 0; i < s->map->n; i++) { + printf("%5d <- %c%c", i, colnames[s->colouring[i]], + (col < 6 && i+1 < s->map->n ? ' ' : '\n')); + if (++col == 7) + col = 0; + } + } + } + } + + return 0; +} + +#endif + +/* vim: set shiftwidth=4 tabstop=8: */