diff options
Diffstat (limited to 'apps/plugins/puzzles/src/keen.c')
-rw-r--r-- | apps/plugins/puzzles/src/keen.c | 2479 |
1 files changed, 2479 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/keen.c b/apps/plugins/puzzles/src/keen.c new file mode 100644 index 0000000000..fdaae32e5d --- /dev/null +++ b/apps/plugins/puzzles/src/keen.c | |||
@@ -0,0 +1,2479 @@ | |||
1 | /* | ||
2 | * keen.c: an implementation of the Times's 'KenKen' puzzle, and | ||
3 | * also of Nikoli's very similar 'Inshi No Heya' puzzle. | ||
4 | */ | ||
5 | |||
6 | #include <stdio.h> | ||
7 | #include <stdlib.h> | ||
8 | #include <string.h> | ||
9 | #include <assert.h> | ||
10 | #include <ctype.h> | ||
11 | #include <math.h> | ||
12 | |||
13 | #include "puzzles.h" | ||
14 | #include "latin.h" | ||
15 | |||
16 | /* | ||
17 | * Difficulty levels. I do some macro ickery here to ensure that my | ||
18 | * enum and the various forms of my name list always match up. | ||
19 | */ | ||
20 | #define DIFFLIST(A) \ | ||
21 | A(EASY,Easy,solver_easy,e) \ | ||
22 | A(NORMAL,Normal,solver_normal,n) \ | ||
23 | A(HARD,Hard,solver_hard,h) \ | ||
24 | A(EXTREME,Extreme,NULL,x) \ | ||
25 | A(UNREASONABLE,Unreasonable,NULL,u) | ||
26 | #define ENUM(upper,title,func,lower) DIFF_ ## upper, | ||
27 | #define TITLE(upper,title,func,lower) #title, | ||
28 | #define ENCODE(upper,title,func,lower) #lower | ||
29 | #define CONFIG(upper,title,func,lower) ":" #title | ||
30 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
31 | static char const *const keen_diffnames[] = { DIFFLIST(TITLE) }; | ||
32 | static char const keen_diffchars[] = DIFFLIST(ENCODE); | ||
33 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
34 | |||
35 | /* | ||
36 | * Clue notation. Important here that ADD and MUL come before SUB | ||
37 | * and DIV, and that DIV comes last. | ||
38 | */ | ||
39 | #define C_ADD 0x00000000L | ||
40 | #define C_MUL 0x20000000L | ||
41 | #define C_SUB 0x40000000L | ||
42 | #define C_DIV 0x60000000L | ||
43 | #define CMASK 0x60000000L | ||
44 | #define CUNIT 0x20000000L | ||
45 | |||
46 | /* | ||
47 | * Maximum size of any clue block. Very large ones are annoying in UI | ||
48 | * terms (if they're multiplicative you end up with too many digits to | ||
49 | * fit in the square) and also in solver terms (too many possibilities | ||
50 | * to iterate over). | ||
51 | */ | ||
52 | #define MAXBLK 6 | ||
53 | |||
54 | enum { | ||
55 | COL_BACKGROUND, | ||
56 | COL_GRID, | ||
57 | COL_USER, | ||
58 | COL_HIGHLIGHT, | ||
59 | COL_ERROR, | ||
60 | COL_PENCIL, | ||
61 | NCOLOURS | ||
62 | }; | ||
63 | |||
64 | struct game_params { | ||
65 | int w, diff, multiplication_only; | ||
66 | }; | ||
67 | |||
68 | struct clues { | ||
69 | int refcount; | ||
70 | int w; | ||
71 | int *dsf; | ||
72 | long *clues; | ||
73 | }; | ||
74 | |||
75 | struct game_state { | ||
76 | game_params par; | ||
77 | struct clues *clues; | ||
78 | digit *grid; | ||
79 | int *pencil; /* bitmaps using bits 1<<1..1<<n */ | ||
80 | int completed, cheated; | ||
81 | }; | ||
82 | |||
83 | static game_params *default_params(void) | ||
84 | { | ||
85 | game_params *ret = snew(game_params); | ||
86 | |||
87 | ret->w = 6; | ||
88 | ret->diff = DIFF_NORMAL; | ||
89 | ret->multiplication_only = FALSE; | ||
90 | |||
91 | return ret; | ||
92 | } | ||
93 | |||
94 | const static struct game_params keen_presets[] = { | ||
95 | { 4, DIFF_EASY, FALSE }, | ||
96 | { 5, DIFF_EASY, FALSE }, | ||
97 | { 5, DIFF_EASY, TRUE }, | ||
98 | { 6, DIFF_EASY, FALSE }, | ||
99 | { 6, DIFF_NORMAL, FALSE }, | ||
100 | { 6, DIFF_NORMAL, TRUE }, | ||
101 | { 6, DIFF_HARD, FALSE }, | ||
102 | { 6, DIFF_EXTREME, FALSE }, | ||
103 | { 6, DIFF_UNREASONABLE, FALSE }, | ||
104 | { 9, DIFF_NORMAL, FALSE }, | ||
105 | }; | ||
106 | |||
107 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
108 | { | ||
109 | game_params *ret; | ||
110 | char buf[80]; | ||
111 | |||
112 | if (i < 0 || i >= lenof(keen_presets)) | ||
113 | return FALSE; | ||
114 | |||
115 | ret = snew(game_params); | ||
116 | *ret = keen_presets[i]; /* structure copy */ | ||
117 | |||
118 | sprintf(buf, "%dx%d %s%s", ret->w, ret->w, keen_diffnames[ret->diff], | ||
119 | ret->multiplication_only ? ", multiplication only" : ""); | ||
120 | |||
121 | *name = dupstr(buf); | ||
122 | *params = ret; | ||
123 | return TRUE; | ||
124 | } | ||
125 | |||
126 | static void free_params(game_params *params) | ||
127 | { | ||
128 | sfree(params); | ||
129 | } | ||
130 | |||
131 | static game_params *dup_params(const game_params *params) | ||
132 | { | ||
133 | game_params *ret = snew(game_params); | ||
134 | *ret = *params; /* structure copy */ | ||
135 | return ret; | ||
136 | } | ||
137 | |||
138 | static void decode_params(game_params *params, char const *string) | ||
139 | { | ||
140 | char const *p = string; | ||
141 | |||
142 | params->w = atoi(p); | ||
143 | while (*p && isdigit((unsigned char)*p)) p++; | ||
144 | |||
145 | if (*p == 'd') { | ||
146 | int i; | ||
147 | p++; | ||
148 | params->diff = DIFFCOUNT+1; /* ...which is invalid */ | ||
149 | if (*p) { | ||
150 | for (i = 0; i < DIFFCOUNT; i++) { | ||
151 | if (*p == keen_diffchars[i]) | ||
152 | params->diff = i; | ||
153 | } | ||
154 | p++; | ||
155 | } | ||
156 | } | ||
157 | |||
158 | if (*p == 'm') { | ||
159 | p++; | ||
160 | params->multiplication_only = TRUE; | ||
161 | } | ||
162 | } | ||
163 | |||
164 | static char *encode_params(const game_params *params, int full) | ||
165 | { | ||
166 | char ret[80]; | ||
167 | |||
168 | sprintf(ret, "%d", params->w); | ||
169 | if (full) | ||
170 | sprintf(ret + strlen(ret), "d%c%s", keen_diffchars[params->diff], | ||
171 | params->multiplication_only ? "m" : ""); | ||
172 | |||
173 | return dupstr(ret); | ||
174 | } | ||
175 | |||
176 | static config_item *game_configure(const game_params *params) | ||
177 | { | ||
178 | config_item *ret; | ||
179 | char buf[80]; | ||
180 | |||
181 | ret = snewn(4, config_item); | ||
182 | |||
183 | ret[0].name = "Grid size"; | ||
184 | ret[0].type = C_STRING; | ||
185 | sprintf(buf, "%d", params->w); | ||
186 | ret[0].sval = dupstr(buf); | ||
187 | ret[0].ival = 0; | ||
188 | |||
189 | ret[1].name = "Difficulty"; | ||
190 | ret[1].type = C_CHOICES; | ||
191 | ret[1].sval = DIFFCONFIG; | ||
192 | ret[1].ival = params->diff; | ||
193 | |||
194 | ret[2].name = "Multiplication only"; | ||
195 | ret[2].type = C_BOOLEAN; | ||
196 | ret[2].sval = NULL; | ||
197 | ret[2].ival = params->multiplication_only; | ||
198 | |||
199 | ret[3].name = NULL; | ||
200 | ret[3].type = C_END; | ||
201 | ret[3].sval = NULL; | ||
202 | ret[3].ival = 0; | ||
203 | |||
204 | return ret; | ||
205 | } | ||
206 | |||
207 | static game_params *custom_params(const config_item *cfg) | ||
208 | { | ||
209 | game_params *ret = snew(game_params); | ||
210 | |||
211 | ret->w = atoi(cfg[0].sval); | ||
212 | ret->diff = cfg[1].ival; | ||
213 | ret->multiplication_only = cfg[2].ival; | ||
214 | |||
215 | return ret; | ||
216 | } | ||
217 | |||
218 | static char *validate_params(const game_params *params, int full) | ||
219 | { | ||
220 | if (params->w < 3 || params->w > 9) | ||
221 | return "Grid size must be between 3 and 9"; | ||
222 | if (params->diff >= DIFFCOUNT) | ||
223 | return "Unknown difficulty rating"; | ||
224 | return NULL; | ||
225 | } | ||
226 | |||
227 | /* ---------------------------------------------------------------------- | ||
228 | * Solver. | ||
229 | */ | ||
230 | |||
231 | struct solver_ctx { | ||
232 | int w, diff; | ||
233 | int nboxes; | ||
234 | int *boxes, *boxlist, *whichbox; | ||
235 | long *clues; | ||
236 | digit *soln; | ||
237 | digit *dscratch; | ||
238 | int *iscratch; | ||
239 | }; | ||
240 | |||
241 | static void solver_clue_candidate(struct solver_ctx *ctx, int diff, int box) | ||
242 | { | ||
243 | int w = ctx->w; | ||
244 | int n = ctx->boxes[box+1] - ctx->boxes[box]; | ||
245 | int j; | ||
246 | |||
247 | /* | ||
248 | * This function is called from the main clue-based solver | ||
249 | * routine when we discover a candidate layout for a given clue | ||
250 | * box consistent with everything we currently know about the | ||
251 | * digit constraints in that box. We expect to find the digits | ||
252 | * of the candidate layout in ctx->dscratch, and we update | ||
253 | * ctx->iscratch as appropriate. | ||
254 | * | ||
255 | * The contents of ctx->iscratch are completely different | ||
256 | * depending on whether diff == DIFF_HARD or not. This function | ||
257 | * uses iscratch completely differently between the two cases, and | ||
258 | * the code in solver_common() which consumes the result must | ||
259 | * likewise have an if statement with completely different | ||
260 | * branches for the two cases. | ||
261 | * | ||
262 | * In DIFF_EASY and DIFF_NORMAL modes, the valid entries in | ||
263 | * ctx->iscratch are 0,...,n-1, and each of those entries | ||
264 | * ctx->iscratch[i] gives a bitmap of the possible digits in the | ||
265 | * ith square of the clue box currently under consideration. So | ||
266 | * each entry of iscratch starts off as an empty bitmap, and we | ||
267 | * set bits in it as possible layouts for the clue box are | ||
268 | * considered (and the difference between DIFF_EASY and | ||
269 | * DIFF_NORMAL is just that in DIFF_EASY mode we deliberately set | ||
270 | * more bits than absolutely necessary, hence restricting our own | ||
271 | * knowledge). | ||
272 | * | ||
273 | * But in DIFF_HARD mode, the valid entries are 0,...,2*w-1 (at | ||
274 | * least outside *this* function - inside this function, we also | ||
275 | * use 2*w,...,4*w-1 as scratch space in the loop below); the | ||
276 | * first w of those give the possible digits in the intersection | ||
277 | * of the current clue box with each column of the puzzle, and the | ||
278 | * next w do the same for each row. In this mode, each iscratch | ||
279 | * entry starts off as a _full_ bitmap, and in this function we | ||
280 | * _clear_ bits for digits that are absent from a given row or | ||
281 | * column in each candidate layout, so that the only bits which | ||
282 | * remain set are those for digits which have to appear in a given | ||
283 | * row/column no matter how the clue box is laid out. | ||
284 | */ | ||
285 | if (diff == DIFF_EASY) { | ||
286 | unsigned mask = 0; | ||
287 | /* | ||
288 | * Easy-mode clue deductions: we do not record information | ||
289 | * about which squares take which values, so we amalgamate | ||
290 | * all the values in dscratch and OR them all into | ||
291 | * everywhere. | ||
292 | */ | ||
293 | for (j = 0; j < n; j++) | ||
294 | mask |= 1 << ctx->dscratch[j]; | ||
295 | for (j = 0; j < n; j++) | ||
296 | ctx->iscratch[j] |= mask; | ||
297 | } else if (diff == DIFF_NORMAL) { | ||
298 | /* | ||
299 | * Normal-mode deductions: we process the information in | ||
300 | * dscratch in the obvious way. | ||
301 | */ | ||
302 | for (j = 0; j < n; j++) | ||
303 | ctx->iscratch[j] |= 1 << ctx->dscratch[j]; | ||
304 | } else if (diff == DIFF_HARD) { | ||
305 | /* | ||
306 | * Hard-mode deductions: instead of ruling things out | ||
307 | * _inside_ the clue box, we look for numbers which occur in | ||
308 | * a given row or column in all candidate layouts, and rule | ||
309 | * them out of all squares in that row or column that | ||
310 | * _aren't_ part of this clue box. | ||
311 | */ | ||
312 | int *sq = ctx->boxlist + ctx->boxes[box]; | ||
313 | |||
314 | for (j = 0; j < 2*w; j++) | ||
315 | ctx->iscratch[2*w+j] = 0; | ||
316 | for (j = 0; j < n; j++) { | ||
317 | int x = sq[j] / w, y = sq[j] % w; | ||
318 | ctx->iscratch[2*w+x] |= 1 << ctx->dscratch[j]; | ||
319 | ctx->iscratch[3*w+y] |= 1 << ctx->dscratch[j]; | ||
320 | } | ||
321 | for (j = 0; j < 2*w; j++) | ||
322 | ctx->iscratch[j] &= ctx->iscratch[2*w+j]; | ||
323 | } | ||
324 | } | ||
325 | |||
326 | static int solver_common(struct latin_solver *solver, void *vctx, int diff) | ||
327 | { | ||
328 | struct solver_ctx *ctx = (struct solver_ctx *)vctx; | ||
329 | int w = ctx->w; | ||
330 | int box, i, j, k; | ||
331 | int ret = 0, total; | ||
332 | |||
333 | /* | ||
334 | * Iterate over each clue box and deduce what we can. | ||
335 | */ | ||
336 | for (box = 0; box < ctx->nboxes; box++) { | ||
337 | int *sq = ctx->boxlist + ctx->boxes[box]; | ||
338 | int n = ctx->boxes[box+1] - ctx->boxes[box]; | ||
339 | long value = ctx->clues[box] & ~CMASK; | ||
340 | long op = ctx->clues[box] & CMASK; | ||
341 | |||
342 | /* | ||
343 | * Initialise ctx->iscratch for this clue box. At different | ||
344 | * difficulty levels we must initialise a different amount of | ||
345 | * it to different things; see the comments in | ||
346 | * solver_clue_candidate explaining what each version does. | ||
347 | */ | ||
348 | if (diff == DIFF_HARD) { | ||
349 | for (i = 0; i < 2*w; i++) | ||
350 | ctx->iscratch[i] = (1 << (w+1)) - (1 << 1); | ||
351 | } else { | ||
352 | for (i = 0; i < n; i++) | ||
353 | ctx->iscratch[i] = 0; | ||
354 | } | ||
355 | |||
356 | switch (op) { | ||
357 | case C_SUB: | ||
358 | case C_DIV: | ||
359 | /* | ||
360 | * These two clue types must always apply to a box of | ||
361 | * area 2. Also, the two digits in these boxes can never | ||
362 | * be the same (because any domino must have its two | ||
363 | * squares in either the same row or the same column). | ||
364 | * So we simply iterate over all possibilities for the | ||
365 | * two squares (both ways round), rule out any which are | ||
366 | * inconsistent with the digit constraints we already | ||
367 | * have, and update the digit constraints with any new | ||
368 | * information thus garnered. | ||
369 | */ | ||
370 | assert(n == 2); | ||
371 | |||
372 | for (i = 1; i <= w; i++) { | ||
373 | j = (op == C_SUB ? i + value : i * value); | ||
374 | if (j > w) break; | ||
375 | |||
376 | /* (i,j) is a valid digit pair. Try it both ways round. */ | ||
377 | |||
378 | if (solver->cube[sq[0]*w+i-1] && | ||
379 | solver->cube[sq[1]*w+j-1]) { | ||
380 | ctx->dscratch[0] = i; | ||
381 | ctx->dscratch[1] = j; | ||
382 | solver_clue_candidate(ctx, diff, box); | ||
383 | } | ||
384 | |||
385 | if (solver->cube[sq[0]*w+j-1] && | ||
386 | solver->cube[sq[1]*w+i-1]) { | ||
387 | ctx->dscratch[0] = j; | ||
388 | ctx->dscratch[1] = i; | ||
389 | solver_clue_candidate(ctx, diff, box); | ||
390 | } | ||
391 | } | ||
392 | |||
393 | break; | ||
394 | |||
395 | case C_ADD: | ||
396 | case C_MUL: | ||
397 | /* | ||
398 | * For these clue types, I have no alternative but to go | ||
399 | * through all possible number combinations. | ||
400 | * | ||
401 | * Instead of a tedious physical recursion, I iterate in | ||
402 | * the scratch array through all possibilities. At any | ||
403 | * given moment, i indexes the element of the box that | ||
404 | * will next be incremented. | ||
405 | */ | ||
406 | i = 0; | ||
407 | ctx->dscratch[i] = 0; | ||
408 | total = value; /* start with the identity */ | ||
409 | while (1) { | ||
410 | if (i < n) { | ||
411 | /* | ||
412 | * Find the next valid value for cell i. | ||
413 | */ | ||
414 | for (j = ctx->dscratch[i] + 1; j <= w; j++) { | ||
415 | if (op == C_ADD ? (total < j) : (total % j != 0)) | ||
416 | continue; /* this one won't fit */ | ||
417 | if (!solver->cube[sq[i]*w+j-1]) | ||
418 | continue; /* this one is ruled out already */ | ||
419 | for (k = 0; k < i; k++) | ||
420 | if (ctx->dscratch[k] == j && | ||
421 | (sq[k] % w == sq[i] % w || | ||
422 | sq[k] / w == sq[i] / w)) | ||
423 | break; /* clashes with another row/col */ | ||
424 | if (k < i) | ||
425 | continue; | ||
426 | |||
427 | /* Found one. */ | ||
428 | break; | ||
429 | } | ||
430 | |||
431 | if (j > w) { | ||
432 | /* No valid values left; drop back. */ | ||
433 | i--; | ||
434 | if (i < 0) | ||
435 | break; /* overall iteration is finished */ | ||
436 | if (op == C_ADD) | ||
437 | total += ctx->dscratch[i]; | ||
438 | else | ||
439 | total *= ctx->dscratch[i]; | ||
440 | } else { | ||
441 | /* Got a valid value; store it and move on. */ | ||
442 | ctx->dscratch[i++] = j; | ||
443 | if (op == C_ADD) | ||
444 | total -= j; | ||
445 | else | ||
446 | total /= j; | ||
447 | ctx->dscratch[i] = 0; | ||
448 | } | ||
449 | } else { | ||
450 | if (total == (op == C_ADD ? 0 : 1)) | ||
451 | solver_clue_candidate(ctx, diff, box); | ||
452 | i--; | ||
453 | if (op == C_ADD) | ||
454 | total += ctx->dscratch[i]; | ||
455 | else | ||
456 | total *= ctx->dscratch[i]; | ||
457 | } | ||
458 | } | ||
459 | |||
460 | break; | ||
461 | } | ||
462 | |||
463 | /* | ||
464 | * Do deductions based on the information we've now | ||
465 | * accumulated in ctx->iscratch. See the comments above in | ||
466 | * solver_clue_candidate explaining what data is left in here, | ||
467 | * and how it differs between DIFF_HARD and lower difficulty | ||
468 | * levels (hence the big if statement here). | ||
469 | */ | ||
470 | if (diff < DIFF_HARD) { | ||
471 | #ifdef STANDALONE_SOLVER | ||
472 | char prefix[256]; | ||
473 | |||
474 | if (solver_show_working) | ||
475 | sprintf(prefix, "%*susing clue at (%d,%d):\n", | ||
476 | solver_recurse_depth*4, "", | ||
477 | sq[0]/w+1, sq[0]%w+1); | ||
478 | else | ||
479 | prefix[0] = '\0'; /* placate optimiser */ | ||
480 | #endif | ||
481 | |||
482 | for (i = 0; i < n; i++) | ||
483 | for (j = 1; j <= w; j++) { | ||
484 | if (solver->cube[sq[i]*w+j-1] && | ||
485 | !(ctx->iscratch[i] & (1 << j))) { | ||
486 | #ifdef STANDALONE_SOLVER | ||
487 | if (solver_show_working) { | ||
488 | printf("%s%*s ruling out %d at (%d,%d)\n", | ||
489 | prefix, solver_recurse_depth*4, "", | ||
490 | j, sq[i]/w+1, sq[i]%w+1); | ||
491 | prefix[0] = '\0'; | ||
492 | } | ||
493 | #endif | ||
494 | solver->cube[sq[i]*w+j-1] = 0; | ||
495 | ret = 1; | ||
496 | } | ||
497 | } | ||
498 | } else { | ||
499 | #ifdef STANDALONE_SOLVER | ||
500 | char prefix[256]; | ||
501 | |||
502 | if (solver_show_working) | ||
503 | sprintf(prefix, "%*susing clue at (%d,%d):\n", | ||
504 | solver_recurse_depth*4, "", | ||
505 | sq[0]/w+1, sq[0]%w+1); | ||
506 | else | ||
507 | prefix[0] = '\0'; /* placate optimiser */ | ||
508 | #endif | ||
509 | |||
510 | for (i = 0; i < 2*w; i++) { | ||
511 | int start = (i < w ? i*w : i-w); | ||
512 | int step = (i < w ? 1 : w); | ||
513 | for (j = 1; j <= w; j++) if (ctx->iscratch[i] & (1 << j)) { | ||
514 | #ifdef STANDALONE_SOLVER | ||
515 | char prefix2[256]; | ||
516 | |||
517 | if (solver_show_working) | ||
518 | sprintf(prefix2, "%*s this clue requires %d in" | ||
519 | " %s %d:\n", solver_recurse_depth*4, "", | ||
520 | j, i < w ? "column" : "row", i%w+1); | ||
521 | else | ||
522 | prefix2[0] = '\0'; /* placate optimiser */ | ||
523 | #endif | ||
524 | |||
525 | for (k = 0; k < w; k++) { | ||
526 | int pos = start + k*step; | ||
527 | if (ctx->whichbox[pos] != box && | ||
528 | solver->cube[pos*w+j-1]) { | ||
529 | #ifdef STANDALONE_SOLVER | ||
530 | if (solver_show_working) { | ||
531 | printf("%s%s%*s ruling out %d at (%d,%d)\n", | ||
532 | prefix, prefix2, | ||
533 | solver_recurse_depth*4, "", | ||
534 | j, pos/w+1, pos%w+1); | ||
535 | prefix[0] = prefix2[0] = '\0'; | ||
536 | } | ||
537 | #endif | ||
538 | solver->cube[pos*w+j-1] = 0; | ||
539 | ret = 1; | ||
540 | } | ||
541 | } | ||
542 | } | ||
543 | } | ||
544 | |||
545 | /* | ||
546 | * Once we find one block we can do something with in | ||
547 | * this way, revert to trying easier deductions, so as | ||
548 | * not to generate solver diagnostics that make the | ||
549 | * problem look harder than it is. (We have to do this | ||
550 | * for the Hard deductions but not the Easy/Normal ones, | ||
551 | * because only the Hard deductions are cross-box.) | ||
552 | */ | ||
553 | if (ret) | ||
554 | return ret; | ||
555 | } | ||
556 | } | ||
557 | |||
558 | return ret; | ||
559 | } | ||
560 | |||
561 | static int solver_easy(struct latin_solver *solver, void *vctx) | ||
562 | { | ||
563 | /* | ||
564 | * Omit the EASY deductions when solving at NORMAL level, since | ||
565 | * the NORMAL deductions are a superset of them anyway and it | ||
566 | * saves on time and confusing solver diagnostics. | ||
567 | * | ||
568 | * Note that this breaks the natural semantics of the return | ||
569 | * value of latin_solver. Without this hack, you could determine | ||
570 | * a puzzle's difficulty in one go by trying to solve it at | ||
571 | * maximum difficulty and seeing what difficulty value was | ||
572 | * returned; but with this hack, solving an Easy puzzle on | ||
573 | * Normal difficulty will typically return Normal. Hence the | ||
574 | * uses of the solver to determine difficulty are all arranged | ||
575 | * so as to double-check by re-solving at the next difficulty | ||
576 | * level down and making sure it failed. | ||
577 | */ | ||
578 | struct solver_ctx *ctx = (struct solver_ctx *)vctx; | ||
579 | if (ctx->diff > DIFF_EASY) | ||
580 | return 0; | ||
581 | return solver_common(solver, vctx, DIFF_EASY); | ||
582 | } | ||
583 | |||
584 | static int solver_normal(struct latin_solver *solver, void *vctx) | ||
585 | { | ||
586 | return solver_common(solver, vctx, DIFF_NORMAL); | ||
587 | } | ||
588 | |||
589 | static int solver_hard(struct latin_solver *solver, void *vctx) | ||
590 | { | ||
591 | return solver_common(solver, vctx, DIFF_HARD); | ||
592 | } | ||
593 | |||
594 | #define SOLVER(upper,title,func,lower) func, | ||
595 | static usersolver_t const keen_solvers[] = { DIFFLIST(SOLVER) }; | ||
596 | |||
597 | static int solver(int w, int *dsf, long *clues, digit *soln, int maxdiff) | ||
598 | { | ||
599 | int a = w*w; | ||
600 | struct solver_ctx ctx; | ||
601 | int ret; | ||
602 | int i, j, n, m; | ||
603 | |||
604 | ctx.w = w; | ||
605 | ctx.soln = soln; | ||
606 | ctx.diff = maxdiff; | ||
607 | |||
608 | /* | ||
609 | * Transform the dsf-formatted clue list into one over which we | ||
610 | * can iterate more easily. | ||
611 | * | ||
612 | * Also transpose the x- and y-coordinates at this point, | ||
613 | * because the 'cube' array in the general Latin square solver | ||
614 | * puts x first (oops). | ||
615 | */ | ||
616 | for (ctx.nboxes = i = 0; i < a; i++) | ||
617 | if (dsf_canonify(dsf, i) == i) | ||
618 | ctx.nboxes++; | ||
619 | ctx.boxlist = snewn(a, int); | ||
620 | ctx.boxes = snewn(ctx.nboxes+1, int); | ||
621 | ctx.clues = snewn(ctx.nboxes, long); | ||
622 | ctx.whichbox = snewn(a, int); | ||
623 | for (n = m = i = 0; i < a; i++) | ||
624 | if (dsf_canonify(dsf, i) == i) { | ||
625 | ctx.clues[n] = clues[i]; | ||
626 | ctx.boxes[n] = m; | ||
627 | for (j = 0; j < a; j++) | ||
628 | if (dsf_canonify(dsf, j) == i) { | ||
629 | ctx.boxlist[m++] = (j % w) * w + (j / w); /* transpose */ | ||
630 | ctx.whichbox[ctx.boxlist[m-1]] = n; | ||
631 | } | ||
632 | n++; | ||
633 | } | ||
634 | assert(n == ctx.nboxes); | ||
635 | assert(m == a); | ||
636 | ctx.boxes[n] = m; | ||
637 | |||
638 | ctx.dscratch = snewn(a+1, digit); | ||
639 | ctx.iscratch = snewn(max(a+1, 4*w), int); | ||
640 | |||
641 | ret = latin_solver(soln, w, maxdiff, | ||
642 | DIFF_EASY, DIFF_HARD, DIFF_EXTREME, | ||
643 | DIFF_EXTREME, DIFF_UNREASONABLE, | ||
644 | keen_solvers, &ctx, NULL, NULL); | ||
645 | |||
646 | sfree(ctx.dscratch); | ||
647 | sfree(ctx.iscratch); | ||
648 | sfree(ctx.whichbox); | ||
649 | sfree(ctx.boxlist); | ||
650 | sfree(ctx.boxes); | ||
651 | sfree(ctx.clues); | ||
652 | |||
653 | return ret; | ||
654 | } | ||
655 | |||
656 | /* ---------------------------------------------------------------------- | ||
657 | * Grid generation. | ||
658 | */ | ||
659 | |||
660 | static char *encode_block_structure(char *p, int w, int *dsf) | ||
661 | { | ||
662 | int i, currrun = 0; | ||
663 | char *orig, *q, *r, c; | ||
664 | |||
665 | orig = p; | ||
666 | |||
667 | /* | ||
668 | * Encode the block structure. We do this by encoding the | ||
669 | * pattern of dividing lines: first we iterate over the w*(w-1) | ||
670 | * internal vertical grid lines in ordinary reading order, then | ||
671 | * over the w*(w-1) internal horizontal ones in transposed | ||
672 | * reading order. | ||
673 | * | ||
674 | * We encode the number of non-lines between the lines; _ means | ||
675 | * zero (two adjacent divisions), a means 1, ..., y means 25, | ||
676 | * and z means 25 non-lines _and no following line_ (so that za | ||
677 | * means 26, zb 27 etc). | ||
678 | */ | ||
679 | for (i = 0; i <= 2*w*(w-1); i++) { | ||
680 | int x, y, p0, p1, edge; | ||
681 | |||
682 | if (i == 2*w*(w-1)) { | ||
683 | edge = TRUE; /* terminating virtual edge */ | ||
684 | } else { | ||
685 | if (i < w*(w-1)) { | ||
686 | y = i/(w-1); | ||
687 | x = i%(w-1); | ||
688 | p0 = y*w+x; | ||
689 | p1 = y*w+x+1; | ||
690 | } else { | ||
691 | x = i/(w-1) - w; | ||
692 | y = i%(w-1); | ||
693 | p0 = y*w+x; | ||
694 | p1 = (y+1)*w+x; | ||
695 | } | ||
696 | edge = (dsf_canonify(dsf, p0) != dsf_canonify(dsf, p1)); | ||
697 | } | ||
698 | |||
699 | if (edge) { | ||
700 | while (currrun > 25) | ||
701 | *p++ = 'z', currrun -= 25; | ||
702 | if (currrun) | ||
703 | *p++ = 'a'-1 + currrun; | ||
704 | else | ||
705 | *p++ = '_'; | ||
706 | currrun = 0; | ||
707 | } else | ||
708 | currrun++; | ||
709 | } | ||
710 | |||
711 | /* | ||
712 | * Now go through and compress the string by replacing runs of | ||
713 | * the same letter with a single copy of that letter followed by | ||
714 | * a repeat count, where that makes it shorter. (This puzzle | ||
715 | * seems to generate enough long strings of _ to make this a | ||
716 | * worthwhile step.) | ||
717 | */ | ||
718 | for (q = r = orig; r < p ;) { | ||
719 | *q++ = c = *r; | ||
720 | |||
721 | for (i = 0; r+i < p && r[i] == c; i++); | ||
722 | r += i; | ||
723 | |||
724 | if (i == 2) { | ||
725 | *q++ = c; | ||
726 | } else if (i > 2) { | ||
727 | q += sprintf(q, "%d", i); | ||
728 | } | ||
729 | } | ||
730 | |||
731 | return q; | ||
732 | } | ||
733 | |||
734 | static char *parse_block_structure(const char **p, int w, int *dsf) | ||
735 | { | ||
736 | int a = w*w; | ||
737 | int pos = 0; | ||
738 | int repc = 0, repn = 0; | ||
739 | |||
740 | dsf_init(dsf, a); | ||
741 | |||
742 | while (**p && (repn > 0 || **p != ',')) { | ||
743 | int c, adv; | ||
744 | |||
745 | if (repn > 0) { | ||
746 | repn--; | ||
747 | c = repc; | ||
748 | } else if (**p == '_' || (**p >= 'a' && **p <= 'z')) { | ||
749 | c = (**p == '_' ? 0 : **p - 'a' + 1); | ||
750 | (*p)++; | ||
751 | if (**p && isdigit((unsigned char)**p)) { | ||
752 | repc = c; | ||
753 | repn = atoi(*p)-1; | ||
754 | while (**p && isdigit((unsigned char)**p)) (*p)++; | ||
755 | } | ||
756 | } else | ||
757 | return "Invalid character in game description"; | ||
758 | |||
759 | adv = (c != 25); /* 'z' is a special case */ | ||
760 | |||
761 | while (c-- > 0) { | ||
762 | int p0, p1; | ||
763 | |||
764 | /* | ||
765 | * Non-edge; merge the two dsf classes on either | ||
766 | * side of it. | ||
767 | */ | ||
768 | if (pos >= 2*w*(w-1)) | ||
769 | return "Too much data in block structure specification"; | ||
770 | if (pos < w*(w-1)) { | ||
771 | int y = pos/(w-1); | ||
772 | int x = pos%(w-1); | ||
773 | p0 = y*w+x; | ||
774 | p1 = y*w+x+1; | ||
775 | } else { | ||
776 | int x = pos/(w-1) - w; | ||
777 | int y = pos%(w-1); | ||
778 | p0 = y*w+x; | ||
779 | p1 = (y+1)*w+x; | ||
780 | } | ||
781 | dsf_merge(dsf, p0, p1); | ||
782 | |||
783 | pos++; | ||
784 | } | ||
785 | if (adv) { | ||
786 | pos++; | ||
787 | if (pos > 2*w*(w-1)+1) | ||
788 | return "Too much data in block structure specification"; | ||
789 | } | ||
790 | } | ||
791 | |||
792 | /* | ||
793 | * When desc is exhausted, we expect to have gone exactly | ||
794 | * one space _past_ the end of the grid, due to the dummy | ||
795 | * edge at the end. | ||
796 | */ | ||
797 | if (pos != 2*w*(w-1)+1) | ||
798 | return "Not enough data in block structure specification"; | ||
799 | |||
800 | return NULL; | ||
801 | } | ||
802 | |||
803 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
804 | char **aux, int interactive) | ||
805 | { | ||
806 | int w = params->w, a = w*w; | ||
807 | digit *grid, *soln; | ||
808 | int *order, *revorder, *singletons, *dsf; | ||
809 | long *clues, *cluevals; | ||
810 | int i, j, k, n, x, y, ret; | ||
811 | int diff = params->diff; | ||
812 | char *desc, *p; | ||
813 | |||
814 | /* | ||
815 | * Difficulty exceptions: 3x3 puzzles at difficulty Hard or | ||
816 | * higher are currently not generable - the generator will spin | ||
817 | * forever looking for puzzles of the appropriate difficulty. We | ||
818 | * dial each of these down to the next lower difficulty. | ||
819 | * | ||
820 | * Remember to re-test this whenever a change is made to the | ||
821 | * solver logic! | ||
822 | * | ||
823 | * I tested it using the following shell command: | ||
824 | |||
825 | for d in e n h x u; do | ||
826 | for i in {3..9}; do | ||
827 | echo ./keen --generate 1 ${i}d${d} | ||
828 | perl -e 'alarm 30; exec @ARGV' ./keen --generate 5 ${i}d${d} >/dev/null \ | ||
829 | || echo broken | ||
830 | done | ||
831 | done | ||
832 | |||
833 | * Of course, it's better to do that after taking the exceptions | ||
834 | * _out_, so as to detect exceptions that should be removed as | ||
835 | * well as those which should be added. | ||
836 | */ | ||
837 | if (w == 3 && diff > DIFF_NORMAL) | ||
838 | diff = DIFF_NORMAL; | ||
839 | |||
840 | grid = NULL; | ||
841 | |||
842 | order = snewn(a, int); | ||
843 | revorder = snewn(a, int); | ||
844 | singletons = snewn(a, int); | ||
845 | dsf = snew_dsf(a); | ||
846 | clues = snewn(a, long); | ||
847 | cluevals = snewn(a, long); | ||
848 | soln = snewn(a, digit); | ||
849 | |||
850 | while (1) { | ||
851 | /* | ||
852 | * First construct a latin square to be the solution. | ||
853 | */ | ||
854 | sfree(grid); | ||
855 | grid = latin_generate(w, rs); | ||
856 | |||
857 | /* | ||
858 | * Divide the grid into arbitrarily sized blocks, but so as | ||
859 | * to arrange plenty of dominoes which can be SUB/DIV clues. | ||
860 | * We do this by first placing dominoes at random for a | ||
861 | * while, then tying the remaining singletons one by one | ||
862 | * into neighbouring blocks. | ||
863 | */ | ||
864 | for (i = 0; i < a; i++) | ||
865 | order[i] = i; | ||
866 | shuffle(order, a, sizeof(*order), rs); | ||
867 | for (i = 0; i < a; i++) | ||
868 | revorder[order[i]] = i; | ||
869 | |||
870 | for (i = 0; i < a; i++) | ||
871 | singletons[i] = TRUE; | ||
872 | |||
873 | dsf_init(dsf, a); | ||
874 | |||
875 | /* Place dominoes. */ | ||
876 | for (i = 0; i < a; i++) { | ||
877 | if (singletons[i]) { | ||
878 | int best = -1; | ||
879 | |||
880 | x = i % w; | ||
881 | y = i / w; | ||
882 | |||
883 | if (x > 0 && singletons[i-1] && | ||
884 | (best == -1 || revorder[i-1] < revorder[best])) | ||
885 | best = i-1; | ||
886 | if (x+1 < w && singletons[i+1] && | ||
887 | (best == -1 || revorder[i+1] < revorder[best])) | ||
888 | best = i+1; | ||
889 | if (y > 0 && singletons[i-w] && | ||
890 | (best == -1 || revorder[i-w] < revorder[best])) | ||
891 | best = i-w; | ||
892 | if (y+1 < w && singletons[i+w] && | ||
893 | (best == -1 || revorder[i+w] < revorder[best])) | ||
894 | best = i+w; | ||
895 | |||
896 | /* | ||
897 | * When we find a potential domino, we place it with | ||
898 | * probability 3/4, which seems to strike a decent | ||
899 | * balance between plenty of dominoes and leaving | ||
900 | * enough singletons to make interesting larger | ||
901 | * shapes. | ||
902 | */ | ||
903 | if (best >= 0 && random_upto(rs, 4)) { | ||
904 | singletons[i] = singletons[best] = FALSE; | ||
905 | dsf_merge(dsf, i, best); | ||
906 | } | ||
907 | } | ||
908 | } | ||
909 | |||
910 | /* Fold in singletons. */ | ||
911 | for (i = 0; i < a; i++) { | ||
912 | if (singletons[i]) { | ||
913 | int best = -1; | ||
914 | |||
915 | x = i % w; | ||
916 | y = i / w; | ||
917 | |||
918 | if (x > 0 && dsf_size(dsf, i-1) < MAXBLK && | ||
919 | (best == -1 || revorder[i-1] < revorder[best])) | ||
920 | best = i-1; | ||
921 | if (x+1 < w && dsf_size(dsf, i+1) < MAXBLK && | ||
922 | (best == -1 || revorder[i+1] < revorder[best])) | ||
923 | best = i+1; | ||
924 | if (y > 0 && dsf_size(dsf, i-w) < MAXBLK && | ||
925 | (best == -1 || revorder[i-w] < revorder[best])) | ||
926 | best = i-w; | ||
927 | if (y+1 < w && dsf_size(dsf, i+w) < MAXBLK && | ||
928 | (best == -1 || revorder[i+w] < revorder[best])) | ||
929 | best = i+w; | ||
930 | |||
931 | if (best >= 0) { | ||
932 | singletons[i] = singletons[best] = FALSE; | ||
933 | dsf_merge(dsf, i, best); | ||
934 | } | ||
935 | } | ||
936 | } | ||
937 | |||
938 | /* Quit and start again if we have any singletons left over | ||
939 | * which we weren't able to do anything at all with. */ | ||
940 | for (i = 0; i < a; i++) | ||
941 | if (singletons[i]) | ||
942 | break; | ||
943 | if (i < a) | ||
944 | continue; | ||
945 | |||
946 | /* | ||
947 | * Decide what would be acceptable clues for each block. | ||
948 | * | ||
949 | * Blocks larger than 2 have free choice of ADD or MUL; | ||
950 | * blocks of size 2 can be anything in principle (except | ||
951 | * that they can only be DIV if the two numbers have an | ||
952 | * integer quotient, of course), but we rule out (or try to | ||
953 | * avoid) some clues because they're of low quality. | ||
954 | * | ||
955 | * Hence, we iterate once over the grid, stopping at the | ||
956 | * canonical element of every >2 block and the _non_- | ||
957 | * canonical element of every 2-block; the latter means that | ||
958 | * we can make our decision about a 2-block in the knowledge | ||
959 | * of both numbers in it. | ||
960 | * | ||
961 | * We reuse the 'singletons' array (finished with in the | ||
962 | * above loop) to hold information about which blocks are | ||
963 | * suitable for what. | ||
964 | */ | ||
965 | #define F_ADD 0x01 | ||
966 | #define F_SUB 0x02 | ||
967 | #define F_MUL 0x04 | ||
968 | #define F_DIV 0x08 | ||
969 | #define BAD_SHIFT 4 | ||
970 | |||
971 | for (i = 0; i < a; i++) { | ||
972 | singletons[i] = 0; | ||
973 | j = dsf_canonify(dsf, i); | ||
974 | k = dsf_size(dsf, j); | ||
975 | if (params->multiplication_only) | ||
976 | singletons[j] = F_MUL; | ||
977 | else if (j == i && k > 2) { | ||
978 | singletons[j] |= F_ADD | F_MUL; | ||
979 | } else if (j != i && k == 2) { | ||
980 | /* Fetch the two numbers and sort them into order. */ | ||
981 | int p = grid[j], q = grid[i], v; | ||
982 | if (p < q) { | ||
983 | int t = p; p = q; q = t; | ||
984 | } | ||
985 | |||
986 | /* | ||
987 | * Addition clues are always allowed, but we try to | ||
988 | * avoid sums of 3, 4, (2w-1) and (2w-2) if we can, | ||
989 | * because they're too easy - they only leave one | ||
990 | * option for the pair of numbers involved. | ||
991 | */ | ||
992 | v = p + q; | ||
993 | if (v > 4 && v < 2*w-2) | ||
994 | singletons[j] |= F_ADD; | ||
995 | else | ||
996 | singletons[j] |= F_ADD << BAD_SHIFT; | ||
997 | |||
998 | /* | ||
999 | * Multiplication clues: above Normal difficulty, we | ||
1000 | * prefer (but don't absolutely insist on) clues of | ||
1001 | * this type which leave multiple options open. | ||
1002 | */ | ||
1003 | v = p * q; | ||
1004 | n = 0; | ||
1005 | for (k = 1; k <= w; k++) | ||
1006 | if (v % k == 0 && v / k <= w && v / k != k) | ||
1007 | n++; | ||
1008 | if (n <= 2 && diff > DIFF_NORMAL) | ||
1009 | singletons[j] |= F_MUL << BAD_SHIFT; | ||
1010 | else | ||
1011 | singletons[j] |= F_MUL; | ||
1012 | |||
1013 | /* | ||
1014 | * Subtraction: we completely avoid a difference of | ||
1015 | * w-1. | ||
1016 | */ | ||
1017 | v = p - q; | ||
1018 | if (v < w-1) | ||
1019 | singletons[j] |= F_SUB; | ||
1020 | |||
1021 | /* | ||
1022 | * Division: for a start, the quotient must be an | ||
1023 | * integer or the clue type is impossible. Also, we | ||
1024 | * never use quotients strictly greater than w/2, | ||
1025 | * because they're not only too easy but also | ||
1026 | * inelegant. | ||
1027 | */ | ||
1028 | if (p % q == 0 && 2 * (p / q) <= w) | ||
1029 | singletons[j] |= F_DIV; | ||
1030 | } | ||
1031 | } | ||
1032 | |||
1033 | /* | ||
1034 | * Actually choose a clue for each block, trying to keep the | ||
1035 | * numbers of each type even, and starting with the | ||
1036 | * preferred candidates for each type where possible. | ||
1037 | * | ||
1038 | * I'm sure there should be a faster algorithm for doing | ||
1039 | * this, but I can't be bothered: O(N^2) is good enough when | ||
1040 | * N is at most the number of dominoes that fits into a 9x9 | ||
1041 | * square. | ||
1042 | */ | ||
1043 | shuffle(order, a, sizeof(*order), rs); | ||
1044 | for (i = 0; i < a; i++) | ||
1045 | clues[i] = 0; | ||
1046 | while (1) { | ||
1047 | int done_something = FALSE; | ||
1048 | |||
1049 | for (k = 0; k < 4; k++) { | ||
1050 | long clue; | ||
1051 | int good, bad; | ||
1052 | switch (k) { | ||
1053 | case 0: clue = C_DIV; good = F_DIV; break; | ||
1054 | case 1: clue = C_SUB; good = F_SUB; break; | ||
1055 | case 2: clue = C_MUL; good = F_MUL; break; | ||
1056 | default /* case 3 */ : clue = C_ADD; good = F_ADD; break; | ||
1057 | } | ||
1058 | |||
1059 | for (i = 0; i < a; i++) { | ||
1060 | j = order[i]; | ||
1061 | if (singletons[j] & good) { | ||
1062 | clues[j] = clue; | ||
1063 | singletons[j] = 0; | ||
1064 | break; | ||
1065 | } | ||
1066 | } | ||
1067 | if (i == a) { | ||
1068 | /* didn't find a nice one, use a nasty one */ | ||
1069 | bad = good << BAD_SHIFT; | ||
1070 | for (i = 0; i < a; i++) { | ||
1071 | j = order[i]; | ||
1072 | if (singletons[j] & bad) { | ||
1073 | clues[j] = clue; | ||
1074 | singletons[j] = 0; | ||
1075 | break; | ||
1076 | } | ||
1077 | } | ||
1078 | } | ||
1079 | if (i < a) | ||
1080 | done_something = TRUE; | ||
1081 | } | ||
1082 | |||
1083 | if (!done_something) | ||
1084 | break; | ||
1085 | } | ||
1086 | #undef F_ADD | ||
1087 | #undef F_SUB | ||
1088 | #undef F_MUL | ||
1089 | #undef F_DIV | ||
1090 | #undef BAD_SHIFT | ||
1091 | |||
1092 | /* | ||
1093 | * Having chosen the clue types, calculate the clue values. | ||
1094 | */ | ||
1095 | for (i = 0; i < a; i++) { | ||
1096 | j = dsf_canonify(dsf, i); | ||
1097 | if (j == i) { | ||
1098 | cluevals[j] = grid[i]; | ||
1099 | } else { | ||
1100 | switch (clues[j]) { | ||
1101 | case C_ADD: | ||
1102 | cluevals[j] += grid[i]; | ||
1103 | break; | ||
1104 | case C_MUL: | ||
1105 | cluevals[j] *= grid[i]; | ||
1106 | break; | ||
1107 | case C_SUB: | ||
1108 | cluevals[j] = abs(cluevals[j] - grid[i]); | ||
1109 | break; | ||
1110 | case C_DIV: | ||
1111 | { | ||
1112 | int d1 = cluevals[j], d2 = grid[i]; | ||
1113 | if (d1 == 0 || d2 == 0) | ||
1114 | cluevals[j] = 0; | ||
1115 | else | ||
1116 | cluevals[j] = d2/d1 + d1/d2;/* one is 0 :-) */ | ||
1117 | } | ||
1118 | break; | ||
1119 | } | ||
1120 | } | ||
1121 | } | ||
1122 | |||
1123 | for (i = 0; i < a; i++) { | ||
1124 | j = dsf_canonify(dsf, i); | ||
1125 | if (j == i) { | ||
1126 | clues[j] |= cluevals[j]; | ||
1127 | } | ||
1128 | } | ||
1129 | |||
1130 | /* | ||
1131 | * See if the game can be solved at the specified difficulty | ||
1132 | * level, but not at the one below. | ||
1133 | */ | ||
1134 | if (diff > 0) { | ||
1135 | memset(soln, 0, a); | ||
1136 | ret = solver(w, dsf, clues, soln, diff-1); | ||
1137 | if (ret <= diff-1) | ||
1138 | continue; | ||
1139 | } | ||
1140 | memset(soln, 0, a); | ||
1141 | ret = solver(w, dsf, clues, soln, diff); | ||
1142 | if (ret != diff) | ||
1143 | continue; /* go round again */ | ||
1144 | |||
1145 | /* | ||
1146 | * I wondered if at this point it would be worth trying to | ||
1147 | * merge adjacent blocks together, to make the puzzle | ||
1148 | * gradually more difficult if it's currently easier than | ||
1149 | * specced, increasing the chance of a given generation run | ||
1150 | * being successful. | ||
1151 | * | ||
1152 | * It doesn't seem to be critical for the generation speed, | ||
1153 | * though, so for the moment I'm leaving it out. | ||
1154 | */ | ||
1155 | |||
1156 | /* | ||
1157 | * We've got a usable puzzle! | ||
1158 | */ | ||
1159 | break; | ||
1160 | } | ||
1161 | |||
1162 | /* | ||
1163 | * Encode the puzzle description. | ||
1164 | */ | ||
1165 | desc = snewn(40*a, char); | ||
1166 | p = desc; | ||
1167 | p = encode_block_structure(p, w, dsf); | ||
1168 | *p++ = ','; | ||
1169 | for (i = 0; i < a; i++) { | ||
1170 | j = dsf_canonify(dsf, i); | ||
1171 | if (j == i) { | ||
1172 | switch (clues[j] & CMASK) { | ||
1173 | case C_ADD: *p++ = 'a'; break; | ||
1174 | case C_SUB: *p++ = 's'; break; | ||
1175 | case C_MUL: *p++ = 'm'; break; | ||
1176 | case C_DIV: *p++ = 'd'; break; | ||
1177 | } | ||
1178 | p += sprintf(p, "%ld", clues[j] & ~CMASK); | ||
1179 | } | ||
1180 | } | ||
1181 | *p++ = '\0'; | ||
1182 | desc = sresize(desc, p - desc, char); | ||
1183 | |||
1184 | /* | ||
1185 | * Encode the solution. | ||
1186 | */ | ||
1187 | assert(memcmp(soln, grid, a) == 0); | ||
1188 | *aux = snewn(a+2, char); | ||
1189 | (*aux)[0] = 'S'; | ||
1190 | for (i = 0; i < a; i++) | ||
1191 | (*aux)[i+1] = '0' + soln[i]; | ||
1192 | (*aux)[a+1] = '\0'; | ||
1193 | |||
1194 | sfree(grid); | ||
1195 | sfree(order); | ||
1196 | sfree(revorder); | ||
1197 | sfree(singletons); | ||
1198 | sfree(dsf); | ||
1199 | sfree(clues); | ||
1200 | sfree(cluevals); | ||
1201 | sfree(soln); | ||
1202 | |||
1203 | return desc; | ||
1204 | } | ||
1205 | |||
1206 | /* ---------------------------------------------------------------------- | ||
1207 | * Gameplay. | ||
1208 | */ | ||
1209 | |||
1210 | static char *validate_desc(const game_params *params, const char *desc) | ||
1211 | { | ||
1212 | int w = params->w, a = w*w; | ||
1213 | int *dsf; | ||
1214 | char *ret; | ||
1215 | const char *p = desc; | ||
1216 | int i; | ||
1217 | |||
1218 | /* | ||
1219 | * Verify that the block structure makes sense. | ||
1220 | */ | ||
1221 | dsf = snew_dsf(a); | ||
1222 | ret = parse_block_structure(&p, w, dsf); | ||
1223 | if (ret) { | ||
1224 | sfree(dsf); | ||
1225 | return ret; | ||
1226 | } | ||
1227 | |||
1228 | if (*p != ',') | ||
1229 | return "Expected ',' after block structure description"; | ||
1230 | p++; | ||
1231 | |||
1232 | /* | ||
1233 | * Verify that the right number of clues are given, and that SUB | ||
1234 | * and DIV clues don't apply to blocks of the wrong size. | ||
1235 | */ | ||
1236 | for (i = 0; i < a; i++) { | ||
1237 | if (dsf_canonify(dsf, i) == i) { | ||
1238 | if (*p == 'a' || *p == 'm') { | ||
1239 | /* these clues need no validation */ | ||
1240 | } else if (*p == 'd' || *p == 's') { | ||
1241 | if (dsf_size(dsf, i) != 2) | ||
1242 | return "Subtraction and division blocks must have area 2"; | ||
1243 | } else if (!*p) { | ||
1244 | return "Too few clues for block structure"; | ||
1245 | } else { | ||
1246 | return "Unrecognised clue type"; | ||
1247 | } | ||
1248 | p++; | ||
1249 | while (*p && isdigit((unsigned char)*p)) p++; | ||
1250 | } | ||
1251 | } | ||
1252 | if (*p) | ||
1253 | return "Too many clues for block structure"; | ||
1254 | |||
1255 | return NULL; | ||
1256 | } | ||
1257 | |||
1258 | static game_state *new_game(midend *me, const game_params *params, | ||
1259 | const char *desc) | ||
1260 | { | ||
1261 | int w = params->w, a = w*w; | ||
1262 | game_state *state = snew(game_state); | ||
1263 | const char *p = desc; | ||
1264 | int i; | ||
1265 | |||
1266 | state->par = *params; /* structure copy */ | ||
1267 | state->clues = snew(struct clues); | ||
1268 | state->clues->refcount = 1; | ||
1269 | state->clues->w = w; | ||
1270 | state->clues->dsf = snew_dsf(a); | ||
1271 | parse_block_structure(&p, w, state->clues->dsf); | ||
1272 | |||
1273 | assert(*p == ','); | ||
1274 | p++; | ||
1275 | |||
1276 | state->clues->clues = snewn(a, long); | ||
1277 | for (i = 0; i < a; i++) { | ||
1278 | if (dsf_canonify(state->clues->dsf, i) == i) { | ||
1279 | long clue = 0; | ||
1280 | switch (*p) { | ||
1281 | case 'a': | ||
1282 | clue = C_ADD; | ||
1283 | break; | ||
1284 | case 'm': | ||
1285 | clue = C_MUL; | ||
1286 | break; | ||
1287 | case 's': | ||
1288 | clue = C_SUB; | ||
1289 | assert(dsf_size(state->clues->dsf, i) == 2); | ||
1290 | break; | ||
1291 | case 'd': | ||
1292 | clue = C_DIV; | ||
1293 | assert(dsf_size(state->clues->dsf, i) == 2); | ||
1294 | break; | ||
1295 | default: | ||
1296 | assert(!"Bad description in new_game"); | ||
1297 | } | ||
1298 | p++; | ||
1299 | clue |= atol(p); | ||
1300 | while (*p && isdigit((unsigned char)*p)) p++; | ||
1301 | state->clues->clues[i] = clue; | ||
1302 | } else | ||
1303 | state->clues->clues[i] = 0; | ||
1304 | } | ||
1305 | |||
1306 | state->grid = snewn(a, digit); | ||
1307 | state->pencil = snewn(a, int); | ||
1308 | for (i = 0; i < a; i++) { | ||
1309 | state->grid[i] = 0; | ||
1310 | state->pencil[i] = 0; | ||
1311 | } | ||
1312 | |||
1313 | state->completed = state->cheated = FALSE; | ||
1314 | |||
1315 | return state; | ||
1316 | } | ||
1317 | |||
1318 | static game_state *dup_game(const game_state *state) | ||
1319 | { | ||
1320 | int w = state->par.w, a = w*w; | ||
1321 | game_state *ret = snew(game_state); | ||
1322 | |||
1323 | ret->par = state->par; /* structure copy */ | ||
1324 | |||
1325 | ret->clues = state->clues; | ||
1326 | ret->clues->refcount++; | ||
1327 | |||
1328 | ret->grid = snewn(a, digit); | ||
1329 | ret->pencil = snewn(a, int); | ||
1330 | memcpy(ret->grid, state->grid, a*sizeof(digit)); | ||
1331 | memcpy(ret->pencil, state->pencil, a*sizeof(int)); | ||
1332 | |||
1333 | ret->completed = state->completed; | ||
1334 | ret->cheated = state->cheated; | ||
1335 | |||
1336 | return ret; | ||
1337 | } | ||
1338 | |||
1339 | static void free_game(game_state *state) | ||
1340 | { | ||
1341 | sfree(state->grid); | ||
1342 | sfree(state->pencil); | ||
1343 | if (--state->clues->refcount <= 0) { | ||
1344 | sfree(state->clues->dsf); | ||
1345 | sfree(state->clues->clues); | ||
1346 | sfree(state->clues); | ||
1347 | } | ||
1348 | sfree(state); | ||
1349 | } | ||
1350 | |||
1351 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1352 | const char *aux, char **error) | ||
1353 | { | ||
1354 | int w = state->par.w, a = w*w; | ||
1355 | int i, ret; | ||
1356 | digit *soln; | ||
1357 | char *out; | ||
1358 | |||
1359 | if (aux) | ||
1360 | return dupstr(aux); | ||
1361 | |||
1362 | soln = snewn(a, digit); | ||
1363 | memset(soln, 0, a); | ||
1364 | |||
1365 | ret = solver(w, state->clues->dsf, state->clues->clues, | ||
1366 | soln, DIFFCOUNT-1); | ||
1367 | |||
1368 | if (ret == diff_impossible) { | ||
1369 | *error = "No solution exists for this puzzle"; | ||
1370 | out = NULL; | ||
1371 | } else if (ret == diff_ambiguous) { | ||
1372 | *error = "Multiple solutions exist for this puzzle"; | ||
1373 | out = NULL; | ||
1374 | } else { | ||
1375 | out = snewn(a+2, char); | ||
1376 | out[0] = 'S'; | ||
1377 | for (i = 0; i < a; i++) | ||
1378 | out[i+1] = '0' + soln[i]; | ||
1379 | out[a+1] = '\0'; | ||
1380 | } | ||
1381 | |||
1382 | sfree(soln); | ||
1383 | return out; | ||
1384 | } | ||
1385 | |||
1386 | static int game_can_format_as_text_now(const game_params *params) | ||
1387 | { | ||
1388 | return TRUE; | ||
1389 | } | ||
1390 | |||
1391 | static char *game_text_format(const game_state *state) | ||
1392 | { | ||
1393 | return NULL; | ||
1394 | } | ||
1395 | |||
1396 | struct game_ui { | ||
1397 | /* | ||
1398 | * These are the coordinates of the currently highlighted | ||
1399 | * square on the grid, if hshow = 1. | ||
1400 | */ | ||
1401 | int hx, hy; | ||
1402 | /* | ||
1403 | * This indicates whether the current highlight is a | ||
1404 | * pencil-mark one or a real one. | ||
1405 | */ | ||
1406 | int hpencil; | ||
1407 | /* | ||
1408 | * This indicates whether or not we're showing the highlight | ||
1409 | * (used to be hx = hy = -1); important so that when we're | ||
1410 | * using the cursor keys it doesn't keep coming back at a | ||
1411 | * fixed position. When hshow = 1, pressing a valid number | ||
1412 | * or letter key or Space will enter that number or letter in the grid. | ||
1413 | */ | ||
1414 | int hshow; | ||
1415 | /* | ||
1416 | * This indicates whether we're using the highlight as a cursor; | ||
1417 | * it means that it doesn't vanish on a keypress, and that it is | ||
1418 | * allowed on immutable squares. | ||
1419 | */ | ||
1420 | int hcursor; | ||
1421 | }; | ||
1422 | |||
1423 | static game_ui *new_ui(const game_state *state) | ||
1424 | { | ||
1425 | game_ui *ui = snew(game_ui); | ||
1426 | |||
1427 | ui->hx = ui->hy = 0; | ||
1428 | ui->hpencil = ui->hshow = ui->hcursor = 0; | ||
1429 | |||
1430 | return ui; | ||
1431 | } | ||
1432 | |||
1433 | static void free_ui(game_ui *ui) | ||
1434 | { | ||
1435 | sfree(ui); | ||
1436 | } | ||
1437 | |||
1438 | static char *encode_ui(const game_ui *ui) | ||
1439 | { | ||
1440 | return NULL; | ||
1441 | } | ||
1442 | |||
1443 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1444 | { | ||
1445 | } | ||
1446 | |||
1447 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1448 | const game_state *newstate) | ||
1449 | { | ||
1450 | int w = newstate->par.w; | ||
1451 | /* | ||
1452 | * We prevent pencil-mode highlighting of a filled square, unless | ||
1453 | * we're using the cursor keys. So if the user has just filled in | ||
1454 | * a square which we had a pencil-mode highlight in (by Undo, or | ||
1455 | * by Redo, or by Solve), then we cancel the highlight. | ||
1456 | */ | ||
1457 | if (ui->hshow && ui->hpencil && !ui->hcursor && | ||
1458 | newstate->grid[ui->hy * w + ui->hx] != 0) { | ||
1459 | ui->hshow = 0; | ||
1460 | } | ||
1461 | } | ||
1462 | |||
1463 | #define PREFERRED_TILESIZE 48 | ||
1464 | #define TILESIZE (ds->tilesize) | ||
1465 | #define BORDER (TILESIZE / 2) | ||
1466 | #define GRIDEXTRA max((TILESIZE / 32),1) | ||
1467 | #define COORD(x) ((x)*TILESIZE + BORDER) | ||
1468 | #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1) | ||
1469 | |||
1470 | #define FLASH_TIME 0.4F | ||
1471 | |||
1472 | #define DF_PENCIL_SHIFT 16 | ||
1473 | #define DF_ERR_LATIN 0x8000 | ||
1474 | #define DF_ERR_CLUE 0x4000 | ||
1475 | #define DF_HIGHLIGHT 0x2000 | ||
1476 | #define DF_HIGHLIGHT_PENCIL 0x1000 | ||
1477 | #define DF_DIGIT_MASK 0x000F | ||
1478 | |||
1479 | struct game_drawstate { | ||
1480 | int tilesize; | ||
1481 | int started; | ||
1482 | long *tiles; | ||
1483 | long *errors; | ||
1484 | char *minus_sign, *times_sign, *divide_sign; | ||
1485 | }; | ||
1486 | |||
1487 | static int check_errors(const game_state *state, long *errors) | ||
1488 | { | ||
1489 | int w = state->par.w, a = w*w; | ||
1490 | int i, j, x, y, errs = FALSE; | ||
1491 | long *cluevals; | ||
1492 | int *full; | ||
1493 | |||
1494 | cluevals = snewn(a, long); | ||
1495 | full = snewn(a, int); | ||
1496 | |||
1497 | if (errors) | ||
1498 | for (i = 0; i < a; i++) { | ||
1499 | errors[i] = 0; | ||
1500 | full[i] = TRUE; | ||
1501 | } | ||
1502 | |||
1503 | for (i = 0; i < a; i++) { | ||
1504 | long clue; | ||
1505 | |||
1506 | j = dsf_canonify(state->clues->dsf, i); | ||
1507 | if (j == i) { | ||
1508 | cluevals[i] = state->grid[i]; | ||
1509 | } else { | ||
1510 | clue = state->clues->clues[j] & CMASK; | ||
1511 | |||
1512 | switch (clue) { | ||
1513 | case C_ADD: | ||
1514 | cluevals[j] += state->grid[i]; | ||
1515 | break; | ||
1516 | case C_MUL: | ||
1517 | cluevals[j] *= state->grid[i]; | ||
1518 | break; | ||
1519 | case C_SUB: | ||
1520 | cluevals[j] = abs(cluevals[j] - state->grid[i]); | ||
1521 | break; | ||
1522 | case C_DIV: | ||
1523 | { | ||
1524 | int d1 = min(cluevals[j], state->grid[i]); | ||
1525 | int d2 = max(cluevals[j], state->grid[i]); | ||
1526 | if (d1 == 0 || d2 % d1 != 0) | ||
1527 | cluevals[j] = 0; | ||
1528 | else | ||
1529 | cluevals[j] = d2 / d1; | ||
1530 | } | ||
1531 | break; | ||
1532 | } | ||
1533 | } | ||
1534 | |||
1535 | if (!state->grid[i]) | ||
1536 | full[j] = FALSE; | ||
1537 | } | ||
1538 | |||
1539 | for (i = 0; i < a; i++) { | ||
1540 | j = dsf_canonify(state->clues->dsf, i); | ||
1541 | if (j == i) { | ||
1542 | if ((state->clues->clues[j] & ~CMASK) != cluevals[i]) { | ||
1543 | errs = TRUE; | ||
1544 | if (errors && full[j]) | ||
1545 | errors[j] |= DF_ERR_CLUE; | ||
1546 | } | ||
1547 | } | ||
1548 | } | ||
1549 | |||
1550 | sfree(cluevals); | ||
1551 | sfree(full); | ||
1552 | |||
1553 | for (y = 0; y < w; y++) { | ||
1554 | int mask = 0, errmask = 0; | ||
1555 | for (x = 0; x < w; x++) { | ||
1556 | int bit = 1 << state->grid[y*w+x]; | ||
1557 | errmask |= (mask & bit); | ||
1558 | mask |= bit; | ||
1559 | } | ||
1560 | |||
1561 | if (mask != (1 << (w+1)) - (1 << 1)) { | ||
1562 | errs = TRUE; | ||
1563 | errmask &= ~1; | ||
1564 | if (errors) { | ||
1565 | for (x = 0; x < w; x++) | ||
1566 | if (errmask & (1 << state->grid[y*w+x])) | ||
1567 | errors[y*w+x] |= DF_ERR_LATIN; | ||
1568 | } | ||
1569 | } | ||
1570 | } | ||
1571 | |||
1572 | for (x = 0; x < w; x++) { | ||
1573 | int mask = 0, errmask = 0; | ||
1574 | for (y = 0; y < w; y++) { | ||
1575 | int bit = 1 << state->grid[y*w+x]; | ||
1576 | errmask |= (mask & bit); | ||
1577 | mask |= bit; | ||
1578 | } | ||
1579 | |||
1580 | if (mask != (1 << (w+1)) - (1 << 1)) { | ||
1581 | errs = TRUE; | ||
1582 | errmask &= ~1; | ||
1583 | if (errors) { | ||
1584 | for (y = 0; y < w; y++) | ||
1585 | if (errmask & (1 << state->grid[y*w+x])) | ||
1586 | errors[y*w+x] |= DF_ERR_LATIN; | ||
1587 | } | ||
1588 | } | ||
1589 | } | ||
1590 | |||
1591 | return errs; | ||
1592 | } | ||
1593 | |||
1594 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1595 | const game_drawstate *ds, | ||
1596 | int x, int y, int button) | ||
1597 | { | ||
1598 | int w = state->par.w; | ||
1599 | int tx, ty; | ||
1600 | char buf[80]; | ||
1601 | |||
1602 | button &= ~MOD_MASK; | ||
1603 | |||
1604 | tx = FROMCOORD(x); | ||
1605 | ty = FROMCOORD(y); | ||
1606 | |||
1607 | if (tx >= 0 && tx < w && ty >= 0 && ty < w) { | ||
1608 | if (button == LEFT_BUTTON) { | ||
1609 | if (tx == ui->hx && ty == ui->hy && | ||
1610 | ui->hshow && ui->hpencil == 0) { | ||
1611 | ui->hshow = 0; | ||
1612 | } else { | ||
1613 | ui->hx = tx; | ||
1614 | ui->hy = ty; | ||
1615 | ui->hshow = 1; | ||
1616 | ui->hpencil = 0; | ||
1617 | } | ||
1618 | ui->hcursor = 0; | ||
1619 | return ""; /* UI activity occurred */ | ||
1620 | } | ||
1621 | if (button == RIGHT_BUTTON) { | ||
1622 | /* | ||
1623 | * Pencil-mode highlighting for non filled squares. | ||
1624 | */ | ||
1625 | if (state->grid[ty*w+tx] == 0) { | ||
1626 | if (tx == ui->hx && ty == ui->hy && | ||
1627 | ui->hshow && ui->hpencil) { | ||
1628 | ui->hshow = 0; | ||
1629 | } else { | ||
1630 | ui->hpencil = 1; | ||
1631 | ui->hx = tx; | ||
1632 | ui->hy = ty; | ||
1633 | ui->hshow = 1; | ||
1634 | } | ||
1635 | } else { | ||
1636 | ui->hshow = 0; | ||
1637 | } | ||
1638 | ui->hcursor = 0; | ||
1639 | return ""; /* UI activity occurred */ | ||
1640 | } | ||
1641 | } | ||
1642 | if (IS_CURSOR_MOVE(button)) { | ||
1643 | move_cursor(button, &ui->hx, &ui->hy, w, w, 0); | ||
1644 | ui->hshow = ui->hcursor = 1; | ||
1645 | return ""; | ||
1646 | } | ||
1647 | if (ui->hshow && | ||
1648 | (button == CURSOR_SELECT)) { | ||
1649 | ui->hpencil = 1 - ui->hpencil; | ||
1650 | ui->hcursor = 1; | ||
1651 | return ""; | ||
1652 | } | ||
1653 | |||
1654 | if (ui->hshow && | ||
1655 | ((button >= '0' && button <= '9' && button - '0' <= w) || | ||
1656 | button == CURSOR_SELECT2 || button == '\b')) { | ||
1657 | int n = button - '0'; | ||
1658 | if (button == CURSOR_SELECT2 || button == '\b') | ||
1659 | n = 0; | ||
1660 | |||
1661 | /* | ||
1662 | * Can't make pencil marks in a filled square. This can only | ||
1663 | * become highlighted if we're using cursor keys. | ||
1664 | */ | ||
1665 | if (ui->hpencil && state->grid[ui->hy*w+ui->hx]) | ||
1666 | return NULL; | ||
1667 | |||
1668 | sprintf(buf, "%c%d,%d,%d", | ||
1669 | (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n); | ||
1670 | |||
1671 | if (!ui->hcursor) ui->hshow = 0; | ||
1672 | |||
1673 | return dupstr(buf); | ||
1674 | } | ||
1675 | |||
1676 | if (button == 'M' || button == 'm') | ||
1677 | return dupstr("M"); | ||
1678 | |||
1679 | return NULL; | ||
1680 | } | ||
1681 | |||
1682 | static game_state *execute_move(const game_state *from, const char *move) | ||
1683 | { | ||
1684 | int w = from->par.w, a = w*w; | ||
1685 | game_state *ret; | ||
1686 | int x, y, i, n; | ||
1687 | |||
1688 | if (move[0] == 'S') { | ||
1689 | ret = dup_game(from); | ||
1690 | ret->completed = ret->cheated = TRUE; | ||
1691 | |||
1692 | for (i = 0; i < a; i++) { | ||
1693 | if (move[i+1] < '1' || move[i+1] > '0'+w) { | ||
1694 | free_game(ret); | ||
1695 | return NULL; | ||
1696 | } | ||
1697 | ret->grid[i] = move[i+1] - '0'; | ||
1698 | ret->pencil[i] = 0; | ||
1699 | } | ||
1700 | |||
1701 | if (move[a+1] != '\0') { | ||
1702 | free_game(ret); | ||
1703 | return NULL; | ||
1704 | } | ||
1705 | |||
1706 | return ret; | ||
1707 | } else if ((move[0] == 'P' || move[0] == 'R') && | ||
1708 | sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 && | ||
1709 | x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) { | ||
1710 | |||
1711 | ret = dup_game(from); | ||
1712 | if (move[0] == 'P' && n > 0) { | ||
1713 | ret->pencil[y*w+x] ^= 1 << n; | ||
1714 | } else { | ||
1715 | ret->grid[y*w+x] = n; | ||
1716 | ret->pencil[y*w+x] = 0; | ||
1717 | |||
1718 | if (!ret->completed && !check_errors(ret, NULL)) | ||
1719 | ret->completed = TRUE; | ||
1720 | } | ||
1721 | return ret; | ||
1722 | } else if (move[0] == 'M') { | ||
1723 | /* | ||
1724 | * Fill in absolutely all pencil marks everywhere. (I | ||
1725 | * wouldn't use this for actual play, but it's a handy | ||
1726 | * starting point when following through a set of | ||
1727 | * diagnostics output by the standalone solver.) | ||
1728 | */ | ||
1729 | ret = dup_game(from); | ||
1730 | for (i = 0; i < a; i++) { | ||
1731 | if (!ret->grid[i]) | ||
1732 | ret->pencil[i] = (1 << (w+1)) - (1 << 1); | ||
1733 | } | ||
1734 | return ret; | ||
1735 | } else | ||
1736 | return NULL; /* couldn't parse move string */ | ||
1737 | } | ||
1738 | |||
1739 | /* ---------------------------------------------------------------------- | ||
1740 | * Drawing routines. | ||
1741 | */ | ||
1742 | |||
1743 | #define SIZE(w) ((w) * TILESIZE + 2*BORDER) | ||
1744 | |||
1745 | static void game_compute_size(const game_params *params, int tilesize, | ||
1746 | int *x, int *y) | ||
1747 | { | ||
1748 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1749 | struct { int tilesize; } ads, *ds = &ads; | ||
1750 | ads.tilesize = tilesize; | ||
1751 | |||
1752 | *x = *y = SIZE(params->w); | ||
1753 | } | ||
1754 | |||
1755 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1756 | const game_params *params, int tilesize) | ||
1757 | { | ||
1758 | ds->tilesize = tilesize; | ||
1759 | } | ||
1760 | |||
1761 | static float *game_colours(frontend *fe, int *ncolours) | ||
1762 | { | ||
1763 | float *ret = snewn(3 * NCOLOURS, float); | ||
1764 | |||
1765 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1766 | |||
1767 | ret[COL_GRID * 3 + 0] = 0.0F; | ||
1768 | ret[COL_GRID * 3 + 1] = 0.0F; | ||
1769 | ret[COL_GRID * 3 + 2] = 0.0F; | ||
1770 | |||
1771 | ret[COL_USER * 3 + 0] = 0.0F; | ||
1772 | ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; | ||
1773 | ret[COL_USER * 3 + 2] = 0.0F; | ||
1774 | |||
1775 | ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0]; | ||
1776 | ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1]; | ||
1777 | ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2]; | ||
1778 | |||
1779 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1780 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1781 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1782 | |||
1783 | ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
1784 | ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
1785 | ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; | ||
1786 | |||
1787 | *ncolours = NCOLOURS; | ||
1788 | return ret; | ||
1789 | } | ||
1790 | |||
1791 | static const char *const minus_signs[] = { "\xE2\x88\x92", "-" }; | ||
1792 | static const char *const times_signs[] = { "\xC3\x97", "*" }; | ||
1793 | static const char *const divide_signs[] = { "\xC3\xB7", "/" }; | ||
1794 | |||
1795 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1796 | { | ||
1797 | int w = state->par.w, a = w*w; | ||
1798 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1799 | int i; | ||
1800 | |||
1801 | ds->tilesize = 0; | ||
1802 | ds->started = FALSE; | ||
1803 | ds->tiles = snewn(a, long); | ||
1804 | for (i = 0; i < a; i++) | ||
1805 | ds->tiles[i] = -1; | ||
1806 | ds->errors = snewn(a, long); | ||
1807 | ds->minus_sign = text_fallback(dr, minus_signs, lenof(minus_signs)); | ||
1808 | ds->times_sign = text_fallback(dr, times_signs, lenof(times_signs)); | ||
1809 | ds->divide_sign = text_fallback(dr, divide_signs, lenof(divide_signs)); | ||
1810 | |||
1811 | return ds; | ||
1812 | } | ||
1813 | |||
1814 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1815 | { | ||
1816 | sfree(ds->tiles); | ||
1817 | sfree(ds->errors); | ||
1818 | sfree(ds->minus_sign); | ||
1819 | sfree(ds->times_sign); | ||
1820 | sfree(ds->divide_sign); | ||
1821 | sfree(ds); | ||
1822 | } | ||
1823 | |||
1824 | static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, | ||
1825 | int x, int y, long tile, int only_one_op) | ||
1826 | { | ||
1827 | int w = clues->w /* , a = w*w */; | ||
1828 | int tx, ty, tw, th; | ||
1829 | int cx, cy, cw, ch; | ||
1830 | char str[64]; | ||
1831 | |||
1832 | tx = BORDER + x * TILESIZE + 1 + GRIDEXTRA; | ||
1833 | ty = BORDER + y * TILESIZE + 1 + GRIDEXTRA; | ||
1834 | |||
1835 | cx = tx; | ||
1836 | cy = ty; | ||
1837 | cw = tw = TILESIZE-1-2*GRIDEXTRA; | ||
1838 | ch = th = TILESIZE-1-2*GRIDEXTRA; | ||
1839 | |||
1840 | if (x > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x-1)) | ||
1841 | cx -= GRIDEXTRA, cw += GRIDEXTRA; | ||
1842 | if (x+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, y*w+x+1)) | ||
1843 | cw += GRIDEXTRA; | ||
1844 | if (y > 0 && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y-1)*w+x)) | ||
1845 | cy -= GRIDEXTRA, ch += GRIDEXTRA; | ||
1846 | if (y+1 < w && dsf_canonify(clues->dsf, y*w+x) == dsf_canonify(clues->dsf, (y+1)*w+x)) | ||
1847 | ch += GRIDEXTRA; | ||
1848 | |||
1849 | clip(dr, cx, cy, cw, ch); | ||
1850 | |||
1851 | /* background needs erasing */ | ||
1852 | draw_rect(dr, cx, cy, cw, ch, | ||
1853 | (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND); | ||
1854 | |||
1855 | /* pencil-mode highlight */ | ||
1856 | if (tile & DF_HIGHLIGHT_PENCIL) { | ||
1857 | int coords[6]; | ||
1858 | coords[0] = cx; | ||
1859 | coords[1] = cy; | ||
1860 | coords[2] = cx+cw/2; | ||
1861 | coords[3] = cy; | ||
1862 | coords[4] = cx; | ||
1863 | coords[5] = cy+ch/2; | ||
1864 | draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
1865 | } | ||
1866 | |||
1867 | /* | ||
1868 | * Draw the corners of thick lines in corner-adjacent squares, | ||
1869 | * which jut into this square by one pixel. | ||
1870 | */ | ||
1871 | if (x > 0 && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x-1)) | ||
1872 | draw_rect(dr, tx-GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
1873 | if (x+1 < w && y > 0 && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y-1)*w+x+1)) | ||
1874 | draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty-GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
1875 | if (x > 0 && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x-1)) | ||
1876 | draw_rect(dr, tx-GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
1877 | if (x+1 < w && y+1 < w && dsf_canonify(clues->dsf, y*w+x) != dsf_canonify(clues->dsf, (y+1)*w+x+1)) | ||
1878 | draw_rect(dr, tx+TILESIZE-1-2*GRIDEXTRA, ty+TILESIZE-1-2*GRIDEXTRA, GRIDEXTRA, GRIDEXTRA, COL_GRID); | ||
1879 | |||
1880 | /* Draw the box clue. */ | ||
1881 | if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) { | ||
1882 | long clue = clues->clues[y*w+x]; | ||
1883 | long cluetype = clue & CMASK, clueval = clue & ~CMASK; | ||
1884 | int size = dsf_size(clues->dsf, y*w+x); | ||
1885 | /* | ||
1886 | * Special case of clue-drawing: a box with only one square | ||
1887 | * is written as just the number, with no operation, because | ||
1888 | * it doesn't matter whether the operation is ADD or MUL. | ||
1889 | * The generation code above should never produce puzzles | ||
1890 | * containing such a thing - I think they're inelegant - but | ||
1891 | * it's possible to type in game IDs from elsewhere, so I | ||
1892 | * want to display them right if so. | ||
1893 | */ | ||
1894 | sprintf (str, "%ld%s", clueval, | ||
1895 | (size == 1 || only_one_op ? "" : | ||
1896 | cluetype == C_ADD ? "+" : | ||
1897 | cluetype == C_SUB ? ds->minus_sign : | ||
1898 | cluetype == C_MUL ? ds->times_sign : | ||
1899 | /* cluetype == C_DIV ? */ ds->divide_sign)); | ||
1900 | draw_text(dr, tx + GRIDEXTRA * 2, ty + GRIDEXTRA * 2 + TILESIZE/4, | ||
1901 | FONT_VARIABLE, TILESIZE/4, ALIGN_VNORMAL | ALIGN_HLEFT, | ||
1902 | (tile & DF_ERR_CLUE ? COL_ERROR : COL_GRID), str); | ||
1903 | } | ||
1904 | |||
1905 | /* new number needs drawing? */ | ||
1906 | if (tile & DF_DIGIT_MASK) { | ||
1907 | str[1] = '\0'; | ||
1908 | str[0] = (tile & DF_DIGIT_MASK) + '0'; | ||
1909 | draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, | ||
1910 | FONT_VARIABLE, TILESIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
1911 | (tile & DF_ERR_LATIN) ? COL_ERROR : COL_USER, str); | ||
1912 | } else { | ||
1913 | int i, j, npencil; | ||
1914 | int pl, pr, pt, pb; | ||
1915 | float bestsize; | ||
1916 | int pw, ph, minph, pbest, fontsize; | ||
1917 | |||
1918 | /* Count the pencil marks required. */ | ||
1919 | for (i = 1, npencil = 0; i <= w; i++) | ||
1920 | if (tile & (1L << (i + DF_PENCIL_SHIFT))) | ||
1921 | npencil++; | ||
1922 | if (npencil) { | ||
1923 | |||
1924 | minph = 2; | ||
1925 | |||
1926 | /* | ||
1927 | * Determine the bounding rectangle within which we're going | ||
1928 | * to put the pencil marks. | ||
1929 | */ | ||
1930 | /* Start with the whole square */ | ||
1931 | pl = tx + GRIDEXTRA; | ||
1932 | pr = pl + TILESIZE - GRIDEXTRA; | ||
1933 | pt = ty + GRIDEXTRA; | ||
1934 | pb = pt + TILESIZE - GRIDEXTRA; | ||
1935 | if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) { | ||
1936 | /* | ||
1937 | * Make space for the clue text. | ||
1938 | */ | ||
1939 | pt += TILESIZE/4; | ||
1940 | /* minph--; */ | ||
1941 | } | ||
1942 | |||
1943 | /* | ||
1944 | * We arrange our pencil marks in a grid layout, with | ||
1945 | * the number of rows and columns adjusted to allow the | ||
1946 | * maximum font size. | ||
1947 | * | ||
1948 | * So now we work out what the grid size ought to be. | ||
1949 | */ | ||
1950 | bestsize = 0.0; | ||
1951 | pbest = 0; | ||
1952 | /* Minimum */ | ||
1953 | for (pw = 3; pw < max(npencil,4); pw++) { | ||
1954 | float fw, fh, fs; | ||
1955 | |||
1956 | ph = (npencil + pw - 1) / pw; | ||
1957 | ph = max(ph, minph); | ||
1958 | fw = (pr - pl) / (float)pw; | ||
1959 | fh = (pb - pt) / (float)ph; | ||
1960 | fs = min(fw, fh); | ||
1961 | if (fs > bestsize) { | ||
1962 | bestsize = fs; | ||
1963 | pbest = pw; | ||
1964 | } | ||
1965 | } | ||
1966 | assert(pbest > 0); | ||
1967 | pw = pbest; | ||
1968 | ph = (npencil + pw - 1) / pw; | ||
1969 | ph = max(ph, minph); | ||
1970 | |||
1971 | /* | ||
1972 | * Now we've got our grid dimensions, work out the pixel | ||
1973 | * size of a grid element, and round it to the nearest | ||
1974 | * pixel. (We don't want rounding errors to make the | ||
1975 | * grid look uneven at low pixel sizes.) | ||
1976 | */ | ||
1977 | fontsize = min((pr - pl) / pw, (pb - pt) / ph); | ||
1978 | |||
1979 | /* | ||
1980 | * Centre the resulting figure in the square. | ||
1981 | */ | ||
1982 | pl = tx + (TILESIZE - fontsize * pw) / 2; | ||
1983 | pt = ty + (TILESIZE - fontsize * ph) / 2; | ||
1984 | |||
1985 | /* | ||
1986 | * And move it down a bit if it's collided with some | ||
1987 | * clue text. | ||
1988 | */ | ||
1989 | if (dsf_canonify(clues->dsf, y*w+x) == y*w+x) { | ||
1990 | pt = max(pt, ty + GRIDEXTRA * 3 + TILESIZE/4); | ||
1991 | } | ||
1992 | |||
1993 | /* | ||
1994 | * Now actually draw the pencil marks. | ||
1995 | */ | ||
1996 | for (i = 1, j = 0; i <= w; i++) | ||
1997 | if (tile & (1L << (i + DF_PENCIL_SHIFT))) { | ||
1998 | int dx = j % pw, dy = j / pw; | ||
1999 | |||
2000 | str[1] = '\0'; | ||
2001 | str[0] = i + '0'; | ||
2002 | draw_text(dr, pl + fontsize * (2*dx+1) / 2, | ||
2003 | pt + fontsize * (2*dy+1) / 2, | ||
2004 | FONT_VARIABLE, fontsize, | ||
2005 | ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); | ||
2006 | j++; | ||
2007 | } | ||
2008 | } | ||
2009 | } | ||
2010 | |||
2011 | unclip(dr); | ||
2012 | |||
2013 | draw_update(dr, cx, cy, cw, ch); | ||
2014 | } | ||
2015 | |||
2016 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
2017 | const game_state *oldstate, const game_state *state, | ||
2018 | int dir, const game_ui *ui, | ||
2019 | float animtime, float flashtime) | ||
2020 | { | ||
2021 | int w = state->par.w /*, a = w*w */; | ||
2022 | int x, y; | ||
2023 | |||
2024 | if (!ds->started) { | ||
2025 | /* | ||
2026 | * The initial contents of the window are not guaranteed and | ||
2027 | * can vary with front ends. To be on the safe side, all | ||
2028 | * games should start by drawing a big background-colour | ||
2029 | * rectangle covering the whole window. | ||
2030 | */ | ||
2031 | draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND); | ||
2032 | |||
2033 | /* | ||
2034 | * Big containing rectangle. | ||
2035 | */ | ||
2036 | draw_rect(dr, COORD(0) - GRIDEXTRA, COORD(0) - GRIDEXTRA, | ||
2037 | w*TILESIZE+1+GRIDEXTRA*2, w*TILESIZE+1+GRIDEXTRA*2, | ||
2038 | COL_GRID); | ||
2039 | |||
2040 | draw_update(dr, 0, 0, SIZE(w), SIZE(w)); | ||
2041 | |||
2042 | ds->started = TRUE; | ||
2043 | } | ||
2044 | |||
2045 | check_errors(state, ds->errors); | ||
2046 | |||
2047 | for (y = 0; y < w; y++) { | ||
2048 | for (x = 0; x < w; x++) { | ||
2049 | long tile = 0L; | ||
2050 | |||
2051 | if (state->grid[y*w+x]) | ||
2052 | tile = state->grid[y*w+x]; | ||
2053 | else | ||
2054 | tile = (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT; | ||
2055 | |||
2056 | if (ui->hshow && ui->hx == x && ui->hy == y) | ||
2057 | tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT); | ||
2058 | |||
2059 | if (flashtime > 0 && | ||
2060 | (flashtime <= FLASH_TIME/3 || | ||
2061 | flashtime >= FLASH_TIME*2/3)) | ||
2062 | tile |= DF_HIGHLIGHT; /* completion flash */ | ||
2063 | |||
2064 | tile |= ds->errors[y*w+x]; | ||
2065 | |||
2066 | if (ds->tiles[y*w+x] != tile) { | ||
2067 | ds->tiles[y*w+x] = tile; | ||
2068 | draw_tile(dr, ds, state->clues, x, y, tile, | ||
2069 | state->par.multiplication_only); | ||
2070 | } | ||
2071 | } | ||
2072 | } | ||
2073 | } | ||
2074 | |||
2075 | static float game_anim_length(const game_state *oldstate, | ||
2076 | const game_state *newstate, int dir, game_ui *ui) | ||
2077 | { | ||
2078 | return 0.0F; | ||
2079 | } | ||
2080 | |||
2081 | static float game_flash_length(const game_state *oldstate, | ||
2082 | const game_state *newstate, int dir, game_ui *ui) | ||
2083 | { | ||
2084 | if (!oldstate->completed && newstate->completed && | ||
2085 | !oldstate->cheated && !newstate->cheated) | ||
2086 | return FLASH_TIME; | ||
2087 | return 0.0F; | ||
2088 | } | ||
2089 | |||
2090 | static int game_status(const game_state *state) | ||
2091 | { | ||
2092 | return state->completed ? +1 : 0; | ||
2093 | } | ||
2094 | |||
2095 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
2096 | { | ||
2097 | if (state->completed) | ||
2098 | return FALSE; | ||
2099 | return TRUE; | ||
2100 | } | ||
2101 | |||
2102 | static void game_print_size(const game_params *params, float *x, float *y) | ||
2103 | { | ||
2104 | int pw, ph; | ||
2105 | |||
2106 | /* | ||
2107 | * We use 9mm squares by default, like Solo. | ||
2108 | */ | ||
2109 | game_compute_size(params, 900, &pw, &ph); | ||
2110 | *x = pw / 100.0F; | ||
2111 | *y = ph / 100.0F; | ||
2112 | } | ||
2113 | |||
2114 | /* | ||
2115 | * Subfunction to draw the thick lines between cells. In order to do | ||
2116 | * this using the line-drawing rather than rectangle-drawing API (so | ||
2117 | * as to get line thicknesses to scale correctly) and yet have | ||
2118 | * correctly mitred joins between lines, we must do this by tracing | ||
2119 | * the boundary of each sub-block and drawing it in one go as a | ||
2120 | * single polygon. | ||
2121 | */ | ||
2122 | static void outline_block_structure(drawing *dr, game_drawstate *ds, | ||
2123 | int w, int *dsf, int ink) | ||
2124 | { | ||
2125 | int a = w*w; | ||
2126 | int *coords; | ||
2127 | int i, n; | ||
2128 | int x, y, dx, dy, sx, sy, sdx, sdy; | ||
2129 | |||
2130 | coords = snewn(4*a, int); | ||
2131 | |||
2132 | /* | ||
2133 | * Iterate over all the blocks. | ||
2134 | */ | ||
2135 | for (i = 0; i < a; i++) { | ||
2136 | if (dsf_canonify(dsf, i) != i) | ||
2137 | continue; | ||
2138 | |||
2139 | /* | ||
2140 | * For each block, we need a starting square within it which | ||
2141 | * has a boundary at the left. Conveniently, we have one | ||
2142 | * right here, by construction. | ||
2143 | */ | ||
2144 | x = i % w; | ||
2145 | y = i / w; | ||
2146 | dx = -1; | ||
2147 | dy = 0; | ||
2148 | |||
2149 | /* | ||
2150 | * Now begin tracing round the perimeter. At all | ||
2151 | * times, (x,y) describes some square within the | ||
2152 | * block, and (x+dx,y+dy) is some adjacent square | ||
2153 | * outside it; so the edge between those two squares | ||
2154 | * is always an edge of the block. | ||
2155 | */ | ||
2156 | sx = x, sy = y, sdx = dx, sdy = dy; /* save starting position */ | ||
2157 | n = 0; | ||
2158 | do { | ||
2159 | int cx, cy, tx, ty, nin; | ||
2160 | |||
2161 | /* | ||
2162 | * Advance to the next edge, by looking at the two | ||
2163 | * squares beyond it. If they're both outside the block, | ||
2164 | * we turn right (by leaving x,y the same and rotating | ||
2165 | * dx,dy clockwise); if they're both inside, we turn | ||
2166 | * left (by rotating dx,dy anticlockwise and contriving | ||
2167 | * to leave x+dx,y+dy unchanged); if one of each, we go | ||
2168 | * straight on (and may enforce by assertion that | ||
2169 | * they're one of each the _right_ way round). | ||
2170 | */ | ||
2171 | nin = 0; | ||
2172 | tx = x - dy + dx; | ||
2173 | ty = y + dx + dy; | ||
2174 | nin += (tx >= 0 && tx < w && ty >= 0 && ty < w && | ||
2175 | dsf_canonify(dsf, ty*w+tx) == i); | ||
2176 | tx = x - dy; | ||
2177 | ty = y + dx; | ||
2178 | nin += (tx >= 0 && tx < w && ty >= 0 && ty < w && | ||
2179 | dsf_canonify(dsf, ty*w+tx) == i); | ||
2180 | if (nin == 0) { | ||
2181 | /* | ||
2182 | * Turn right. | ||
2183 | */ | ||
2184 | int tmp; | ||
2185 | tmp = dx; | ||
2186 | dx = -dy; | ||
2187 | dy = tmp; | ||
2188 | } else if (nin == 2) { | ||
2189 | /* | ||
2190 | * Turn left. | ||
2191 | */ | ||
2192 | int tmp; | ||
2193 | |||
2194 | x += dx; | ||
2195 | y += dy; | ||
2196 | |||
2197 | tmp = dx; | ||
2198 | dx = dy; | ||
2199 | dy = -tmp; | ||
2200 | |||
2201 | x -= dx; | ||
2202 | y -= dy; | ||
2203 | } else { | ||
2204 | /* | ||
2205 | * Go straight on. | ||
2206 | */ | ||
2207 | x -= dy; | ||
2208 | y += dx; | ||
2209 | } | ||
2210 | |||
2211 | /* | ||
2212 | * Now enforce by assertion that we ended up | ||
2213 | * somewhere sensible. | ||
2214 | */ | ||
2215 | assert(x >= 0 && x < w && y >= 0 && y < w && | ||
2216 | dsf_canonify(dsf, y*w+x) == i); | ||
2217 | assert(x+dx < 0 || x+dx >= w || y+dy < 0 || y+dy >= w || | ||
2218 | dsf_canonify(dsf, (y+dy)*w+(x+dx)) != i); | ||
2219 | |||
2220 | /* | ||
2221 | * Record the point we just went past at one end of the | ||
2222 | * edge. To do this, we translate (x,y) down and right | ||
2223 | * by half a unit (so they're describing a point in the | ||
2224 | * _centre_ of the square) and then translate back again | ||
2225 | * in a manner rotated by dy and dx. | ||
2226 | */ | ||
2227 | assert(n < 2*w+2); | ||
2228 | cx = ((2*x+1) + dy + dx) / 2; | ||
2229 | cy = ((2*y+1) - dx + dy) / 2; | ||
2230 | coords[2*n+0] = BORDER + cx * TILESIZE; | ||
2231 | coords[2*n+1] = BORDER + cy * TILESIZE; | ||
2232 | n++; | ||
2233 | |||
2234 | } while (x != sx || y != sy || dx != sdx || dy != sdy); | ||
2235 | |||
2236 | /* | ||
2237 | * That's our polygon; now draw it. | ||
2238 | */ | ||
2239 | draw_polygon(dr, coords, n, -1, ink); | ||
2240 | } | ||
2241 | |||
2242 | sfree(coords); | ||
2243 | } | ||
2244 | |||
2245 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
2246 | { | ||
2247 | int w = state->par.w; | ||
2248 | int ink = print_mono_colour(dr, 0); | ||
2249 | int x, y; | ||
2250 | char *minus_sign, *times_sign, *divide_sign; | ||
2251 | |||
2252 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
2253 | game_drawstate ads, *ds = &ads; | ||
2254 | game_set_size(dr, ds, NULL, tilesize); | ||
2255 | |||
2256 | minus_sign = text_fallback(dr, minus_signs, lenof(minus_signs)); | ||
2257 | times_sign = text_fallback(dr, times_signs, lenof(times_signs)); | ||
2258 | divide_sign = text_fallback(dr, divide_signs, lenof(divide_signs)); | ||
2259 | |||
2260 | /* | ||
2261 | * Border. | ||
2262 | */ | ||
2263 | print_line_width(dr, 3 * TILESIZE / 40); | ||
2264 | draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink); | ||
2265 | |||
2266 | /* | ||
2267 | * Main grid. | ||
2268 | */ | ||
2269 | for (x = 1; x < w; x++) { | ||
2270 | print_line_width(dr, TILESIZE / 40); | ||
2271 | draw_line(dr, BORDER+x*TILESIZE, BORDER, | ||
2272 | BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink); | ||
2273 | } | ||
2274 | for (y = 1; y < w; y++) { | ||
2275 | print_line_width(dr, TILESIZE / 40); | ||
2276 | draw_line(dr, BORDER, BORDER+y*TILESIZE, | ||
2277 | BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink); | ||
2278 | } | ||
2279 | |||
2280 | /* | ||
2281 | * Thick lines between cells. | ||
2282 | */ | ||
2283 | print_line_width(dr, 3 * TILESIZE / 40); | ||
2284 | outline_block_structure(dr, ds, w, state->clues->dsf, ink); | ||
2285 | |||
2286 | /* | ||
2287 | * Clues. | ||
2288 | */ | ||
2289 | for (y = 0; y < w; y++) | ||
2290 | for (x = 0; x < w; x++) | ||
2291 | if (dsf_canonify(state->clues->dsf, y*w+x) == y*w+x) { | ||
2292 | long clue = state->clues->clues[y*w+x]; | ||
2293 | long cluetype = clue & CMASK, clueval = clue & ~CMASK; | ||
2294 | int size = dsf_size(state->clues->dsf, y*w+x); | ||
2295 | char str[64]; | ||
2296 | |||
2297 | /* | ||
2298 | * As in the drawing code, we omit the operator for | ||
2299 | * blocks of area 1. | ||
2300 | */ | ||
2301 | sprintf (str, "%ld%s", clueval, | ||
2302 | (size == 1 ? "" : | ||
2303 | cluetype == C_ADD ? "+" : | ||
2304 | cluetype == C_SUB ? minus_sign : | ||
2305 | cluetype == C_MUL ? times_sign : | ||
2306 | /* cluetype == C_DIV ? */ divide_sign)); | ||
2307 | |||
2308 | draw_text(dr, | ||
2309 | BORDER+x*TILESIZE + 5*TILESIZE/80, | ||
2310 | BORDER+y*TILESIZE + 20*TILESIZE/80, | ||
2311 | FONT_VARIABLE, TILESIZE/4, | ||
2312 | ALIGN_VNORMAL | ALIGN_HLEFT, | ||
2313 | ink, str); | ||
2314 | } | ||
2315 | |||
2316 | /* | ||
2317 | * Numbers for the solution, if any. | ||
2318 | */ | ||
2319 | for (y = 0; y < w; y++) | ||
2320 | for (x = 0; x < w; x++) | ||
2321 | if (state->grid[y*w+x]) { | ||
2322 | char str[2]; | ||
2323 | str[1] = '\0'; | ||
2324 | str[0] = state->grid[y*w+x] + '0'; | ||
2325 | draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, | ||
2326 | BORDER + y*TILESIZE + TILESIZE/2, | ||
2327 | FONT_VARIABLE, TILESIZE/2, | ||
2328 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); | ||
2329 | } | ||
2330 | |||
2331 | sfree(minus_sign); | ||
2332 | sfree(times_sign); | ||
2333 | sfree(divide_sign); | ||
2334 | } | ||
2335 | |||
2336 | #ifdef COMBINED | ||
2337 | #define thegame keen | ||
2338 | #endif | ||
2339 | |||
2340 | const struct game thegame = { | ||
2341 | "Keen", "games.keen", "keen", | ||
2342 | default_params, | ||
2343 | game_fetch_preset, NULL, | ||
2344 | decode_params, | ||
2345 | encode_params, | ||
2346 | free_params, | ||
2347 | dup_params, | ||
2348 | TRUE, game_configure, custom_params, | ||
2349 | validate_params, | ||
2350 | new_game_desc, | ||
2351 | validate_desc, | ||
2352 | new_game, | ||
2353 | dup_game, | ||
2354 | free_game, | ||
2355 | TRUE, solve_game, | ||
2356 | FALSE, game_can_format_as_text_now, game_text_format, | ||
2357 | new_ui, | ||
2358 | free_ui, | ||
2359 | encode_ui, | ||
2360 | decode_ui, | ||
2361 | game_changed_state, | ||
2362 | interpret_move, | ||
2363 | execute_move, | ||
2364 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
2365 | game_colours, | ||
2366 | game_new_drawstate, | ||
2367 | game_free_drawstate, | ||
2368 | game_redraw, | ||
2369 | game_anim_length, | ||
2370 | game_flash_length, | ||
2371 | game_status, | ||
2372 | TRUE, FALSE, game_print_size, game_print, | ||
2373 | FALSE, /* wants_statusbar */ | ||
2374 | FALSE, game_timing_state, | ||
2375 | REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */ | ||
2376 | }; | ||
2377 | |||
2378 | #ifdef STANDALONE_SOLVER | ||
2379 | |||
2380 | #include <stdarg.h> | ||
2381 | |||
2382 | int main(int argc, char **argv) | ||
2383 | { | ||
2384 | game_params *p; | ||
2385 | game_state *s; | ||
2386 | char *id = NULL, *desc, *err; | ||
2387 | int grade = FALSE; | ||
2388 | int ret, diff, really_show_working = FALSE; | ||
2389 | |||
2390 | while (--argc > 0) { | ||
2391 | char *p = *++argv; | ||
2392 | if (!strcmp(p, "-v")) { | ||
2393 | really_show_working = TRUE; | ||
2394 | } else if (!strcmp(p, "-g")) { | ||
2395 | grade = TRUE; | ||
2396 | } else if (*p == '-') { | ||
2397 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2398 | return 1; | ||
2399 | } else { | ||
2400 | id = p; | ||
2401 | } | ||
2402 | } | ||
2403 | |||
2404 | if (!id) { | ||
2405 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
2406 | return 1; | ||
2407 | } | ||
2408 | |||
2409 | desc = strchr(id, ':'); | ||
2410 | if (!desc) { | ||
2411 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
2412 | return 1; | ||
2413 | } | ||
2414 | *desc++ = '\0'; | ||
2415 | |||
2416 | p = default_params(); | ||
2417 | decode_params(p, id); | ||
2418 | err = validate_desc(p, desc); | ||
2419 | if (err) { | ||
2420 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
2421 | return 1; | ||
2422 | } | ||
2423 | s = new_game(NULL, p, desc); | ||
2424 | |||
2425 | /* | ||
2426 | * When solving an Easy puzzle, we don't want to bother the | ||
2427 | * user with Hard-level deductions. For this reason, we grade | ||
2428 | * the puzzle internally before doing anything else. | ||
2429 | */ | ||
2430 | ret = -1; /* placate optimiser */ | ||
2431 | solver_show_working = FALSE; | ||
2432 | for (diff = 0; diff < DIFFCOUNT; diff++) { | ||
2433 | memset(s->grid, 0, p->w * p->w); | ||
2434 | ret = solver(p->w, s->clues->dsf, s->clues->clues, | ||
2435 | s->grid, diff); | ||
2436 | if (ret <= diff) | ||
2437 | break; | ||
2438 | } | ||
2439 | |||
2440 | if (diff == DIFFCOUNT) { | ||
2441 | if (grade) | ||
2442 | printf("Difficulty rating: ambiguous\n"); | ||
2443 | else | ||
2444 | printf("Unable to find a unique solution\n"); | ||
2445 | } else { | ||
2446 | if (grade) { | ||
2447 | if (ret == diff_impossible) | ||
2448 | printf("Difficulty rating: impossible (no solution exists)\n"); | ||
2449 | else | ||
2450 | printf("Difficulty rating: %s\n", keen_diffnames[ret]); | ||
2451 | } else { | ||
2452 | solver_show_working = really_show_working; | ||
2453 | memset(s->grid, 0, p->w * p->w); | ||
2454 | ret = solver(p->w, s->clues->dsf, s->clues->clues, | ||
2455 | s->grid, diff); | ||
2456 | if (ret != diff) | ||
2457 | printf("Puzzle is inconsistent\n"); | ||
2458 | else { | ||
2459 | /* | ||
2460 | * We don't have a game_text_format for this game, | ||
2461 | * so we have to output the solution manually. | ||
2462 | */ | ||
2463 | int x, y; | ||
2464 | for (y = 0; y < p->w; y++) { | ||
2465 | for (x = 0; x < p->w; x++) { | ||
2466 | printf("%s%c", x>0?" ":"", '0' + s->grid[y*p->w+x]); | ||
2467 | } | ||
2468 | putchar('\n'); | ||
2469 | } | ||
2470 | } | ||
2471 | } | ||
2472 | } | ||
2473 | |||
2474 | return 0; | ||
2475 | } | ||
2476 | |||
2477 | #endif | ||
2478 | |||
2479 | /* vim: set shiftwidth=4 tabstop=8: */ | ||