diff options
Diffstat (limited to 'apps/plugins/puzzles/towers.c')
-rw-r--r-- | apps/plugins/puzzles/towers.c | 2104 |
1 files changed, 2104 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/towers.c b/apps/plugins/puzzles/towers.c new file mode 100644 index 0000000000..d8e087a4bc --- /dev/null +++ b/apps/plugins/puzzles/towers.c | |||
@@ -0,0 +1,2104 @@ | |||
1 | /* | ||
2 | * towers.c: the puzzle also known as 'Skyscrapers'. | ||
3 | * | ||
4 | * Possible future work: | ||
5 | * | ||
6 | * - Relax the upper bound on grid size at 9? | ||
7 | * + I'd need TOCHAR and FROMCHAR macros a bit like group's, to | ||
8 | * be used wherever this code has +'0' or -'0' | ||
9 | * + the pencil marks in the drawstate would need a separate | ||
10 | * word to live in | ||
11 | * + the clues outside the grid would have to cope with being | ||
12 | * multi-digit, meaning in particular that the text formatting | ||
13 | * would become more unpleasant | ||
14 | * + most importantly, though, the solver just isn't fast | ||
15 | * enough. Even at size 9 it can't really do the solver_hard | ||
16 | * factorial-time enumeration at a sensible rate. Easy puzzles | ||
17 | * higher than that would be possible, but more latin-squarey | ||
18 | * than skyscrapery, as it were. | ||
19 | */ | ||
20 | |||
21 | #include <stdio.h> | ||
22 | #include <stdlib.h> | ||
23 | #include <string.h> | ||
24 | #include "rbassert.h" | ||
25 | #include <ctype.h> | ||
26 | #include <math.h> | ||
27 | |||
28 | #include "puzzles.h" | ||
29 | #include "latin.h" | ||
30 | |||
31 | /* | ||
32 | * Difficulty levels. I do some macro ickery here to ensure that my | ||
33 | * enum and the various forms of my name list always match up. | ||
34 | */ | ||
35 | #define DIFFLIST(A) \ | ||
36 | A(EASY,Easy,solver_easy,e) \ | ||
37 | A(HARD,Hard,solver_hard,h) \ | ||
38 | A(EXTREME,Extreme,NULL,x) \ | ||
39 | A(UNREASONABLE,Unreasonable,NULL,u) | ||
40 | #define ENUM(upper,title,func,lower) DIFF_ ## upper, | ||
41 | #define TITLE(upper,title,func,lower) #title, | ||
42 | #define ENCODE(upper,title,func,lower) #lower | ||
43 | #define CONFIG(upper,title,func,lower) ":" #title | ||
44 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
45 | static char const *const towers_diffnames[] = { DIFFLIST(TITLE) }; | ||
46 | static char const towers_diffchars[] = DIFFLIST(ENCODE); | ||
47 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
48 | |||
49 | enum { | ||
50 | COL_BACKGROUND, | ||
51 | COL_GRID, | ||
52 | COL_USER, | ||
53 | COL_HIGHLIGHT, | ||
54 | COL_ERROR, | ||
55 | COL_PENCIL, | ||
56 | COL_DONE, | ||
57 | NCOLOURS | ||
58 | }; | ||
59 | |||
60 | struct game_params { | ||
61 | int w, diff; | ||
62 | }; | ||
63 | |||
64 | struct clues { | ||
65 | int refcount; | ||
66 | int w; | ||
67 | /* | ||
68 | * An array of 4w integers, of which: | ||
69 | * - the first w run across the top | ||
70 | * - the next w across the bottom | ||
71 | * - the third w down the left | ||
72 | * - the last w down the right. | ||
73 | */ | ||
74 | int *clues; | ||
75 | |||
76 | /* | ||
77 | * An array of w*w digits. | ||
78 | */ | ||
79 | digit *immutable; | ||
80 | }; | ||
81 | |||
82 | /* | ||
83 | * Macros to compute clue indices and coordinates. | ||
84 | */ | ||
85 | #define STARTSTEP(start, step, index, w) do { \ | ||
86 | if (index < w) \ | ||
87 | start = index, step = w; \ | ||
88 | else if (index < 2*w) \ | ||
89 | start = (w-1)*w+(index-w), step = -w; \ | ||
90 | else if (index < 3*w) \ | ||
91 | start = w*(index-2*w), step = 1; \ | ||
92 | else \ | ||
93 | start = w*(index-3*w)+(w-1), step = -1; \ | ||
94 | } while (0) | ||
95 | #define CSTARTSTEP(start, step, index, w) \ | ||
96 | STARTSTEP(start, step, (((index)+2*w)%(4*w)), w) | ||
97 | #define CLUEPOS(x, y, index, w) do { \ | ||
98 | if (index < w) \ | ||
99 | x = index, y = -1; \ | ||
100 | else if (index < 2*w) \ | ||
101 | x = index-w, y = w; \ | ||
102 | else if (index < 3*w) \ | ||
103 | x = -1, y = index-2*w; \ | ||
104 | else \ | ||
105 | x = w, y = index-3*w; \ | ||
106 | } while (0) | ||
107 | |||
108 | #ifdef STANDALONE_SOLVER | ||
109 | static const char *const cluepos[] = { | ||
110 | "above column", "below column", "left of row", "right of row" | ||
111 | }; | ||
112 | #endif | ||
113 | |||
114 | struct game_state { | ||
115 | game_params par; | ||
116 | struct clues *clues; | ||
117 | unsigned char *clues_done; | ||
118 | digit *grid; | ||
119 | int *pencil; /* bitmaps using bits 1<<1..1<<n */ | ||
120 | int completed, cheated; | ||
121 | }; | ||
122 | |||
123 | static game_params *default_params(void) | ||
124 | { | ||
125 | game_params *ret = snew(game_params); | ||
126 | |||
127 | ret->w = 5; | ||
128 | ret->diff = DIFF_EASY; | ||
129 | |||
130 | return ret; | ||
131 | } | ||
132 | |||
133 | const static struct game_params towers_presets[] = { | ||
134 | { 4, DIFF_EASY }, | ||
135 | { 5, DIFF_EASY }, | ||
136 | { 5, DIFF_HARD }, | ||
137 | { 6, DIFF_EASY }, | ||
138 | { 6, DIFF_HARD }, | ||
139 | { 6, DIFF_EXTREME }, | ||
140 | { 6, DIFF_UNREASONABLE }, | ||
141 | }; | ||
142 | |||
143 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
144 | { | ||
145 | game_params *ret; | ||
146 | char buf[80]; | ||
147 | |||
148 | if (i < 0 || i >= lenof(towers_presets)) | ||
149 | return FALSE; | ||
150 | |||
151 | ret = snew(game_params); | ||
152 | *ret = towers_presets[i]; /* structure copy */ | ||
153 | |||
154 | sprintf(buf, "%dx%d %s", ret->w, ret->w, towers_diffnames[ret->diff]); | ||
155 | |||
156 | *name = dupstr(buf); | ||
157 | *params = ret; | ||
158 | return TRUE; | ||
159 | } | ||
160 | |||
161 | static void free_params(game_params *params) | ||
162 | { | ||
163 | sfree(params); | ||
164 | } | ||
165 | |||
166 | static game_params *dup_params(const game_params *params) | ||
167 | { | ||
168 | game_params *ret = snew(game_params); | ||
169 | *ret = *params; /* structure copy */ | ||
170 | return ret; | ||
171 | } | ||
172 | |||
173 | static void decode_params(game_params *params, char const *string) | ||
174 | { | ||
175 | char const *p = string; | ||
176 | |||
177 | params->w = atoi(p); | ||
178 | while (*p && isdigit((unsigned char)*p)) p++; | ||
179 | |||
180 | if (*p == 'd') { | ||
181 | int i; | ||
182 | p++; | ||
183 | params->diff = DIFFCOUNT+1; /* ...which is invalid */ | ||
184 | if (*p) { | ||
185 | for (i = 0; i < DIFFCOUNT; i++) { | ||
186 | if (*p == towers_diffchars[i]) | ||
187 | params->diff = i; | ||
188 | } | ||
189 | p++; | ||
190 | } | ||
191 | } | ||
192 | } | ||
193 | |||
194 | static char *encode_params(const game_params *params, int full) | ||
195 | { | ||
196 | char ret[80]; | ||
197 | |||
198 | sprintf(ret, "%d", params->w); | ||
199 | if (full) | ||
200 | sprintf(ret + strlen(ret), "d%c", towers_diffchars[params->diff]); | ||
201 | |||
202 | return dupstr(ret); | ||
203 | } | ||
204 | |||
205 | static config_item *game_configure(const game_params *params) | ||
206 | { | ||
207 | config_item *ret; | ||
208 | char buf[80]; | ||
209 | |||
210 | ret = snewn(3, config_item); | ||
211 | |||
212 | ret[0].name = "Grid size"; | ||
213 | ret[0].type = C_STRING; | ||
214 | sprintf(buf, "%d", params->w); | ||
215 | ret[0].sval = dupstr(buf); | ||
216 | ret[0].ival = 0; | ||
217 | |||
218 | ret[1].name = "Difficulty"; | ||
219 | ret[1].type = C_CHOICES; | ||
220 | ret[1].sval = DIFFCONFIG; | ||
221 | ret[1].ival = params->diff; | ||
222 | |||
223 | ret[2].name = NULL; | ||
224 | ret[2].type = C_END; | ||
225 | ret[2].sval = NULL; | ||
226 | ret[2].ival = 0; | ||
227 | |||
228 | return ret; | ||
229 | } | ||
230 | |||
231 | static game_params *custom_params(const config_item *cfg) | ||
232 | { | ||
233 | game_params *ret = snew(game_params); | ||
234 | |||
235 | ret->w = atoi(cfg[0].sval); | ||
236 | ret->diff = cfg[1].ival; | ||
237 | |||
238 | return ret; | ||
239 | } | ||
240 | |||
241 | static char *validate_params(const game_params *params, int full) | ||
242 | { | ||
243 | if (params->w < 3 || params->w > 9) | ||
244 | return "Grid size must be between 3 and 9"; | ||
245 | if (params->diff >= DIFFCOUNT) | ||
246 | return "Unknown difficulty rating"; | ||
247 | return NULL; | ||
248 | } | ||
249 | |||
250 | /* ---------------------------------------------------------------------- | ||
251 | * Solver. | ||
252 | */ | ||
253 | |||
254 | struct solver_ctx { | ||
255 | int w, diff; | ||
256 | int started; | ||
257 | int *clues; | ||
258 | long *iscratch; | ||
259 | int *dscratch; | ||
260 | }; | ||
261 | |||
262 | static int solver_easy(struct latin_solver *solver, void *vctx) | ||
263 | { | ||
264 | struct solver_ctx *ctx = (struct solver_ctx *)vctx; | ||
265 | int w = ctx->w; | ||
266 | int c, i, j, n, m, furthest; | ||
267 | int start, step, cstart, cstep, clue, pos, cpos; | ||
268 | int ret = 0; | ||
269 | #ifdef STANDALONE_SOLVER | ||
270 | char prefix[256]; | ||
271 | #endif | ||
272 | |||
273 | if (!ctx->started) { | ||
274 | ctx->started = TRUE; | ||
275 | /* | ||
276 | * One-off loop to help get started: when a pair of facing | ||
277 | * clues sum to w+1, it must mean that the row consists of | ||
278 | * two increasing sequences back to back, so we can | ||
279 | * immediately place the highest digit by knowing the | ||
280 | * lengths of those two sequences. | ||
281 | */ | ||
282 | for (c = 0; c < 3*w; c = (c == w-1 ? 2*w : c+1)) { | ||
283 | int c2 = c + w; | ||
284 | |||
285 | if (ctx->clues[c] && ctx->clues[c2] && | ||
286 | ctx->clues[c] + ctx->clues[c2] == w+1) { | ||
287 | STARTSTEP(start, step, c, w); | ||
288 | CSTARTSTEP(cstart, cstep, c, w); | ||
289 | pos = start + (ctx->clues[c]-1)*step; | ||
290 | cpos = cstart + (ctx->clues[c]-1)*cstep; | ||
291 | if (solver->cube[cpos*w+w-1]) { | ||
292 | #ifdef STANDALONE_SOLVER | ||
293 | if (solver_show_working) { | ||
294 | printf("%*sfacing clues on %s %d are maximal:\n", | ||
295 | solver_recurse_depth*4, "", | ||
296 | c>=2*w ? "row" : "column", c % w + 1); | ||
297 | printf("%*s placing %d at (%d,%d)\n", | ||
298 | solver_recurse_depth*4, "", | ||
299 | w, pos%w+1, pos/w+1); | ||
300 | } | ||
301 | #endif | ||
302 | latin_solver_place(solver, pos%w, pos/w, w); | ||
303 | ret = 1; | ||
304 | } else { | ||
305 | ret = -1; | ||
306 | } | ||
307 | } | ||
308 | } | ||
309 | |||
310 | if (ret) | ||
311 | return ret; | ||
312 | } | ||
313 | |||
314 | /* | ||
315 | * Go over every clue doing reasonably simple heuristic | ||
316 | * deductions. | ||
317 | */ | ||
318 | for (c = 0; c < 4*w; c++) { | ||
319 | clue = ctx->clues[c]; | ||
320 | if (!clue) | ||
321 | continue; | ||
322 | STARTSTEP(start, step, c, w); | ||
323 | CSTARTSTEP(cstart, cstep, c, w); | ||
324 | |||
325 | /* Find the location of each number in the row. */ | ||
326 | for (i = 0; i < w; i++) | ||
327 | ctx->dscratch[i] = w; | ||
328 | for (i = 0; i < w; i++) | ||
329 | if (solver->grid[start+i*step]) | ||
330 | ctx->dscratch[solver->grid[start+i*step]-1] = i; | ||
331 | |||
332 | n = m = 0; | ||
333 | furthest = w; | ||
334 | for (i = w; i >= 1; i--) { | ||
335 | if (ctx->dscratch[i-1] == w) { | ||
336 | break; | ||
337 | } else if (ctx->dscratch[i-1] < furthest) { | ||
338 | furthest = ctx->dscratch[i-1]; | ||
339 | m = i; | ||
340 | n++; | ||
341 | } | ||
342 | } | ||
343 | if (clue == n+1 && furthest > 1) { | ||
344 | #ifdef STANDALONE_SOLVER | ||
345 | if (solver_show_working) | ||
346 | sprintf(prefix, "%*sclue %s %d is nearly filled:\n", | ||
347 | solver_recurse_depth*4, "", | ||
348 | cluepos[c/w], c%w+1); | ||
349 | else | ||
350 | prefix[0] = '\0'; /* placate optimiser */ | ||
351 | #endif | ||
352 | /* | ||
353 | * We can already see an increasing sequence of the very | ||
354 | * highest numbers, of length one less than that | ||
355 | * specified in the clue. All of those numbers _must_ be | ||
356 | * part of the clue sequence, so the number right next | ||
357 | * to the clue must be the final one - i.e. it must be | ||
358 | * bigger than any of the numbers between it and m. This | ||
359 | * allows us to rule out small numbers in that square. | ||
360 | * | ||
361 | * (This is a generalisation of the obvious deduction | ||
362 | * that when you see a clue saying 1, it must be right | ||
363 | * next to the largest possible number; and similarly, | ||
364 | * when you see a clue saying 2 opposite that, it must | ||
365 | * be right next to the second-largest.) | ||
366 | */ | ||
367 | j = furthest-1; /* number of small numbers we can rule out */ | ||
368 | for (i = 1; i <= w && j > 0; i++) { | ||
369 | if (ctx->dscratch[i-1] < w && ctx->dscratch[i-1] >= furthest) | ||
370 | continue; /* skip this number, it's elsewhere */ | ||
371 | j--; | ||
372 | if (solver->cube[cstart*w+i-1]) { | ||
373 | #ifdef STANDALONE_SOLVER | ||
374 | if (solver_show_working) { | ||
375 | printf("%s%*s ruling out %d at (%d,%d)\n", | ||
376 | prefix, solver_recurse_depth*4, "", | ||
377 | i, start%w+1, start/w+1); | ||
378 | prefix[0] = '\0'; | ||
379 | } | ||
380 | #endif | ||
381 | solver->cube[cstart*w+i-1] = 0; | ||
382 | ret = 1; | ||
383 | } | ||
384 | } | ||
385 | } | ||
386 | |||
387 | if (ret) | ||
388 | return ret; | ||
389 | |||
390 | #ifdef STANDALONE_SOLVER | ||
391 | if (solver_show_working) | ||
392 | sprintf(prefix, "%*slower bounds for clue %s %d:\n", | ||
393 | solver_recurse_depth*4, "", | ||
394 | cluepos[c/w], c%w+1); | ||
395 | else | ||
396 | prefix[0] = '\0'; /* placate optimiser */ | ||
397 | #endif | ||
398 | |||
399 | i = 0; | ||
400 | for (n = w; n > 0; n--) { | ||
401 | /* | ||
402 | * The largest number cannot occur in the first (clue-1) | ||
403 | * squares of the row, or else there wouldn't be space | ||
404 | * for a sufficiently long increasing sequence which it | ||
405 | * terminated. The second-largest number (not counting | ||
406 | * any that are known to be on the far side of a larger | ||
407 | * number and hence excluded from this sequence) cannot | ||
408 | * occur in the first (clue-2) squares, similarly, and | ||
409 | * so on. | ||
410 | */ | ||
411 | |||
412 | if (ctx->dscratch[n-1] < w) { | ||
413 | for (m = n+1; m < w; m++) | ||
414 | if (ctx->dscratch[m] < ctx->dscratch[n-1]) | ||
415 | break; | ||
416 | if (m < w) | ||
417 | continue; /* this number doesn't count */ | ||
418 | } | ||
419 | |||
420 | for (j = 0; j < clue - i - 1; j++) | ||
421 | if (solver->cube[(cstart + j*cstep)*w+n-1]) { | ||
422 | #ifdef STANDALONE_SOLVER | ||
423 | if (solver_show_working) { | ||
424 | int pos = start+j*step; | ||
425 | printf("%s%*s ruling out %d at (%d,%d)\n", | ||
426 | prefix, solver_recurse_depth*4, "", | ||
427 | n, pos%w+1, pos/w+1); | ||
428 | prefix[0] = '\0'; | ||
429 | } | ||
430 | #endif | ||
431 | solver->cube[(cstart + j*cstep)*w+n-1] = 0; | ||
432 | ret = 1; | ||
433 | } | ||
434 | i++; | ||
435 | } | ||
436 | } | ||
437 | |||
438 | if (ret) | ||
439 | return ret; | ||
440 | |||
441 | return 0; | ||
442 | } | ||
443 | |||
444 | static int solver_hard(struct latin_solver *solver, void *vctx) | ||
445 | { | ||
446 | struct solver_ctx *ctx = (struct solver_ctx *)vctx; | ||
447 | int w = ctx->w; | ||
448 | int c, i, j, n, best, clue, start, step, ret; | ||
449 | long bitmap; | ||
450 | #ifdef STANDALONE_SOLVER | ||
451 | char prefix[256]; | ||
452 | #endif | ||
453 | |||
454 | /* | ||
455 | * Go over every clue analysing all possibilities. | ||
456 | */ | ||
457 | for (c = 0; c < 4*w; c++) { | ||
458 | clue = ctx->clues[c]; | ||
459 | if (!clue) | ||
460 | continue; | ||
461 | CSTARTSTEP(start, step, c, w); | ||
462 | |||
463 | for (i = 0; i < w; i++) | ||
464 | ctx->iscratch[i] = 0; | ||
465 | |||
466 | /* | ||
467 | * Instead of a tedious physical recursion, I iterate in the | ||
468 | * scratch array through all possibilities. At any given | ||
469 | * moment, i indexes the element of the box that will next | ||
470 | * be incremented. | ||
471 | */ | ||
472 | i = 0; | ||
473 | ctx->dscratch[i] = 0; | ||
474 | best = n = 0; | ||
475 | bitmap = 0; | ||
476 | |||
477 | while (1) { | ||
478 | if (i < w) { | ||
479 | /* | ||
480 | * Find the next valid value for cell i. | ||
481 | */ | ||
482 | int limit = (n == clue ? best : w); | ||
483 | int pos = start + step * i; | ||
484 | for (j = ctx->dscratch[i] + 1; j <= limit; j++) { | ||
485 | if (bitmap & (1L << j)) | ||
486 | continue; /* used this one already */ | ||
487 | if (!solver->cube[pos*w+j-1]) | ||
488 | continue; /* ruled out already */ | ||
489 | |||
490 | /* Found one. */ | ||
491 | break; | ||
492 | } | ||
493 | |||
494 | if (j > limit) { | ||
495 | /* No valid values left; drop back. */ | ||
496 | i--; | ||
497 | if (i < 0) | ||
498 | break; /* overall iteration is finished */ | ||
499 | bitmap &= ~(1L << ctx->dscratch[i]); | ||
500 | if (ctx->dscratch[i] == best) { | ||
501 | n--; | ||
502 | best = 0; | ||
503 | for (j = 0; j < i; j++) | ||
504 | if (best < ctx->dscratch[j]) | ||
505 | best = ctx->dscratch[j]; | ||
506 | } | ||
507 | } else { | ||
508 | /* Got a valid value; store it and move on. */ | ||
509 | bitmap |= 1L << j; | ||
510 | ctx->dscratch[i++] = j; | ||
511 | if (j > best) { | ||
512 | best = j; | ||
513 | n++; | ||
514 | } | ||
515 | ctx->dscratch[i] = 0; | ||
516 | } | ||
517 | } else { | ||
518 | if (n == clue) { | ||
519 | for (j = 0; j < w; j++) | ||
520 | ctx->iscratch[j] |= 1L << ctx->dscratch[j]; | ||
521 | } | ||
522 | i--; | ||
523 | bitmap &= ~(1L << ctx->dscratch[i]); | ||
524 | if (ctx->dscratch[i] == best) { | ||
525 | n--; | ||
526 | best = 0; | ||
527 | for (j = 0; j < i; j++) | ||
528 | if (best < ctx->dscratch[j]) | ||
529 | best = ctx->dscratch[j]; | ||
530 | } | ||
531 | } | ||
532 | } | ||
533 | |||
534 | #ifdef STANDALONE_SOLVER | ||
535 | if (solver_show_working) | ||
536 | sprintf(prefix, "%*sexhaustive analysis of clue %s %d:\n", | ||
537 | solver_recurse_depth*4, "", | ||
538 | cluepos[c/w], c%w+1); | ||
539 | else | ||
540 | prefix[0] = '\0'; /* placate optimiser */ | ||
541 | #endif | ||
542 | |||
543 | ret = 0; | ||
544 | |||
545 | for (i = 0; i < w; i++) { | ||
546 | int pos = start + step * i; | ||
547 | for (j = 1; j <= w; j++) { | ||
548 | if (solver->cube[pos*w+j-1] && | ||
549 | !(ctx->iscratch[i] & (1L << j))) { | ||
550 | #ifdef STANDALONE_SOLVER | ||
551 | if (solver_show_working) { | ||
552 | printf("%s%*s ruling out %d at (%d,%d)\n", | ||
553 | prefix, solver_recurse_depth*4, "", | ||
554 | j, pos/w+1, pos%w+1); | ||
555 | prefix[0] = '\0'; | ||
556 | } | ||
557 | #endif | ||
558 | solver->cube[pos*w+j-1] = 0; | ||
559 | ret = 1; | ||
560 | } | ||
561 | } | ||
562 | |||
563 | /* | ||
564 | * Once we find one clue we can do something with in | ||
565 | * this way, revert to trying easier deductions, so as | ||
566 | * not to generate solver diagnostics that make the | ||
567 | * problem look harder than it is. | ||
568 | */ | ||
569 | if (ret) | ||
570 | return ret; | ||
571 | } | ||
572 | } | ||
573 | |||
574 | return 0; | ||
575 | } | ||
576 | |||
577 | #define SOLVER(upper,title,func,lower) func, | ||
578 | static usersolver_t const towers_solvers[] = { DIFFLIST(SOLVER) }; | ||
579 | |||
580 | static int solver(int w, int *clues, digit *soln, int maxdiff) | ||
581 | { | ||
582 | int ret; | ||
583 | struct solver_ctx ctx; | ||
584 | |||
585 | ctx.w = w; | ||
586 | ctx.diff = maxdiff; | ||
587 | ctx.clues = clues; | ||
588 | ctx.started = FALSE; | ||
589 | ctx.iscratch = snewn(w, long); | ||
590 | ctx.dscratch = snewn(w+1, int); | ||
591 | |||
592 | ret = latin_solver(soln, w, maxdiff, | ||
593 | DIFF_EASY, DIFF_HARD, DIFF_EXTREME, | ||
594 | DIFF_EXTREME, DIFF_UNREASONABLE, | ||
595 | towers_solvers, &ctx, NULL, NULL); | ||
596 | |||
597 | sfree(ctx.iscratch); | ||
598 | sfree(ctx.dscratch); | ||
599 | |||
600 | return ret; | ||
601 | } | ||
602 | |||
603 | /* ---------------------------------------------------------------------- | ||
604 | * Grid generation. | ||
605 | */ | ||
606 | |||
607 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
608 | char **aux, int interactive) | ||
609 | { | ||
610 | int w = params->w, a = w*w; | ||
611 | digit *grid, *soln, *soln2; | ||
612 | int *clues, *order; | ||
613 | int i, ret; | ||
614 | int diff = params->diff; | ||
615 | char *desc, *p; | ||
616 | |||
617 | /* | ||
618 | * Difficulty exceptions: some combinations of size and | ||
619 | * difficulty cannot be satisfied, because all puzzles of at | ||
620 | * most that difficulty are actually even easier. | ||
621 | * | ||
622 | * Remember to re-test this whenever a change is made to the | ||
623 | * solver logic! | ||
624 | * | ||
625 | * I tested it using the following shell command: | ||
626 | |||
627 | for d in e h x u; do | ||
628 | for i in {3..9}; do | ||
629 | echo -n "./towers --generate 1 ${i}d${d}: " | ||
630 | perl -e 'alarm 30; exec @ARGV' ./towers --generate 1 ${i}d${d} >/dev/null \ | ||
631 | && echo ok | ||
632 | done | ||
633 | done | ||
634 | |||
635 | * Of course, it's better to do that after taking the exceptions | ||
636 | * _out_, so as to detect exceptions that should be removed as | ||
637 | * well as those which should be added. | ||
638 | */ | ||
639 | if (diff > DIFF_HARD && w <= 3) | ||
640 | diff = DIFF_HARD; | ||
641 | |||
642 | grid = NULL; | ||
643 | clues = snewn(4*w, int); | ||
644 | soln = snewn(a, digit); | ||
645 | soln2 = snewn(a, digit); | ||
646 | order = snewn(max(4*w,a), int); | ||
647 | |||
648 | while (1) { | ||
649 | /* | ||
650 | * Construct a latin square to be the solution. | ||
651 | */ | ||
652 | sfree(grid); | ||
653 | grid = latin_generate(w, rs); | ||
654 | |||
655 | /* | ||
656 | * Fill in the clues. | ||
657 | */ | ||
658 | for (i = 0; i < 4*w; i++) { | ||
659 | int start, step, j, k, best; | ||
660 | STARTSTEP(start, step, i, w); | ||
661 | k = best = 0; | ||
662 | for (j = 0; j < w; j++) { | ||
663 | if (grid[start+j*step] > best) { | ||
664 | best = grid[start+j*step]; | ||
665 | k++; | ||
666 | } | ||
667 | } | ||
668 | clues[i] = k; | ||
669 | } | ||
670 | |||
671 | /* | ||
672 | * Remove the grid numbers and then the clues, one by one, | ||
673 | * for as long as the game remains soluble at the given | ||
674 | * difficulty. | ||
675 | */ | ||
676 | memcpy(soln, grid, a); | ||
677 | |||
678 | if (diff == DIFF_EASY && w <= 5) { | ||
679 | /* | ||
680 | * Special case: for Easy-mode grids that are small | ||
681 | * enough, it's nice to be able to find completely empty | ||
682 | * grids. | ||
683 | */ | ||
684 | memset(soln2, 0, a); | ||
685 | ret = solver(w, clues, soln2, diff); | ||
686 | if (ret > diff) | ||
687 | continue; | ||
688 | } | ||
689 | |||
690 | for (i = 0; i < a; i++) | ||
691 | order[i] = i; | ||
692 | shuffle(order, a, sizeof(*order), rs); | ||
693 | for (i = 0; i < a; i++) { | ||
694 | int j = order[i]; | ||
695 | |||
696 | memcpy(soln2, grid, a); | ||
697 | soln2[j] = 0; | ||
698 | ret = solver(w, clues, soln2, diff); | ||
699 | if (ret <= diff) | ||
700 | grid[j] = 0; | ||
701 | } | ||
702 | |||
703 | if (diff > DIFF_EASY) { /* leave all clues on Easy mode */ | ||
704 | for (i = 0; i < 4*w; i++) | ||
705 | order[i] = i; | ||
706 | shuffle(order, 4*w, sizeof(*order), rs); | ||
707 | for (i = 0; i < 4*w; i++) { | ||
708 | int j = order[i]; | ||
709 | int clue = clues[j]; | ||
710 | |||
711 | memcpy(soln2, grid, a); | ||
712 | clues[j] = 0; | ||
713 | ret = solver(w, clues, soln2, diff); | ||
714 | if (ret > diff) | ||
715 | clues[j] = clue; | ||
716 | } | ||
717 | } | ||
718 | |||
719 | /* | ||
720 | * See if the game can be solved at the specified difficulty | ||
721 | * level, but not at the one below. | ||
722 | */ | ||
723 | memcpy(soln2, grid, a); | ||
724 | ret = solver(w, clues, soln2, diff); | ||
725 | if (ret != diff) | ||
726 | continue; /* go round again */ | ||
727 | |||
728 | /* | ||
729 | * We've got a usable puzzle! | ||
730 | */ | ||
731 | break; | ||
732 | } | ||
733 | |||
734 | /* | ||
735 | * Encode the puzzle description. | ||
736 | */ | ||
737 | desc = snewn(40*a, char); | ||
738 | p = desc; | ||
739 | for (i = 0; i < 4*w; i++) { | ||
740 | if (i) | ||
741 | *p++ = '/'; | ||
742 | if (clues[i]) | ||
743 | p += sprintf(p, "%d", clues[i]); | ||
744 | } | ||
745 | for (i = 0; i < a; i++) | ||
746 | if (grid[i]) | ||
747 | break; | ||
748 | if (i < a) { | ||
749 | int run = 0; | ||
750 | |||
751 | *p++ = ','; | ||
752 | |||
753 | for (i = 0; i <= a; i++) { | ||
754 | int n = (i < a ? grid[i] : -1); | ||
755 | |||
756 | if (!n) | ||
757 | run++; | ||
758 | else { | ||
759 | if (run) { | ||
760 | while (run > 0) { | ||
761 | int thisrun = min(run, 26); | ||
762 | *p++ = thisrun - 1 + 'a'; | ||
763 | run -= thisrun; | ||
764 | } | ||
765 | } else { | ||
766 | /* | ||
767 | * If there's a number in the very top left or | ||
768 | * bottom right, there's no point putting an | ||
769 | * unnecessary _ before or after it. | ||
770 | */ | ||
771 | if (i > 0 && n > 0) | ||
772 | *p++ = '_'; | ||
773 | } | ||
774 | if (n > 0) | ||
775 | p += sprintf(p, "%d", n); | ||
776 | run = 0; | ||
777 | } | ||
778 | } | ||
779 | } | ||
780 | *p++ = '\0'; | ||
781 | desc = sresize(desc, p - desc, char); | ||
782 | |||
783 | /* | ||
784 | * Encode the solution. | ||
785 | */ | ||
786 | *aux = snewn(a+2, char); | ||
787 | (*aux)[0] = 'S'; | ||
788 | for (i = 0; i < a; i++) | ||
789 | (*aux)[i+1] = '0' + soln[i]; | ||
790 | (*aux)[a+1] = '\0'; | ||
791 | |||
792 | sfree(grid); | ||
793 | sfree(clues); | ||
794 | sfree(soln); | ||
795 | sfree(soln2); | ||
796 | sfree(order); | ||
797 | |||
798 | return desc; | ||
799 | } | ||
800 | |||
801 | /* ---------------------------------------------------------------------- | ||
802 | * Gameplay. | ||
803 | */ | ||
804 | |||
805 | static char *validate_desc(const game_params *params, const char *desc) | ||
806 | { | ||
807 | int w = params->w, a = w*w; | ||
808 | const char *p = desc; | ||
809 | int i, clue; | ||
810 | |||
811 | /* | ||
812 | * Verify that the right number of clues are given, and that | ||
813 | * they're in range. | ||
814 | */ | ||
815 | for (i = 0; i < 4*w; i++) { | ||
816 | if (!*p) | ||
817 | return "Too few clues for grid size"; | ||
818 | |||
819 | if (i > 0) { | ||
820 | if (*p != '/') | ||
821 | return "Expected commas between clues"; | ||
822 | p++; | ||
823 | } | ||
824 | |||
825 | if (isdigit((unsigned char)*p)) { | ||
826 | clue = atoi(p); | ||
827 | while (*p && isdigit((unsigned char)*p)) p++; | ||
828 | |||
829 | if (clue <= 0 || clue > w) | ||
830 | return "Clue number out of range"; | ||
831 | } | ||
832 | } | ||
833 | if (*p == '/') | ||
834 | return "Too many clues for grid size"; | ||
835 | |||
836 | if (*p == ',') { | ||
837 | /* | ||
838 | * Verify that the right amount of grid data is given, and | ||
839 | * that any grid elements provided are in range. | ||
840 | */ | ||
841 | int squares = 0; | ||
842 | |||
843 | p++; | ||
844 | while (*p) { | ||
845 | int c = *p++; | ||
846 | if (c >= 'a' && c <= 'z') { | ||
847 | squares += c - 'a' + 1; | ||
848 | } else if (c == '_') { | ||
849 | /* do nothing */; | ||
850 | } else if (c > '0' && c <= '9') { | ||
851 | int val = atoi(p-1); | ||
852 | if (val < 1 || val > w) | ||
853 | return "Out-of-range number in grid description"; | ||
854 | squares++; | ||
855 | while (*p && isdigit((unsigned char)*p)) p++; | ||
856 | } else | ||
857 | return "Invalid character in game description"; | ||
858 | } | ||
859 | |||
860 | if (squares < a) | ||
861 | return "Not enough data to fill grid"; | ||
862 | |||
863 | if (squares > a) | ||
864 | return "Too much data to fit in grid"; | ||
865 | } | ||
866 | |||
867 | return NULL; | ||
868 | } | ||
869 | |||
870 | static game_state *new_game(midend *me, const game_params *params, | ||
871 | const char *desc) | ||
872 | { | ||
873 | int w = params->w, a = w*w; | ||
874 | game_state *state = snew(game_state); | ||
875 | const char *p = desc; | ||
876 | int i; | ||
877 | |||
878 | state->par = *params; /* structure copy */ | ||
879 | state->clues = snew(struct clues); | ||
880 | state->clues->refcount = 1; | ||
881 | state->clues->w = w; | ||
882 | state->clues->clues = snewn(4*w, int); | ||
883 | state->clues->immutable = snewn(a, digit); | ||
884 | state->grid = snewn(a, digit); | ||
885 | state->clues_done = snewn(4*w, unsigned char); | ||
886 | state->pencil = snewn(a, int); | ||
887 | |||
888 | for (i = 0; i < a; i++) { | ||
889 | state->grid[i] = 0; | ||
890 | state->pencil[i] = 0; | ||
891 | } | ||
892 | |||
893 | memset(state->clues->immutable, 0, a); | ||
894 | memset(state->clues_done, 0, 4*w*sizeof(unsigned char)); | ||
895 | |||
896 | for (i = 0; i < 4*w; i++) { | ||
897 | if (i > 0) { | ||
898 | assert(*p == '/'); | ||
899 | p++; | ||
900 | } | ||
901 | if (*p && isdigit((unsigned char)*p)) { | ||
902 | state->clues->clues[i] = atoi(p); | ||
903 | while (*p && isdigit((unsigned char)*p)) p++; | ||
904 | } else | ||
905 | state->clues->clues[i] = 0; | ||
906 | } | ||
907 | |||
908 | if (*p == ',') { | ||
909 | int pos = 0; | ||
910 | p++; | ||
911 | while (*p) { | ||
912 | int c = *p++; | ||
913 | if (c >= 'a' && c <= 'z') { | ||
914 | pos += c - 'a' + 1; | ||
915 | } else if (c == '_') { | ||
916 | /* do nothing */; | ||
917 | } else if (c > '0' && c <= '9') { | ||
918 | int val = atoi(p-1); | ||
919 | assert(val >= 1 && val <= w); | ||
920 | assert(pos < a); | ||
921 | state->grid[pos] = state->clues->immutable[pos] = val; | ||
922 | pos++; | ||
923 | while (*p && isdigit((unsigned char)*p)) p++; | ||
924 | } else | ||
925 | assert(!"Corrupt game description"); | ||
926 | } | ||
927 | assert(pos == a); | ||
928 | } | ||
929 | assert(!*p); | ||
930 | |||
931 | state->completed = state->cheated = FALSE; | ||
932 | |||
933 | return state; | ||
934 | } | ||
935 | |||
936 | static game_state *dup_game(const game_state *state) | ||
937 | { | ||
938 | int w = state->par.w, a = w*w; | ||
939 | game_state *ret = snew(game_state); | ||
940 | |||
941 | ret->par = state->par; /* structure copy */ | ||
942 | |||
943 | ret->clues = state->clues; | ||
944 | ret->clues->refcount++; | ||
945 | |||
946 | ret->grid = snewn(a, digit); | ||
947 | ret->pencil = snewn(a, int); | ||
948 | ret->clues_done = snewn(4*w, unsigned char); | ||
949 | memcpy(ret->grid, state->grid, a*sizeof(digit)); | ||
950 | memcpy(ret->pencil, state->pencil, a*sizeof(int)); | ||
951 | memcpy(ret->clues_done, state->clues_done, 4*w*sizeof(unsigned char)); | ||
952 | |||
953 | ret->completed = state->completed; | ||
954 | ret->cheated = state->cheated; | ||
955 | |||
956 | return ret; | ||
957 | } | ||
958 | |||
959 | static void free_game(game_state *state) | ||
960 | { | ||
961 | sfree(state->grid); | ||
962 | sfree(state->pencil); | ||
963 | sfree(state->clues_done); | ||
964 | if (--state->clues->refcount <= 0) { | ||
965 | sfree(state->clues->immutable); | ||
966 | sfree(state->clues->clues); | ||
967 | sfree(state->clues); | ||
968 | } | ||
969 | sfree(state); | ||
970 | } | ||
971 | |||
972 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
973 | const char *aux, char **error) | ||
974 | { | ||
975 | int w = state->par.w, a = w*w; | ||
976 | int i, ret; | ||
977 | digit *soln; | ||
978 | char *out; | ||
979 | |||
980 | if (aux) | ||
981 | return dupstr(aux); | ||
982 | |||
983 | soln = snewn(a, digit); | ||
984 | memcpy(soln, state->clues->immutable, a); | ||
985 | |||
986 | ret = solver(w, state->clues->clues, soln, DIFFCOUNT-1); | ||
987 | |||
988 | if (ret == diff_impossible) { | ||
989 | *error = "No solution exists for this puzzle"; | ||
990 | out = NULL; | ||
991 | } else if (ret == diff_ambiguous) { | ||
992 | *error = "Multiple solutions exist for this puzzle"; | ||
993 | out = NULL; | ||
994 | } else { | ||
995 | out = snewn(a+2, char); | ||
996 | out[0] = 'S'; | ||
997 | for (i = 0; i < a; i++) | ||
998 | out[i+1] = '0' + soln[i]; | ||
999 | out[a+1] = '\0'; | ||
1000 | } | ||
1001 | |||
1002 | sfree(soln); | ||
1003 | return out; | ||
1004 | } | ||
1005 | |||
1006 | static int game_can_format_as_text_now(const game_params *params) | ||
1007 | { | ||
1008 | return TRUE; | ||
1009 | } | ||
1010 | |||
1011 | static char *game_text_format(const game_state *state) | ||
1012 | { | ||
1013 | int w = state->par.w /* , a = w*w */; | ||
1014 | char *ret; | ||
1015 | char *p; | ||
1016 | int x, y; | ||
1017 | int total; | ||
1018 | |||
1019 | /* | ||
1020 | * We have: | ||
1021 | * - a top clue row, consisting of three spaces, then w clue | ||
1022 | * digits with spaces between (total 2*w+3 chars including | ||
1023 | * newline) | ||
1024 | * - a blank line (one newline) | ||
1025 | * - w main rows, consisting of a left clue digit, two spaces, | ||
1026 | * w grid digits with spaces between, two spaces and a right | ||
1027 | * clue digit (total 2*w+6 chars each including newline) | ||
1028 | * - a blank line (one newline) | ||
1029 | * - a bottom clue row (same as top clue row) | ||
1030 | * - terminating NUL. | ||
1031 | * | ||
1032 | * Total size is therefore 2*(2*w+3) + 2 + w*(2*w+6) + 1 | ||
1033 | * = 2w^2+10w+9. | ||
1034 | */ | ||
1035 | total = 2*w*w + 10*w + 9; | ||
1036 | ret = snewn(total, char); | ||
1037 | p = ret; | ||
1038 | |||
1039 | /* Top clue row. */ | ||
1040 | *p++ = ' '; *p++ = ' '; | ||
1041 | for (x = 0; x < w; x++) { | ||
1042 | *p++ = ' '; | ||
1043 | *p++ = (state->clues->clues[x] ? '0' + state->clues->clues[x] : ' '); | ||
1044 | } | ||
1045 | *p++ = '\n'; | ||
1046 | |||
1047 | /* Blank line. */ | ||
1048 | *p++ = '\n'; | ||
1049 | |||
1050 | /* Main grid. */ | ||
1051 | for (y = 0; y < w; y++) { | ||
1052 | *p++ = (state->clues->clues[y+2*w] ? '0' + state->clues->clues[y+2*w] : | ||
1053 | ' '); | ||
1054 | *p++ = ' '; | ||
1055 | for (x = 0; x < w; x++) { | ||
1056 | *p++ = ' '; | ||
1057 | *p++ = (state->grid[y*w+x] ? '0' + state->grid[y*w+x] : ' '); | ||
1058 | } | ||
1059 | *p++ = ' '; *p++ = ' '; | ||
1060 | *p++ = (state->clues->clues[y+3*w] ? '0' + state->clues->clues[y+3*w] : | ||
1061 | ' '); | ||
1062 | *p++ = '\n'; | ||
1063 | } | ||
1064 | |||
1065 | /* Blank line. */ | ||
1066 | *p++ = '\n'; | ||
1067 | |||
1068 | /* Bottom clue row. */ | ||
1069 | *p++ = ' '; *p++ = ' '; | ||
1070 | for (x = 0; x < w; x++) { | ||
1071 | *p++ = ' '; | ||
1072 | *p++ = (state->clues->clues[x+w] ? '0' + state->clues->clues[x+w] : | ||
1073 | ' '); | ||
1074 | } | ||
1075 | *p++ = '\n'; | ||
1076 | |||
1077 | *p++ = '\0'; | ||
1078 | assert(p == ret + total); | ||
1079 | |||
1080 | return ret; | ||
1081 | } | ||
1082 | |||
1083 | struct game_ui { | ||
1084 | /* | ||
1085 | * These are the coordinates of the currently highlighted | ||
1086 | * square on the grid, if hshow = 1. | ||
1087 | */ | ||
1088 | int hx, hy; | ||
1089 | /* | ||
1090 | * This indicates whether the current highlight is a | ||
1091 | * pencil-mark one or a real one. | ||
1092 | */ | ||
1093 | int hpencil; | ||
1094 | /* | ||
1095 | * This indicates whether or not we're showing the highlight | ||
1096 | * (used to be hx = hy = -1); important so that when we're | ||
1097 | * using the cursor keys it doesn't keep coming back at a | ||
1098 | * fixed position. When hshow = 1, pressing a valid number | ||
1099 | * or letter key or Space will enter that number or letter in the grid. | ||
1100 | */ | ||
1101 | int hshow; | ||
1102 | /* | ||
1103 | * This indicates whether we're using the highlight as a cursor; | ||
1104 | * it means that it doesn't vanish on a keypress, and that it is | ||
1105 | * allowed on immutable squares. | ||
1106 | */ | ||
1107 | int hcursor; | ||
1108 | }; | ||
1109 | |||
1110 | static game_ui *new_ui(const game_state *state) | ||
1111 | { | ||
1112 | game_ui *ui = snew(game_ui); | ||
1113 | |||
1114 | ui->hx = ui->hy = 0; | ||
1115 | ui->hpencil = ui->hshow = ui->hcursor = 0; | ||
1116 | |||
1117 | return ui; | ||
1118 | } | ||
1119 | |||
1120 | static void free_ui(game_ui *ui) | ||
1121 | { | ||
1122 | sfree(ui); | ||
1123 | } | ||
1124 | |||
1125 | static char *encode_ui(const game_ui *ui) | ||
1126 | { | ||
1127 | return NULL; | ||
1128 | } | ||
1129 | |||
1130 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1131 | { | ||
1132 | } | ||
1133 | |||
1134 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1135 | const game_state *newstate) | ||
1136 | { | ||
1137 | int w = newstate->par.w; | ||
1138 | /* | ||
1139 | * We prevent pencil-mode highlighting of a filled square, unless | ||
1140 | * we're using the cursor keys. So if the user has just filled in | ||
1141 | * a square which we had a pencil-mode highlight in (by Undo, or | ||
1142 | * by Redo, or by Solve), then we cancel the highlight. | ||
1143 | */ | ||
1144 | if (ui->hshow && ui->hpencil && !ui->hcursor && | ||
1145 | newstate->grid[ui->hy * w + ui->hx] != 0) { | ||
1146 | ui->hshow = 0; | ||
1147 | } | ||
1148 | } | ||
1149 | |||
1150 | #define PREFERRED_TILESIZE 48 | ||
1151 | #define TILESIZE (ds->tilesize) | ||
1152 | #define BORDER (TILESIZE * 9 / 8) | ||
1153 | #define COORD(x) ((x)*TILESIZE + BORDER) | ||
1154 | #define FROMCOORD(x) (((x)+(TILESIZE-BORDER)) / TILESIZE - 1) | ||
1155 | |||
1156 | /* These always return positive values, though y offsets are actually -ve */ | ||
1157 | #define X_3D_DISP(height, w) ((height) * TILESIZE / (8 * (w))) | ||
1158 | #define Y_3D_DISP(height, w) ((height) * TILESIZE / (4 * (w))) | ||
1159 | |||
1160 | #define FLASH_TIME 0.4F | ||
1161 | |||
1162 | #define DF_PENCIL_SHIFT 16 | ||
1163 | #define DF_CLUE_DONE 0x10000 | ||
1164 | #define DF_ERROR 0x8000 | ||
1165 | #define DF_HIGHLIGHT 0x4000 | ||
1166 | #define DF_HIGHLIGHT_PENCIL 0x2000 | ||
1167 | #define DF_IMMUTABLE 0x1000 | ||
1168 | #define DF_PLAYAREA 0x0800 | ||
1169 | #define DF_DIGIT_MASK 0x00FF | ||
1170 | |||
1171 | struct game_drawstate { | ||
1172 | int tilesize; | ||
1173 | int three_d; /* default 3D graphics are user-disableable */ | ||
1174 | int started; | ||
1175 | long *tiles; /* (w+2)*(w+2) temp space */ | ||
1176 | long *drawn; /* (w+2)*(w+2)*4: current drawn data */ | ||
1177 | int *errtmp; | ||
1178 | }; | ||
1179 | |||
1180 | static int check_errors(const game_state *state, int *errors) | ||
1181 | { | ||
1182 | int w = state->par.w /*, a = w*w */; | ||
1183 | int W = w+2, A = W*W; /* the errors array is (w+2) square */ | ||
1184 | int *clues = state->clues->clues; | ||
1185 | digit *grid = state->grid; | ||
1186 | int i, x, y, errs = FALSE; | ||
1187 | int tmp[32]; | ||
1188 | |||
1189 | assert(w < lenof(tmp)); | ||
1190 | |||
1191 | if (errors) | ||
1192 | for (i = 0; i < A; i++) | ||
1193 | errors[i] = 0; | ||
1194 | |||
1195 | for (y = 0; y < w; y++) { | ||
1196 | unsigned long mask = 0, errmask = 0; | ||
1197 | for (x = 0; x < w; x++) { | ||
1198 | unsigned long bit = 1UL << grid[y*w+x]; | ||
1199 | errmask |= (mask & bit); | ||
1200 | mask |= bit; | ||
1201 | } | ||
1202 | |||
1203 | if (mask != (1L << (w+1)) - (1L << 1)) { | ||
1204 | errs = TRUE; | ||
1205 | errmask &= ~1UL; | ||
1206 | if (errors) { | ||
1207 | for (x = 0; x < w; x++) | ||
1208 | if (errmask & (1UL << grid[y*w+x])) | ||
1209 | errors[(y+1)*W+(x+1)] = TRUE; | ||
1210 | } | ||
1211 | } | ||
1212 | } | ||
1213 | |||
1214 | for (x = 0; x < w; x++) { | ||
1215 | unsigned long mask = 0, errmask = 0; | ||
1216 | for (y = 0; y < w; y++) { | ||
1217 | unsigned long bit = 1UL << grid[y*w+x]; | ||
1218 | errmask |= (mask & bit); | ||
1219 | mask |= bit; | ||
1220 | } | ||
1221 | |||
1222 | if (mask != (1 << (w+1)) - (1 << 1)) { | ||
1223 | errs = TRUE; | ||
1224 | errmask &= ~1UL; | ||
1225 | if (errors) { | ||
1226 | for (y = 0; y < w; y++) | ||
1227 | if (errmask & (1UL << grid[y*w+x])) | ||
1228 | errors[(y+1)*W+(x+1)] = TRUE; | ||
1229 | } | ||
1230 | } | ||
1231 | } | ||
1232 | |||
1233 | for (i = 0; i < 4*w; i++) { | ||
1234 | int start, step, j, n, best; | ||
1235 | STARTSTEP(start, step, i, w); | ||
1236 | |||
1237 | if (!clues[i]) | ||
1238 | continue; | ||
1239 | |||
1240 | best = n = 0; | ||
1241 | for (j = 0; j < w; j++) { | ||
1242 | int number = grid[start+j*step]; | ||
1243 | if (!number) | ||
1244 | break; /* can't tell what happens next */ | ||
1245 | if (number > best) { | ||
1246 | best = number; | ||
1247 | n++; | ||
1248 | } | ||
1249 | } | ||
1250 | |||
1251 | if (n > clues[i] || (best == w && n < clues[i]) || | ||
1252 | (best < w && n == clues[i])) { | ||
1253 | if (errors) { | ||
1254 | int x, y; | ||
1255 | CLUEPOS(x, y, i, w); | ||
1256 | errors[(y+1)*W+(x+1)] = TRUE; | ||
1257 | } | ||
1258 | errs = TRUE; | ||
1259 | } | ||
1260 | } | ||
1261 | |||
1262 | return errs; | ||
1263 | } | ||
1264 | |||
1265 | static int clue_index(const game_state *state, int x, int y) | ||
1266 | { | ||
1267 | int w = state->par.w; | ||
1268 | |||
1269 | if (x == -1 || x == w) | ||
1270 | return w * (x == -1 ? 2 : 3) + y; | ||
1271 | else if (y == -1 || y == w) | ||
1272 | return (y == -1 ? 0 : w) + x; | ||
1273 | |||
1274 | return -1; | ||
1275 | } | ||
1276 | |||
1277 | static int is_clue(const game_state *state, int x, int y) | ||
1278 | { | ||
1279 | int w = state->par.w; | ||
1280 | |||
1281 | if (((x == -1 || x == w) && y >= 0 && y < w) || | ||
1282 | ((y == -1 || y == w) && x >= 0 && x < w)) | ||
1283 | { | ||
1284 | if (state->clues->clues[clue_index(state, x, y)] & DF_DIGIT_MASK) | ||
1285 | return TRUE; | ||
1286 | } | ||
1287 | |||
1288 | return FALSE; | ||
1289 | } | ||
1290 | |||
1291 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1292 | const game_drawstate *ds, | ||
1293 | int x, int y, int button) | ||
1294 | { | ||
1295 | int w = state->par.w; | ||
1296 | int shift_or_control = button & (MOD_SHFT | MOD_CTRL); | ||
1297 | int tx, ty; | ||
1298 | char buf[80]; | ||
1299 | |||
1300 | button &= ~MOD_MASK; | ||
1301 | |||
1302 | tx = FROMCOORD(x); | ||
1303 | ty = FROMCOORD(y); | ||
1304 | |||
1305 | if (ds->three_d) { | ||
1306 | /* | ||
1307 | * In 3D mode, just locating the mouse click in the natural | ||
1308 | * square grid may not be sufficient to tell which tower the | ||
1309 | * user clicked on. Investigate the _tops_ of the nearby | ||
1310 | * towers to see if a click on one grid square was actually | ||
1311 | * a click on a tower protruding into that region from | ||
1312 | * another. | ||
1313 | */ | ||
1314 | int dx, dy; | ||
1315 | for (dy = 0; dy <= 1; dy++) | ||
1316 | for (dx = 0; dx >= -1; dx--) { | ||
1317 | int cx = tx + dx, cy = ty + dy; | ||
1318 | if (cx >= 0 && cx < w && cy >= 0 && cy < w) { | ||
1319 | int height = state->grid[cy*w+cx]; | ||
1320 | int bx = COORD(cx), by = COORD(cy); | ||
1321 | int ox = bx + X_3D_DISP(height, w); | ||
1322 | int oy = by - Y_3D_DISP(height, w); | ||
1323 | if (/* on top face? */ | ||
1324 | (x - ox >= 0 && x - ox < TILESIZE && | ||
1325 | y - oy >= 0 && y - oy < TILESIZE) || | ||
1326 | /* in triangle between top-left corners? */ | ||
1327 | (ox > bx && x >= bx && x <= ox && y <= by && | ||
1328 | (by-y) * (ox-bx) <= (by-oy) * (x-bx)) || | ||
1329 | /* in triangle between bottom-right corners? */ | ||
1330 | (ox > bx && x >= bx+TILESIZE && x <= ox+TILESIZE && | ||
1331 | y >= oy+TILESIZE && | ||
1332 | (by-y+TILESIZE)*(ox-bx) >= (by-oy)*(x-bx-TILESIZE))) { | ||
1333 | tx = cx; | ||
1334 | ty = cy; | ||
1335 | } | ||
1336 | } | ||
1337 | } | ||
1338 | } | ||
1339 | |||
1340 | if (tx >= 0 && tx < w && ty >= 0 && ty < w) { | ||
1341 | if (button == LEFT_BUTTON) { | ||
1342 | if (tx == ui->hx && ty == ui->hy && | ||
1343 | ui->hshow && ui->hpencil == 0) { | ||
1344 | ui->hshow = 0; | ||
1345 | } else { | ||
1346 | ui->hx = tx; | ||
1347 | ui->hy = ty; | ||
1348 | ui->hshow = !state->clues->immutable[ty*w+tx]; | ||
1349 | ui->hpencil = 0; | ||
1350 | } | ||
1351 | ui->hcursor = 0; | ||
1352 | return ""; /* UI activity occurred */ | ||
1353 | } | ||
1354 | if (button == RIGHT_BUTTON) { | ||
1355 | /* | ||
1356 | * Pencil-mode highlighting for non filled squares. | ||
1357 | */ | ||
1358 | if (state->grid[ty*w+tx] == 0) { | ||
1359 | if (tx == ui->hx && ty == ui->hy && | ||
1360 | ui->hshow && ui->hpencil) { | ||
1361 | ui->hshow = 0; | ||
1362 | } else { | ||
1363 | ui->hpencil = 1; | ||
1364 | ui->hx = tx; | ||
1365 | ui->hy = ty; | ||
1366 | ui->hshow = 1; | ||
1367 | } | ||
1368 | } else { | ||
1369 | ui->hshow = 0; | ||
1370 | } | ||
1371 | ui->hcursor = 0; | ||
1372 | return ""; /* UI activity occurred */ | ||
1373 | } | ||
1374 | } else if (button == LEFT_BUTTON) { | ||
1375 | if (is_clue(state, tx, ty)) { | ||
1376 | sprintf(buf, "%c%d,%d", 'D', tx, ty); | ||
1377 | return dupstr(buf); | ||
1378 | } | ||
1379 | } | ||
1380 | if (IS_CURSOR_MOVE(button)) { | ||
1381 | if (shift_or_control) { | ||
1382 | int x = ui->hx, y = ui->hy; | ||
1383 | switch (button) { | ||
1384 | case CURSOR_LEFT: x = -1; break; | ||
1385 | case CURSOR_RIGHT: x = w; break; | ||
1386 | case CURSOR_UP: y = -1; break; | ||
1387 | case CURSOR_DOWN: y = w; break; | ||
1388 | } | ||
1389 | if (is_clue(state, x, y)) { | ||
1390 | sprintf(buf, "%c%d,%d", 'D', x, y); | ||
1391 | return dupstr(buf); | ||
1392 | } | ||
1393 | return NULL; | ||
1394 | } | ||
1395 | move_cursor(button, &ui->hx, &ui->hy, w, w, 0); | ||
1396 | ui->hshow = ui->hcursor = 1; | ||
1397 | return ""; | ||
1398 | } | ||
1399 | if (ui->hshow && | ||
1400 | (button == CURSOR_SELECT)) { | ||
1401 | ui->hpencil = 1 - ui->hpencil; | ||
1402 | ui->hcursor = 1; | ||
1403 | return ""; | ||
1404 | } | ||
1405 | |||
1406 | if (ui->hshow && | ||
1407 | ((button >= '0' && button <= '9' && button - '0' <= w) || | ||
1408 | button == CURSOR_SELECT2 || button == '\b')) { | ||
1409 | int n = button - '0'; | ||
1410 | if (button == CURSOR_SELECT2 || button == '\b') | ||
1411 | n = 0; | ||
1412 | |||
1413 | /* | ||
1414 | * Can't make pencil marks in a filled square. This can only | ||
1415 | * become highlighted if we're using cursor keys. | ||
1416 | */ | ||
1417 | if (ui->hpencil && state->grid[ui->hy*w+ui->hx]) | ||
1418 | return NULL; | ||
1419 | |||
1420 | /* | ||
1421 | * Can't do anything to an immutable square. | ||
1422 | */ | ||
1423 | if (state->clues->immutable[ui->hy*w+ui->hx]) | ||
1424 | return NULL; | ||
1425 | |||
1426 | sprintf(buf, "%c%d,%d,%d", | ||
1427 | (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n); | ||
1428 | |||
1429 | if (!ui->hcursor) ui->hshow = 0; | ||
1430 | |||
1431 | return dupstr(buf); | ||
1432 | } | ||
1433 | |||
1434 | if (button == 'M' || button == 'm') | ||
1435 | return dupstr("M"); | ||
1436 | |||
1437 | return NULL; | ||
1438 | } | ||
1439 | |||
1440 | static game_state *execute_move(const game_state *from, const char *move) | ||
1441 | { | ||
1442 | int w = from->par.w, a = w*w; | ||
1443 | game_state *ret = dup_game(from); | ||
1444 | int x, y, i, n; | ||
1445 | |||
1446 | if (move[0] == 'S') { | ||
1447 | ret->completed = ret->cheated = TRUE; | ||
1448 | |||
1449 | for (i = 0; i < a; i++) { | ||
1450 | if (move[i+1] < '1' || move[i+1] > '0'+w) | ||
1451 | goto badmove; | ||
1452 | ret->grid[i] = move[i+1] - '0'; | ||
1453 | ret->pencil[i] = 0; | ||
1454 | } | ||
1455 | |||
1456 | if (move[a+1] != '\0') | ||
1457 | goto badmove; | ||
1458 | |||
1459 | return ret; | ||
1460 | } else if ((move[0] == 'P' || move[0] == 'R') && | ||
1461 | sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 && | ||
1462 | x >= 0 && x < w && y >= 0 && y < w && n >= 0 && n <= w) { | ||
1463 | if (from->clues->immutable[y*w+x]) | ||
1464 | goto badmove; | ||
1465 | |||
1466 | if (move[0] == 'P' && n > 0) { | ||
1467 | ret->pencil[y*w+x] ^= 1L << n; | ||
1468 | } else { | ||
1469 | ret->grid[y*w+x] = n; | ||
1470 | ret->pencil[y*w+x] = 0; | ||
1471 | |||
1472 | if (!ret->completed && !check_errors(ret, NULL)) | ||
1473 | ret->completed = TRUE; | ||
1474 | } | ||
1475 | return ret; | ||
1476 | } else if (move[0] == 'M') { | ||
1477 | /* | ||
1478 | * Fill in absolutely all pencil marks everywhere. (I | ||
1479 | * wouldn't use this for actual play, but it's a handy | ||
1480 | * starting point when following through a set of | ||
1481 | * diagnostics output by the standalone solver.) | ||
1482 | */ | ||
1483 | for (i = 0; i < a; i++) { | ||
1484 | if (!ret->grid[i]) | ||
1485 | ret->pencil[i] = (1L << (w+1)) - (1L << 1); | ||
1486 | } | ||
1487 | return ret; | ||
1488 | } else if (move[0] == 'D' && sscanf(move+1, "%d,%d", &x, &y) == 2 && | ||
1489 | is_clue(from, x, y)) { | ||
1490 | int index = clue_index(from, x, y); | ||
1491 | ret->clues_done[index] = !ret->clues_done[index]; | ||
1492 | return ret; | ||
1493 | } | ||
1494 | |||
1495 | badmove: | ||
1496 | /* couldn't parse move string */ | ||
1497 | free_game(ret); | ||
1498 | return NULL; | ||
1499 | } | ||
1500 | |||
1501 | /* ---------------------------------------------------------------------- | ||
1502 | * Drawing routines. | ||
1503 | */ | ||
1504 | |||
1505 | #define SIZE(w) ((w) * TILESIZE + 2*BORDER) | ||
1506 | |||
1507 | static void game_compute_size(const game_params *params, int tilesize, | ||
1508 | int *x, int *y) | ||
1509 | { | ||
1510 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1511 | struct { int tilesize; } ads, *ds = &ads; | ||
1512 | ads.tilesize = tilesize; | ||
1513 | |||
1514 | *x = *y = SIZE(params->w); | ||
1515 | } | ||
1516 | |||
1517 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1518 | const game_params *params, int tilesize) | ||
1519 | { | ||
1520 | ds->tilesize = tilesize; | ||
1521 | } | ||
1522 | |||
1523 | static float *game_colours(frontend *fe, int *ncolours) | ||
1524 | { | ||
1525 | float *ret = snewn(3 * NCOLOURS, float); | ||
1526 | |||
1527 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1528 | |||
1529 | ret[COL_GRID * 3 + 0] = 0.0F; | ||
1530 | ret[COL_GRID * 3 + 1] = 0.0F; | ||
1531 | ret[COL_GRID * 3 + 2] = 0.0F; | ||
1532 | |||
1533 | ret[COL_USER * 3 + 0] = 0.0F; | ||
1534 | ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1]; | ||
1535 | ret[COL_USER * 3 + 2] = 0.0F; | ||
1536 | |||
1537 | ret[COL_HIGHLIGHT * 3 + 0] = 0.78F * ret[COL_BACKGROUND * 3 + 0]; | ||
1538 | ret[COL_HIGHLIGHT * 3 + 1] = 0.78F * ret[COL_BACKGROUND * 3 + 1]; | ||
1539 | ret[COL_HIGHLIGHT * 3 + 2] = 0.78F * ret[COL_BACKGROUND * 3 + 2]; | ||
1540 | |||
1541 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1542 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1543 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1544 | |||
1545 | ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0]; | ||
1546 | ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1]; | ||
1547 | ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2]; | ||
1548 | |||
1549 | ret[COL_DONE * 3 + 0] = ret[COL_BACKGROUND * 3 + 0] / 1.5F; | ||
1550 | ret[COL_DONE * 3 + 1] = ret[COL_BACKGROUND * 3 + 1] / 1.5F; | ||
1551 | ret[COL_DONE * 3 + 2] = ret[COL_BACKGROUND * 3 + 2] / 1.5F; | ||
1552 | |||
1553 | *ncolours = NCOLOURS; | ||
1554 | return ret; | ||
1555 | } | ||
1556 | |||
1557 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1558 | { | ||
1559 | int w = state->par.w /*, a = w*w */; | ||
1560 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1561 | int i; | ||
1562 | |||
1563 | ds->tilesize = 0; | ||
1564 | ds->three_d = !getenv("TOWERS_2D"); | ||
1565 | ds->started = FALSE; | ||
1566 | ds->tiles = snewn((w+2)*(w+2), long); | ||
1567 | ds->drawn = snewn((w+2)*(w+2)*4, long); | ||
1568 | for (i = 0; i < (w+2)*(w+2)*4; i++) | ||
1569 | ds->drawn[i] = -1; | ||
1570 | ds->errtmp = snewn((w+2)*(w+2), int); | ||
1571 | |||
1572 | return ds; | ||
1573 | } | ||
1574 | |||
1575 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1576 | { | ||
1577 | sfree(ds->errtmp); | ||
1578 | sfree(ds->tiles); | ||
1579 | sfree(ds->drawn); | ||
1580 | sfree(ds); | ||
1581 | } | ||
1582 | |||
1583 | static void draw_tile(drawing *dr, game_drawstate *ds, struct clues *clues, | ||
1584 | int x, int y, long tile) | ||
1585 | { | ||
1586 | int w = clues->w /* , a = w*w */; | ||
1587 | int tx, ty, bg; | ||
1588 | char str[64]; | ||
1589 | |||
1590 | tx = COORD(x); | ||
1591 | ty = COORD(y); | ||
1592 | |||
1593 | bg = (tile & DF_HIGHLIGHT) ? COL_HIGHLIGHT : COL_BACKGROUND; | ||
1594 | |||
1595 | /* draw tower */ | ||
1596 | if (ds->three_d && (tile & DF_PLAYAREA) && (tile & DF_DIGIT_MASK)) { | ||
1597 | int coords[8]; | ||
1598 | int xoff = X_3D_DISP(tile & DF_DIGIT_MASK, w); | ||
1599 | int yoff = Y_3D_DISP(tile & DF_DIGIT_MASK, w); | ||
1600 | |||
1601 | /* left face of tower */ | ||
1602 | coords[0] = tx; | ||
1603 | coords[1] = ty - 1; | ||
1604 | coords[2] = tx; | ||
1605 | coords[3] = ty + TILESIZE - 1; | ||
1606 | coords[4] = coords[2] + xoff; | ||
1607 | coords[5] = coords[3] - yoff; | ||
1608 | coords[6] = coords[0] + xoff; | ||
1609 | coords[7] = coords[1] - yoff; | ||
1610 | draw_polygon(dr, coords, 4, bg, COL_GRID); | ||
1611 | |||
1612 | /* bottom face of tower */ | ||
1613 | coords[0] = tx + TILESIZE; | ||
1614 | coords[1] = ty + TILESIZE - 1; | ||
1615 | coords[2] = tx; | ||
1616 | coords[3] = ty + TILESIZE - 1; | ||
1617 | coords[4] = coords[2] + xoff; | ||
1618 | coords[5] = coords[3] - yoff; | ||
1619 | coords[6] = coords[0] + xoff; | ||
1620 | coords[7] = coords[1] - yoff; | ||
1621 | draw_polygon(dr, coords, 4, bg, COL_GRID); | ||
1622 | |||
1623 | /* now offset all subsequent drawing to the top of the tower */ | ||
1624 | tx += xoff; | ||
1625 | ty -= yoff; | ||
1626 | } | ||
1627 | |||
1628 | /* erase background */ | ||
1629 | draw_rect(dr, tx, ty, TILESIZE, TILESIZE, bg); | ||
1630 | |||
1631 | /* pencil-mode highlight */ | ||
1632 | if (tile & DF_HIGHLIGHT_PENCIL) { | ||
1633 | int coords[6]; | ||
1634 | coords[0] = tx; | ||
1635 | coords[1] = ty; | ||
1636 | coords[2] = tx+TILESIZE/2; | ||
1637 | coords[3] = ty; | ||
1638 | coords[4] = tx; | ||
1639 | coords[5] = ty+TILESIZE/2; | ||
1640 | draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT); | ||
1641 | } | ||
1642 | |||
1643 | /* draw box outline */ | ||
1644 | if (tile & DF_PLAYAREA) { | ||
1645 | int coords[8]; | ||
1646 | coords[0] = tx; | ||
1647 | coords[1] = ty - 1; | ||
1648 | coords[2] = tx + TILESIZE; | ||
1649 | coords[3] = ty - 1; | ||
1650 | coords[4] = tx + TILESIZE; | ||
1651 | coords[5] = ty + TILESIZE - 1; | ||
1652 | coords[6] = tx; | ||
1653 | coords[7] = ty + TILESIZE - 1; | ||
1654 | draw_polygon(dr, coords, 4, -1, COL_GRID); | ||
1655 | } | ||
1656 | |||
1657 | /* new number needs drawing? */ | ||
1658 | if (tile & DF_DIGIT_MASK) { | ||
1659 | int color; | ||
1660 | |||
1661 | str[1] = '\0'; | ||
1662 | str[0] = (tile & DF_DIGIT_MASK) + '0'; | ||
1663 | |||
1664 | if (tile & DF_ERROR) | ||
1665 | color = COL_ERROR; | ||
1666 | else if (tile & DF_CLUE_DONE) | ||
1667 | color = COL_DONE; | ||
1668 | else if (x < 0 || y < 0 || x >= w || y >= w) | ||
1669 | color = COL_GRID; | ||
1670 | else if (tile & DF_IMMUTABLE) | ||
1671 | color = COL_GRID; | ||
1672 | else | ||
1673 | color = COL_USER; | ||
1674 | |||
1675 | draw_text(dr, tx + TILESIZE/2, ty + TILESIZE/2, FONT_VARIABLE, | ||
1676 | (tile & DF_PLAYAREA ? TILESIZE/2 : TILESIZE*2/5), | ||
1677 | ALIGN_VCENTRE | ALIGN_HCENTRE, color, str); | ||
1678 | } else { | ||
1679 | int i, j, npencil; | ||
1680 | int pl, pr, pt, pb; | ||
1681 | float bestsize; | ||
1682 | int pw, ph, minph, pbest, fontsize; | ||
1683 | |||
1684 | /* Count the pencil marks required. */ | ||
1685 | for (i = 1, npencil = 0; i <= w; i++) | ||
1686 | if (tile & (1L << (i + DF_PENCIL_SHIFT))) | ||
1687 | npencil++; | ||
1688 | if (npencil) { | ||
1689 | |||
1690 | minph = 2; | ||
1691 | |||
1692 | /* | ||
1693 | * Determine the bounding rectangle within which we're going | ||
1694 | * to put the pencil marks. | ||
1695 | */ | ||
1696 | /* Start with the whole square, minus space for impinging towers */ | ||
1697 | pl = tx + (ds->three_d ? X_3D_DISP(w,w) : 0); | ||
1698 | pr = tx + TILESIZE; | ||
1699 | pt = ty; | ||
1700 | pb = ty + TILESIZE - (ds->three_d ? Y_3D_DISP(w,w) : 0); | ||
1701 | |||
1702 | /* | ||
1703 | * We arrange our pencil marks in a grid layout, with | ||
1704 | * the number of rows and columns adjusted to allow the | ||
1705 | * maximum font size. | ||
1706 | * | ||
1707 | * So now we work out what the grid size ought to be. | ||
1708 | */ | ||
1709 | bestsize = 0.0; | ||
1710 | pbest = 0; | ||
1711 | /* Minimum */ | ||
1712 | for (pw = 3; pw < max(npencil,4); pw++) { | ||
1713 | float fw, fh, fs; | ||
1714 | |||
1715 | ph = (npencil + pw - 1) / pw; | ||
1716 | ph = max(ph, minph); | ||
1717 | fw = (pr - pl) / (float)pw; | ||
1718 | fh = (pb - pt) / (float)ph; | ||
1719 | fs = min(fw, fh); | ||
1720 | if (fs > bestsize) { | ||
1721 | bestsize = fs; | ||
1722 | pbest = pw; | ||
1723 | } | ||
1724 | } | ||
1725 | assert(pbest > 0); | ||
1726 | pw = pbest; | ||
1727 | ph = (npencil + pw - 1) / pw; | ||
1728 | ph = max(ph, minph); | ||
1729 | |||
1730 | /* | ||
1731 | * Now we've got our grid dimensions, work out the pixel | ||
1732 | * size of a grid element, and round it to the nearest | ||
1733 | * pixel. (We don't want rounding errors to make the | ||
1734 | * grid look uneven at low pixel sizes.) | ||
1735 | */ | ||
1736 | fontsize = min((pr - pl) / pw, (pb - pt) / ph); | ||
1737 | |||
1738 | /* | ||
1739 | * Centre the resulting figure in the square. | ||
1740 | */ | ||
1741 | pl = pl + (pr - pl - fontsize * pw) / 2; | ||
1742 | pt = pt + (pb - pt - fontsize * ph) / 2; | ||
1743 | |||
1744 | /* | ||
1745 | * Now actually draw the pencil marks. | ||
1746 | */ | ||
1747 | for (i = 1, j = 0; i <= w; i++) | ||
1748 | if (tile & (1L << (i + DF_PENCIL_SHIFT))) { | ||
1749 | int dx = j % pw, dy = j / pw; | ||
1750 | |||
1751 | str[1] = '\0'; | ||
1752 | str[0] = i + '0'; | ||
1753 | draw_text(dr, pl + fontsize * (2*dx+1) / 2, | ||
1754 | pt + fontsize * (2*dy+1) / 2, | ||
1755 | FONT_VARIABLE, fontsize, | ||
1756 | ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str); | ||
1757 | j++; | ||
1758 | } | ||
1759 | } | ||
1760 | } | ||
1761 | } | ||
1762 | |||
1763 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1764 | const game_state *oldstate, const game_state *state, | ||
1765 | int dir, const game_ui *ui, | ||
1766 | float animtime, float flashtime) | ||
1767 | { | ||
1768 | int w = state->par.w /*, a = w*w */; | ||
1769 | int i, x, y; | ||
1770 | |||
1771 | if (!ds->started) { | ||
1772 | /* | ||
1773 | * The initial contents of the window are not guaranteed and | ||
1774 | * can vary with front ends. To be on the safe side, all | ||
1775 | * games should start by drawing a big background-colour | ||
1776 | * rectangle covering the whole window. | ||
1777 | */ | ||
1778 | draw_rect(dr, 0, 0, SIZE(w), SIZE(w), COL_BACKGROUND); | ||
1779 | |||
1780 | draw_update(dr, 0, 0, SIZE(w), SIZE(w)); | ||
1781 | |||
1782 | ds->started = TRUE; | ||
1783 | } | ||
1784 | |||
1785 | check_errors(state, ds->errtmp); | ||
1786 | |||
1787 | /* | ||
1788 | * Work out what data each tile should contain. | ||
1789 | */ | ||
1790 | for (i = 0; i < (w+2)*(w+2); i++) | ||
1791 | ds->tiles[i] = 0; /* completely blank square */ | ||
1792 | /* The clue squares... */ | ||
1793 | for (i = 0; i < 4*w; i++) { | ||
1794 | long tile = state->clues->clues[i]; | ||
1795 | |||
1796 | CLUEPOS(x, y, i, w); | ||
1797 | |||
1798 | if (ds->errtmp[(y+1)*(w+2)+(x+1)]) | ||
1799 | tile |= DF_ERROR; | ||
1800 | else if (state->clues_done[i]) | ||
1801 | tile |= DF_CLUE_DONE; | ||
1802 | |||
1803 | ds->tiles[(y+1)*(w+2)+(x+1)] = tile; | ||
1804 | } | ||
1805 | /* ... and the main grid. */ | ||
1806 | for (y = 0; y < w; y++) { | ||
1807 | for (x = 0; x < w; x++) { | ||
1808 | long tile = DF_PLAYAREA; | ||
1809 | |||
1810 | if (state->grid[y*w+x]) | ||
1811 | tile |= state->grid[y*w+x]; | ||
1812 | else | ||
1813 | tile |= (long)state->pencil[y*w+x] << DF_PENCIL_SHIFT; | ||
1814 | |||
1815 | if (ui->hshow && ui->hx == x && ui->hy == y) | ||
1816 | tile |= (ui->hpencil ? DF_HIGHLIGHT_PENCIL : DF_HIGHLIGHT); | ||
1817 | |||
1818 | if (state->clues->immutable[y*w+x]) | ||
1819 | tile |= DF_IMMUTABLE; | ||
1820 | |||
1821 | if (flashtime > 0 && | ||
1822 | (flashtime <= FLASH_TIME/3 || | ||
1823 | flashtime >= FLASH_TIME*2/3)) | ||
1824 | tile |= DF_HIGHLIGHT; /* completion flash */ | ||
1825 | |||
1826 | if (ds->errtmp[(y+1)*(w+2)+(x+1)]) | ||
1827 | tile |= DF_ERROR; | ||
1828 | |||
1829 | ds->tiles[(y+1)*(w+2)+(x+1)] = tile; | ||
1830 | } | ||
1831 | } | ||
1832 | |||
1833 | /* | ||
1834 | * Now actually draw anything that needs to be changed. | ||
1835 | */ | ||
1836 | for (y = 0; y < w+2; y++) { | ||
1837 | for (x = 0; x < w+2; x++) { | ||
1838 | long tl, tr, bl, br; | ||
1839 | int i = y*(w+2)+x; | ||
1840 | |||
1841 | tr = ds->tiles[y*(w+2)+x]; | ||
1842 | tl = (x == 0 ? 0 : ds->tiles[y*(w+2)+(x-1)]); | ||
1843 | br = (y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+x]); | ||
1844 | bl = (x == 0 || y == w+1 ? 0 : ds->tiles[(y+1)*(w+2)+(x-1)]); | ||
1845 | |||
1846 | if (ds->drawn[i*4] != tl || ds->drawn[i*4+1] != tr || | ||
1847 | ds->drawn[i*4+2] != bl || ds->drawn[i*4+3] != br) { | ||
1848 | clip(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE); | ||
1849 | |||
1850 | draw_tile(dr, ds, state->clues, x-1, y-1, tr); | ||
1851 | if (x > 0) | ||
1852 | draw_tile(dr, ds, state->clues, x-2, y-1, tl); | ||
1853 | if (y <= w) | ||
1854 | draw_tile(dr, ds, state->clues, x-1, y, br); | ||
1855 | if (x > 0 && y <= w) | ||
1856 | draw_tile(dr, ds, state->clues, x-2, y, bl); | ||
1857 | |||
1858 | unclip(dr); | ||
1859 | draw_update(dr, COORD(x-1), COORD(y-1), TILESIZE, TILESIZE); | ||
1860 | |||
1861 | ds->drawn[i*4] = tl; | ||
1862 | ds->drawn[i*4+1] = tr; | ||
1863 | ds->drawn[i*4+2] = bl; | ||
1864 | ds->drawn[i*4+3] = br; | ||
1865 | } | ||
1866 | } | ||
1867 | } | ||
1868 | } | ||
1869 | |||
1870 | static float game_anim_length(const game_state *oldstate, | ||
1871 | const game_state *newstate, int dir, game_ui *ui) | ||
1872 | { | ||
1873 | return 0.0F; | ||
1874 | } | ||
1875 | |||
1876 | static float game_flash_length(const game_state *oldstate, | ||
1877 | const game_state *newstate, int dir, game_ui *ui) | ||
1878 | { | ||
1879 | if (!oldstate->completed && newstate->completed && | ||
1880 | !oldstate->cheated && !newstate->cheated) | ||
1881 | return FLASH_TIME; | ||
1882 | return 0.0F; | ||
1883 | } | ||
1884 | |||
1885 | static int game_status(const game_state *state) | ||
1886 | { | ||
1887 | return state->completed ? +1 : 0; | ||
1888 | } | ||
1889 | |||
1890 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1891 | { | ||
1892 | if (state->completed) | ||
1893 | return FALSE; | ||
1894 | return TRUE; | ||
1895 | } | ||
1896 | |||
1897 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1898 | { | ||
1899 | int pw, ph; | ||
1900 | |||
1901 | /* | ||
1902 | * We use 9mm squares by default, like Solo. | ||
1903 | */ | ||
1904 | game_compute_size(params, 900, &pw, &ph); | ||
1905 | *x = pw / 100.0F; | ||
1906 | *y = ph / 100.0F; | ||
1907 | } | ||
1908 | |||
1909 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1910 | { | ||
1911 | int w = state->par.w; | ||
1912 | int ink = print_mono_colour(dr, 0); | ||
1913 | int i, x, y; | ||
1914 | |||
1915 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1916 | game_drawstate ads, *ds = &ads; | ||
1917 | game_set_size(dr, ds, NULL, tilesize); | ||
1918 | |||
1919 | /* | ||
1920 | * Border. | ||
1921 | */ | ||
1922 | print_line_width(dr, 3 * TILESIZE / 40); | ||
1923 | draw_rect_outline(dr, BORDER, BORDER, w*TILESIZE, w*TILESIZE, ink); | ||
1924 | |||
1925 | /* | ||
1926 | * Main grid. | ||
1927 | */ | ||
1928 | for (x = 1; x < w; x++) { | ||
1929 | print_line_width(dr, TILESIZE / 40); | ||
1930 | draw_line(dr, BORDER+x*TILESIZE, BORDER, | ||
1931 | BORDER+x*TILESIZE, BORDER+w*TILESIZE, ink); | ||
1932 | } | ||
1933 | for (y = 1; y < w; y++) { | ||
1934 | print_line_width(dr, TILESIZE / 40); | ||
1935 | draw_line(dr, BORDER, BORDER+y*TILESIZE, | ||
1936 | BORDER+w*TILESIZE, BORDER+y*TILESIZE, ink); | ||
1937 | } | ||
1938 | |||
1939 | /* | ||
1940 | * Clues. | ||
1941 | */ | ||
1942 | for (i = 0; i < 4*w; i++) { | ||
1943 | char str[128]; | ||
1944 | |||
1945 | if (!state->clues->clues[i]) | ||
1946 | continue; | ||
1947 | |||
1948 | CLUEPOS(x, y, i, w); | ||
1949 | |||
1950 | sprintf (str, "%d", state->clues->clues[i]); | ||
1951 | |||
1952 | draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, | ||
1953 | BORDER + y*TILESIZE + TILESIZE/2, | ||
1954 | FONT_VARIABLE, TILESIZE/2, | ||
1955 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); | ||
1956 | } | ||
1957 | |||
1958 | /* | ||
1959 | * Numbers for the solution, if any. | ||
1960 | */ | ||
1961 | for (y = 0; y < w; y++) | ||
1962 | for (x = 0; x < w; x++) | ||
1963 | if (state->grid[y*w+x]) { | ||
1964 | char str[2]; | ||
1965 | str[1] = '\0'; | ||
1966 | str[0] = state->grid[y*w+x] + '0'; | ||
1967 | draw_text(dr, BORDER + x*TILESIZE + TILESIZE/2, | ||
1968 | BORDER + y*TILESIZE + TILESIZE/2, | ||
1969 | FONT_VARIABLE, TILESIZE/2, | ||
1970 | ALIGN_VCENTRE | ALIGN_HCENTRE, ink, str); | ||
1971 | } | ||
1972 | } | ||
1973 | |||
1974 | #ifdef COMBINED | ||
1975 | #define thegame towers | ||
1976 | #endif | ||
1977 | |||
1978 | const struct game thegame = { | ||
1979 | "Towers", "games.towers", "towers", | ||
1980 | default_params, | ||
1981 | game_fetch_preset, | ||
1982 | decode_params, | ||
1983 | encode_params, | ||
1984 | free_params, | ||
1985 | dup_params, | ||
1986 | TRUE, game_configure, custom_params, | ||
1987 | validate_params, | ||
1988 | new_game_desc, | ||
1989 | validate_desc, | ||
1990 | new_game, | ||
1991 | dup_game, | ||
1992 | free_game, | ||
1993 | TRUE, solve_game, | ||
1994 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1995 | new_ui, | ||
1996 | free_ui, | ||
1997 | encode_ui, | ||
1998 | decode_ui, | ||
1999 | game_changed_state, | ||
2000 | interpret_move, | ||
2001 | execute_move, | ||
2002 | PREFERRED_TILESIZE, game_compute_size, game_set_size, | ||
2003 | game_colours, | ||
2004 | game_new_drawstate, | ||
2005 | game_free_drawstate, | ||
2006 | game_redraw, | ||
2007 | game_anim_length, | ||
2008 | game_flash_length, | ||
2009 | game_status, | ||
2010 | TRUE, FALSE, game_print_size, game_print, | ||
2011 | FALSE, /* wants_statusbar */ | ||
2012 | FALSE, game_timing_state, | ||
2013 | REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */ | ||
2014 | }; | ||
2015 | |||
2016 | #ifdef STANDALONE_SOLVER | ||
2017 | |||
2018 | #include <stdarg.h> | ||
2019 | |||
2020 | int main(int argc, char **argv) | ||
2021 | { | ||
2022 | game_params *p; | ||
2023 | game_state *s; | ||
2024 | char *id = NULL, *desc, *err; | ||
2025 | int grade = FALSE; | ||
2026 | int ret, diff, really_show_working = FALSE; | ||
2027 | |||
2028 | while (--argc > 0) { | ||
2029 | char *p = *++argv; | ||
2030 | if (!strcmp(p, "-v")) { | ||
2031 | really_show_working = TRUE; | ||
2032 | } else if (!strcmp(p, "-g")) { | ||
2033 | grade = TRUE; | ||
2034 | } else if (*p == '-') { | ||
2035 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
2036 | return 1; | ||
2037 | } else { | ||
2038 | id = p; | ||
2039 | } | ||
2040 | } | ||
2041 | |||
2042 | if (!id) { | ||
2043 | fprintf(stderr, "usage: %s [-g | -v] <game_id>\n", argv[0]); | ||
2044 | return 1; | ||
2045 | } | ||
2046 | |||
2047 | desc = strchr(id, ':'); | ||
2048 | if (!desc) { | ||
2049 | fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]); | ||
2050 | return 1; | ||
2051 | } | ||
2052 | *desc++ = '\0'; | ||
2053 | |||
2054 | p = default_params(); | ||
2055 | decode_params(p, id); | ||
2056 | err = validate_desc(p, desc); | ||
2057 | if (err) { | ||
2058 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
2059 | return 1; | ||
2060 | } | ||
2061 | s = new_game(NULL, p, desc); | ||
2062 | |||
2063 | /* | ||
2064 | * When solving an Easy puzzle, we don't want to bother the | ||
2065 | * user with Hard-level deductions. For this reason, we grade | ||
2066 | * the puzzle internally before doing anything else. | ||
2067 | */ | ||
2068 | ret = -1; /* placate optimiser */ | ||
2069 | solver_show_working = FALSE; | ||
2070 | for (diff = 0; diff < DIFFCOUNT; diff++) { | ||
2071 | memcpy(s->grid, s->clues->immutable, p->w * p->w); | ||
2072 | ret = solver(p->w, s->clues->clues, s->grid, diff); | ||
2073 | if (ret <= diff) | ||
2074 | break; | ||
2075 | } | ||
2076 | |||
2077 | if (diff == DIFFCOUNT) { | ||
2078 | if (grade) | ||
2079 | printf("Difficulty rating: ambiguous\n"); | ||
2080 | else | ||
2081 | printf("Unable to find a unique solution\n"); | ||
2082 | } else { | ||
2083 | if (grade) { | ||
2084 | if (ret == diff_impossible) | ||
2085 | printf("Difficulty rating: impossible (no solution exists)\n"); | ||
2086 | else | ||
2087 | printf("Difficulty rating: %s\n", towers_diffnames[ret]); | ||
2088 | } else { | ||
2089 | solver_show_working = really_show_working; | ||
2090 | memcpy(s->grid, s->clues->immutable, p->w * p->w); | ||
2091 | ret = solver(p->w, s->clues->clues, s->grid, diff); | ||
2092 | if (ret != diff) | ||
2093 | printf("Puzzle is inconsistent\n"); | ||
2094 | else | ||
2095 | fputs(game_text_format(s), stdout); | ||
2096 | } | ||
2097 | } | ||
2098 | |||
2099 | return 0; | ||
2100 | } | ||
2101 | |||
2102 | #endif | ||
2103 | |||
2104 | /* vim: set shiftwidth=4 tabstop=8: */ | ||