X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=map.c;h=f1af38ba5edaa0d80af92cee5160079b92ad5a0e;hb=08927a3b285307a7f1dca250277e2ef8597180ea;hp=2e1e097fa8387bf8789828801ea53e085bfef2aa;hpb=b0614e6da8f8a709e8fad797d7bb6ba05491ac79;p=sgt-puzzles.git diff --git a/map.c b/map.c index 2e1e097..f1af38b 100644 --- a/map.c +++ b/map.c @@ -5,11 +5,8 @@ /* * TODO: * - * - error highlighting * - clue marking - * - more solver brains? * - better four-colouring algorithm? - * - pencil marks? */ #include @@ -21,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,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 @@ -59,6 +70,7 @@ enum { COL_BACKGROUND, COL_GRID, COL_0, COL_1, COL_2, COL_3, + COL_ERROR, COL_ERRTEXT, NCOLOURS }; @@ -73,12 +85,14 @@ struct map { int n; int ngraph; int *immutable; + 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; }; @@ -86,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; @@ -95,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) @@ -124,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 */ @@ -161,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]; @@ -172,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]; @@ -210,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); @@ -222,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"; @@ -607,7 +638,7 @@ static int gengraph(int w, int h, int n, int *map, int *graph) return j; } -static int graph_adjacent(int *graph, int n, int ngraph, int i, int j) +static int graph_edge_index(int *graph, int n, int ngraph, int i, int j) { int v = i*n+j; int top, bot, mid; @@ -617,15 +648,18 @@ static int graph_adjacent(int *graph, int n, int ngraph, int i, int j) while (top - bot > 1) { mid = (top + bot) / 2; if (graph[mid] == v) - return TRUE; + return mid; else if (graph[mid] < v) bot = mid; else top = mid; } - return FALSE; + return -1; } +#define graph_adjacent(graph, n, ngraph, i, j) \ + (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0) + static int graph_vertex_start(int *graph, int n, int ngraph, int i) { int v = i*n; @@ -782,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) @@ -796,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; } @@ -803,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 @@ -841,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. @@ -872,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; } } @@ -907,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 */ @@ -942,31 +1082,318 @@ 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 */ + +#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); - return 1; /* success! */ +#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; + } } /* ---------------------------------------------------------------------- * 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; @@ -1142,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, @@ -1151,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 */ } @@ -1277,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; @@ -1354,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; @@ -1363,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"; @@ -1389,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; @@ -1453,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; @@ -1502,16 +1933,238 @@ static game_state *new_game(midend *me, game_params *params, char *desc) random_free(rs); } + /* + * Analyse the map to find a canonical line segment + * 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 + 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 + n; i++) { + bestx[i] = besty[i] = -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 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 + * segment is always something-and-a-half; so we store our + * coordinates as twice their normal value. + */ + for (pass = 0; pass < 2; pass++) { + int x, y; + + for (y = 0; y < h; y++) + for (x = 0; x < w; x++) { + 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. 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)]; + 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]; + 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]; + 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 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; + + 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); + + if (pass == 0) { + /* + * In pass 0, accumulate the values + * we'll use to compute the average + * positions. + */ + ax[gindex] += ex[i]; + ay[gindex] += ey[i]; + an[gindex] += 1; + } else { + /* + * In pass 1, work out whether this + * point is closer to the average than + * the last one we've seen. + */ + float dx, dy, d; + + assert(an[gindex] > 0); + dx = ex[i] - ax[gindex]; + dy = ey[i] - ay[gindex]; + d = (float)sqrt(dx*dx + dy*dy); + if (d < best[gindex]) { + best[gindex] = d; + bestx[gindex] = ex[i]; + besty[gindex] = ey[i]; + } + } + } + } + + if (pass == 0) { + for (i = 0; i < state->map->ngraph + n; i++) + if (an[i] > 0) { + ax[i] /= an[i]; + ay[i] /= an[i]; + } + } + } + + 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) { + /* Find the other representation of this edge. */ + int e = state->map->graph[i]; + int iprime = graph_edge_index(state->map->graph, n, + state->map->ngraph, e%n, e/n); + assert(state->map->edgex[iprime] >= 0); + state->map->edgex[i] = state->map->edgex[iprime]; + state->map->edgey[i] = state->map->edgey[iprime]; + } + + sfree(ax); + 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; @@ -1526,14 +2179,19 @@ static void free_game(game_state *state) sfree(state->map->map); sfree(state->map->graph); 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) { /* @@ -1592,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; } @@ -1615,35 +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 char *drawn; + unsigned long *drawn, *todraw; int started; int dragx, dragy, drag_visible; blitter *bl; }; +/* Flags in `drawn'. */ +#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); @@ -1661,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 ""; } @@ -1687,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 */ @@ -1702,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; @@ -1775,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; @@ -1787,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); @@ -1821,17 +2634,28 @@ static float *game_colours(frontend *fe, game_state *state, int *ncolours) memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float)); memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float)); + ret[COL_ERROR * 3 + 0] = 1.0F; + ret[COL_ERROR * 3 + 1] = 0.0F; + ret[COL_ERROR * 3 + 2] = 0.0F; + + ret[COL_ERRTEXT * 3 + 0] = 1.0F; + ret[COL_ERRTEXT * 3 + 1] = 1.0F; + ret[COL_ERRTEXT * 3 + 2] = 1.0F; + *ncolours = 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 char); - memset(ds->drawn, 0xFF, state->p.w * state->p.h); + 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] = 0xFFFFL; + ds->todraw = snewn(state->p.w * state->p.h, unsigned long); ds->started = FALSE; ds->bl = NULL; ds->drag_visible = FALSE; @@ -1843,17 +2667,59 @@ static game_drawstate *game_new_drawstate(drawing *dr, game_state *state) static void game_free_drawstate(drawing *dr, game_drawstate *ds) { sfree(ds->drawn); + sfree(ds->todraw); if (ds->bl) blitter_free(dr, ds->bl); sfree(ds); } +static void draw_error(drawing *dr, game_drawstate *ds, int x, int y) +{ + int coords[8]; + int yext, xext; + + /* + * Draw a diamond. + */ + coords[0] = x - TILESIZE*2/5; + coords[1] = y; + coords[2] = x; + coords[3] = y - TILESIZE*2/5; + coords[4] = x + TILESIZE*2/5; + coords[5] = y; + coords[6] = x; + coords[7] = y + TILESIZE*2/5; + draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID); + + /* + * Draw an exclamation mark in the diamond. This turns out to + * look unpleasantly off-centre if done via draw_text, so I do + * it by hand on the basis that exclamation marks aren't that + * difficult to draw... + */ + 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), + 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) + 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 = v / FIVE, bv = v % FIVE; + 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; clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); @@ -1881,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. */ @@ -1893,16 +2794,53 @@ static void draw_square(drawing *dr, game_drawstate *ds, map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x]) draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID); + /* + * Draw error markers. + */ + 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); + 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; + int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; + int x, y, i; int flash; if (ds->drag_visible) { @@ -1937,11 +2875,14 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate, } else flash = -1; + /* + * Set up the `todraw' array. + */ for (y = 0; y < h; y++) 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; @@ -1967,6 +2908,64 @@ 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; + } + + /* + * Add error markers to the `todraw' array. + */ + 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; + if (state->colouring[v1] != state->colouring[v2]) + continue; + + x = state->map->edgex[i]; + y = state->map->edgey[i]; + + 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); + } + } + + /* + * Now actually draw everything. + */ + for (y = 0; y < h; y++) + for (x = 0; x < 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; @@ -1976,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) { @@ -2005,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; @@ -2032,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; @@ -2045,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; @@ -2140,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; @@ -2178,9 +3197,9 @@ 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, + game_fetch_preset, NULL, decode_params, encode_params, free_params, @@ -2193,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, @@ -2208,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: */