diff options
author | Franklin Wei <frankhwei536@gmail.com> | 2016-11-20 15:16:41 -0500 |
---|---|---|
committer | Franklin Wei <me@fwei.tk> | 2016-12-18 18:13:22 +0100 |
commit | 1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99 (patch) | |
tree | 8e7f2d6b0cbdb5d15c13457b2c3e1de69f598440 /apps/plugins/puzzles/map.c | |
parent | 3ee79724f6fb033d50e26ef37b33d3f8cedf0c5b (diff) | |
download | rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.tar.gz rockbox-1a6a8b52f7aa4e2da6f4c34a0c743c760b8cfd99.zip |
Port of Simon Tatham's Puzzle Collection
Original revision: 5123b1bf68777ffa86e651f178046b26a87cf2d9
MIT Licensed. Some games still crash and others are unplayable due to
issues with controls. Still need a "real" polygon filling algorithm.
Currently builds one plugin per puzzle (about 40 in total, around 100K
each on ARM), but can easily be made to build a single monolithic
overlay (800K or so on ARM).
The following games are at least partially broken for various reasons,
and have been disabled on this commit:
Cube: failed assertion with "Icosahedron" setting
Keen: input issues
Mines: weird stuff happens on target
Palisade: input issues
Solo: input issues, occasional crash on target
Towers: input issues
Undead: input issues
Unequal: input and drawing issues (concave polys)
Untangle: input issues
Features left to do:
- In-game help system
- Figure out the weird bugs
Change-Id: I7c69b6860ab115f973c8d76799502e9bb3d52368
Diffstat (limited to 'apps/plugins/puzzles/map.c')
-rw-r--r-- | apps/plugins/puzzles/map.c | 3340 |
1 files changed, 3340 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/map.c b/apps/plugins/puzzles/map.c new file mode 100644 index 0000000000..6e9c12523a --- /dev/null +++ b/apps/plugins/puzzles/map.c | |||
@@ -0,0 +1,3340 @@ | |||
1 | /* | ||
2 | * map.c: Game involving four-colouring a map. | ||
3 | */ | ||
4 | |||
5 | /* | ||
6 | * TODO: | ||
7 | * | ||
8 | * - clue marking | ||
9 | * - better four-colouring algorithm? | ||
10 | */ | ||
11 | |||
12 | #include <stdio.h> | ||
13 | #include <stdlib.h> | ||
14 | #include <string.h> | ||
15 | #include "rbassert.h" | ||
16 | #include <ctype.h> | ||
17 | #include <math.h> | ||
18 | |||
19 | #include "puzzles.h" | ||
20 | |||
21 | /* | ||
22 | * In standalone solver mode, `verbose' is a variable which can be | ||
23 | * set by command-line option; in debugging mode it's simply always | ||
24 | * true. | ||
25 | */ | ||
26 | #if defined STANDALONE_SOLVER | ||
27 | #define SOLVER_DIAGNOSTICS | ||
28 | int verbose = FALSE; | ||
29 | #elif defined SOLVER_DIAGNOSTICS | ||
30 | #define verbose TRUE | ||
31 | #endif | ||
32 | |||
33 | /* | ||
34 | * I don't seriously anticipate wanting to change the number of | ||
35 | * colours used in this game, but it doesn't cost much to use a | ||
36 | * #define just in case :-) | ||
37 | */ | ||
38 | #define FOUR 4 | ||
39 | #define THREE (FOUR-1) | ||
40 | #define FIVE (FOUR+1) | ||
41 | #define SIX (FOUR+2) | ||
42 | |||
43 | /* | ||
44 | * Ghastly run-time configuration option, just for Gareth (again). | ||
45 | */ | ||
46 | static int flash_type = -1; | ||
47 | static float flash_length; | ||
48 | |||
49 | /* | ||
50 | * Difficulty levels. I do some macro ickery here to ensure that my | ||
51 | * enum and the various forms of my name list always match up. | ||
52 | */ | ||
53 | #define DIFFLIST(A) \ | ||
54 | A(EASY,Easy,e) \ | ||
55 | A(NORMAL,Normal,n) \ | ||
56 | A(HARD,Hard,h) \ | ||
57 | A(RECURSE,Unreasonable,u) | ||
58 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
59 | #define TITLE(upper,title,lower) #title, | ||
60 | #define ENCODE(upper,title,lower) #lower | ||
61 | #define CONFIG(upper,title,lower) ":" #title | ||
62 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
63 | static char const *const map_diffnames[] = { DIFFLIST(TITLE) }; | ||
64 | static char const map_diffchars[] = DIFFLIST(ENCODE); | ||
65 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
66 | |||
67 | enum { TE, BE, LE, RE }; /* top/bottom/left/right edges */ | ||
68 | |||
69 | enum { | ||
70 | COL_BACKGROUND, | ||
71 | COL_GRID, | ||
72 | COL_0, COL_1, COL_2, COL_3, | ||
73 | COL_ERROR, COL_ERRTEXT, | ||
74 | NCOLOURS | ||
75 | }; | ||
76 | |||
77 | struct game_params { | ||
78 | int w, h, n, diff; | ||
79 | }; | ||
80 | |||
81 | struct map { | ||
82 | int refcount; | ||
83 | int *map; | ||
84 | int *graph; | ||
85 | int n; | ||
86 | int ngraph; | ||
87 | int *immutable; | ||
88 | int *edgex, *edgey; /* position of a point on each edge */ | ||
89 | int *regionx, *regiony; /* position of a point in each region */ | ||
90 | }; | ||
91 | |||
92 | struct game_state { | ||
93 | game_params p; | ||
94 | struct map *map; | ||
95 | int *colouring, *pencil; | ||
96 | int completed, cheated; | ||
97 | }; | ||
98 | |||
99 | static game_params *default_params(void) | ||
100 | { | ||
101 | game_params *ret = snew(game_params); | ||
102 | |||
103 | #ifdef PORTRAIT_SCREEN | ||
104 | ret->w = 16; | ||
105 | ret->h = 18; | ||
106 | #else | ||
107 | ret->w = 20; | ||
108 | ret->h = 15; | ||
109 | #endif | ||
110 | ret->n = 30; | ||
111 | ret->diff = DIFF_NORMAL; | ||
112 | |||
113 | return ret; | ||
114 | } | ||
115 | |||
116 | static const struct game_params map_presets[] = { | ||
117 | #ifdef PORTRAIT_SCREEN | ||
118 | {16, 18, 30, DIFF_EASY}, | ||
119 | {16, 18, 30, DIFF_NORMAL}, | ||
120 | {16, 18, 30, DIFF_HARD}, | ||
121 | {16, 18, 30, DIFF_RECURSE}, | ||
122 | {25, 30, 75, DIFF_NORMAL}, | ||
123 | {25, 30, 75, DIFF_HARD}, | ||
124 | #else | ||
125 | {20, 15, 30, DIFF_EASY}, | ||
126 | {20, 15, 30, DIFF_NORMAL}, | ||
127 | {20, 15, 30, DIFF_HARD}, | ||
128 | {20, 15, 30, DIFF_RECURSE}, | ||
129 | {30, 25, 75, DIFF_NORMAL}, | ||
130 | {30, 25, 75, DIFF_HARD}, | ||
131 | #endif | ||
132 | }; | ||
133 | |||
134 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
135 | { | ||
136 | game_params *ret; | ||
137 | char str[80]; | ||
138 | |||
139 | if (i < 0 || i >= lenof(map_presets)) | ||
140 | return FALSE; | ||
141 | |||
142 | ret = snew(game_params); | ||
143 | *ret = map_presets[i]; | ||
144 | |||
145 | sprintf(str, "%dx%d, %d regions, %s", ret->w, ret->h, ret->n, | ||
146 | map_diffnames[ret->diff]); | ||
147 | |||
148 | *name = dupstr(str); | ||
149 | *params = ret; | ||
150 | return TRUE; | ||
151 | } | ||
152 | |||
153 | static void free_params(game_params *params) | ||
154 | { | ||
155 | sfree(params); | ||
156 | } | ||
157 | |||
158 | static game_params *dup_params(const game_params *params) | ||
159 | { | ||
160 | game_params *ret = snew(game_params); | ||
161 | *ret = *params; /* structure copy */ | ||
162 | return ret; | ||
163 | } | ||
164 | |||
165 | static void decode_params(game_params *params, char const *string) | ||
166 | { | ||
167 | char const *p = string; | ||
168 | |||
169 | params->w = atoi(p); | ||
170 | while (*p && isdigit((unsigned char)*p)) p++; | ||
171 | if (*p == 'x') { | ||
172 | p++; | ||
173 | params->h = atoi(p); | ||
174 | while (*p && isdigit((unsigned char)*p)) p++; | ||
175 | } else { | ||
176 | params->h = params->w; | ||
177 | } | ||
178 | if (*p == 'n') { | ||
179 | p++; | ||
180 | params->n = atoi(p); | ||
181 | while (*p && (*p == '.' || isdigit((unsigned char)*p))) p++; | ||
182 | } else { | ||
183 | params->n = params->w * params->h / 8; | ||
184 | } | ||
185 | if (*p == 'd') { | ||
186 | int i; | ||
187 | p++; | ||
188 | for (i = 0; i < DIFFCOUNT; i++) | ||
189 | if (*p == map_diffchars[i]) | ||
190 | params->diff = i; | ||
191 | if (*p) p++; | ||
192 | } | ||
193 | } | ||
194 | |||
195 | static char *encode_params(const game_params *params, int full) | ||
196 | { | ||
197 | char ret[400]; | ||
198 | |||
199 | sprintf(ret, "%dx%dn%d", params->w, params->h, params->n); | ||
200 | if (full) | ||
201 | sprintf(ret + strlen(ret), "d%c", map_diffchars[params->diff]); | ||
202 | |||
203 | return dupstr(ret); | ||
204 | } | ||
205 | |||
206 | static config_item *game_configure(const game_params *params) | ||
207 | { | ||
208 | config_item *ret; | ||
209 | char buf[80]; | ||
210 | |||
211 | ret = snewn(5, config_item); | ||
212 | |||
213 | ret[0].name = "Width"; | ||
214 | ret[0].type = C_STRING; | ||
215 | sprintf(buf, "%d", params->w); | ||
216 | ret[0].sval = dupstr(buf); | ||
217 | ret[0].ival = 0; | ||
218 | |||
219 | ret[1].name = "Height"; | ||
220 | ret[1].type = C_STRING; | ||
221 | sprintf(buf, "%d", params->h); | ||
222 | ret[1].sval = dupstr(buf); | ||
223 | ret[1].ival = 0; | ||
224 | |||
225 | ret[2].name = "Regions"; | ||
226 | ret[2].type = C_STRING; | ||
227 | sprintf(buf, "%d", params->n); | ||
228 | ret[2].sval = dupstr(buf); | ||
229 | ret[2].ival = 0; | ||
230 | |||
231 | ret[3].name = "Difficulty"; | ||
232 | ret[3].type = C_CHOICES; | ||
233 | ret[3].sval = DIFFCONFIG; | ||
234 | ret[3].ival = params->diff; | ||
235 | |||
236 | ret[4].name = NULL; | ||
237 | ret[4].type = C_END; | ||
238 | ret[4].sval = NULL; | ||
239 | ret[4].ival = 0; | ||
240 | |||
241 | return ret; | ||
242 | } | ||
243 | |||
244 | static game_params *custom_params(const config_item *cfg) | ||
245 | { | ||
246 | game_params *ret = snew(game_params); | ||
247 | |||
248 | ret->w = atoi(cfg[0].sval); | ||
249 | ret->h = atoi(cfg[1].sval); | ||
250 | ret->n = atoi(cfg[2].sval); | ||
251 | ret->diff = cfg[3].ival; | ||
252 | |||
253 | return ret; | ||
254 | } | ||
255 | |||
256 | static char *validate_params(const game_params *params, int full) | ||
257 | { | ||
258 | if (params->w < 2 || params->h < 2) | ||
259 | return "Width and height must be at least two"; | ||
260 | if (params->n < 5) | ||
261 | return "Must have at least five regions"; | ||
262 | if (params->n > params->w * params->h) | ||
263 | return "Too many regions to fit in grid"; | ||
264 | return NULL; | ||
265 | } | ||
266 | |||
267 | /* ---------------------------------------------------------------------- | ||
268 | * Cumulative frequency table functions. | ||
269 | */ | ||
270 | |||
271 | /* | ||
272 | * Initialise a cumulative frequency table. (Hardly worth writing | ||
273 | * this function; all it does is to initialise everything in the | ||
274 | * array to zero.) | ||
275 | */ | ||
276 | static void cf_init(int *table, int n) | ||
277 | { | ||
278 | int i; | ||
279 | |||
280 | for (i = 0; i < n; i++) | ||
281 | table[i] = 0; | ||
282 | } | ||
283 | |||
284 | /* | ||
285 | * Increment the count of symbol `sym' by `count'. | ||
286 | */ | ||
287 | static void cf_add(int *table, int n, int sym, int count) | ||
288 | { | ||
289 | int bit; | ||
290 | |||
291 | bit = 1; | ||
292 | while (sym != 0) { | ||
293 | if (sym & bit) { | ||
294 | table[sym] += count; | ||
295 | sym &= ~bit; | ||
296 | } | ||
297 | bit <<= 1; | ||
298 | } | ||
299 | |||
300 | table[0] += count; | ||
301 | } | ||
302 | |||
303 | /* | ||
304 | * Cumulative frequency lookup: return the total count of symbols | ||
305 | * with value less than `sym'. | ||
306 | */ | ||
307 | static int cf_clookup(int *table, int n, int sym) | ||
308 | { | ||
309 | int bit, index, limit, count; | ||
310 | |||
311 | if (sym == 0) | ||
312 | return 0; | ||
313 | |||
314 | assert(0 < sym && sym <= n); | ||
315 | |||
316 | count = table[0]; /* start with the whole table size */ | ||
317 | |||
318 | bit = 1; | ||
319 | while (bit < n) | ||
320 | bit <<= 1; | ||
321 | |||
322 | limit = n; | ||
323 | |||
324 | while (bit > 0) { | ||
325 | /* | ||
326 | * Find the least number with its lowest set bit in this | ||
327 | * position which is greater than or equal to sym. | ||
328 | */ | ||
329 | index = ((sym + bit - 1) &~ (bit * 2 - 1)) + bit; | ||
330 | |||
331 | if (index < limit) { | ||
332 | count -= table[index]; | ||
333 | limit = index; | ||
334 | } | ||
335 | |||
336 | bit >>= 1; | ||
337 | } | ||
338 | |||
339 | return count; | ||
340 | } | ||
341 | |||
342 | /* | ||
343 | * Single frequency lookup: return the count of symbol `sym'. | ||
344 | */ | ||
345 | static int cf_slookup(int *table, int n, int sym) | ||
346 | { | ||
347 | int count, bit; | ||
348 | |||
349 | assert(0 <= sym && sym < n); | ||
350 | |||
351 | count = table[sym]; | ||
352 | |||
353 | for (bit = 1; sym+bit < n && !(sym & bit); bit <<= 1) | ||
354 | count -= table[sym+bit]; | ||
355 | |||
356 | return count; | ||
357 | } | ||
358 | |||
359 | /* | ||
360 | * Return the largest symbol index such that the cumulative | ||
361 | * frequency up to that symbol is less than _or equal to_ count. | ||
362 | */ | ||
363 | static int cf_whichsym(int *table, int n, int count) { | ||
364 | int bit, sym, top; | ||
365 | |||
366 | assert(count >= 0 && count < table[0]); | ||
367 | |||
368 | bit = 1; | ||
369 | while (bit < n) | ||
370 | bit <<= 1; | ||
371 | |||
372 | sym = 0; | ||
373 | top = table[0]; | ||
374 | |||
375 | while (bit > 0) { | ||
376 | if (sym+bit < n) { | ||
377 | if (count >= top - table[sym+bit]) | ||
378 | sym += bit; | ||
379 | else | ||
380 | top -= table[sym+bit]; | ||
381 | } | ||
382 | |||
383 | bit >>= 1; | ||
384 | } | ||
385 | |||
386 | return sym; | ||
387 | } | ||
388 | |||
389 | /* ---------------------------------------------------------------------- | ||
390 | * Map generation. | ||
391 | * | ||
392 | * FIXME: this isn't entirely optimal at present, because it | ||
393 | * inherently prioritises growing the largest region since there | ||
394 | * are more squares adjacent to it. This acts as a destabilising | ||
395 | * influence leading to a few large regions and mostly small ones. | ||
396 | * It might be better to do it some other way. | ||
397 | */ | ||
398 | |||
399 | #define WEIGHT_INCREASED 2 /* for increased perimeter */ | ||
400 | #define WEIGHT_DECREASED 4 /* for decreased perimeter */ | ||
401 | #define WEIGHT_UNCHANGED 3 /* for unchanged perimeter */ | ||
402 | |||
403 | /* | ||
404 | * Look at a square and decide which colours can be extended into | ||
405 | * it. | ||
406 | * | ||
407 | * If called with index < 0, it adds together one of | ||
408 | * WEIGHT_INCREASED, WEIGHT_DECREASED or WEIGHT_UNCHANGED for each | ||
409 | * colour that has a valid extension (according to the effect that | ||
410 | * it would have on the perimeter of the region being extended) and | ||
411 | * returns the overall total. | ||
412 | * | ||
413 | * If called with index >= 0, it returns one of the possible | ||
414 | * colours depending on the value of index, in such a way that the | ||
415 | * number of possible inputs which would give rise to a given | ||
416 | * return value correspond to the weight of that value. | ||
417 | */ | ||
418 | static int extend_options(int w, int h, int n, int *map, | ||
419 | int x, int y, int index) | ||
420 | { | ||
421 | int c, i, dx, dy; | ||
422 | int col[8]; | ||
423 | int total = 0; | ||
424 | |||
425 | if (map[y*w+x] >= 0) { | ||
426 | assert(index < 0); | ||
427 | return 0; /* can't do this square at all */ | ||
428 | } | ||
429 | |||
430 | /* | ||
431 | * Fetch the eight neighbours of this square, in order around | ||
432 | * the square. | ||
433 | */ | ||
434 | for (dy = -1; dy <= +1; dy++) | ||
435 | for (dx = -1; dx <= +1; dx++) { | ||
436 | int index = (dy < 0 ? 6-dx : dy > 0 ? 2+dx : 2*(1+dx)); | ||
437 | if (x+dx >= 0 && x+dx < w && y+dy >= 0 && y+dy < h) | ||
438 | col[index] = map[(y+dy)*w+(x+dx)]; | ||
439 | else | ||
440 | col[index] = -1; | ||
441 | } | ||
442 | |||
443 | /* | ||
444 | * Iterate over each colour that might be feasible. | ||
445 | * | ||
446 | * FIXME: this routine currently has O(n) running time. We | ||
447 | * could turn it into O(FOUR) by only bothering to iterate over | ||
448 | * the colours mentioned in the four neighbouring squares. | ||
449 | */ | ||
450 | |||
451 | for (c = 0; c < n; c++) { | ||
452 | int count, neighbours, runs; | ||
453 | |||
454 | /* | ||
455 | * One of the even indices of col (representing the | ||
456 | * orthogonal neighbours of this square) must be equal to | ||
457 | * c, or else this square is not adjacent to region c and | ||
458 | * obviously cannot become an extension of it at this time. | ||
459 | */ | ||
460 | neighbours = 0; | ||
461 | for (i = 0; i < 8; i += 2) | ||
462 | if (col[i] == c) | ||
463 | neighbours++; | ||
464 | if (!neighbours) | ||
465 | continue; | ||
466 | |||
467 | /* | ||
468 | * Now we know this square is adjacent to region c. The | ||
469 | * next question is, would extending it cause the region to | ||
470 | * become non-simply-connected? If so, we mustn't do it. | ||
471 | * | ||
472 | * We determine this by looking around col to see if we can | ||
473 | * find more than one separate run of colour c. | ||
474 | */ | ||
475 | runs = 0; | ||
476 | for (i = 0; i < 8; i++) | ||
477 | if (col[i] == c && col[(i+1) & 7] != c) | ||
478 | runs++; | ||
479 | if (runs > 1) | ||
480 | continue; | ||
481 | |||
482 | assert(runs == 1); | ||
483 | |||
484 | /* | ||
485 | * This square is a possibility. Determine its effect on | ||
486 | * the region's perimeter (computed from the number of | ||
487 | * orthogonal neighbours - 1 means a perimeter increase, 3 | ||
488 | * a decrease, 2 no change; 4 is impossible because the | ||
489 | * region would already not be simply connected) and we're | ||
490 | * done. | ||
491 | */ | ||
492 | assert(neighbours > 0 && neighbours < 4); | ||
493 | count = (neighbours == 1 ? WEIGHT_INCREASED : | ||
494 | neighbours == 2 ? WEIGHT_UNCHANGED : WEIGHT_DECREASED); | ||
495 | |||
496 | total += count; | ||
497 | if (index >= 0 && index < count) | ||
498 | return c; | ||
499 | else | ||
500 | index -= count; | ||
501 | } | ||
502 | |||
503 | assert(index < 0); | ||
504 | |||
505 | return total; | ||
506 | } | ||
507 | |||
508 | static void genmap(int w, int h, int n, int *map, random_state *rs) | ||
509 | { | ||
510 | int wh = w*h; | ||
511 | int x, y, i, k; | ||
512 | int *tmp; | ||
513 | |||
514 | assert(n <= wh); | ||
515 | tmp = snewn(wh, int); | ||
516 | |||
517 | /* | ||
518 | * Clear the map, and set up `tmp' as a list of grid indices. | ||
519 | */ | ||
520 | for (i = 0; i < wh; i++) { | ||
521 | map[i] = -1; | ||
522 | tmp[i] = i; | ||
523 | } | ||
524 | |||
525 | /* | ||
526 | * Place the region seeds by selecting n members from `tmp'. | ||
527 | */ | ||
528 | k = wh; | ||
529 | for (i = 0; i < n; i++) { | ||
530 | int j = random_upto(rs, k); | ||
531 | map[tmp[j]] = i; | ||
532 | tmp[j] = tmp[--k]; | ||
533 | } | ||
534 | |||
535 | /* | ||
536 | * Re-initialise `tmp' as a cumulative frequency table. This | ||
537 | * will store the number of possible region colours we can | ||
538 | * extend into each square. | ||
539 | */ | ||
540 | cf_init(tmp, wh); | ||
541 | |||
542 | /* | ||
543 | * Go through the grid and set up the initial cumulative | ||
544 | * frequencies. | ||
545 | */ | ||
546 | for (y = 0; y < h; y++) | ||
547 | for (x = 0; x < w; x++) | ||
548 | cf_add(tmp, wh, y*w+x, | ||
549 | extend_options(w, h, n, map, x, y, -1)); | ||
550 | |||
551 | /* | ||
552 | * Now repeatedly choose a square we can extend a region into, | ||
553 | * and do so. | ||
554 | */ | ||
555 | while (tmp[0] > 0) { | ||
556 | int k = random_upto(rs, tmp[0]); | ||
557 | int sq; | ||
558 | int colour; | ||
559 | int xx, yy; | ||
560 | |||
561 | sq = cf_whichsym(tmp, wh, k); | ||
562 | k -= cf_clookup(tmp, wh, sq); | ||
563 | x = sq % w; | ||
564 | y = sq / w; | ||
565 | colour = extend_options(w, h, n, map, x, y, k); | ||
566 | |||
567 | map[sq] = colour; | ||
568 | |||
569 | /* | ||
570 | * Re-scan the nine cells around the one we've just | ||
571 | * modified. | ||
572 | */ | ||
573 | for (yy = max(y-1, 0); yy < min(y+2, h); yy++) | ||
574 | for (xx = max(x-1, 0); xx < min(x+2, w); xx++) { | ||
575 | cf_add(tmp, wh, yy*w+xx, | ||
576 | -cf_slookup(tmp, wh, yy*w+xx) + | ||
577 | extend_options(w, h, n, map, xx, yy, -1)); | ||
578 | } | ||
579 | } | ||
580 | |||
581 | /* | ||
582 | * Finally, go through and normalise the region labels into | ||
583 | * order, meaning that indistinguishable maps are actually | ||
584 | * identical. | ||
585 | */ | ||
586 | for (i = 0; i < n; i++) | ||
587 | tmp[i] = -1; | ||
588 | k = 0; | ||
589 | for (i = 0; i < wh; i++) { | ||
590 | assert(map[i] >= 0); | ||
591 | if (tmp[map[i]] < 0) | ||
592 | tmp[map[i]] = k++; | ||
593 | map[i] = tmp[map[i]]; | ||
594 | } | ||
595 | |||
596 | sfree(tmp); | ||
597 | } | ||
598 | |||
599 | /* ---------------------------------------------------------------------- | ||
600 | * Functions to handle graphs. | ||
601 | */ | ||
602 | |||
603 | /* | ||
604 | * Having got a map in a square grid, convert it into a graph | ||
605 | * representation. | ||
606 | */ | ||
607 | static int gengraph(int w, int h, int n, int *map, int *graph) | ||
608 | { | ||
609 | int i, j, x, y; | ||
610 | |||
611 | /* | ||
612 | * Start by setting the graph up as an adjacency matrix. We'll | ||
613 | * turn it into a list later. | ||
614 | */ | ||
615 | for (i = 0; i < n*n; i++) | ||
616 | graph[i] = 0; | ||
617 | |||
618 | /* | ||
619 | * Iterate over the map looking for all adjacencies. | ||
620 | */ | ||
621 | for (y = 0; y < h; y++) | ||
622 | for (x = 0; x < w; x++) { | ||
623 | int v, vx, vy; | ||
624 | v = map[y*w+x]; | ||
625 | if (x+1 < w && (vx = map[y*w+(x+1)]) != v) | ||
626 | graph[v*n+vx] = graph[vx*n+v] = 1; | ||
627 | if (y+1 < h && (vy = map[(y+1)*w+x]) != v) | ||
628 | graph[v*n+vy] = graph[vy*n+v] = 1; | ||
629 | } | ||
630 | |||
631 | /* | ||
632 | * Turn the matrix into a list. | ||
633 | */ | ||
634 | for (i = j = 0; i < n*n; i++) | ||
635 | if (graph[i]) | ||
636 | graph[j++] = i; | ||
637 | |||
638 | return j; | ||
639 | } | ||
640 | |||
641 | static int graph_edge_index(int *graph, int n, int ngraph, int i, int j) | ||
642 | { | ||
643 | int v = i*n+j; | ||
644 | int top, bot, mid; | ||
645 | |||
646 | bot = -1; | ||
647 | top = ngraph; | ||
648 | while (top - bot > 1) { | ||
649 | mid = (top + bot) / 2; | ||
650 | if (graph[mid] == v) | ||
651 | return mid; | ||
652 | else if (graph[mid] < v) | ||
653 | bot = mid; | ||
654 | else | ||
655 | top = mid; | ||
656 | } | ||
657 | return -1; | ||
658 | } | ||
659 | |||
660 | #define graph_adjacent(graph, n, ngraph, i, j) \ | ||
661 | (graph_edge_index((graph), (n), (ngraph), (i), (j)) >= 0) | ||
662 | |||
663 | static int graph_vertex_start(int *graph, int n, int ngraph, int i) | ||
664 | { | ||
665 | int v = i*n; | ||
666 | int top, bot, mid; | ||
667 | |||
668 | bot = -1; | ||
669 | top = ngraph; | ||
670 | while (top - bot > 1) { | ||
671 | mid = (top + bot) / 2; | ||
672 | if (graph[mid] < v) | ||
673 | bot = mid; | ||
674 | else | ||
675 | top = mid; | ||
676 | } | ||
677 | return top; | ||
678 | } | ||
679 | |||
680 | /* ---------------------------------------------------------------------- | ||
681 | * Generate a four-colouring of a graph. | ||
682 | * | ||
683 | * FIXME: it would be nice if we could convert this recursion into | ||
684 | * pseudo-recursion using some sort of explicit stack array, for | ||
685 | * the sake of the Palm port and its limited stack. | ||
686 | */ | ||
687 | |||
688 | static int fourcolour_recurse(int *graph, int n, int ngraph, | ||
689 | int *colouring, int *scratch, random_state *rs) | ||
690 | { | ||
691 | int nfree, nvert, start, i, j, k, c, ci; | ||
692 | int cs[FOUR]; | ||
693 | |||
694 | /* | ||
695 | * Find the smallest number of free colours in any uncoloured | ||
696 | * vertex, and count the number of such vertices. | ||
697 | */ | ||
698 | |||
699 | nfree = FIVE; /* start off bigger than FOUR! */ | ||
700 | nvert = 0; | ||
701 | for (i = 0; i < n; i++) | ||
702 | if (colouring[i] < 0 && scratch[i*FIVE+FOUR] <= nfree) { | ||
703 | if (nfree > scratch[i*FIVE+FOUR]) { | ||
704 | nfree = scratch[i*FIVE+FOUR]; | ||
705 | nvert = 0; | ||
706 | } | ||
707 | nvert++; | ||
708 | } | ||
709 | |||
710 | /* | ||
711 | * If there aren't any uncoloured vertices at all, we're done. | ||
712 | */ | ||
713 | if (nvert == 0) | ||
714 | return TRUE; /* we've got a colouring! */ | ||
715 | |||
716 | /* | ||
717 | * Pick a random vertex in that set. | ||
718 | */ | ||
719 | j = random_upto(rs, nvert); | ||
720 | for (i = 0; i < n; i++) | ||
721 | if (colouring[i] < 0 && scratch[i*FIVE+FOUR] == nfree) | ||
722 | if (j-- == 0) | ||
723 | break; | ||
724 | assert(i < n); | ||
725 | start = graph_vertex_start(graph, n, ngraph, i); | ||
726 | |||
727 | /* | ||
728 | * Loop over the possible colours for i, and recurse for each | ||
729 | * one. | ||
730 | */ | ||
731 | ci = 0; | ||
732 | for (c = 0; c < FOUR; c++) | ||
733 | if (scratch[i*FIVE+c] == 0) | ||
734 | cs[ci++] = c; | ||
735 | shuffle(cs, ci, sizeof(*cs), rs); | ||
736 | |||
737 | while (ci-- > 0) { | ||
738 | c = cs[ci]; | ||
739 | |||
740 | /* | ||
741 | * Fill in this colour. | ||
742 | */ | ||
743 | colouring[i] = c; | ||
744 | |||
745 | /* | ||
746 | * Update the scratch space to reflect a new neighbour | ||
747 | * of this colour for each neighbour of vertex i. | ||
748 | */ | ||
749 | for (j = start; j < ngraph && graph[j] < n*(i+1); j++) { | ||
750 | k = graph[j] - i*n; | ||
751 | if (scratch[k*FIVE+c] == 0) | ||
752 | scratch[k*FIVE+FOUR]--; | ||
753 | scratch[k*FIVE+c]++; | ||
754 | } | ||
755 | |||
756 | /* | ||
757 | * Recurse. | ||
758 | */ | ||
759 | if (fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs)) | ||
760 | return TRUE; /* got one! */ | ||
761 | |||
762 | /* | ||
763 | * If that didn't work, clean up and try again with a | ||
764 | * different colour. | ||
765 | */ | ||
766 | for (j = start; j < ngraph && graph[j] < n*(i+1); j++) { | ||
767 | k = graph[j] - i*n; | ||
768 | scratch[k*FIVE+c]--; | ||
769 | if (scratch[k*FIVE+c] == 0) | ||
770 | scratch[k*FIVE+FOUR]++; | ||
771 | } | ||
772 | colouring[i] = -1; | ||
773 | } | ||
774 | |||
775 | /* | ||
776 | * If we reach here, we were unable to find a colouring at all. | ||
777 | * (This doesn't necessarily mean the Four Colour Theorem is | ||
778 | * violated; it might just mean we've gone down a dead end and | ||
779 | * need to back up and look somewhere else. It's only an FCT | ||
780 | * violation if we get all the way back up to the top level and | ||
781 | * still fail.) | ||
782 | */ | ||
783 | return FALSE; | ||
784 | } | ||
785 | |||
786 | static void fourcolour(int *graph, int n, int ngraph, int *colouring, | ||
787 | random_state *rs) | ||
788 | { | ||
789 | int *scratch; | ||
790 | int i; | ||
791 | |||
792 | /* | ||
793 | * For each vertex and each colour, we store the number of | ||
794 | * neighbours that have that colour. Also, we store the number | ||
795 | * of free colours for the vertex. | ||
796 | */ | ||
797 | scratch = snewn(n * FIVE, int); | ||
798 | for (i = 0; i < n * FIVE; i++) | ||
799 | scratch[i] = (i % FIVE == FOUR ? FOUR : 0); | ||
800 | |||
801 | /* | ||
802 | * Clear the colouring to start with. | ||
803 | */ | ||
804 | for (i = 0; i < n; i++) | ||
805 | colouring[i] = -1; | ||
806 | |||
807 | i = fourcolour_recurse(graph, n, ngraph, colouring, scratch, rs); | ||
808 | assert(i); /* by the Four Colour Theorem :-) */ | ||
809 | |||
810 | sfree(scratch); | ||
811 | } | ||
812 | |||
813 | /* ---------------------------------------------------------------------- | ||
814 | * Non-recursive solver. | ||
815 | */ | ||
816 | |||
817 | struct solver_scratch { | ||
818 | unsigned char *possible; /* bitmap of colours for each region */ | ||
819 | |||
820 | int *graph; | ||
821 | int n; | ||
822 | int ngraph; | ||
823 | |||
824 | int *bfsqueue; | ||
825 | int *bfscolour; | ||
826 | #ifdef SOLVER_DIAGNOSTICS | ||
827 | int *bfsprev; | ||
828 | #endif | ||
829 | |||
830 | int depth; | ||
831 | }; | ||
832 | |||
833 | static struct solver_scratch *new_scratch(int *graph, int n, int ngraph) | ||
834 | { | ||
835 | struct solver_scratch *sc; | ||
836 | |||
837 | sc = snew(struct solver_scratch); | ||
838 | sc->graph = graph; | ||
839 | sc->n = n; | ||
840 | sc->ngraph = ngraph; | ||
841 | sc->possible = snewn(n, unsigned char); | ||
842 | sc->depth = 0; | ||
843 | sc->bfsqueue = snewn(n, int); | ||
844 | sc->bfscolour = snewn(n, int); | ||
845 | #ifdef SOLVER_DIAGNOSTICS | ||
846 | sc->bfsprev = snewn(n, int); | ||
847 | #endif | ||
848 | |||
849 | return sc; | ||
850 | } | ||
851 | |||
852 | static void free_scratch(struct solver_scratch *sc) | ||
853 | { | ||
854 | sfree(sc->possible); | ||
855 | sfree(sc->bfsqueue); | ||
856 | sfree(sc->bfscolour); | ||
857 | #ifdef SOLVER_DIAGNOSTICS | ||
858 | sfree(sc->bfsprev); | ||
859 | #endif | ||
860 | sfree(sc); | ||
861 | } | ||
862 | |||
863 | /* | ||
864 | * Count the bits in a word. Only needs to cope with FOUR bits. | ||
865 | */ | ||
866 | static int bitcount(int word) | ||
867 | { | ||
868 | assert(FOUR <= 4); /* or this needs changing */ | ||
869 | word = ((word & 0xA) >> 1) + (word & 0x5); | ||
870 | word = ((word & 0xC) >> 2) + (word & 0x3); | ||
871 | return word; | ||
872 | } | ||
873 | |||
874 | #ifdef SOLVER_DIAGNOSTICS | ||
875 | static const char colnames[FOUR] = { 'R', 'Y', 'G', 'B' }; | ||
876 | #endif | ||
877 | |||
878 | static int place_colour(struct solver_scratch *sc, | ||
879 | int *colouring, int index, int colour | ||
880 | #ifdef SOLVER_DIAGNOSTICS | ||
881 | , char *verb | ||
882 | #endif | ||
883 | ) | ||
884 | { | ||
885 | int *graph = sc->graph, n = sc->n, ngraph = sc->ngraph; | ||
886 | int j, k; | ||
887 | |||
888 | if (!(sc->possible[index] & (1 << colour))) { | ||
889 | #ifdef SOLVER_DIAGNOSTICS | ||
890 | if (verbose) | ||
891 | printf("%*scannot place %c in region %d\n", 2*sc->depth, "", | ||
892 | colnames[colour], index); | ||
893 | #endif | ||
894 | return FALSE; /* can't do it */ | ||
895 | } | ||
896 | |||
897 | sc->possible[index] = 1 << colour; | ||
898 | colouring[index] = colour; | ||
899 | |||
900 | #ifdef SOLVER_DIAGNOSTICS | ||
901 | if (verbose) | ||
902 | printf("%*s%s %c in region %d\n", 2*sc->depth, "", | ||
903 | verb, colnames[colour], index); | ||
904 | #endif | ||
905 | |||
906 | /* | ||
907 | * Rule out this colour from all the region's neighbours. | ||
908 | */ | ||
909 | for (j = graph_vertex_start(graph, n, ngraph, index); | ||
910 | j < ngraph && graph[j] < n*(index+1); j++) { | ||
911 | k = graph[j] - index*n; | ||
912 | #ifdef SOLVER_DIAGNOSTICS | ||
913 | if (verbose && (sc->possible[k] & (1 << colour))) | ||
914 | printf("%*s ruling out %c in region %d\n", 2*sc->depth, "", | ||
915 | colnames[colour], k); | ||
916 | #endif | ||
917 | sc->possible[k] &= ~(1 << colour); | ||
918 | } | ||
919 | |||
920 | return TRUE; | ||
921 | } | ||
922 | |||
923 | #ifdef SOLVER_DIAGNOSTICS | ||
924 | static char *colourset(char *buf, int set) | ||
925 | { | ||
926 | int i; | ||
927 | char *p = buf; | ||
928 | char *sep = ""; | ||
929 | |||
930 | for (i = 0; i < FOUR; i++) | ||
931 | if (set & (1 << i)) { | ||
932 | p += sprintf(p, "%s%c", sep, colnames[i]); | ||
933 | sep = ","; | ||
934 | } | ||
935 | |||
936 | return buf; | ||
937 | } | ||
938 | #endif | ||
939 | |||
940 | /* | ||
941 | * Returns 0 for impossible, 1 for success, 2 for failure to | ||
942 | * converge (i.e. puzzle is either ambiguous or just too | ||
943 | * difficult). | ||
944 | */ | ||
945 | static int map_solver(struct solver_scratch *sc, | ||
946 | int *graph, int n, int ngraph, int *colouring, | ||
947 | int difficulty) | ||
948 | { | ||
949 | int i; | ||
950 | |||
951 | if (sc->depth == 0) { | ||
952 | /* | ||
953 | * Initialise scratch space. | ||
954 | */ | ||
955 | for (i = 0; i < n; i++) | ||
956 | sc->possible[i] = (1 << FOUR) - 1; | ||
957 | |||
958 | /* | ||
959 | * Place clues. | ||
960 | */ | ||
961 | for (i = 0; i < n; i++) | ||
962 | if (colouring[i] >= 0) { | ||
963 | if (!place_colour(sc, colouring, i, colouring[i] | ||
964 | #ifdef SOLVER_DIAGNOSTICS | ||
965 | , "initial clue:" | ||
966 | #endif | ||
967 | )) { | ||
968 | #ifdef SOLVER_DIAGNOSTICS | ||
969 | if (verbose) | ||
970 | printf("%*sinitial clue set is inconsistent\n", | ||
971 | 2*sc->depth, ""); | ||
972 | #endif | ||
973 | return 0; /* the clues aren't even consistent! */ | ||
974 | } | ||
975 | } | ||
976 | } | ||
977 | |||
978 | /* | ||
979 | * Now repeatedly loop until we find nothing further to do. | ||
980 | */ | ||
981 | while (1) { | ||
982 | int done_something = FALSE; | ||
983 | |||
984 | if (difficulty < DIFF_EASY) | ||
985 | break; /* can't do anything at all! */ | ||
986 | |||
987 | /* | ||
988 | * Simplest possible deduction: find a region with only one | ||
989 | * possible colour. | ||
990 | */ | ||
991 | for (i = 0; i < n; i++) if (colouring[i] < 0) { | ||
992 | int p = sc->possible[i]; | ||
993 | |||
994 | if (p == 0) { | ||
995 | #ifdef SOLVER_DIAGNOSTICS | ||
996 | if (verbose) | ||
997 | printf("%*sregion %d has no possible colours left\n", | ||
998 | 2*sc->depth, "", i); | ||
999 | #endif | ||
1000 | return 0; /* puzzle is inconsistent */ | ||
1001 | } | ||
1002 | |||
1003 | if ((p & (p-1)) == 0) { /* p is a power of two */ | ||
1004 | int c, ret; | ||
1005 | for (c = 0; c < FOUR; c++) | ||
1006 | if (p == (1 << c)) | ||
1007 | break; | ||
1008 | assert(c < FOUR); | ||
1009 | ret = place_colour(sc, colouring, i, c | ||
1010 | #ifdef SOLVER_DIAGNOSTICS | ||
1011 | , "placing" | ||
1012 | #endif | ||
1013 | ); | ||
1014 | /* | ||
1015 | * place_colour() can only fail if colour c was not | ||
1016 | * even a _possibility_ for region i, and we're | ||
1017 | * pretty sure it was because we checked before | ||
1018 | * calling place_colour(). So we can safely assert | ||
1019 | * here rather than having to return a nice | ||
1020 | * friendly error code. | ||
1021 | */ | ||
1022 | assert(ret); | ||
1023 | done_something = TRUE; | ||
1024 | } | ||
1025 | } | ||
1026 | |||
1027 | if (done_something) | ||
1028 | continue; | ||
1029 | |||
1030 | if (difficulty < DIFF_NORMAL) | ||
1031 | break; /* can't do anything harder */ | ||
1032 | |||
1033 | /* | ||
1034 | * Failing that, go up one level. Look for pairs of regions | ||
1035 | * which (a) both have the same pair of possible colours, | ||
1036 | * (b) are adjacent to one another, (c) are adjacent to the | ||
1037 | * same region, and (d) that region still thinks it has one | ||
1038 | * or both of those possible colours. | ||
1039 | * | ||
1040 | * Simplest way to do this is by going through the graph | ||
1041 | * edge by edge, so that we start with property (b) and | ||
1042 | * then look for (a) and finally (c) and (d). | ||
1043 | */ | ||
1044 | for (i = 0; i < ngraph; i++) { | ||
1045 | int j1 = graph[i] / n, j2 = graph[i] % n; | ||
1046 | int j, k, v, v2; | ||
1047 | #ifdef SOLVER_DIAGNOSTICS | ||
1048 | int started = FALSE; | ||
1049 | #endif | ||
1050 | |||
1051 | if (j1 > j2) | ||
1052 | continue; /* done it already, other way round */ | ||
1053 | |||
1054 | if (colouring[j1] >= 0 || colouring[j2] >= 0) | ||
1055 | continue; /* they're not undecided */ | ||
1056 | |||
1057 | if (sc->possible[j1] != sc->possible[j2]) | ||
1058 | continue; /* they don't have the same possibles */ | ||
1059 | |||
1060 | v = sc->possible[j1]; | ||
1061 | /* | ||
1062 | * See if v contains exactly two set bits. | ||
1063 | */ | ||
1064 | v2 = v & -v; /* find lowest set bit */ | ||
1065 | v2 = v & ~v2; /* clear it */ | ||
1066 | if (v2 == 0 || (v2 & (v2-1)) != 0) /* not power of 2 */ | ||
1067 | continue; | ||
1068 | |||
1069 | /* | ||
1070 | * We've found regions j1 and j2 satisfying properties | ||
1071 | * (a) and (b): they have two possible colours between | ||
1072 | * them, and since they're adjacent to one another they | ||
1073 | * must use _both_ those colours between them. | ||
1074 | * Therefore, if they are both adjacent to any other | ||
1075 | * region then that region cannot be either colour. | ||
1076 | * | ||
1077 | * Go through the neighbours of j1 and see if any are | ||
1078 | * shared with j2. | ||
1079 | */ | ||
1080 | for (j = graph_vertex_start(graph, n, ngraph, j1); | ||
1081 | j < ngraph && graph[j] < n*(j1+1); j++) { | ||
1082 | k = graph[j] - j1*n; | ||
1083 | if (graph_adjacent(graph, n, ngraph, k, j2) && | ||
1084 | (sc->possible[k] & v)) { | ||
1085 | #ifdef SOLVER_DIAGNOSTICS | ||
1086 | if (verbose) { | ||
1087 | char buf[80]; | ||
1088 | if (!started) | ||
1089 | printf("%*sadjacent regions %d,%d share colours" | ||
1090 | " %s\n", 2*sc->depth, "", j1, j2, | ||
1091 | colourset(buf, v)); | ||
1092 | started = TRUE; | ||
1093 | printf("%*s ruling out %s in region %d\n",2*sc->depth, | ||
1094 | "", colourset(buf, sc->possible[k] & v), k); | ||
1095 | } | ||
1096 | #endif | ||
1097 | sc->possible[k] &= ~v; | ||
1098 | done_something = TRUE; | ||
1099 | } | ||
1100 | } | ||
1101 | } | ||
1102 | |||
1103 | if (done_something) | ||
1104 | continue; | ||
1105 | |||
1106 | if (difficulty < DIFF_HARD) | ||
1107 | break; /* can't do anything harder */ | ||
1108 | |||
1109 | /* | ||
1110 | * Right; now we get creative. Now we're going to look for | ||
1111 | * `forcing chains'. A forcing chain is a path through the | ||
1112 | * graph with the following properties: | ||
1113 | * | ||
1114 | * (a) Each vertex on the path has precisely two possible | ||
1115 | * colours. | ||
1116 | * | ||
1117 | * (b) Each pair of vertices which are adjacent on the | ||
1118 | * path share at least one possible colour in common. | ||
1119 | * | ||
1120 | * (c) Each vertex in the middle of the path shares _both_ | ||
1121 | * of its colours with at least one of its neighbours | ||
1122 | * (not the same one with both neighbours). | ||
1123 | * | ||
1124 | * These together imply that at least one of the possible | ||
1125 | * colour choices at one end of the path forces _all_ the | ||
1126 | * rest of the colours along the path. In order to make | ||
1127 | * real use of this, we need further properties: | ||
1128 | * | ||
1129 | * (c) Ruling out some colour C from the vertex at one end | ||
1130 | * of the path forces the vertex at the other end to | ||
1131 | * take colour C. | ||
1132 | * | ||
1133 | * (d) The two end vertices are mutually adjacent to some | ||
1134 | * third vertex. | ||
1135 | * | ||
1136 | * (e) That third vertex currently has C as a possibility. | ||
1137 | * | ||
1138 | * If we can find all of that lot, we can deduce that at | ||
1139 | * least one of the two ends of the forcing chain has | ||
1140 | * colour C, and that therefore the mutually adjacent third | ||
1141 | * vertex does not. | ||
1142 | * | ||
1143 | * To find forcing chains, we're going to start a bfs at | ||
1144 | * each suitable vertex of the graph, once for each of its | ||
1145 | * two possible colours. | ||
1146 | */ | ||
1147 | for (i = 0; i < n; i++) { | ||
1148 | int c; | ||
1149 | |||
1150 | if (colouring[i] >= 0 || bitcount(sc->possible[i]) != 2) | ||
1151 | continue; | ||
1152 | |||
1153 | for (c = 0; c < FOUR; c++) | ||
1154 | if (sc->possible[i] & (1 << c)) { | ||
1155 | int j, k, gi, origc, currc, head, tail; | ||
1156 | /* | ||
1157 | * Try a bfs from this vertex, ruling out | ||
1158 | * colour c. | ||
1159 | * | ||
1160 | * Within this loop, we work in colour bitmaps | ||
1161 | * rather than actual colours, because | ||
1162 | * converting back and forth is a needless | ||
1163 | * computational expense. | ||
1164 | */ | ||
1165 | |||
1166 | origc = 1 << c; | ||
1167 | |||
1168 | for (j = 0; j < n; j++) { | ||
1169 | sc->bfscolour[j] = -1; | ||
1170 | #ifdef SOLVER_DIAGNOSTICS | ||
1171 | sc->bfsprev[j] = -1; | ||
1172 | #endif | ||
1173 | } | ||
1174 | head = tail = 0; | ||
1175 | sc->bfsqueue[tail++] = i; | ||
1176 | sc->bfscolour[i] = sc->possible[i] &~ origc; | ||
1177 | |||
1178 | while (head < tail) { | ||
1179 | j = sc->bfsqueue[head++]; | ||
1180 | currc = sc->bfscolour[j]; | ||
1181 | |||
1182 | /* | ||
1183 | * Try neighbours of j. | ||
1184 | */ | ||
1185 | for (gi = graph_vertex_start(graph, n, ngraph, j); | ||
1186 | gi < ngraph && graph[gi] < n*(j+1); gi++) { | ||
1187 | k = graph[gi] - j*n; | ||
1188 | |||
1189 | /* | ||
1190 | * To continue with the bfs in vertex | ||
1191 | * k, we need k to be | ||
1192 | * (a) not already visited | ||
1193 | * (b) have two possible colours | ||
1194 | * (c) those colours include currc. | ||
1195 | */ | ||
1196 | |||
1197 | if (sc->bfscolour[k] < 0 && | ||
1198 | colouring[k] < 0 && | ||
1199 | bitcount(sc->possible[k]) == 2 && | ||
1200 | (sc->possible[k] & currc)) { | ||
1201 | sc->bfsqueue[tail++] = k; | ||
1202 | sc->bfscolour[k] = | ||
1203 | sc->possible[k] &~ currc; | ||
1204 | #ifdef SOLVER_DIAGNOSTICS | ||
1205 | sc->bfsprev[k] = j; | ||
1206 | #endif | ||
1207 | } | ||
1208 | |||
1209 | /* | ||
1210 | * One other possibility is that k | ||
1211 | * might be the region in which we can | ||
1212 | * make a real deduction: if it's | ||
1213 | * adjacent to i, contains currc as a | ||
1214 | * possibility, and currc is equal to | ||
1215 | * the original colour we ruled out. | ||
1216 | */ | ||
1217 | if (currc == origc && | ||
1218 | graph_adjacent(graph, n, ngraph, k, i) && | ||
1219 | (sc->possible[k] & currc)) { | ||
1220 | #ifdef SOLVER_DIAGNOSTICS | ||
1221 | if (verbose) { | ||
1222 | char buf[80], *sep = ""; | ||
1223 | int r; | ||
1224 | |||
1225 | printf("%*sforcing chain, colour %s, ", | ||
1226 | 2*sc->depth, "", | ||
1227 | colourset(buf, origc)); | ||
1228 | for (r = j; r != -1; r = sc->bfsprev[r]) { | ||
1229 | printf("%s%d", sep, r); | ||
1230 | sep = "-"; | ||
1231 | } | ||
1232 | printf("\n%*s ruling out %s in region" | ||
1233 | " %d\n", 2*sc->depth, "", | ||
1234 | colourset(buf, origc), k); | ||
1235 | } | ||
1236 | #endif | ||
1237 | sc->possible[k] &= ~origc; | ||
1238 | done_something = TRUE; | ||
1239 | } | ||
1240 | } | ||
1241 | } | ||
1242 | |||
1243 | assert(tail <= n); | ||
1244 | } | ||
1245 | } | ||
1246 | |||
1247 | if (!done_something) | ||
1248 | break; | ||
1249 | } | ||
1250 | |||
1251 | /* | ||
1252 | * See if we've got a complete solution, and return if so. | ||
1253 | */ | ||
1254 | for (i = 0; i < n; i++) | ||
1255 | if (colouring[i] < 0) | ||
1256 | break; | ||
1257 | if (i == n) { | ||
1258 | #ifdef SOLVER_DIAGNOSTICS | ||
1259 | if (verbose) | ||
1260 | printf("%*sone solution found\n", 2*sc->depth, ""); | ||
1261 | #endif | ||
1262 | return 1; /* success! */ | ||
1263 | } | ||
1264 | |||
1265 | /* | ||
1266 | * If recursion is not permissible, we now give up. | ||
1267 | */ | ||
1268 | if (difficulty < DIFF_RECURSE) { | ||
1269 | #ifdef SOLVER_DIAGNOSTICS | ||
1270 | if (verbose) | ||
1271 | printf("%*sunable to proceed further without recursion\n", | ||
1272 | 2*sc->depth, ""); | ||
1273 | #endif | ||
1274 | return 2; /* unable to complete */ | ||
1275 | } | ||
1276 | |||
1277 | /* | ||
1278 | * Now we've got to do something recursive. So first hunt for a | ||
1279 | * currently-most-constrained region. | ||
1280 | */ | ||
1281 | { | ||
1282 | int best, bestc; | ||
1283 | struct solver_scratch *rsc; | ||
1284 | int *subcolouring, *origcolouring; | ||
1285 | int ret, subret; | ||
1286 | int we_already_got_one; | ||
1287 | |||
1288 | best = -1; | ||
1289 | bestc = FIVE; | ||
1290 | |||
1291 | for (i = 0; i < n; i++) if (colouring[i] < 0) { | ||
1292 | int p = sc->possible[i]; | ||
1293 | enum { compile_time_assertion = 1 / (FOUR <= 4) }; | ||
1294 | int c; | ||
1295 | |||
1296 | /* Count the set bits. */ | ||
1297 | c = (p & 5) + ((p >> 1) & 5); | ||
1298 | c = (c & 3) + ((c >> 2) & 3); | ||
1299 | assert(c > 1); /* or colouring[i] would be >= 0 */ | ||
1300 | |||
1301 | if (c < bestc) { | ||
1302 | best = i; | ||
1303 | bestc = c; | ||
1304 | } | ||
1305 | } | ||
1306 | |||
1307 | assert(best >= 0); /* or we'd be solved already */ | ||
1308 | |||
1309 | #ifdef SOLVER_DIAGNOSTICS | ||
1310 | if (verbose) | ||
1311 | printf("%*srecursing on region %d\n", 2*sc->depth, "", best); | ||
1312 | #endif | ||
1313 | |||
1314 | /* | ||
1315 | * Now iterate over the possible colours for this region. | ||
1316 | */ | ||
1317 | rsc = new_scratch(graph, n, ngraph); | ||
1318 | rsc->depth = sc->depth + 1; | ||
1319 | origcolouring = snewn(n, int); | ||
1320 | memcpy(origcolouring, colouring, n * sizeof(int)); | ||
1321 | subcolouring = snewn(n, int); | ||
1322 | we_already_got_one = FALSE; | ||
1323 | ret = 0; | ||
1324 | |||
1325 | for (i = 0; i < FOUR; i++) { | ||
1326 | if (!(sc->possible[best] & (1 << i))) | ||
1327 | continue; | ||
1328 | |||
1329 | memcpy(rsc->possible, sc->possible, n); | ||
1330 | memcpy(subcolouring, origcolouring, n * sizeof(int)); | ||
1331 | |||
1332 | place_colour(rsc, subcolouring, best, i | ||
1333 | #ifdef SOLVER_DIAGNOSTICS | ||
1334 | , "trying" | ||
1335 | #endif | ||
1336 | ); | ||
1337 | |||
1338 | subret = map_solver(rsc, graph, n, ngraph, | ||
1339 | subcolouring, difficulty); | ||
1340 | |||
1341 | #ifdef SOLVER_DIAGNOSTICS | ||
1342 | if (verbose) { | ||
1343 | printf("%*sretracting %c in region %d; found %s\n", | ||
1344 | 2*sc->depth, "", colnames[i], best, | ||
1345 | subret == 0 ? "no solutions" : | ||
1346 | subret == 1 ? "one solution" : "multiple solutions"); | ||
1347 | } | ||
1348 | #endif | ||
1349 | |||
1350 | /* | ||
1351 | * If this possibility turned up more than one valid | ||
1352 | * solution, or if it turned up one and we already had | ||
1353 | * one, we're definitely ambiguous. | ||
1354 | */ | ||
1355 | if (subret == 2 || (subret == 1 && we_already_got_one)) { | ||
1356 | ret = 2; | ||
1357 | break; | ||
1358 | } | ||
1359 | |||
1360 | /* | ||
1361 | * If this possibility turned up one valid solution and | ||
1362 | * it's the first we've seen, copy it into the output. | ||
1363 | */ | ||
1364 | if (subret == 1) { | ||
1365 | memcpy(colouring, subcolouring, n * sizeof(int)); | ||
1366 | we_already_got_one = TRUE; | ||
1367 | ret = 1; | ||
1368 | } | ||
1369 | |||
1370 | /* | ||
1371 | * Otherwise, this guess led to a contradiction, so we | ||
1372 | * do nothing. | ||
1373 | */ | ||
1374 | } | ||
1375 | |||
1376 | sfree(origcolouring); | ||
1377 | sfree(subcolouring); | ||
1378 | free_scratch(rsc); | ||
1379 | |||
1380 | #ifdef SOLVER_DIAGNOSTICS | ||
1381 | if (verbose && sc->depth == 0) { | ||
1382 | printf("%*s%s found\n", | ||
1383 | 2*sc->depth, "", | ||
1384 | ret == 0 ? "no solutions" : | ||
1385 | ret == 1 ? "one solution" : "multiple solutions"); | ||
1386 | } | ||
1387 | #endif | ||
1388 | return ret; | ||
1389 | } | ||
1390 | } | ||
1391 | |||
1392 | /* ---------------------------------------------------------------------- | ||
1393 | * Game generation main function. | ||
1394 | */ | ||
1395 | |||
1396 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1397 | char **aux, int interactive) | ||
1398 | { | ||
1399 | struct solver_scratch *sc = NULL; | ||
1400 | int *map, *graph, ngraph, *colouring, *colouring2, *regions; | ||
1401 | int i, j, w, h, n, solveret, cfreq[FOUR]; | ||
1402 | int wh; | ||
1403 | int mindiff, tries; | ||
1404 | #ifdef GENERATION_DIAGNOSTICS | ||
1405 | int x, y; | ||
1406 | #endif | ||
1407 | char *ret, buf[80]; | ||
1408 | int retlen, retsize; | ||
1409 | |||
1410 | w = params->w; | ||
1411 | h = params->h; | ||
1412 | n = params->n; | ||
1413 | wh = w*h; | ||
1414 | |||
1415 | *aux = NULL; | ||
1416 | |||
1417 | map = snewn(wh, int); | ||
1418 | graph = snewn(n*n, int); | ||
1419 | colouring = snewn(n, int); | ||
1420 | colouring2 = snewn(n, int); | ||
1421 | regions = snewn(n, int); | ||
1422 | |||
1423 | /* | ||
1424 | * This is the minimum difficulty below which we'll completely | ||
1425 | * reject a map design. Normally we set this to one below the | ||
1426 | * requested difficulty, ensuring that we have the right | ||
1427 | * result. However, for particularly dense maps or maps with | ||
1428 | * particularly few regions it might not be possible to get the | ||
1429 | * desired difficulty, so we will eventually drop this down to | ||
1430 | * -1 to indicate that any old map will do. | ||
1431 | */ | ||
1432 | mindiff = params->diff; | ||
1433 | tries = 50; | ||
1434 | |||
1435 | while (1) { | ||
1436 | |||
1437 | /* | ||
1438 | * Create the map. | ||
1439 | */ | ||
1440 | genmap(w, h, n, map, rs); | ||
1441 | |||
1442 | #ifdef GENERATION_DIAGNOSTICS | ||
1443 | for (y = 0; y < h; y++) { | ||
1444 | for (x = 0; x < w; x++) { | ||
1445 | int v = map[y*w+x]; | ||
1446 | if (v >= 62) | ||
1447 | putchar('!'); | ||
1448 | else if (v >= 36) | ||
1449 | putchar('a' + v-36); | ||
1450 | else if (v >= 10) | ||
1451 | putchar('A' + v-10); | ||
1452 | else | ||
1453 | putchar('0' + v); | ||
1454 | } | ||
1455 | putchar('\n'); | ||
1456 | } | ||
1457 | #endif | ||
1458 | |||
1459 | /* | ||
1460 | * Convert the map into a graph. | ||
1461 | */ | ||
1462 | ngraph = gengraph(w, h, n, map, graph); | ||
1463 | |||
1464 | #ifdef GENERATION_DIAGNOSTICS | ||
1465 | for (i = 0; i < ngraph; i++) | ||
1466 | printf("%d-%d\n", graph[i]/n, graph[i]%n); | ||
1467 | #endif | ||
1468 | |||
1469 | /* | ||
1470 | * Colour the map. | ||
1471 | */ | ||
1472 | fourcolour(graph, n, ngraph, colouring, rs); | ||
1473 | |||
1474 | #ifdef GENERATION_DIAGNOSTICS | ||
1475 | for (i = 0; i < n; i++) | ||
1476 | printf("%d: %d\n", i, colouring[i]); | ||
1477 | |||
1478 | for (y = 0; y < h; y++) { | ||
1479 | for (x = 0; x < w; x++) { | ||
1480 | int v = colouring[map[y*w+x]]; | ||
1481 | if (v >= 36) | ||
1482 | putchar('a' + v-36); | ||
1483 | else if (v >= 10) | ||
1484 | putchar('A' + v-10); | ||
1485 | else | ||
1486 | putchar('0' + v); | ||
1487 | } | ||
1488 | putchar('\n'); | ||
1489 | } | ||
1490 | #endif | ||
1491 | |||
1492 | /* | ||
1493 | * Encode the solution as an aux string. | ||
1494 | */ | ||
1495 | if (*aux) /* in case we've come round again */ | ||
1496 | sfree(*aux); | ||
1497 | retlen = retsize = 0; | ||
1498 | ret = NULL; | ||
1499 | for (i = 0; i < n; i++) { | ||
1500 | int len; | ||
1501 | |||
1502 | if (colouring[i] < 0) | ||
1503 | continue; | ||
1504 | |||
1505 | len = sprintf(buf, "%s%d:%d", i ? ";" : "S;", colouring[i], i); | ||
1506 | if (retlen + len >= retsize) { | ||
1507 | retsize = retlen + len + 256; | ||
1508 | ret = sresize(ret, retsize, char); | ||
1509 | } | ||
1510 | strcpy(ret + retlen, buf); | ||
1511 | retlen += len; | ||
1512 | } | ||
1513 | *aux = ret; | ||
1514 | |||
1515 | /* | ||
1516 | * Remove the region colours one by one, keeping | ||
1517 | * solubility. Also ensure that there always remains at | ||
1518 | * least one region of every colour, so that the user can | ||
1519 | * drag from somewhere. | ||
1520 | */ | ||
1521 | for (i = 0; i < FOUR; i++) | ||
1522 | cfreq[i] = 0; | ||
1523 | for (i = 0; i < n; i++) { | ||
1524 | regions[i] = i; | ||
1525 | cfreq[colouring[i]]++; | ||
1526 | } | ||
1527 | for (i = 0; i < FOUR; i++) | ||
1528 | if (cfreq[i] == 0) | ||
1529 | continue; | ||
1530 | |||
1531 | shuffle(regions, n, sizeof(*regions), rs); | ||
1532 | |||
1533 | if (sc) free_scratch(sc); | ||
1534 | sc = new_scratch(graph, n, ngraph); | ||
1535 | |||
1536 | for (i = 0; i < n; i++) { | ||
1537 | j = regions[i]; | ||
1538 | |||
1539 | if (cfreq[colouring[j]] == 1) | ||
1540 | continue; /* can't remove last region of colour */ | ||
1541 | |||
1542 | memcpy(colouring2, colouring, n*sizeof(int)); | ||
1543 | colouring2[j] = -1; | ||
1544 | solveret = map_solver(sc, graph, n, ngraph, colouring2, | ||
1545 | params->diff); | ||
1546 | assert(solveret >= 0); /* mustn't be impossible! */ | ||
1547 | if (solveret == 1) { | ||
1548 | cfreq[colouring[j]]--; | ||
1549 | colouring[j] = -1; | ||
1550 | } | ||
1551 | } | ||
1552 | |||
1553 | #ifdef GENERATION_DIAGNOSTICS | ||
1554 | for (i = 0; i < n; i++) | ||
1555 | if (colouring[i] >= 0) { | ||
1556 | if (i >= 62) | ||
1557 | putchar('!'); | ||
1558 | else if (i >= 36) | ||
1559 | putchar('a' + i-36); | ||
1560 | else if (i >= 10) | ||
1561 | putchar('A' + i-10); | ||
1562 | else | ||
1563 | putchar('0' + i); | ||
1564 | printf(": %d\n", colouring[i]); | ||
1565 | } | ||
1566 | #endif | ||
1567 | |||
1568 | /* | ||
1569 | * Finally, check that the puzzle is _at least_ as hard as | ||
1570 | * required, and indeed that it isn't already solved. | ||
1571 | * (Calling map_solver with negative difficulty ensures the | ||
1572 | * latter - if a solver which _does nothing_ can solve it, | ||
1573 | * it's too easy!) | ||
1574 | */ | ||
1575 | memcpy(colouring2, colouring, n*sizeof(int)); | ||
1576 | if (map_solver(sc, graph, n, ngraph, colouring2, | ||
1577 | mindiff - 1) == 1) { | ||
1578 | /* | ||
1579 | * Drop minimum difficulty if necessary. | ||
1580 | */ | ||
1581 | if (mindiff > 0 && (n < 9 || n > 2*wh/3)) { | ||
1582 | if (tries-- <= 0) | ||
1583 | mindiff = 0; /* give up and go for Easy */ | ||
1584 | } | ||
1585 | continue; | ||
1586 | } | ||
1587 | |||
1588 | break; | ||
1589 | } | ||
1590 | |||
1591 | /* | ||
1592 | * Encode as a game ID. We do this by: | ||
1593 | * | ||
1594 | * - first going along the horizontal edges row by row, and | ||
1595 | * then the vertical edges column by column | ||
1596 | * - encoding the lengths of runs of edges and runs of | ||
1597 | * non-edges | ||
1598 | * - the decoder will reconstitute the region boundaries from | ||
1599 | * this and automatically number them the same way we did | ||
1600 | * - then we encode the initial region colours in a Slant-like | ||
1601 | * fashion (digits 0-3 interspersed with letters giving | ||
1602 | * lengths of runs of empty spaces). | ||
1603 | */ | ||
1604 | retlen = retsize = 0; | ||
1605 | ret = NULL; | ||
1606 | |||
1607 | { | ||
1608 | int run, pv; | ||
1609 | |||
1610 | /* | ||
1611 | * Start with a notional non-edge, so that there'll be an | ||
1612 | * explicit `a' to distinguish the case where we start with | ||
1613 | * an edge. | ||
1614 | */ | ||
1615 | run = 1; | ||
1616 | pv = 0; | ||
1617 | |||
1618 | for (i = 0; i < w*(h-1) + (w-1)*h; i++) { | ||
1619 | int x, y, dx, dy, v; | ||
1620 | |||
1621 | if (i < w*(h-1)) { | ||
1622 | /* Horizontal edge. */ | ||
1623 | y = i / w; | ||
1624 | x = i % w; | ||
1625 | dx = 0; | ||
1626 | dy = 1; | ||
1627 | } else { | ||
1628 | /* Vertical edge. */ | ||
1629 | x = (i - w*(h-1)) / h; | ||
1630 | y = (i - w*(h-1)) % h; | ||
1631 | dx = 1; | ||
1632 | dy = 0; | ||
1633 | } | ||
1634 | |||
1635 | if (retlen + 10 >= retsize) { | ||
1636 | retsize = retlen + 256; | ||
1637 | ret = sresize(ret, retsize, char); | ||
1638 | } | ||
1639 | |||
1640 | v = (map[y*w+x] != map[(y+dy)*w+(x+dx)]); | ||
1641 | |||
1642 | if (pv != v) { | ||
1643 | ret[retlen++] = 'a'-1 + run; | ||
1644 | run = 1; | ||
1645 | pv = v; | ||
1646 | } else { | ||
1647 | /* | ||
1648 | * 'z' is a special case in this encoding. Rather | ||
1649 | * than meaning a run of 26 and a state switch, it | ||
1650 | * means a run of 25 and _no_ state switch, because | ||
1651 | * otherwise there'd be no way to encode runs of | ||
1652 | * more than 26. | ||
1653 | */ | ||
1654 | if (run == 25) { | ||
1655 | ret[retlen++] = 'z'; | ||
1656 | run = 0; | ||
1657 | } | ||
1658 | run++; | ||
1659 | } | ||
1660 | } | ||
1661 | |||
1662 | ret[retlen++] = 'a'-1 + run; | ||
1663 | ret[retlen++] = ','; | ||
1664 | |||
1665 | run = 0; | ||
1666 | for (i = 0; i < n; i++) { | ||
1667 | if (retlen + 10 >= retsize) { | ||
1668 | retsize = retlen + 256; | ||
1669 | ret = sresize(ret, retsize, char); | ||
1670 | } | ||
1671 | |||
1672 | if (colouring[i] < 0) { | ||
1673 | /* | ||
1674 | * In _this_ encoding, 'z' is a run of 26, since | ||
1675 | * there's no implicit state switch after each run. | ||
1676 | * Confusingly different, but more compact. | ||
1677 | */ | ||
1678 | if (run == 26) { | ||
1679 | ret[retlen++] = 'z'; | ||
1680 | run = 0; | ||
1681 | } | ||
1682 | run++; | ||
1683 | } else { | ||
1684 | if (run > 0) | ||
1685 | ret[retlen++] = 'a'-1 + run; | ||
1686 | ret[retlen++] = '0' + colouring[i]; | ||
1687 | run = 0; | ||
1688 | } | ||
1689 | } | ||
1690 | if (run > 0) | ||
1691 | ret[retlen++] = 'a'-1 + run; | ||
1692 | ret[retlen] = '\0'; | ||
1693 | |||
1694 | assert(retlen < retsize); | ||
1695 | } | ||
1696 | |||
1697 | free_scratch(sc); | ||
1698 | sfree(regions); | ||
1699 | sfree(colouring2); | ||
1700 | sfree(colouring); | ||
1701 | sfree(graph); | ||
1702 | sfree(map); | ||
1703 | |||
1704 | return ret; | ||
1705 | } | ||
1706 | |||
1707 | static char *parse_edge_list(const game_params *params, const char **desc, | ||
1708 | int *map) | ||
1709 | { | ||
1710 | int w = params->w, h = params->h, wh = w*h, n = params->n; | ||
1711 | int i, k, pos, state; | ||
1712 | const char *p = *desc; | ||
1713 | |||
1714 | dsf_init(map+wh, wh); | ||
1715 | |||
1716 | pos = -1; | ||
1717 | state = 0; | ||
1718 | |||
1719 | /* | ||
1720 | * Parse the game description to get the list of edges, and | ||
1721 | * build up a disjoint set forest as we go (by identifying | ||
1722 | * pairs of squares whenever the edge list shows a non-edge). | ||
1723 | */ | ||
1724 | while (*p && *p != ',') { | ||
1725 | if (*p < 'a' || *p > 'z') | ||
1726 | return "Unexpected character in edge list"; | ||
1727 | if (*p == 'z') | ||
1728 | k = 25; | ||
1729 | else | ||
1730 | k = *p - 'a' + 1; | ||
1731 | while (k-- > 0) { | ||
1732 | int x, y, dx, dy; | ||
1733 | |||
1734 | if (pos < 0) { | ||
1735 | pos++; | ||
1736 | continue; | ||
1737 | } else if (pos < w*(h-1)) { | ||
1738 | /* Horizontal edge. */ | ||
1739 | y = pos / w; | ||
1740 | x = pos % w; | ||
1741 | dx = 0; | ||
1742 | dy = 1; | ||
1743 | } else if (pos < 2*wh-w-h) { | ||
1744 | /* Vertical edge. */ | ||
1745 | x = (pos - w*(h-1)) / h; | ||
1746 | y = (pos - w*(h-1)) % h; | ||
1747 | dx = 1; | ||
1748 | dy = 0; | ||
1749 | } else | ||
1750 | return "Too much data in edge list"; | ||
1751 | if (!state) | ||
1752 | dsf_merge(map+wh, y*w+x, (y+dy)*w+(x+dx)); | ||
1753 | |||
1754 | pos++; | ||
1755 | } | ||
1756 | if (*p != 'z') | ||
1757 | state = !state; | ||
1758 | p++; | ||
1759 | } | ||
1760 | assert(pos <= 2*wh-w-h); | ||
1761 | if (pos < 2*wh-w-h) | ||
1762 | return "Too little data in edge list"; | ||
1763 | |||
1764 | /* | ||
1765 | * Now go through again and allocate region numbers. | ||
1766 | */ | ||
1767 | pos = 0; | ||
1768 | for (i = 0; i < wh; i++) | ||
1769 | map[i] = -1; | ||
1770 | for (i = 0; i < wh; i++) { | ||
1771 | k = dsf_canonify(map+wh, i); | ||
1772 | if (map[k] < 0) | ||
1773 | map[k] = pos++; | ||
1774 | map[i] = map[k]; | ||
1775 | } | ||
1776 | if (pos != n) | ||
1777 | return "Edge list defines the wrong number of regions"; | ||
1778 | |||
1779 | *desc = p; | ||
1780 | |||
1781 | return NULL; | ||
1782 | } | ||
1783 | |||
1784 | static char *validate_desc(const game_params *params, const char *desc) | ||
1785 | { | ||
1786 | int w = params->w, h = params->h, wh = w*h, n = params->n; | ||
1787 | int area; | ||
1788 | int *map; | ||
1789 | char *ret; | ||
1790 | |||
1791 | map = snewn(2*wh, int); | ||
1792 | ret = parse_edge_list(params, &desc, map); | ||
1793 | sfree(map); | ||
1794 | if (ret) | ||
1795 | return ret; | ||
1796 | |||
1797 | if (*desc != ',') | ||
1798 | return "Expected comma before clue list"; | ||
1799 | desc++; /* eat comma */ | ||
1800 | |||
1801 | area = 0; | ||
1802 | while (*desc) { | ||
1803 | if (*desc >= '0' && *desc < '0'+FOUR) | ||
1804 | area++; | ||
1805 | else if (*desc >= 'a' && *desc <= 'z') | ||
1806 | area += *desc - 'a' + 1; | ||
1807 | else | ||
1808 | return "Unexpected character in clue list"; | ||
1809 | desc++; | ||
1810 | } | ||
1811 | if (area < n) | ||
1812 | return "Too little data in clue list"; | ||
1813 | else if (area > n) | ||
1814 | return "Too much data in clue list"; | ||
1815 | |||
1816 | return NULL; | ||
1817 | } | ||
1818 | |||
1819 | static game_state *new_game(midend *me, const game_params *params, | ||
1820 | const char *desc) | ||
1821 | { | ||
1822 | int w = params->w, h = params->h, wh = w*h, n = params->n; | ||
1823 | int i, pos; | ||
1824 | const char *p; | ||
1825 | game_state *state = snew(game_state); | ||
1826 | |||
1827 | state->p = *params; | ||
1828 | state->colouring = snewn(n, int); | ||
1829 | for (i = 0; i < n; i++) | ||
1830 | state->colouring[i] = -1; | ||
1831 | state->pencil = snewn(n, int); | ||
1832 | for (i = 0; i < n; i++) | ||
1833 | state->pencil[i] = 0; | ||
1834 | |||
1835 | state->completed = state->cheated = FALSE; | ||
1836 | |||
1837 | state->map = snew(struct map); | ||
1838 | state->map->refcount = 1; | ||
1839 | state->map->map = snewn(wh*4, int); | ||
1840 | state->map->graph = snewn(n*n, int); | ||
1841 | state->map->n = n; | ||
1842 | state->map->immutable = snewn(n, int); | ||
1843 | for (i = 0; i < n; i++) | ||
1844 | state->map->immutable[i] = FALSE; | ||
1845 | |||
1846 | p = desc; | ||
1847 | |||
1848 | { | ||
1849 | char *ret; | ||
1850 | ret = parse_edge_list(params, &p, state->map->map); | ||
1851 | assert(!ret); | ||
1852 | } | ||
1853 | |||
1854 | /* | ||
1855 | * Set up the other three quadrants in `map'. | ||
1856 | */ | ||
1857 | for (i = wh; i < 4*wh; i++) | ||
1858 | state->map->map[i] = state->map->map[i % wh]; | ||
1859 | |||
1860 | assert(*p == ','); | ||
1861 | p++; | ||
1862 | |||
1863 | /* | ||
1864 | * Now process the clue list. | ||
1865 | */ | ||
1866 | pos = 0; | ||
1867 | while (*p) { | ||
1868 | if (*p >= '0' && *p < '0'+FOUR) { | ||
1869 | state->colouring[pos] = *p - '0'; | ||
1870 | state->map->immutable[pos] = TRUE; | ||
1871 | pos++; | ||
1872 | } else { | ||
1873 | assert(*p >= 'a' && *p <= 'z'); | ||
1874 | pos += *p - 'a' + 1; | ||
1875 | } | ||
1876 | p++; | ||
1877 | } | ||
1878 | assert(pos == n); | ||
1879 | |||
1880 | state->map->ngraph = gengraph(w, h, n, state->map->map, state->map->graph); | ||
1881 | |||
1882 | /* | ||
1883 | * Attempt to smooth out some of the more jagged region | ||
1884 | * outlines by the judicious use of diagonally divided squares. | ||
1885 | */ | ||
1886 | { | ||
1887 | random_state *rs = random_new(desc, strlen(desc)); | ||
1888 | int *squares = snewn(wh, int); | ||
1889 | int done_something; | ||
1890 | |||
1891 | for (i = 0; i < wh; i++) | ||
1892 | squares[i] = i; | ||
1893 | shuffle(squares, wh, sizeof(*squares), rs); | ||
1894 | |||
1895 | do { | ||
1896 | done_something = FALSE; | ||
1897 | for (i = 0; i < wh; i++) { | ||
1898 | int y = squares[i] / w, x = squares[i] % w; | ||
1899 | int c = state->map->map[y*w+x]; | ||
1900 | int tc, bc, lc, rc; | ||
1901 | |||
1902 | if (x == 0 || x == w-1 || y == 0 || y == h-1) | ||
1903 | continue; | ||
1904 | |||
1905 | if (state->map->map[TE * wh + y*w+x] != | ||
1906 | state->map->map[BE * wh + y*w+x]) | ||
1907 | continue; | ||
1908 | |||
1909 | tc = state->map->map[BE * wh + (y-1)*w+x]; | ||
1910 | bc = state->map->map[TE * wh + (y+1)*w+x]; | ||
1911 | lc = state->map->map[RE * wh + y*w+(x-1)]; | ||
1912 | rc = state->map->map[LE * wh + y*w+(x+1)]; | ||
1913 | |||
1914 | /* | ||
1915 | * If this square is adjacent on two sides to one | ||
1916 | * region and on the other two sides to the other | ||
1917 | * region, and is itself one of the two regions, we can | ||
1918 | * adjust it so that it's a diagonal. | ||
1919 | */ | ||
1920 | if (tc != bc && (tc == c || bc == c)) { | ||
1921 | if ((lc == tc && rc == bc) || | ||
1922 | (lc == bc && rc == tc)) { | ||
1923 | state->map->map[TE * wh + y*w+x] = tc; | ||
1924 | state->map->map[BE * wh + y*w+x] = bc; | ||
1925 | state->map->map[LE * wh + y*w+x] = lc; | ||
1926 | state->map->map[RE * wh + y*w+x] = rc; | ||
1927 | done_something = TRUE; | ||
1928 | } | ||
1929 | } | ||
1930 | } | ||
1931 | } while (done_something); | ||
1932 | sfree(squares); | ||
1933 | random_free(rs); | ||
1934 | } | ||
1935 | |||
1936 | /* | ||
1937 | * Analyse the map to find a canonical line segment | ||
1938 | * corresponding to each edge, and a canonical point | ||
1939 | * corresponding to each region. The former are where we'll | ||
1940 | * eventually put error markers; the latter are where we'll put | ||
1941 | * per-region flags such as numbers (when in diagnostic mode). | ||
1942 | */ | ||
1943 | { | ||
1944 | int *bestx, *besty, *an, pass; | ||
1945 | float *ax, *ay, *best; | ||
1946 | |||
1947 | ax = snewn(state->map->ngraph + n, float); | ||
1948 | ay = snewn(state->map->ngraph + n, float); | ||
1949 | an = snewn(state->map->ngraph + n, int); | ||
1950 | bestx = snewn(state->map->ngraph + n, int); | ||
1951 | besty = snewn(state->map->ngraph + n, int); | ||
1952 | best = snewn(state->map->ngraph + n, float); | ||
1953 | |||
1954 | for (i = 0; i < state->map->ngraph + n; i++) { | ||
1955 | bestx[i] = besty[i] = -1; | ||
1956 | best[i] = (float)(2*(w+h)+1); | ||
1957 | ax[i] = ay[i] = 0.0F; | ||
1958 | an[i] = 0; | ||
1959 | } | ||
1960 | |||
1961 | /* | ||
1962 | * We make two passes over the map, finding all the line | ||
1963 | * segments separating regions and all the suitable points | ||
1964 | * within regions. In the first pass, we compute the | ||
1965 | * _average_ x and y coordinate of all the points in a | ||
1966 | * given class; in the second pass, for each such average | ||
1967 | * point, we find the candidate closest to it and call that | ||
1968 | * canonical. | ||
1969 | * | ||
1970 | * Line segments are considered to have coordinates in | ||
1971 | * their centre. Thus, at least one coordinate for any line | ||
1972 | * segment is always something-and-a-half; so we store our | ||
1973 | * coordinates as twice their normal value. | ||
1974 | */ | ||
1975 | for (pass = 0; pass < 2; pass++) { | ||
1976 | int x, y; | ||
1977 | |||
1978 | for (y = 0; y < h; y++) | ||
1979 | for (x = 0; x < w; x++) { | ||
1980 | int ex[4], ey[4], ea[4], eb[4], en = 0; | ||
1981 | |||
1982 | /* | ||
1983 | * Look for an edge to the right of this | ||
1984 | * square, an edge below it, and an edge in the | ||
1985 | * middle of it. Also look to see if the point | ||
1986 | * at the bottom right of this square is on an | ||
1987 | * edge (and isn't a place where more than two | ||
1988 | * regions meet). | ||
1989 | */ | ||
1990 | if (x+1 < w) { | ||
1991 | /* right edge */ | ||
1992 | ea[en] = state->map->map[RE * wh + y*w+x]; | ||
1993 | eb[en] = state->map->map[LE * wh + y*w+(x+1)]; | ||
1994 | ex[en] = (x+1)*2; | ||
1995 | ey[en] = y*2+1; | ||
1996 | en++; | ||
1997 | } | ||
1998 | if (y+1 < h) { | ||
1999 | /* bottom edge */ | ||
2000 | ea[en] = state->map->map[BE * wh + y*w+x]; | ||
2001 | eb[en] = state->map->map[TE * wh + (y+1)*w+x]; | ||
2002 | ex[en] = x*2+1; | ||
2003 | ey[en] = (y+1)*2; | ||
2004 | en++; | ||
2005 | } | ||
2006 | /* diagonal edge */ | ||
2007 | ea[en] = state->map->map[TE * wh + y*w+x]; | ||
2008 | eb[en] = state->map->map[BE * wh + y*w+x]; | ||
2009 | ex[en] = x*2+1; | ||
2010 | ey[en] = y*2+1; | ||
2011 | en++; | ||
2012 | |||
2013 | if (x+1 < w && y+1 < h) { | ||
2014 | /* bottom right corner */ | ||
2015 | int oct[8], othercol, nchanges; | ||
2016 | oct[0] = state->map->map[RE * wh + y*w+x]; | ||
2017 | oct[1] = state->map->map[LE * wh + y*w+(x+1)]; | ||
2018 | oct[2] = state->map->map[BE * wh + y*w+(x+1)]; | ||
2019 | oct[3] = state->map->map[TE * wh + (y+1)*w+(x+1)]; | ||
2020 | oct[4] = state->map->map[LE * wh + (y+1)*w+(x+1)]; | ||
2021 | oct[5] = state->map->map[RE * wh + (y+1)*w+x]; | ||
2022 | oct[6] = state->map->map[TE * wh + (y+1)*w+x]; | ||
2023 | oct[7] = state->map->map[BE * wh + y*w+x]; | ||
2024 | |||
2025 | othercol = -1; | ||
2026 | nchanges = 0; | ||
2027 | for (i = 0; i < 8; i++) { | ||
2028 | if (oct[i] != oct[0]) { | ||
2029 | if (othercol < 0) | ||
2030 | othercol = oct[i]; | ||
2031 | else if (othercol != oct[i]) | ||
2032 | break; /* three colours at this point */ | ||
2033 | } | ||
2034 | if (oct[i] != oct[(i+1) & 7]) | ||
2035 | nchanges++; | ||
2036 | } | ||
2037 | |||
2038 | /* | ||
2039 | * Now if there are exactly two regions at | ||
2040 | * this point (not one, and not three or | ||
2041 | * more), and only two changes around the | ||
2042 | * loop, then this is a valid place to put | ||
2043 | * an error marker. | ||
2044 | */ | ||
2045 | if (i == 8 && othercol >= 0 && nchanges == 2) { | ||
2046 | ea[en] = oct[0]; | ||
2047 | eb[en] = othercol; | ||
2048 | ex[en] = (x+1)*2; | ||
2049 | ey[en] = (y+1)*2; | ||
2050 | en++; | ||
2051 | } | ||
2052 | |||
2053 | /* | ||
2054 | * If there's exactly _one_ region at this | ||
2055 | * point, on the other hand, it's a valid | ||
2056 | * place to put a region centre. | ||
2057 | */ | ||
2058 | if (othercol < 0) { | ||
2059 | ea[en] = eb[en] = oct[0]; | ||
2060 | ex[en] = (x+1)*2; | ||
2061 | ey[en] = (y+1)*2; | ||
2062 | en++; | ||
2063 | } | ||
2064 | } | ||
2065 | |||
2066 | /* | ||
2067 | * Now process the points we've found, one by | ||
2068 | * one. | ||
2069 | */ | ||
2070 | for (i = 0; i < en; i++) { | ||
2071 | int emin = min(ea[i], eb[i]); | ||
2072 | int emax = max(ea[i], eb[i]); | ||
2073 | int gindex; | ||
2074 | |||
2075 | if (emin != emax) { | ||
2076 | /* Graph edge */ | ||
2077 | gindex = | ||
2078 | graph_edge_index(state->map->graph, n, | ||
2079 | state->map->ngraph, emin, | ||
2080 | emax); | ||
2081 | } else { | ||
2082 | /* Region number */ | ||
2083 | gindex = state->map->ngraph + emin; | ||
2084 | } | ||
2085 | |||
2086 | assert(gindex >= 0); | ||
2087 | |||
2088 | if (pass == 0) { | ||
2089 | /* | ||
2090 | * In pass 0, accumulate the values | ||
2091 | * we'll use to compute the average | ||
2092 | * positions. | ||
2093 | */ | ||
2094 | ax[gindex] += ex[i]; | ||
2095 | ay[gindex] += ey[i]; | ||
2096 | an[gindex] += 1; | ||
2097 | } else { | ||
2098 | /* | ||
2099 | * In pass 1, work out whether this | ||
2100 | * point is closer to the average than | ||
2101 | * the last one we've seen. | ||
2102 | */ | ||
2103 | float dx, dy, d; | ||
2104 | |||
2105 | assert(an[gindex] > 0); | ||
2106 | dx = ex[i] - ax[gindex]; | ||
2107 | dy = ey[i] - ay[gindex]; | ||
2108 | d = (float)sqrt(dx*dx + dy*dy); | ||
2109 | if (d < best[gindex]) { | ||
2110 | best[gindex] = d; | ||
2111 | bestx[gindex] = ex[i]; | ||
2112 | besty[gindex] = ey[i]; | ||
2113 | } | ||
2114 | } | ||
2115 | } | ||
2116 | } | ||
2117 | |||
2118 | if (pass == 0) { | ||
2119 | for (i = 0; i < state->map->ngraph + n; i++) | ||
2120 | if (an[i] > 0) { | ||
2121 | ax[i] /= an[i]; | ||
2122 | ay[i] /= an[i]; | ||
2123 | } | ||
2124 | } | ||
2125 | } | ||
2126 | |||
2127 | state->map->edgex = snewn(state->map->ngraph, int); | ||
2128 | state->map->edgey = snewn(state->map->ngraph, int); | ||
2129 | memcpy(state->map->edgex, bestx, state->map->ngraph * sizeof(int)); | ||
2130 | memcpy(state->map->edgey, besty, state->map->ngraph * sizeof(int)); | ||
2131 | |||
2132 | state->map->regionx = snewn(n, int); | ||
2133 | state->map->regiony = snewn(n, int); | ||
2134 | memcpy(state->map->regionx, bestx + state->map->ngraph, n*sizeof(int)); | ||
2135 | memcpy(state->map->regiony, besty + state->map->ngraph, n*sizeof(int)); | ||
2136 | |||
2137 | for (i = 0; i < state->map->ngraph; i++) | ||
2138 | if (state->map->edgex[i] < 0) { | ||
2139 | /* Find the other representation of this edge. */ | ||
2140 | int e = state->map->graph[i]; | ||
2141 | int iprime = graph_edge_index(state->map->graph, n, | ||
2142 | state->map->ngraph, e%n, e/n); | ||
2143 | assert(state->map->edgex[iprime] >= 0); | ||
2144 | state->map->edgex[i] = state->map->edgex[iprime]; | ||
2145 | state->map->edgey[i] = state->map->edgey[iprime]; | ||
2146 | } | ||
2147 | |||
2148 | sfree(ax); | ||
2149 | sfree(ay); | ||
2150 | sfree(an); | ||
2151 | sfree(best); | ||
2152 | sfree(bestx); | ||
2153 | sfree(besty); | ||
2154 | } | ||
2155 | |||
2156 | return state; | ||
2157 | } | ||
2158 | |||
2159 | static game_state *dup_game(const game_state *state) | ||
2160 | { | ||
2161 | game_state *ret = snew(game_state); | ||
2162 | |||
2163 | ret->p = state->p; | ||
2164 | ret->colouring = snewn(state->p.n, int); | ||
2165 | memcpy(ret->colouring, state->colouring, state->p.n * sizeof(int)); | ||
2166 | ret->pencil = snewn(state->p.n, int); | ||
2167 | memcpy(ret->pencil, state->pencil, state->p.n * sizeof(int)); | ||
2168 | ret->map = state->map; | ||
2169 | ret->map->refcount++; | ||
2170 | ret->completed = state->completed; | ||
2171 | ret->cheated = state->cheated; | ||
2172 | |||
2173 | return ret; | ||
2174 | } | ||
2175 | |||
2176 | static void free_game(game_state *state) | ||
2177 | { | ||
2178 | if (--state->map->refcount <= 0) { | ||
2179 | sfree(state->map->map); | ||
2180 | sfree(state->map->graph); | ||
2181 | sfree(state->map->immutable); | ||
2182 | sfree(state->map->edgex); | ||
2183 | sfree(state->map->edgey); | ||
2184 | sfree(state->map->regionx); | ||
2185 | sfree(state->map->regiony); | ||
2186 | sfree(state->map); | ||
2187 | } | ||
2188 | sfree(state->pencil); | ||
2189 | sfree(state->colouring); | ||
2190 | sfree(state); | ||
2191 | } | ||
2192 | |||
2193 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
2194 | const char *aux, char **error) | ||
2195 | { | ||
2196 | if (!aux) { | ||
2197 | /* | ||
2198 | * Use the solver. | ||
2199 | */ | ||
2200 | int *colouring; | ||
2201 | struct solver_scratch *sc; | ||
2202 | int sret; | ||
2203 | int i; | ||
2204 | char *ret, buf[80]; | ||
2205 | int retlen, retsize; | ||
2206 | |||
2207 | colouring = snewn(state->map->n, int); | ||
2208 | memcpy(colouring, state->colouring, state->map->n * sizeof(int)); | ||
2209 | |||
2210 | sc = new_scratch(state->map->graph, state->map->n, state->map->ngraph); | ||
2211 | sret = map_solver(sc, state->map->graph, state->map->n, | ||
2212 | state->map->ngraph, colouring, DIFFCOUNT-1); | ||
2213 | free_scratch(sc); | ||
2214 | |||
2215 | if (sret != 1) { | ||
2216 | sfree(colouring); | ||
2217 | if (sret == 0) | ||
2218 | *error = "Puzzle is inconsistent"; | ||
2219 | else | ||
2220 | *error = "Unable to find a unique solution for this puzzle"; | ||
2221 | return NULL; | ||
2222 | } | ||
2223 | |||
2224 | retsize = 64; | ||
2225 | ret = snewn(retsize, char); | ||
2226 | strcpy(ret, "S"); | ||
2227 | retlen = 1; | ||
2228 | |||
2229 | for (i = 0; i < state->map->n; i++) { | ||
2230 | int len; | ||
2231 | |||
2232 | assert(colouring[i] >= 0); | ||
2233 | if (colouring[i] == currstate->colouring[i]) | ||
2234 | continue; | ||
2235 | assert(!state->map->immutable[i]); | ||
2236 | |||
2237 | len = sprintf(buf, ";%d:%d", colouring[i], i); | ||
2238 | if (retlen + len >= retsize) { | ||
2239 | retsize = retlen + len + 256; | ||
2240 | ret = sresize(ret, retsize, char); | ||
2241 | } | ||
2242 | strcpy(ret + retlen, buf); | ||
2243 | retlen += len; | ||
2244 | } | ||
2245 | |||
2246 | sfree(colouring); | ||
2247 | |||
2248 | return ret; | ||
2249 | } | ||
2250 | return dupstr(aux); | ||
2251 | } | ||
2252 | |||
2253 | static int game_can_format_as_text_now(const game_params *params) | ||
2254 | { | ||
2255 | return TRUE; | ||
2256 | } | ||
2257 | |||
2258 | static char *game_text_format(const game_state *state) | ||
2259 | { | ||
2260 | return NULL; | ||
2261 | } | ||
2262 | |||
2263 | struct game_ui { | ||
2264 | /* | ||
2265 | * drag_colour: | ||
2266 | * | ||
2267 | * - -2 means no drag currently active. | ||
2268 | * - >=0 means we're dragging a solid colour. | ||
2269 | * - -1 means we're dragging a blank space, and drag_pencil | ||
2270 | * might or might not add some pencil-mark stipples to that. | ||
2271 | */ | ||
2272 | int drag_colour; | ||
2273 | int drag_pencil; | ||
2274 | int dragx, dragy; | ||
2275 | int show_numbers; | ||
2276 | |||
2277 | int cur_x, cur_y, cur_visible, cur_moved, cur_lastmove; | ||
2278 | }; | ||
2279 | |||
2280 | static game_ui *new_ui(const game_state *state) | ||
2281 | { | ||
2282 | game_ui *ui = snew(game_ui); | ||
2283 | ui->dragx = ui->dragy = -1; | ||
2284 | ui->drag_colour = -2; | ||
2285 | ui->drag_pencil = 0; | ||
2286 | ui->show_numbers = FALSE; | ||
2287 | ui->cur_x = ui->cur_y = ui->cur_visible = ui->cur_moved = 0; | ||
2288 | ui->cur_lastmove = 0; | ||
2289 | return ui; | ||
2290 | } | ||
2291 | |||
2292 | static void free_ui(game_ui *ui) | ||
2293 | { | ||
2294 | sfree(ui); | ||
2295 | } | ||
2296 | |||
2297 | static char *encode_ui(const game_ui *ui) | ||
2298 | { | ||
2299 | return NULL; | ||
2300 | } | ||
2301 | |||
2302 | static void decode_ui(game_ui *ui, const char *encoding) | ||
2303 | { | ||
2304 | } | ||
2305 | |||
2306 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
2307 | const game_state *newstate) | ||
2308 | { | ||
2309 | } | ||
2310 | |||
2311 | struct game_drawstate { | ||
2312 | int tilesize; | ||
2313 | unsigned long *drawn, *todraw; | ||
2314 | int started; | ||
2315 | int dragx, dragy, drag_visible; | ||
2316 | blitter *bl; | ||
2317 | }; | ||
2318 | |||
2319 | /* Flags in `drawn'. */ | ||
2320 | #define ERR_BASE 0x00800000L | ||
2321 | #define ERR_MASK 0xFF800000L | ||
2322 | #define PENCIL_T_BASE 0x00080000L | ||
2323 | #define PENCIL_T_MASK 0x00780000L | ||
2324 | #define PENCIL_B_BASE 0x00008000L | ||
2325 | #define PENCIL_B_MASK 0x00078000L | ||
2326 | #define PENCIL_MASK 0x007F8000L | ||
2327 | #define SHOW_NUMBERS 0x00004000L | ||
2328 | |||
2329 | #define TILESIZE (ds->tilesize) | ||
2330 | #define BORDER (TILESIZE) | ||
2331 | #define COORD(x) ( (x) * TILESIZE + BORDER ) | ||
2332 | #define FROMCOORD(x) ( ((x) - BORDER + TILESIZE) / TILESIZE - 1 ) | ||
2333 | |||
2334 | /* | ||
2335 | * EPSILON_FOO are epsilons added to absolute cursor position by | ||
2336 | * cursor movement, such that in pathological cases (e.g. a very | ||
2337 | * small diamond-shaped area) it's relatively easy to select the | ||
2338 | * region you wanted. | ||
2339 | */ | ||
2340 | |||
2341 | #define EPSILON_X(button) (((button) == CURSOR_RIGHT) ? +1 : \ | ||
2342 | ((button) == CURSOR_LEFT) ? -1 : 0) | ||
2343 | #define EPSILON_Y(button) (((button) == CURSOR_DOWN) ? +1 : \ | ||
2344 | ((button) == CURSOR_UP) ? -1 : 0) | ||
2345 | |||
2346 | |||
2347 | static int region_from_coords(const game_state *state, | ||
2348 | const game_drawstate *ds, int x, int y) | ||
2349 | { | ||
2350 | int w = state->p.w, h = state->p.h, wh = w*h /*, n = state->p.n */; | ||
2351 | int tx = FROMCOORD(x), ty = FROMCOORD(y); | ||
2352 | int dx = x - COORD(tx), dy = y - COORD(ty); | ||
2353 | int quadrant; | ||
2354 | |||
2355 | if (tx < 0 || tx >= w || ty < 0 || ty >= h) | ||
2356 | return -1; /* border */ | ||
2357 | |||
2358 | quadrant = 2 * (dx > dy) + (TILESIZE - dx > dy); | ||
2359 | quadrant = (quadrant == 0 ? BE : | ||
2360 | quadrant == 1 ? LE : | ||
2361 | quadrant == 2 ? RE : TE); | ||
2362 | |||
2363 | return state->map->map[quadrant * wh + ty*w+tx]; | ||
2364 | } | ||
2365 | |||
2366 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
2367 | const game_drawstate *ds, | ||
2368 | int x, int y, int button) | ||
2369 | { | ||
2370 | char *bufp, buf[256]; | ||
2371 | int alt_button; | ||
2372 | |||
2373 | /* | ||
2374 | * Enable or disable numeric labels on regions. | ||
2375 | */ | ||
2376 | if (button == 'l' || button == 'L') { | ||
2377 | ui->show_numbers = !ui->show_numbers; | ||
2378 | return ""; | ||
2379 | } | ||
2380 | |||
2381 | if (IS_CURSOR_MOVE(button)) { | ||
2382 | move_cursor(button, &ui->cur_x, &ui->cur_y, state->p.w, state->p.h, 0); | ||
2383 | ui->cur_visible = 1; | ||
2384 | ui->cur_moved = 1; | ||
2385 | ui->cur_lastmove = button; | ||
2386 | ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(button); | ||
2387 | ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(button); | ||
2388 | return ""; | ||
2389 | } | ||
2390 | if (IS_CURSOR_SELECT(button)) { | ||
2391 | if (!ui->cur_visible) { | ||
2392 | ui->dragx = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove); | ||
2393 | ui->dragy = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove); | ||
2394 | ui->cur_visible = 1; | ||
2395 | return ""; | ||
2396 | } | ||
2397 | if (ui->drag_colour == -2) { /* not currently cursor-dragging, start. */ | ||
2398 | int r = region_from_coords(state, ds, ui->dragx, ui->dragy); | ||
2399 | if (r >= 0) { | ||
2400 | ui->drag_colour = state->colouring[r]; | ||
2401 | ui->drag_pencil = (ui->drag_colour >= 0) ? 0 : state->pencil[r]; | ||
2402 | } else { | ||
2403 | ui->drag_colour = -1; | ||
2404 | ui->drag_pencil = 0; | ||
2405 | } | ||
2406 | ui->cur_moved = 0; | ||
2407 | return ""; | ||
2408 | } else { /* currently cursor-dragging; drop the colour in the new region. */ | ||
2409 | x = COORD(ui->cur_x) + TILESIZE/2 + EPSILON_X(ui->cur_lastmove); | ||
2410 | y = COORD(ui->cur_y) + TILESIZE/2 + EPSILON_Y(ui->cur_lastmove); | ||
2411 | alt_button = (button == CURSOR_SELECT2) ? 1 : 0; | ||
2412 | /* Double-select removes current colour. */ | ||
2413 | if (!ui->cur_moved) ui->drag_colour = -1; | ||
2414 | goto drag_dropped; | ||
2415 | } | ||
2416 | } | ||
2417 | |||
2418 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON) { | ||
2419 | int r = region_from_coords(state, ds, x, y); | ||
2420 | |||
2421 | if (r >= 0) { | ||
2422 | ui->drag_colour = state->colouring[r]; | ||
2423 | ui->drag_pencil = state->pencil[r]; | ||
2424 | if (ui->drag_colour >= 0) | ||
2425 | ui->drag_pencil = 0; /* should be already, but double-check */ | ||
2426 | } else { | ||
2427 | ui->drag_colour = -1; | ||
2428 | ui->drag_pencil = 0; | ||
2429 | } | ||
2430 | ui->dragx = x; | ||
2431 | ui->dragy = y; | ||
2432 | ui->cur_visible = 0; | ||
2433 | return ""; | ||
2434 | } | ||
2435 | |||
2436 | if ((button == LEFT_DRAG || button == RIGHT_DRAG) && | ||
2437 | ui->drag_colour > -2) { | ||
2438 | ui->dragx = x; | ||
2439 | ui->dragy = y; | ||
2440 | return ""; | ||
2441 | } | ||
2442 | |||
2443 | if ((button == LEFT_RELEASE || button == RIGHT_RELEASE) && | ||
2444 | ui->drag_colour > -2) { | ||
2445 | alt_button = (button == RIGHT_RELEASE) ? 1 : 0; | ||
2446 | goto drag_dropped; | ||
2447 | } | ||
2448 | |||
2449 | return NULL; | ||
2450 | |||
2451 | drag_dropped: | ||
2452 | { | ||
2453 | int r = region_from_coords(state, ds, x, y); | ||
2454 | int c = ui->drag_colour; | ||
2455 | int p = ui->drag_pencil; | ||
2456 | int oldp; | ||
2457 | |||
2458 | /* | ||
2459 | * Cancel the drag, whatever happens. | ||
2460 | */ | ||
2461 | ui->drag_colour = -2; | ||
2462 | |||
2463 | if (r < 0) | ||
2464 | return ""; /* drag into border; do nothing else */ | ||
2465 | |||
2466 | if (state->map->immutable[r]) | ||
2467 | return ""; /* can't change this region */ | ||
2468 | |||
2469 | if (state->colouring[r] == c && state->pencil[r] == p) | ||
2470 | return ""; /* don't _need_ to change this region */ | ||
2471 | |||
2472 | if (alt_button) { | ||
2473 | if (state->colouring[r] >= 0) { | ||
2474 | /* Can't pencil on a coloured region */ | ||
2475 | return ""; | ||
2476 | } else if (c >= 0) { | ||
2477 | /* Right-dragging from colour to blank toggles one pencil */ | ||
2478 | p = state->pencil[r] ^ (1 << c); | ||
2479 | c = -1; | ||
2480 | } | ||
2481 | /* Otherwise, right-dragging from blank to blank is equivalent | ||
2482 | * to left-dragging. */ | ||
2483 | } | ||
2484 | |||
2485 | bufp = buf; | ||
2486 | oldp = state->pencil[r]; | ||
2487 | if (c != state->colouring[r]) { | ||
2488 | bufp += sprintf(bufp, ";%c:%d", (int)(c < 0 ? 'C' : '0' + c), r); | ||
2489 | if (c >= 0) | ||
2490 | oldp = 0; | ||
2491 | } | ||
2492 | if (p != oldp) { | ||
2493 | int i; | ||
2494 | for (i = 0; i < FOUR; i++) | ||
2495 | if ((oldp ^ p) & (1 << i)) | ||
2496 | bufp += sprintf(bufp, ";p%c:%d", (int)('0' + i), r); | ||
2497 | } | ||
2498 | |||
2499 | return dupstr(buf+1); /* ignore first semicolon */ | ||
2500 | } | ||
2501 | } | ||
2502 | |||
2503 | static game_state *execute_move(const game_state *state, const char *move) | ||
2504 | { | ||
2505 | int n = state->p.n; | ||
2506 | game_state *ret = dup_game(state); | ||
2507 | int c, k, adv, i; | ||
2508 | |||
2509 | while (*move) { | ||
2510 | int pencil = FALSE; | ||
2511 | |||
2512 | c = *move; | ||
2513 | if (c == 'p') { | ||
2514 | pencil = TRUE; | ||
2515 | c = *++move; | ||
2516 | } | ||
2517 | if ((c == 'C' || (c >= '0' && c < '0'+FOUR)) && | ||
2518 | sscanf(move+1, ":%d%n", &k, &adv) == 1 && | ||
2519 | k >= 0 && k < state->p.n) { | ||
2520 | move += 1 + adv; | ||
2521 | if (pencil) { | ||
2522 | if (ret->colouring[k] >= 0) { | ||
2523 | free_game(ret); | ||
2524 | return NULL; | ||
2525 | } | ||
2526 | if (c == 'C') | ||
2527 | ret->pencil[k] = 0; | ||
2528 | else | ||
2529 | ret->pencil[k] ^= 1 << (c - '0'); | ||
2530 | } else { | ||
2531 | ret->colouring[k] = (c == 'C' ? -1 : c - '0'); | ||
2532 | ret->pencil[k] = 0; | ||
2533 | } | ||
2534 | } else if (*move == 'S') { | ||
2535 | move++; | ||
2536 | ret->cheated = TRUE; | ||
2537 | } else { | ||
2538 | free_game(ret); | ||
2539 | return NULL; | ||
2540 | } | ||
2541 | |||
2542 | if (*move && *move != ';') { | ||
2543 | free_game(ret); | ||
2544 | return NULL; | ||
2545 | } | ||
2546 | if (*move) | ||
2547 | move++; | ||
2548 | } | ||
2549 | |||
2550 | /* | ||
2551 | * Check for completion. | ||
2552 | */ | ||
2553 | if (!ret->completed) { | ||
2554 | int ok = TRUE; | ||
2555 | |||
2556 | for (i = 0; i < n; i++) | ||
2557 | if (ret->colouring[i] < 0) { | ||
2558 | ok = FALSE; | ||
2559 | break; | ||
2560 | } | ||
2561 | |||
2562 | if (ok) { | ||
2563 | for (i = 0; i < ret->map->ngraph; i++) { | ||
2564 | int j = ret->map->graph[i] / n; | ||
2565 | int k = ret->map->graph[i] % n; | ||
2566 | if (ret->colouring[j] == ret->colouring[k]) { | ||
2567 | ok = FALSE; | ||
2568 | break; | ||
2569 | } | ||
2570 | } | ||
2571 | } | ||
2572 | |||
2573 | if (ok) | ||
2574 | ret->completed = TRUE; | ||
2575 | } | ||
2576 | |||
2577 | return ret; | ||
2578 | } | ||
2579 | |||
2580 | /* ---------------------------------------------------------------------- | ||
2581 | * Drawing routines. | ||
2582 | */ | ||
2583 | |||
2584 | static void game_compute_size(const game_params *params, int tilesize, | ||
2585 | int *x, int *y) | ||
2586 | { | ||
2587 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2588 | struct { int tilesize; } ads, *ds = &ads; | ||
2589 | ads.tilesize = tilesize; | ||
2590 | |||
2591 | *x = params->w * TILESIZE + 2 * BORDER + 1; | ||
2592 | *y = params->h * TILESIZE + 2 * BORDER + 1; | ||
2593 | } | ||
2594 | |||
2595 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
2596 | const game_params *params, int tilesize) | ||
2597 | { | ||
2598 | ds->tilesize = tilesize; | ||
2599 | |||
2600 | assert(!ds->bl); /* set_size is never called twice */ | ||
2601 | ds->bl = blitter_new(dr, TILESIZE+3, TILESIZE+3); | ||
2602 | } | ||
2603 | |||
2604 | const float map_colours[FOUR][3] = { | ||
2605 | #ifdef VIVID_COLOURS | ||
2606 | /* Use more vivid colours (e.g. on the Pocket PC) */ | ||
2607 | {0.75F, 0.25F, 0.25F}, | ||
2608 | {0.3F, 0.7F, 0.3F}, | ||
2609 | {0.3F, 0.3F, 0.7F}, | ||
2610 | {0.85F, 0.85F, 0.1F}, | ||
2611 | #else | ||
2612 | {0.7F, 0.5F, 0.4F}, | ||
2613 | {0.8F, 0.7F, 0.4F}, | ||
2614 | {0.5F, 0.6F, 0.4F}, | ||
2615 | {0.55F, 0.45F, 0.35F}, | ||
2616 | #endif | ||
2617 | }; | ||
2618 | const int map_hatching[FOUR] = { | ||
2619 | HATCH_VERT, HATCH_SLASH, HATCH_HORIZ, HATCH_BACKSLASH | ||
2620 | }; | ||
2621 | |||
2622 | static float *game_colours(frontend *fe, int *ncolours) | ||
2623 | { | ||
2624 | float *ret = snewn(3 * NCOLOURS, float); | ||
2625 | |||
2626 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
2627 | |||
2628 | ret[COL_GRID * 3 + 0] = 0.0F; | ||
2629 | ret[COL_GRID * 3 + 1] = 0.0F; | ||
2630 | ret[COL_GRID * 3 + 2] = 0.0F; | ||
2631 | |||
2632 | memcpy(ret + COL_0 * 3, map_colours[0], 3 * sizeof(float)); | ||
2633 | memcpy(ret + COL_1 * 3, map_colours[1], 3 * sizeof(float)); | ||
2634 | memcpy(ret + COL_2 * 3, map_colours[2], 3 * sizeof(float)); | ||
2635 | memcpy(ret + COL_3 * 3, map_colours[3], 3 * sizeof(float)); | ||
2636 | |||
2637 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
2638 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
2639 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
2640 | |||
2641 | ret[COL_ERRTEXT * 3 + 0] = 1.0F; | ||
2642 | ret[COL_ERRTEXT * 3 + 1] = 1.0F; | ||
2643 | ret[COL_ERRTEXT * 3 + 2] = 1.0F; | ||
2644 | |||
2645 | *ncolours = NCOLOURS; | ||
2646 | return ret; | ||
2647 | } | ||
2648 | |||
2649 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
2650 | { | ||
2651 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
2652 | int i; | ||
2653 | |||
2654 | ds->tilesize = 0; | ||
2655 | ds->drawn = snewn(state->p.w * state->p.h, unsigned long); | ||
2656 | for (i = 0; i < state->p.w * state->p.h; i++) | ||
2657 | ds->drawn[i] = 0xFFFFL; | ||
2658 | ds->todraw = snewn(state->p.w * state->p.h, unsigned long); | ||
2659 | ds->started = FALSE; | ||
2660 | ds->bl = NULL; | ||
2661 | ds->drag_visible = FALSE; | ||
2662 | ds->dragx = ds->dragy = -1; | ||
2663 | |||
2664 | return ds; | ||
2665 | } | ||
2666 | |||
2667 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
2668 | { | ||
2669 | sfree(ds->drawn); | ||
2670 | sfree(ds->todraw); | ||
2671 | if (ds->bl) | ||
2672 | blitter_free(dr, ds->bl); | ||
2673 | sfree(ds); | ||
2674 | } | ||
2675 | |||
2676 | static void draw_error(drawing *dr, game_drawstate *ds, int x, int y) | ||
2677 | { | ||
2678 | int coords[8]; | ||
2679 | int yext, xext; | ||
2680 | |||
2681 | /* | ||
2682 | * Draw a diamond. | ||
2683 | */ | ||
2684 | coords[0] = x - TILESIZE*2/5; | ||
2685 | coords[1] = y; | ||
2686 | coords[2] = x; | ||
2687 | coords[3] = y - TILESIZE*2/5; | ||
2688 | coords[4] = x + TILESIZE*2/5; | ||
2689 | coords[5] = y; | ||
2690 | coords[6] = x; | ||
2691 | coords[7] = y + TILESIZE*2/5; | ||
2692 | draw_polygon(dr, coords, 4, COL_ERROR, COL_GRID); | ||
2693 | |||
2694 | /* | ||
2695 | * Draw an exclamation mark in the diamond. This turns out to | ||
2696 | * look unpleasantly off-centre if done via draw_text, so I do | ||
2697 | * it by hand on the basis that exclamation marks aren't that | ||
2698 | * difficult to draw... | ||
2699 | */ | ||
2700 | xext = TILESIZE/16; | ||
2701 | yext = TILESIZE*2/5 - (xext*2+2); | ||
2702 | draw_rect(dr, x-xext, y-yext, xext*2+1, yext*2+1 - (xext*3), | ||
2703 | COL_ERRTEXT); | ||
2704 | draw_rect(dr, x-xext, y+yext-xext*2+1, xext*2+1, xext*2, COL_ERRTEXT); | ||
2705 | } | ||
2706 | |||
2707 | static void draw_square(drawing *dr, game_drawstate *ds, | ||
2708 | const game_params *params, struct map *map, | ||
2709 | int x, int y, unsigned long v) | ||
2710 | { | ||
2711 | int w = params->w, h = params->h, wh = w*h; | ||
2712 | int tv, bv, xo, yo, i, j, oldj; | ||
2713 | unsigned long errs, pencil, show_numbers; | ||
2714 | |||
2715 | errs = v & ERR_MASK; | ||
2716 | v &= ~ERR_MASK; | ||
2717 | pencil = v & PENCIL_MASK; | ||
2718 | v &= ~PENCIL_MASK; | ||
2719 | show_numbers = v & SHOW_NUMBERS; | ||
2720 | v &= ~SHOW_NUMBERS; | ||
2721 | tv = v / FIVE; | ||
2722 | bv = v % FIVE; | ||
2723 | |||
2724 | clip(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); | ||
2725 | |||
2726 | /* | ||
2727 | * Draw the region colour. | ||
2728 | */ | ||
2729 | draw_rect(dr, COORD(x), COORD(y), TILESIZE, TILESIZE, | ||
2730 | (tv == FOUR ? COL_BACKGROUND : COL_0 + tv)); | ||
2731 | /* | ||
2732 | * Draw the second region colour, if this is a diagonally | ||
2733 | * divided square. | ||
2734 | */ | ||
2735 | if (map->map[TE * wh + y*w+x] != map->map[BE * wh + y*w+x]) { | ||
2736 | int coords[6]; | ||
2737 | coords[0] = COORD(x)-1; | ||
2738 | coords[1] = COORD(y+1)+1; | ||
2739 | if (map->map[LE * wh + y*w+x] == map->map[TE * wh + y*w+x]) | ||
2740 | coords[2] = COORD(x+1)+1; | ||
2741 | else | ||
2742 | coords[2] = COORD(x)-1; | ||
2743 | coords[3] = COORD(y)-1; | ||
2744 | coords[4] = COORD(x+1)+1; | ||
2745 | coords[5] = COORD(y+1)+1; | ||
2746 | draw_polygon(dr, coords, 3, | ||
2747 | (bv == FOUR ? COL_BACKGROUND : COL_0 + bv), COL_GRID); | ||
2748 | } | ||
2749 | |||
2750 | /* | ||
2751 | * Draw `pencil marks'. Currently we arrange these in a square | ||
2752 | * formation, which means we may be in trouble if the value of | ||
2753 | * FOUR changes later... | ||
2754 | */ | ||
2755 | assert(FOUR == 4); | ||
2756 | for (yo = 0; yo < 4; yo++) | ||
2757 | for (xo = 0; xo < 4; xo++) { | ||
2758 | int te = map->map[TE * wh + y*w+x]; | ||
2759 | int e, ee, c; | ||
2760 | |||
2761 | e = (yo < xo && yo < 3-xo ? TE : | ||
2762 | yo > xo && yo > 3-xo ? BE : | ||
2763 | xo < 2 ? LE : RE); | ||
2764 | ee = map->map[e * wh + y*w+x]; | ||
2765 | |||
2766 | if (xo != (yo * 2 + 1) % 5) | ||
2767 | continue; | ||
2768 | c = yo; | ||
2769 | |||
2770 | if (!(pencil & ((ee == te ? PENCIL_T_BASE : PENCIL_B_BASE) << c))) | ||
2771 | continue; | ||
2772 | |||
2773 | if (yo == xo && | ||
2774 | (map->map[TE * wh + y*w+x] != map->map[LE * wh + y*w+x])) | ||
2775 | continue; /* avoid TL-BR diagonal line */ | ||
2776 | if (yo == 3-xo && | ||
2777 | (map->map[TE * wh + y*w+x] != map->map[RE * wh + y*w+x])) | ||
2778 | continue; /* avoid BL-TR diagonal line */ | ||
2779 | |||
2780 | draw_circle(dr, COORD(x) + (xo+1)*TILESIZE/5, | ||
2781 | COORD(y) + (yo+1)*TILESIZE/5, | ||
2782 | TILESIZE/7, COL_0 + c, COL_0 + c); | ||
2783 | } | ||
2784 | |||
2785 | /* | ||
2786 | * Draw the grid lines, if required. | ||
2787 | */ | ||
2788 | if (x <= 0 || map->map[RE*wh+y*w+(x-1)] != map->map[LE*wh+y*w+x]) | ||
2789 | draw_rect(dr, COORD(x), COORD(y), 1, TILESIZE, COL_GRID); | ||
2790 | if (y <= 0 || map->map[BE*wh+(y-1)*w+x] != map->map[TE*wh+y*w+x]) | ||
2791 | draw_rect(dr, COORD(x), COORD(y), TILESIZE, 1, COL_GRID); | ||
2792 | if (x <= 0 || y <= 0 || | ||
2793 | map->map[RE*wh+(y-1)*w+(x-1)] != map->map[TE*wh+y*w+x] || | ||
2794 | map->map[BE*wh+(y-1)*w+(x-1)] != map->map[LE*wh+y*w+x]) | ||
2795 | draw_rect(dr, COORD(x), COORD(y), 1, 1, COL_GRID); | ||
2796 | |||
2797 | /* | ||
2798 | * Draw error markers. | ||
2799 | */ | ||
2800 | for (yo = 0; yo < 3; yo++) | ||
2801 | for (xo = 0; xo < 3; xo++) | ||
2802 | if (errs & (ERR_BASE << (yo*3+xo))) | ||
2803 | draw_error(dr, ds, | ||
2804 | (COORD(x)*2+TILESIZE*xo)/2, | ||
2805 | (COORD(y)*2+TILESIZE*yo)/2); | ||
2806 | |||
2807 | /* | ||
2808 | * Draw region numbers, if desired. | ||
2809 | */ | ||
2810 | if (show_numbers) { | ||
2811 | oldj = -1; | ||
2812 | for (i = 0; i < 2; i++) { | ||
2813 | j = map->map[(i?BE:TE)*wh+y*w+x]; | ||
2814 | if (oldj == j) | ||
2815 | continue; | ||
2816 | oldj = j; | ||
2817 | |||
2818 | xo = map->regionx[j] - 2*x; | ||
2819 | yo = map->regiony[j] - 2*y; | ||
2820 | if (xo >= 0 && xo <= 2 && yo >= 0 && yo <= 2) { | ||
2821 | char buf[80]; | ||
2822 | sprintf(buf, "%d", j); | ||
2823 | draw_text(dr, (COORD(x)*2+TILESIZE*xo)/2, | ||
2824 | (COORD(y)*2+TILESIZE*yo)/2, | ||
2825 | FONT_VARIABLE, 3*TILESIZE/5, | ||
2826 | ALIGN_HCENTRE|ALIGN_VCENTRE, | ||
2827 | COL_GRID, buf); | ||
2828 | } | ||
2829 | } | ||
2830 | } | ||
2831 | |||
2832 | unclip(dr); | ||
2833 | |||
2834 | draw_update(dr, COORD(x), COORD(y), TILESIZE, TILESIZE); | ||
2835 | } | ||
2836 | |||
2837 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2838 | const game_state *oldstate, const game_state *state, | ||
2839 | int dir, const game_ui *ui, | ||
2840 | float animtime, float flashtime) | ||
2841 | { | ||
2842 | int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; | ||
2843 | int x, y, i; | ||
2844 | int flash; | ||
2845 | |||
2846 | if (ds->drag_visible) { | ||
2847 | blitter_load(dr, ds->bl, ds->dragx, ds->dragy); | ||
2848 | draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); | ||
2849 | ds->drag_visible = FALSE; | ||
2850 | } | ||
2851 | |||
2852 | /* | ||
2853 | * The initial contents of the window are not guaranteed and | ||
2854 | * can vary with front ends. To be on the safe side, all games | ||
2855 | * should start by drawing a big background-colour rectangle | ||
2856 | * covering the whole window. | ||
2857 | */ | ||
2858 | if (!ds->started) { | ||
2859 | int ww, wh; | ||
2860 | |||
2861 | game_compute_size(&state->p, TILESIZE, &ww, &wh); | ||
2862 | draw_rect(dr, 0, 0, ww, wh, COL_BACKGROUND); | ||
2863 | draw_rect(dr, COORD(0), COORD(0), w*TILESIZE+1, h*TILESIZE+1, | ||
2864 | COL_GRID); | ||
2865 | |||
2866 | draw_update(dr, 0, 0, ww, wh); | ||
2867 | ds->started = TRUE; | ||
2868 | } | ||
2869 | |||
2870 | if (flashtime) { | ||
2871 | if (flash_type == 1) | ||
2872 | flash = (int)(flashtime * FOUR / flash_length); | ||
2873 | else | ||
2874 | flash = 1 + (int)(flashtime * THREE / flash_length); | ||
2875 | } else | ||
2876 | flash = -1; | ||
2877 | |||
2878 | /* | ||
2879 | * Set up the `todraw' array. | ||
2880 | */ | ||
2881 | for (y = 0; y < h; y++) | ||
2882 | for (x = 0; x < w; x++) { | ||
2883 | int tv = state->colouring[state->map->map[TE * wh + y*w+x]]; | ||
2884 | int bv = state->colouring[state->map->map[BE * wh + y*w+x]]; | ||
2885 | unsigned long v; | ||
2886 | |||
2887 | if (tv < 0) | ||
2888 | tv = FOUR; | ||
2889 | if (bv < 0) | ||
2890 | bv = FOUR; | ||
2891 | |||
2892 | if (flash >= 0) { | ||
2893 | if (flash_type == 1) { | ||
2894 | if (tv == flash) | ||
2895 | tv = FOUR; | ||
2896 | if (bv == flash) | ||
2897 | bv = FOUR; | ||
2898 | } else if (flash_type == 2) { | ||
2899 | if (flash % 2) | ||
2900 | tv = bv = FOUR; | ||
2901 | } else { | ||
2902 | if (tv != FOUR) | ||
2903 | tv = (tv + flash) % FOUR; | ||
2904 | if (bv != FOUR) | ||
2905 | bv = (bv + flash) % FOUR; | ||
2906 | } | ||
2907 | } | ||
2908 | |||
2909 | v = tv * FIVE + bv; | ||
2910 | |||
2911 | /* | ||
2912 | * Add pencil marks. | ||
2913 | */ | ||
2914 | for (i = 0; i < FOUR; i++) { | ||
2915 | if (state->colouring[state->map->map[TE * wh + y*w+x]] < 0 && | ||
2916 | (state->pencil[state->map->map[TE * wh + y*w+x]] & (1<<i))) | ||
2917 | v |= PENCIL_T_BASE << i; | ||
2918 | if (state->colouring[state->map->map[BE * wh + y*w+x]] < 0 && | ||
2919 | (state->pencil[state->map->map[BE * wh + y*w+x]] & (1<<i))) | ||
2920 | v |= PENCIL_B_BASE << i; | ||
2921 | } | ||
2922 | |||
2923 | if (ui->show_numbers) | ||
2924 | v |= SHOW_NUMBERS; | ||
2925 | |||
2926 | ds->todraw[y*w+x] = v; | ||
2927 | } | ||
2928 | |||
2929 | /* | ||
2930 | * Add error markers to the `todraw' array. | ||
2931 | */ | ||
2932 | for (i = 0; i < state->map->ngraph; i++) { | ||
2933 | int v1 = state->map->graph[i] / n; | ||
2934 | int v2 = state->map->graph[i] % n; | ||
2935 | int xo, yo; | ||
2936 | |||
2937 | if (state->colouring[v1] < 0 || state->colouring[v2] < 0) | ||
2938 | continue; | ||
2939 | if (state->colouring[v1] != state->colouring[v2]) | ||
2940 | continue; | ||
2941 | |||
2942 | x = state->map->edgex[i]; | ||
2943 | y = state->map->edgey[i]; | ||
2944 | |||
2945 | xo = x % 2; x /= 2; | ||
2946 | yo = y % 2; y /= 2; | ||
2947 | |||
2948 | ds->todraw[y*w+x] |= ERR_BASE << (yo*3+xo); | ||
2949 | if (xo == 0) { | ||
2950 | assert(x > 0); | ||
2951 | ds->todraw[y*w+(x-1)] |= ERR_BASE << (yo*3+2); | ||
2952 | } | ||
2953 | if (yo == 0) { | ||
2954 | assert(y > 0); | ||
2955 | ds->todraw[(y-1)*w+x] |= ERR_BASE << (2*3+xo); | ||
2956 | } | ||
2957 | if (xo == 0 && yo == 0) { | ||
2958 | assert(x > 0 && y > 0); | ||
2959 | ds->todraw[(y-1)*w+(x-1)] |= ERR_BASE << (2*3+2); | ||
2960 | } | ||
2961 | } | ||
2962 | |||
2963 | /* | ||
2964 | * Now actually draw everything. | ||
2965 | */ | ||
2966 | for (y = 0; y < h; y++) | ||
2967 | for (x = 0; x < w; x++) { | ||
2968 | unsigned long v = ds->todraw[y*w+x]; | ||
2969 | if (ds->drawn[y*w+x] != v) { | ||
2970 | draw_square(dr, ds, &state->p, state->map, x, y, v); | ||
2971 | ds->drawn[y*w+x] = v; | ||
2972 | } | ||
2973 | } | ||
2974 | |||
2975 | /* | ||
2976 | * Draw the dragged colour blob if any. | ||
2977 | */ | ||
2978 | if ((ui->drag_colour > -2) || ui->cur_visible) { | ||
2979 | int bg, iscur = 0; | ||
2980 | if (ui->drag_colour >= 0) | ||
2981 | bg = COL_0 + ui->drag_colour; | ||
2982 | else if (ui->drag_colour == -1) { | ||
2983 | bg = COL_BACKGROUND; | ||
2984 | } else { | ||
2985 | int r = region_from_coords(state, ds, ui->dragx, ui->dragy); | ||
2986 | int c = (r < 0) ? -1 : state->colouring[r]; | ||
2987 | assert(ui->cur_visible); | ||
2988 | /*bg = COL_GRID;*/ | ||
2989 | bg = (c < 0) ? COL_BACKGROUND : COL_0 + c; | ||
2990 | iscur = 1; | ||
2991 | } | ||
2992 | |||
2993 | ds->dragx = ui->dragx - TILESIZE/2 - 2; | ||
2994 | ds->dragy = ui->dragy - TILESIZE/2 - 2; | ||
2995 | blitter_save(dr, ds->bl, ds->dragx, ds->dragy); | ||
2996 | draw_circle(dr, ui->dragx, ui->dragy, | ||
2997 | iscur ? TILESIZE/4 : TILESIZE/2, bg, COL_GRID); | ||
2998 | for (i = 0; i < FOUR; i++) | ||
2999 | if (ui->drag_pencil & (1 << i)) | ||
3000 | draw_circle(dr, ui->dragx + ((i*4+2)%10-3) * TILESIZE/10, | ||
3001 | ui->dragy + (i*2-3) * TILESIZE/10, | ||
3002 | TILESIZE/8, COL_0 + i, COL_0 + i); | ||
3003 | draw_update(dr, ds->dragx, ds->dragy, TILESIZE + 3, TILESIZE + 3); | ||
3004 | ds->drag_visible = TRUE; | ||
3005 | } | ||
3006 | } | ||
3007 | |||
3008 | static float game_anim_length(const game_state *oldstate, | ||
3009 | const game_state *newstate, int dir, game_ui *ui) | ||
3010 | { | ||
3011 | return 0.0F; | ||
3012 | } | ||
3013 | |||
3014 | static float game_flash_length(const game_state *oldstate, | ||
3015 | const game_state *newstate, int dir, game_ui *ui) | ||
3016 | { | ||
3017 | if (!oldstate->completed && newstate->completed && | ||
3018 | !oldstate->cheated && !newstate->cheated) { | ||
3019 | if (flash_type < 0) { | ||
3020 | char *env = getenv("MAP_ALTERNATIVE_FLASH"); | ||
3021 | if (env) | ||
3022 | flash_type = atoi(env); | ||
3023 | else | ||
3024 | flash_type = 0; | ||
3025 | flash_length = (flash_type == 1 ? 0.50F : 0.30F); | ||
3026 | } | ||
3027 | return flash_length; | ||
3028 | } else | ||
3029 | return 0.0F; | ||
3030 | } | ||
3031 | |||
3032 | static int game_status(const game_state *state) | ||
3033 | { | ||
3034 | return state->completed ? +1 : 0; | ||
3035 | } | ||
3036 | |||
3037 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
3038 | { | ||
3039 | return TRUE; | ||
3040 | } | ||
3041 | |||
3042 | static void game_print_size(const game_params *params, float *x, float *y) | ||
3043 | { | ||
3044 | int pw, ph; | ||
3045 | |||
3046 | /* | ||
3047 | * I'll use 4mm squares by default, I think. Simplest way to | ||
3048 | * compute this size is to compute the pixel puzzle size at a | ||
3049 | * given tile size and then scale. | ||
3050 | */ | ||
3051 | game_compute_size(params, 400, &pw, &ph); | ||
3052 | *x = pw / 100.0F; | ||
3053 | *y = ph / 100.0F; | ||
3054 | } | ||
3055 | |||
3056 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
3057 | { | ||
3058 | int w = state->p.w, h = state->p.h, wh = w*h, n = state->p.n; | ||
3059 | int ink, c[FOUR], i; | ||
3060 | int x, y, r; | ||
3061 | int *coords, ncoords, coordsize; | ||
3062 | |||
3063 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
3064 | struct { int tilesize; } ads, *ds = &ads; | ||
3065 | /* We can't call game_set_size() here because we don't want a blitter */ | ||
3066 | ads.tilesize = tilesize; | ||
3067 | |||
3068 | ink = print_mono_colour(dr, 0); | ||
3069 | for (i = 0; i < FOUR; i++) | ||
3070 | c[i] = print_rgb_hatched_colour(dr, map_colours[i][0], | ||
3071 | map_colours[i][1], map_colours[i][2], | ||
3072 | map_hatching[i]); | ||
3073 | |||
3074 | coordsize = 0; | ||
3075 | coords = NULL; | ||
3076 | |||
3077 | print_line_width(dr, TILESIZE / 16); | ||
3078 | |||
3079 | /* | ||
3080 | * Draw a single filled polygon around each region. | ||
3081 | */ | ||
3082 | for (r = 0; r < n; r++) { | ||
3083 | int octants[8], lastdir, d1, d2, ox, oy; | ||
3084 | |||
3085 | /* | ||
3086 | * Start by finding a point on the region boundary. Any | ||
3087 | * point will do. To do this, we'll search for a square | ||
3088 | * containing the region and then decide which corner of it | ||
3089 | * to use. | ||
3090 | */ | ||
3091 | x = w; | ||
3092 | for (y = 0; y < h; y++) { | ||
3093 | for (x = 0; x < w; x++) { | ||
3094 | if (state->map->map[wh*0+y*w+x] == r || | ||
3095 | state->map->map[wh*1+y*w+x] == r || | ||
3096 | state->map->map[wh*2+y*w+x] == r || | ||
3097 | state->map->map[wh*3+y*w+x] == r) | ||
3098 | break; | ||
3099 | } | ||
3100 | if (x < w) | ||
3101 | break; | ||
3102 | } | ||
3103 | assert(y < h && x < w); /* we must have found one somewhere */ | ||
3104 | /* | ||
3105 | * This is the first square in lexicographic order which | ||
3106 | * contains part of this region. Therefore, one of the top | ||
3107 | * two corners of the square must be what we're after. The | ||
3108 | * only case in which it isn't the top left one is if the | ||
3109 | * square is diagonally divided and the region is in the | ||
3110 | * bottom right half. | ||
3111 | */ | ||
3112 | if (state->map->map[wh*TE+y*w+x] != r && | ||
3113 | state->map->map[wh*LE+y*w+x] != r) | ||
3114 | x++; /* could just as well have done y++ */ | ||
3115 | |||
3116 | /* | ||
3117 | * Now we have a point on the region boundary. Trace around | ||
3118 | * the region until we come back to this point, | ||
3119 | * accumulating coordinates for a polygon draw operation as | ||
3120 | * we go. | ||
3121 | */ | ||
3122 | lastdir = -1; | ||
3123 | ox = x; | ||
3124 | oy = y; | ||
3125 | ncoords = 0; | ||
3126 | |||
3127 | do { | ||
3128 | /* | ||
3129 | * There are eight possible directions we could head in | ||
3130 | * from here. We identify them by octant numbers, and | ||
3131 | * we also use octant numbers to identify the spaces | ||
3132 | * between them: | ||
3133 | * | ||
3134 | * 6 7 0 | ||
3135 | * \ 7|0 / | ||
3136 | * \ | / | ||
3137 | * 6 \|/ 1 | ||
3138 | * 5-----+-----1 | ||
3139 | * 5 /|\ 2 | ||
3140 | * / | \ | ||
3141 | * / 4|3 \ | ||
3142 | * 4 3 2 | ||
3143 | */ | ||
3144 | octants[0] = x<w && y>0 ? state->map->map[wh*LE+(y-1)*w+x] : -1; | ||
3145 | octants[1] = x<w && y>0 ? state->map->map[wh*BE+(y-1)*w+x] : -1; | ||
3146 | octants[2] = x<w && y<h ? state->map->map[wh*TE+y*w+x] : -1; | ||
3147 | octants[3] = x<w && y<h ? state->map->map[wh*LE+y*w+x] : -1; | ||
3148 | octants[4] = x>0 && y<h ? state->map->map[wh*RE+y*w+(x-1)] : -1; | ||
3149 | octants[5] = x>0 && y<h ? state->map->map[wh*TE+y*w+(x-1)] : -1; | ||
3150 | octants[6] = x>0 && y>0 ? state->map->map[wh*BE+(y-1)*w+(x-1)] :-1; | ||
3151 | octants[7] = x>0 && y>0 ? state->map->map[wh*RE+(y-1)*w+(x-1)] :-1; | ||
3152 | |||
3153 | d1 = d2 = -1; | ||
3154 | for (i = 0; i < 8; i++) | ||
3155 | if ((octants[i] == r) ^ (octants[(i+1)%8] == r)) { | ||
3156 | assert(d2 == -1); | ||
3157 | if (d1 == -1) | ||
3158 | d1 = i; | ||
3159 | else | ||
3160 | d2 = i; | ||
3161 | } | ||
3162 | |||
3163 | assert(d1 != -1 && d2 != -1); | ||
3164 | if (d1 == lastdir) | ||
3165 | d1 = d2; | ||
3166 | |||
3167 | /* | ||
3168 | * Now we're heading in direction d1. Save the current | ||
3169 | * coordinates. | ||
3170 | */ | ||
3171 | if (ncoords + 2 > coordsize) { | ||
3172 | coordsize += 128; | ||
3173 | coords = sresize(coords, coordsize, int); | ||
3174 | } | ||
3175 | coords[ncoords++] = COORD(x); | ||
3176 | coords[ncoords++] = COORD(y); | ||
3177 | |||
3178 | /* | ||
3179 | * Compute the new coordinates. | ||
3180 | */ | ||
3181 | x += (d1 % 4 == 3 ? 0 : d1 < 4 ? +1 : -1); | ||
3182 | y += (d1 % 4 == 1 ? 0 : d1 > 1 && d1 < 5 ? +1 : -1); | ||
3183 | assert(x >= 0 && x <= w && y >= 0 && y <= h); | ||
3184 | |||
3185 | lastdir = d1 ^ 4; | ||
3186 | } while (x != ox || y != oy); | ||
3187 | |||
3188 | draw_polygon(dr, coords, ncoords/2, | ||
3189 | state->colouring[r] >= 0 ? | ||
3190 | c[state->colouring[r]] : -1, ink); | ||
3191 | } | ||
3192 | sfree(coords); | ||
3193 | } | ||
3194 | |||
3195 | #ifdef COMBINED | ||
3196 | #define thegame map | ||
3197 | #endif | ||
3198 | |||
3199 | const struct game thegame = { | ||
3200 | "Map", "games.map", "map", | ||
3201 | default_params, | ||
3202 | game_fetch_preset, | ||
3203 | decode_params, | ||
3204 | encode_params, | ||
3205 | free_params, | ||
3206 | dup_params, | ||
3207 | TRUE, game_configure, custom_params, | ||
3208 | validate_params, | ||
3209 | new_game_desc, | ||
3210 | validate_desc, | ||
3211 | new_game, | ||
3212 | dup_game, | ||
3213 | free_game, | ||
3214 | TRUE, solve_game, | ||
3215 | FALSE, game_can_format_as_text_now, game_text_format, | ||
3216 | new_ui, | ||
3217 | free_ui, | ||
3218 | encode_ui, | ||
3219 | decode_ui, | ||
3220 | game_changed_state, | ||
3221 | interpret_move, | ||
3222 | execute_move, | ||
3223 | 20, game_compute_size, game_set_size, | ||
3224 | game_colours, | ||
3225 | game_new_drawstate, | ||
3226 | game_free_drawstate, | ||
3227 | game_redraw, | ||
3228 | game_anim_length, | ||
3229 | game_flash_length, | ||
3230 | game_status, | ||
3231 | TRUE, TRUE, game_print_size, game_print, | ||
3232 | FALSE, /* wants_statusbar */ | ||
3233 | FALSE, game_timing_state, | ||
3234 | 0, /* flags */ | ||
3235 | }; | ||
3236 | |||
3237 | #ifdef STANDALONE_SOLVER | ||
3238 | |||
3239 | int main(int argc, char **argv) | ||
3240 | { | ||
3241 | game_params *p; | ||
3242 | game_state *s; | ||
3243 | char *id = NULL, *desc, *err; | ||
3244 | int grade = FALSE; | ||
3245 | int ret, diff, really_verbose = FALSE; | ||
3246 | struct solver_scratch *sc; | ||
3247 | int i; | ||
3248 | |||
3249 | while (--argc > 0) { | ||
3250 | char *p = *++argv; | ||
3251 | if (!strcmp(p, "-v")) { | ||
3252 | really_verbose = TRUE; | ||
3253 | } else if (!strcmp(p, "-g")) { | ||
3254 | grade = TRUE; | ||
3255 | } else if (*p == '-') { | ||
3256 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
3257 | return 1; | ||
3258 | } else { | ||
3259 | id = p; | ||
3260 | } | ||
3261 | } | ||
3262 | |||
3263 | if (!id) { | ||
3264 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
3265 | return 1; | ||
3266 | } | ||
3267 | |||
3268 | desc = strchr(id, ':'); | ||
3269 | if (!desc) { | ||
3270 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
3271 | return 1; | ||
3272 | } | ||
3273 | *desc++ = '\0'; | ||
3274 | |||
3275 | p = default_params(); | ||
3276 | decode_params(p, id); | ||
3277 | err = validate_desc(p, desc); | ||
3278 | if (err) { | ||
3279 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
3280 | return 1; | ||
3281 | } | ||
3282 | s = new_game(NULL, p, desc); | ||
3283 | |||
3284 | sc = new_scratch(s->map->graph, s->map->n, s->map->ngraph); | ||
3285 | |||
3286 | /* | ||
3287 | * When solving an Easy puzzle, we don't want to bother the | ||
3288 | * user with Hard-level deductions. For this reason, we grade | ||
3289 | * the puzzle internally before doing anything else. | ||
3290 | */ | ||
3291 | ret = -1; /* placate optimiser */ | ||
3292 | for (diff = 0; diff < DIFFCOUNT; diff++) { | ||
3293 | for (i = 0; i < s->map->n; i++) | ||
3294 | if (!s->map->immutable[i]) | ||
3295 | s->colouring[i] = -1; | ||
3296 | ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph, | ||
3297 | s->colouring, diff); | ||
3298 | if (ret < 2) | ||
3299 | break; | ||
3300 | } | ||
3301 | |||
3302 | if (diff == DIFFCOUNT) { | ||
3303 | if (grade) | ||
3304 | printf("Difficulty rating: harder than Hard, or ambiguous\n"); | ||
3305 | else | ||
3306 | printf("Unable to find a unique solution\n"); | ||
3307 | } else { | ||
3308 | if (grade) { | ||
3309 | if (ret == 0) | ||
3310 | printf("Difficulty rating: impossible (no solution exists)\n"); | ||
3311 | else if (ret == 1) | ||
3312 | printf("Difficulty rating: %s\n", map_diffnames[diff]); | ||
3313 | } else { | ||
3314 | verbose = really_verbose; | ||
3315 | for (i = 0; i < s->map->n; i++) | ||
3316 | if (!s->map->immutable[i]) | ||
3317 | s->colouring[i] = -1; | ||
3318 | ret = map_solver(sc, s->map->graph, s->map->n, s->map->ngraph, | ||
3319 | s->colouring, diff); | ||
3320 | if (ret == 0) | ||
3321 | printf("Puzzle is inconsistent\n"); | ||
3322 | else { | ||
3323 | int col = 0; | ||
3324 | |||
3325 | for (i = 0; i < s->map->n; i++) { | ||
3326 | printf("%5d <- %c%c", i, colnames[s->colouring[i]], | ||
3327 | (col < 6 && i+1 < s->map->n ? ' ' : '\n')); | ||
3328 | if (++col == 7) | ||
3329 | col = 0; | ||
3330 | } | ||
3331 | } | ||
3332 | } | ||
3333 | } | ||
3334 | |||
3335 | return 0; | ||
3336 | } | ||
3337 | |||
3338 | #endif | ||
3339 | |||
3340 | /* vim: set shiftwidth=4 tabstop=8: */ | ||