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