X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=map.c;h=f3c4430391e1a59d7ee678a841918fdee01d577f;hb=3ce69e84cad15844282d691fa03e711c5353c05e;hp=45d632903b66e3e999d2203568942ebc9ab75b3b;hpb=4d6c8c73373bf7eb1f72b1cf4fbb78a5719ade3f;p=sgt-puzzles.git diff --git a/map.c b/map.c index 45d6329..f3c4430 100644 --- a/map.c +++ b/map.c @@ -6,9 +6,7 @@ * TODO: * * - clue marking - * - more solver brains? * - better four-colouring algorithm? - * - pencil marks? */ #include @@ -20,6 +18,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 @@ -43,6 +53,7 @@ static float flash_length; #define DIFFLIST(A) \ A(EASY,Easy,e) \ 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, @@ -74,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; }; @@ -88,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; @@ -97,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) @@ -126,7 +155,7 @@ static void free_params(game_params *params) 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 */ @@ -163,7 +192,7 @@ static void decode_params(game_params *params, char const *string) } } -static char *encode_params(game_params *params, int full) +static char *encode_params(const game_params *params, int full) { char ret[400]; @@ -174,7 +203,7 @@ static char *encode_params(game_params *params, int full) return dupstr(ret); } -static config_item *game_configure(game_params *params) +static config_item *game_configure(const game_params *params) { config_item *ret; char buf[80]; @@ -212,7 +241,7 @@ static config_item *game_configure(game_params *params) 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); @@ -224,7 +253,7 @@ static game_params *custom_params(config_item *cfg) return ret; } -static char *validate_params(game_params *params, int full) +static char *validate_params(const game_params *params, int full) { if (params->w < 2 || params->h < 2) return "Width and height must be at least two"; @@ -787,9 +816,17 @@ 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; }; @@ -803,6 +840,11 @@ static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) 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; } @@ -810,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 @@ -848,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. @@ -879,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; } } @@ -914,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 */ @@ -949,12 +1082,168 @@ 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; } @@ -965,14 +1254,25 @@ static int map_solver(struct solver_scratch *sc, for (i = 0; i < n; i++) if (colouring[i] < 0) break; - if (i == n) + 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) + 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 @@ -1006,6 +1306,11 @@ static int map_solver(struct solver_scratch *sc, assert(best >= 0); /* or we'd be solved already */ +#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. */ @@ -1021,11 +1326,27 @@ static int map_solver(struct solver_scratch *sc, if (!(sc->possible[best] & (1 << i))) continue; + memcpy(rsc->possible, sc->possible, n); memcpy(subcolouring, origcolouring, n * sizeof(int)); - subcolouring[best] = i; + + 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 @@ -1052,9 +1373,18 @@ static int map_solver(struct solver_scratch *sc, */ } + 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; } } @@ -1063,7 +1393,7 @@ static int map_solver(struct solver_scratch *sc, * Game generation main function. */ -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) { struct solver_scratch *sc = NULL; @@ -1374,14 +1704,14 @@ static char *new_game_desc(game_params *params, random_state *rs, return ret; } -static char *parse_edge_list(game_params *params, char **desc, int *map) +static char *parse_edge_list(const game_params *params, const char **desc, + int *map) { int w = params->w, h = params->h, wh = w*h, n = params->n; int i, k, pos, state; - char *p = *desc; + const char *p = *desc; - for (i = 0; i < wh; i++) - map[wh+i] = i; + dsf_init(map+wh, wh); pos = -1; state = 0; @@ -1451,7 +1781,7 @@ static char *parse_edge_list(game_params *params, char **desc, int *map) return NULL; } -static char *validate_desc(game_params *params, char *desc) +static char *validate_desc(const game_params *params, const char *desc) { int w = params->w, h = params->h, wh = w*h, n = params->n; int area; @@ -1460,9 +1790,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"; @@ -1486,17 +1816,21 @@ static char *validate_desc(game_params *params, char *desc) return NULL; } -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) { int w = params->w, h = params->h, wh = w*h, n = params->n; int i, pos; - char *p; + const char *p; game_state *state = snew(game_state); state->p = *params; 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; @@ -1550,7 +1884,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; @@ -1601,34 +1935,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 @@ -1654,30 +1991,25 @@ static game_state *new_game(midend *me, game_params *params, char *desc) /* 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; @@ -1717,18 +2049,39 @@ static game_state *new_game(midend *me, game_params *params, char *desc) 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); @@ -1740,7 +2093,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 @@ -1752,7 +2105,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]; @@ -1763,7 +2116,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]; @@ -1771,8 +2124,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) { @@ -1789,18 +2149,22 @@ static game_state *new_game(midend *me, game_params *params, char *desc) sfree(ay); sfree(an); sfree(best); + sfree(bestx); + sfree(besty); } return state; } -static game_state *dup_game(game_state *state) +static game_state *dup_game(const game_state *state) { game_state *ret = snew(game_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; @@ -1817,14 +2181,17 @@ 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); } -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) { if (!aux) { /* @@ -1883,21 +2250,42 @@ static char *solve_game(game_state *state, game_state *currstate, return dupstr(aux); } -static char *game_text_format(game_state *state) +static int game_can_format_as_text_now(const game_params *params) +{ + return TRUE; +} + +static char *game_text_format(const 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) +static game_ui *new_ui(const 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; } @@ -1906,39 +2294,58 @@ static void free_ui(game_ui *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) { } 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_BASE 0x0080 -#define ERR_MASK 0xFF80 +#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 ) -static int region_from_coords(game_state *state, game_drawstate *ds, - int x, int y) + /* + * 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(const game_state *state, + const game_drawstate *ds, int x, int y) { int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */; int tx = FROMCOORD(x), ty = FROMCOORD(y); @@ -1956,20 +2363,73 @@ static int region_from_coords(game_state *state, game_drawstate *ds, return state->map->map[quadrant * wh + ty*w+tx]; } -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) { - 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 ""; } @@ -1982,14 +2442,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 */ @@ -1997,29 +2466,71 @@ 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) +static game_state *execute_move(const game_state *state, const char *move) { int n = state->p.n; game_state *ret = dup_game(state); 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; @@ -2070,8 +2581,8 @@ static game_state *execute_move(game_state *state, char *move) * 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; @@ -2082,26 +2593,33 @@ static void game_compute_size(game_params *params, int tilesize, } static void game_set_size(drawing *dr, game_drawstate *ds, - game_params *params, int tilesize) + const game_params *params, int tilesize) { 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); @@ -2128,16 +2646,16 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) 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 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; @@ -2187,14 +2705,19 @@ static void draw_error(drawing *dr, game_drawstate *ds, int x, int y) } static void draw_square(drawing *dr, game_drawstate *ds, - game_params *params, struct map *map, - int x, int y, int v) + const game_params *params, struct map *map, + int x, int y, unsigned long v) { int w = params->w, h = params->h, wh = w*h; - int tv, bv, xo, yo, 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; @@ -2224,6 +2747,41 @@ static void draw_square(drawing *dr, game_drawstate *ds, (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID); } + /* + * 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. */ @@ -2246,14 +2804,40 @@ static void draw_square(drawing *dr, game_drawstate *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); draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); } -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 w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; int x, y, i; @@ -2298,7 +2882,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; @@ -2324,6 +2908,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; } @@ -2366,7 +2965,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; @@ -2376,26 +2975,44 @@ 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; } } -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->cheated && !newstate->cheated) { @@ -2405,24 +3022,24 @@ 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(const game_state *state) { - return FALSE; + 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; @@ -2432,11 +3049,11 @@ 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) +static void game_print(drawing *dr, const game_state *state, int tilesize) { int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; int ink, c[FOUR], i; @@ -2445,12 +3062,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; @@ -2540,7 +3159,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; @@ -2578,7 +3197,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, @@ -2593,7 +3212,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, @@ -2608,8 +3227,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: */