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