tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
1/*
2 * unequal.c
3 *
4 * Implementation of 'Futoshiki', a puzzle featured in the Guardian.
5 *
6 * TTD:
7 * add multiple-links-on-same-col/row solver nous
8 * Optimise set solver to use bit operations instead
9 *
10 * Guardian puzzles of note:
11 * #1: 5:0,0L,0L,0,0,0R,0,0L,0D,0L,0R,0,2,0D,0,0,0,0,0,0,0U,0,0,0,0U,
12 * #2: 5:0,0,0,4L,0L,0,2LU,0L,0U,0,0,0U,0,0,0,0,0D,0,3LRUD,0,0R,3,0L,0,0,
13 * #3: (reprint of #2)
14 * #4:
15 * #5: 5:0,0,0,0,0,0,2,0U,3U,0U,0,0,3,0,0,0,3,0D,4,0,0,0L,0R,0,0,
16 * #6: 5:0D,0L,0,0R,0,0,0D,0,3,0D,0,0R,0,0R,0D,0U,0L,0,1,2,0,0,0U,0,0L,
17 */
18
19#include <stdio.h>
20#include <stdlib.h>
21#include <string.h>
22#include <assert.h>
23#include <ctype.h>
24#ifdef NO_TGMATH_H
25# include <math.h>
26#else
27# include <tgmath.h>
28#endif
29
30#include "puzzles.h"
31#include "latin.h" /* contains typedef for digit */
32
33/* ----------------------------------------------------------
34 * Constant and structure definitions
35 */
36
37#define FLASH_TIME 0.4F
38
39#define PREFERRED_TILE_SIZE 32
40
41#define TILE_SIZE (ds->tilesize)
42#define GAP_SIZE (TILE_SIZE/2)
43#define SQUARE_SIZE (TILE_SIZE + GAP_SIZE)
44
45#define BORDER (TILE_SIZE / 2)
46
47#define COORD(x) ( (x) * SQUARE_SIZE + BORDER )
48#define FROMCOORD(x) ( ((x) - BORDER + SQUARE_SIZE) / SQUARE_SIZE - 1 )
49
50#define GRID(p,w,x,y) ((p)->w[((y)*(p)->order)+(x)])
51#define GRID3(p,w,x,y,z) ((p)->w[ (((x)*(p)->order+(y))*(p)->order+(z)) ])
52#define HINT(p,x,y,n) GRID3(p, hints, x, y, n)
53
54enum {
55 COL_BACKGROUND,
56 COL_GRID,
57 COL_TEXT, COL_GUESS, COL_ERROR, COL_PENCIL,
58 COL_HIGHLIGHT, COL_LOWLIGHT, COL_SPENT = COL_LOWLIGHT,
59 NCOLOURS
60};
61
62typedef enum {
63 MODE_UNEQUAL, /* Puzzle indicators are 'greater-than'. */
64 MODE_ADJACENT /* Puzzle indicators are 'adjacent number'. */
65} Mode;
66
67enum {
68 PREF_PENCIL_KEEP_HIGHLIGHT,
69 N_PREF_ITEMS
70};
71
72struct game_params {
73 int order; /* Size of latin square */
74 int diff; /* Difficulty */
75 Mode mode;
76};
77
78#define F_IMMUTABLE 1 /* passed in as game description */
79#define F_ADJ_UP 2
80#define F_ADJ_RIGHT 4
81#define F_ADJ_DOWN 8
82#define F_ADJ_LEFT 16
83#define F_ERROR 32
84#define F_ERROR_UP 64
85#define F_ERROR_RIGHT 128
86#define F_ERROR_DOWN 256
87#define F_ERROR_LEFT 512
88#define F_SPENT_UP 1024
89#define F_SPENT_RIGHT 2048
90#define F_SPENT_DOWN 4096
91#define F_SPENT_LEFT 8192
92
93#define ADJ_TO_SPENT(x) ((x) << 9)
94
95#define F_ERROR_MASK (F_ERROR|F_ERROR_UP|F_ERROR_RIGHT|F_ERROR_DOWN|F_ERROR_LEFT)
96#define F_SPENT_MASK (F_SPENT_UP|F_SPENT_RIGHT|F_SPENT_DOWN|F_SPENT_LEFT)
97
98struct game_state {
99 int order;
100 bool completed, cheated;
101 Mode mode;
102 digit *nums; /* actual numbers (size order^2) */
103 unsigned char *hints; /* remaining possiblities (size order^3) */
104 unsigned int *flags; /* flags (size order^2) */
105};
106
107/* ----------------------------------------------------------
108 * Game parameters and presets
109 */
110
111/* Steal the method from map.c for difficulty levels. */
112#define DIFFLIST(A) \
113 A(LATIN,Trivial,NULL,t) \
114 A(EASY,Easy,solver_easy, e) \
115 A(SET,Tricky,solver_set, k) \
116 A(EXTREME,Extreme,NULL,x) \
117 A(RECURSIVE,Recursive,NULL,r)
118
119#define ENUM(upper,title,func,lower) DIFF_ ## upper,
120#define TITLE(upper,title,func,lower) #title,
121#define ENCODE(upper,title,func,lower) #lower
122#define CONFIG(upper,title,func,lower) ":" #title
123enum { DIFFLIST(ENUM) DIFFCOUNT, DIFF_IMPOSSIBLE = diff_impossible, DIFF_AMBIGUOUS = diff_ambiguous, DIFF_UNFINISHED = diff_unfinished };
124static char const *const unequal_diffnames[] = { DIFFLIST(TITLE) };
125static char const unequal_diffchars[] = DIFFLIST(ENCODE);
126#define DIFFCONFIG DIFFLIST(CONFIG)
127
128#define DEFAULT_PRESET 0
129
130static const struct game_params unequal_presets[] = {
131 { 4, DIFF_EASY, 0 },
132 { 5, DIFF_EASY, 0 },
133 { 5, DIFF_SET, 0 },
134 { 5, DIFF_SET, 1 },
135 { 5, DIFF_EXTREME, 0 },
136 { 6, DIFF_EASY, 0 },
137 { 6, DIFF_SET, 0 },
138 { 6, DIFF_SET, 1 },
139 { 6, DIFF_EXTREME, 0 },
140 { 7, DIFF_SET, 0 },
141 { 7, DIFF_SET, 1 },
142 { 7, DIFF_EXTREME, 0 }
143};
144
145static bool game_fetch_preset(int i, char **name, game_params **params)
146{
147 game_params *ret;
148 char buf[80];
149
150 if (i < 0 || i >= lenof(unequal_presets))
151 return false;
152
153 ret = snew(game_params);
154 *ret = unequal_presets[i]; /* structure copy */
155
156 sprintf(buf, "%s: %dx%d %s",
157 ret->mode == MODE_ADJACENT ? "Adjacent" : "Unequal",
158 ret->order, ret->order,
159 unequal_diffnames[ret->diff]);
160
161 *name = dupstr(buf);
162 *params = ret;
163 return true;
164}
165
166static game_params *default_params(void)
167{
168 game_params *ret;
169 char *name;
170
171 if (!game_fetch_preset(DEFAULT_PRESET, &name, &ret)) return NULL;
172 sfree(name);
173 return ret;
174}
175
176static void free_params(game_params *params)
177{
178 sfree(params);
179}
180
181static game_params *dup_params(const game_params *params)
182{
183 game_params *ret = snew(game_params);
184 *ret = *params; /* structure copy */
185 return ret;
186}
187
188static void decode_params(game_params *ret, char const *string)
189{
190 char const *p = string;
191
192 ret->order = atoi(p);
193 while (*p && isdigit((unsigned char)*p)) p++;
194
195 if (*p == 'a') {
196 p++;
197 ret->mode = MODE_ADJACENT;
198 } else
199 ret->mode = MODE_UNEQUAL;
200
201 if (*p == 'd') {
202 int i;
203 p++;
204 ret->diff = DIFFCOUNT+1; /* ...which is invalid */
205 if (*p) {
206 for (i = 0; i < DIFFCOUNT; i++) {
207 if (*p == unequal_diffchars[i])
208 ret->diff = i;
209 }
210 p++;
211 }
212 }
213}
214
215static char *encode_params(const game_params *params, bool full)
216{
217 char ret[80];
218
219 sprintf(ret, "%d", params->order);
220 if (params->mode == MODE_ADJACENT)
221 sprintf(ret + strlen(ret), "a");
222 if (full)
223 sprintf(ret + strlen(ret), "d%c", unequal_diffchars[params->diff]);
224
225 return dupstr(ret);
226}
227
228static config_item *game_configure(const game_params *params)
229{
230 config_item *ret;
231 char buf[80];
232
233 ret = snewn(4, config_item);
234
235 ret[0].name = "Mode";
236 ret[0].type = C_CHOICES;
237 ret[0].u.choices.choicenames = ":Unequal:Adjacent";
238 ret[0].u.choices.selected = params->mode;
239
240 ret[1].name = "Size (s*s)";
241 ret[1].type = C_STRING;
242 sprintf(buf, "%d", params->order);
243 ret[1].u.string.sval = dupstr(buf);
244
245 ret[2].name = "Difficulty";
246 ret[2].type = C_CHOICES;
247 ret[2].u.choices.choicenames = DIFFCONFIG;
248 ret[2].u.choices.selected = params->diff;
249
250 ret[3].name = NULL;
251 ret[3].type = C_END;
252
253 return ret;
254}
255
256static game_params *custom_params(const config_item *cfg)
257{
258 game_params *ret = snew(game_params);
259
260 ret->mode = cfg[0].u.choices.selected;
261 ret->order = atoi(cfg[1].u.string.sval);
262 ret->diff = cfg[2].u.choices.selected;
263
264 return ret;
265}
266
267static const char *validate_params(const game_params *params, bool full)
268{
269 if (params->order < 3 || params->order > 32)
270 return "Order must be between 3 and 32";
271 if (params->diff >= DIFFCOUNT)
272 return "Unknown difficulty rating";
273 if (params->order < 5 && params->mode == MODE_ADJACENT &&
274 params->diff >= DIFF_SET)
275 return "Order must be at least 5 for Adjacent puzzles of this difficulty.";
276 return NULL;
277}
278
279/* ----------------------------------------------------------
280 * Various utility functions
281 */
282
283static const struct { unsigned int f, fo, fe; int dx, dy; char c, ac; } adjthan[] = {
284 { F_ADJ_UP, F_ADJ_DOWN, F_ERROR_UP, 0, -1, '^', '-' },
285 { F_ADJ_RIGHT, F_ADJ_LEFT, F_ERROR_RIGHT, 1, 0, '>', '|' },
286 { F_ADJ_DOWN, F_ADJ_UP, F_ERROR_DOWN, 0, 1, 'v', '-' },
287 { F_ADJ_LEFT, F_ADJ_RIGHT, F_ERROR_LEFT, -1, 0, '<', '|' }
288};
289
290static game_state *blank_game(int order, Mode mode)
291{
292 game_state *state = snew(game_state);
293 int o2 = order*order, o3 = o2*order;
294
295 state->order = order;
296 state->mode = mode;
297 state->completed = false;
298 state->cheated = false;
299
300 state->nums = snewn(o2, digit);
301 state->hints = snewn(o3, unsigned char);
302 state->flags = snewn(o2, unsigned int);
303
304 memset(state->nums, 0, o2 * sizeof(digit));
305 memset(state->hints, 0, o3);
306 memset(state->flags, 0, o2 * sizeof(unsigned int));
307
308 return state;
309}
310
311static game_state *dup_game(const game_state *state)
312{
313 game_state *ret = blank_game(state->order, state->mode);
314 int o2 = state->order*state->order, o3 = o2*state->order;
315
316 memcpy(ret->nums, state->nums, o2 * sizeof(digit));
317 memcpy(ret->hints, state->hints, o3);
318 memcpy(ret->flags, state->flags, o2 * sizeof(unsigned int));
319
320 return ret;
321}
322
323static void free_game(game_state *state)
324{
325 sfree(state->nums);
326 sfree(state->hints);
327 sfree(state->flags);
328 sfree(state);
329}
330
331#define CHECKG(x,y) grid[(y)*o+(x)]
332
333/* Returns false if it finds an error, true if ok. */
334static bool check_num_adj(digit *grid, game_state *state,
335 int x, int y, bool me)
336{
337 unsigned int f = GRID(state, flags, x, y);
338 bool ret = true;
339 int i, o = state->order;
340
341 for (i = 0; i < 4; i++) {
342 int dx = adjthan[i].dx, dy = adjthan[i].dy, n, dn;
343
344 if (x+dx < 0 || x+dx >= o || y+dy < 0 || y+dy >= o)
345 continue;
346
347 n = CHECKG(x, y);
348 dn = CHECKG(x+dx, y+dy);
349
350 assert (n != 0);
351 if (dn == 0) continue;
352
353 if (state->mode == MODE_ADJACENT) {
354 int gd = abs(n-dn);
355
356 if ((f & adjthan[i].f) && (gd != 1)) {
357 debug(("check_adj error (%d,%d):%d should be | (%d,%d):%d",
358 x, y, n, x+dx, y+dy, dn));
359 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
360 ret = false;
361 }
362 if (!(f & adjthan[i].f) && (gd == 1)) {
363 debug(("check_adj error (%d,%d):%d should not be | (%d,%d):%d",
364 x, y, n, x+dx, y+dy, dn));
365 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
366 ret = false;
367 }
368
369 } else {
370 if ((f & adjthan[i].f) && (n <= dn)) {
371 debug(("check_adj error (%d,%d):%d not > (%d,%d):%d",
372 x, y, n, x+dx, y+dy, dn));
373 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
374 ret = false;
375 }
376 }
377 }
378 return ret;
379}
380
381/* Returns false if it finds an error, true if ok. */
382static bool check_num_error(digit *grid, game_state *state,
383 int x, int y, bool mark_errors)
384{
385 int o = state->order;
386 int xx, yy, val = CHECKG(x,y);
387 bool ret = true;
388
389 assert(val != 0);
390
391 /* check for dups in same column. */
392 for (yy = 0; yy < state->order; yy++) {
393 if (yy == y) continue;
394 if (CHECKG(x,yy) == val) ret = false;
395 }
396
397 /* check for dups in same row. */
398 for (xx = 0; xx < state->order; xx++) {
399 if (xx == x) continue;
400 if (CHECKG(xx,y) == val) ret = false;
401 }
402
403 if (!ret) {
404 debug(("check_num_error (%d,%d) duplicate %d", x, y, val));
405 if (mark_errors) GRID(state, flags, x, y) |= F_ERROR;
406 }
407 return ret;
408}
409
410/* Returns: -1 for 'wrong'
411 * 0 for 'incomplete'
412 * 1 for 'complete and correct'
413 */
414static int check_complete(digit *grid, game_state *state, bool mark_errors)
415{
416 int x, y, ret = 1, o = state->order;
417
418 if (mark_errors)
419 assert(grid == state->nums);
420
421 for (x = 0; x < state->order; x++) {
422 for (y = 0; y < state->order; y++) {
423 if (mark_errors)
424 GRID(state, flags, x, y) &= ~F_ERROR_MASK;
425 if (grid[y*o+x] == 0) {
426 ret = 0;
427 } else {
428 if (!check_num_error(grid, state, x, y, mark_errors)) ret = -1;
429 if (!check_num_adj(grid, state, x, y, mark_errors)) ret = -1;
430 }
431 }
432 }
433 if (ret == 1 && latin_check(grid, o))
434 ret = -1;
435 return ret;
436}
437
438static char n2c(digit n, int order) {
439 if (n == 0) return ' ';
440 if (order < 10) {
441 if (n < 10) return '0' + n;
442 } else {
443 if (n < 11) return '0' + n-1;
444 n -= 11;
445 if (n <= 26) return 'A' + n;
446 }
447 return '?';
448}
449
450/* should be 'digit', but includes -1 for 'not a digit'.
451 * Includes keypresses (0 especially) for interpret_move. */
452static int c2n(int c, int order) {
453 if (c < 0 || c > 0xff)
454 return -1;
455 if (c == ' ' || c == '\b')
456 return 0;
457 if (order < 10) {
458 if (c >= '0' && c <= '9')
459 return (int)(c - '0');
460 } else {
461 if (c >= '0' && c <= '9')
462 return (int)(c - '0' + 1);
463 if (c >= 'A' && c <= 'Z')
464 return (int)(c - 'A' + 11);
465 if (c >= 'a' && c <= 'z')
466 return (int)(c - 'a' + 11);
467 }
468 return -1;
469}
470
471static bool game_can_format_as_text_now(const game_params *params)
472{
473 return true;
474}
475
476static char *game_text_format(const game_state *state)
477{
478 int x, y, len, n;
479 char *ret, *p;
480
481 len = (state->order*2) * (state->order*2-1) + 1;
482 ret = snewn(len, char);
483 p = ret;
484
485 for (y = 0; y < state->order; y++) {
486 for (x = 0; x < state->order; x++) {
487 n = GRID(state, nums, x, y);
488 *p++ = n > 0 ? n2c(n, state->order) : '.';
489
490 if (x < (state->order-1)) {
491 if (state->mode == MODE_ADJACENT) {
492 *p++ = (GRID(state, flags, x, y) & F_ADJ_RIGHT) ? '|' : ' ';
493 } else {
494 if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
495 *p++ = '>';
496 else if (GRID(state, flags, x+1, y) & F_ADJ_LEFT)
497 *p++ = '<';
498 else
499 *p++ = ' ';
500 }
501 }
502 }
503 *p++ = '\n';
504
505 if (y < (state->order-1)) {
506 for (x = 0; x < state->order; x++) {
507 if (state->mode == MODE_ADJACENT) {
508 *p++ = (GRID(state, flags, x, y) & F_ADJ_DOWN) ? '-' : ' ';
509 } else {
510 if (GRID(state, flags, x, y) & F_ADJ_DOWN)
511 *p++ = 'v';
512 else if (GRID(state, flags, x, y+1) & F_ADJ_UP)
513 *p++ = '^';
514 else
515 *p++ = ' ';
516 }
517
518 if (x < state->order-1)
519 *p++ = ' ';
520 }
521 *p++ = '\n';
522 }
523 }
524 *p++ = '\0';
525
526 assert(p - ret == len);
527 return ret;
528}
529
530#ifdef STANDALONE_SOLVER
531static void game_debug(game_state *state)
532{
533 char *dbg = game_text_format(state);
534 printf("%s", dbg);
535 sfree(dbg);
536}
537#endif
538
539/* ----------------------------------------------------------
540 * Solver.
541 */
542
543struct solver_link {
544 int len, gx, gy, lx, ly;
545};
546
547struct solver_ctx {
548 game_state *state;
549
550 int nlinks, alinks;
551 struct solver_link *links;
552};
553
554static void solver_add_link(struct solver_ctx *ctx,
555 int gx, int gy, int lx, int ly, int len)
556{
557 if (ctx->alinks < ctx->nlinks+1) {
558 ctx->alinks = ctx->alinks*2 + 1;
559 /*debug(("resizing ctx->links, new size %d", ctx->alinks));*/
560 ctx->links = sresize(ctx->links, ctx->alinks, struct solver_link);
561 }
562 ctx->links[ctx->nlinks].gx = gx;
563 ctx->links[ctx->nlinks].gy = gy;
564 ctx->links[ctx->nlinks].lx = lx;
565 ctx->links[ctx->nlinks].ly = ly;
566 ctx->links[ctx->nlinks].len = len;
567 ctx->nlinks++;
568 /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d",
569 len, lx, ly, gx, gy, ctx->nlinks));*/
570}
571
572static struct solver_ctx *new_ctx(game_state *state)
573{
574 struct solver_ctx *ctx = snew(struct solver_ctx);
575 int o = state->order;
576 int i, x, y;
577 unsigned int f;
578
579 ctx->nlinks = ctx->alinks = 0;
580 ctx->links = NULL;
581 ctx->state = state;
582
583 if (state->mode == MODE_ADJACENT)
584 return ctx; /* adjacent mode doesn't use links. */
585
586 for (x = 0; x < o; x++) {
587 for (y = 0; y < o; y++) {
588 f = GRID(state, flags, x, y);
589 for (i = 0; i < 4; i++) {
590 if (f & adjthan[i].f)
591 solver_add_link(ctx, x, y, x+adjthan[i].dx, y+adjthan[i].dy, 1);
592 }
593 }
594 }
595
596 return ctx;
597}
598
599static void *clone_ctx(void *vctx)
600{
601 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
602 return new_ctx(ctx->state);
603}
604
605static void free_ctx(void *vctx)
606{
607 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
608 if (ctx->links) sfree(ctx->links);
609 sfree(ctx);
610}
611
612static void solver_nminmax(struct latin_solver *solver,
613 int x, int y, int *min_r, int *max_r,
614 unsigned char **ns_r)
615{
616 int o = solver->o, min = o, max = 0, n;
617 unsigned char *ns;
618
619 assert(x >= 0 && y >= 0 && x < o && y < o);
620
621 ns = solver->cube + cubepos(x,y,1);
622
623 if (grid(x,y) > 0) {
624 min = max = grid(x,y)-1;
625 } else {
626 for (n = 0; n < o; n++) {
627 if (ns[n]) {
628 if (n > max) max = n;
629 if (n < min) min = n;
630 }
631 }
632 }
633 if (min_r) *min_r = min;
634 if (max_r) *max_r = max;
635 if (ns_r) *ns_r = ns;
636}
637
638static int solver_links(struct latin_solver *solver, void *vctx)
639{
640 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
641 int i, j, lmin, gmax, nchanged = 0;
642 unsigned char *gns, *lns;
643 struct solver_link *link;
644
645 for (i = 0; i < ctx->nlinks; i++) {
646 link = &ctx->links[i];
647 solver_nminmax(solver, link->gx, link->gy, NULL, &gmax, &gns);
648 solver_nminmax(solver, link->lx, link->ly, &lmin, NULL, &lns);
649
650 for (j = 0; j < solver->o; j++) {
651 /* For the 'greater' end of the link, discount all numbers
652 * too small to satisfy the inequality. */
653 if (gns[j]) {
654 if (j < (lmin+link->len)) {
655#ifdef STANDALONE_SOLVER
656 if (solver_show_working) {
657 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
658 solver_recurse_depth*4, "",
659 link->gx+1, link->gy+1, link->lx+1, link->ly+1);
660 printf("%*s ruling out %d at (%d,%d)\n",
661 solver_recurse_depth*4, "",
662 j+1, link->gx+1, link->gy+1);
663 }
664#endif
665 cube(link->gx, link->gy, j+1) = false;
666 nchanged++;
667 }
668 }
669 /* For the 'lesser' end of the link, discount all numbers
670 * too large to satisfy inequality. */
671 if (lns[j]) {
672 if (j > (gmax-link->len)) {
673#ifdef STANDALONE_SOLVER
674 if (solver_show_working) {
675 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
676 solver_recurse_depth*4, "",
677 link->gx+1, link->gy+1, link->lx+1, link->ly+1);
678 printf("%*s ruling out %d at (%d,%d)\n",
679 solver_recurse_depth*4, "",
680 j+1, link->lx+1, link->ly+1);
681 }
682#endif
683 cube(link->lx, link->ly, j+1) = false;
684 nchanged++;
685 }
686 }
687 }
688 }
689 return nchanged;
690}
691
692static int solver_adjacent(struct latin_solver *solver, void *vctx)
693{
694 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
695 int nchanged = 0, x, y, i, n, o = solver->o, nx, ny, gd;
696
697 /* Update possible values based on known values and adjacency clues. */
698
699 for (x = 0; x < o; x++) {
700 for (y = 0; y < o; y++) {
701 if (grid(x, y) == 0) continue;
702
703 /* We have a definite number here. Make sure that any
704 * adjacent possibles reflect the adjacent/non-adjacent clue. */
705
706 for (i = 0; i < 4; i++) {
707 bool isadjacent =
708 (GRID(ctx->state, flags, x, y) & adjthan[i].f);
709
710 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
711 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
712 continue;
713
714 for (n = 0; n < o; n++) {
715 /* Continue past numbers the adjacent square _could_ be,
716 * given the clue we have. */
717 gd = abs((n+1) - grid(x, y));
718 if (isadjacent && (gd == 1)) continue;
719 if (!isadjacent && (gd != 1)) continue;
720
721 if (!cube(nx, ny, n+1))
722 continue; /* already discounted this possibility. */
723
724#ifdef STANDALONE_SOLVER
725 if (solver_show_working) {
726 printf("%*sadjacent elimination, (%d,%d):%d %s (%d,%d):\n",
727 solver_recurse_depth*4, "",
728 x+1, y+1, grid(x, y), isadjacent ? "|" : "!|", nx+1, ny+1);
729 printf("%*s ruling out %d at (%d,%d)\n",
730 solver_recurse_depth*4, "", n+1, nx+1, ny+1);
731 }
732#endif
733 cube(nx, ny, n+1) = false;
734 nchanged++;
735 }
736 }
737 }
738 }
739
740 return nchanged;
741}
742
743static int solver_adjacent_set(struct latin_solver *solver, void *vctx)
744{
745 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
746 int x, y, i, n, nn, o = solver->o, nx, ny, gd;
747 int nchanged = 0, *scratch = snewn(o, int);
748
749 /* Update possible values based on other possible values
750 * of adjacent squares, and adjacency clues. */
751
752 for (x = 0; x < o; x++) {
753 for (y = 0; y < o; y++) {
754 for (i = 0; i < 4; i++) {
755 bool isadjacent =
756 (GRID(ctx->state, flags, x, y) & adjthan[i].f);
757
758 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
759 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
760 continue;
761
762 /* We know the current possibles for the square (x,y)
763 * and also the adjacency clue from (x,y) to (nx,ny).
764 * Construct a maximum set of possibles for (nx,ny)
765 * in scratch, based on these constraints... */
766
767 memset(scratch, 0, o*sizeof(int));
768
769 for (n = 0; n < o; n++) {
770 if (!cube(x, y, n+1)) continue;
771
772 for (nn = 0; nn < o; nn++) {
773 if (n == nn) continue;
774
775 gd = abs(nn - n);
776 if (isadjacent && (gd != 1)) continue;
777 if (!isadjacent && (gd == 1)) continue;
778
779 scratch[nn] = 1;
780 }
781 }
782
783 /* ...and remove any possibilities for (nx,ny) that are
784 * currently set but are not indicated in scratch. */
785 for (n = 0; n < o; n++) {
786 if (scratch[n] == 1) continue;
787 if (!cube(nx, ny, n+1)) continue;
788
789#ifdef STANDALONE_SOLVER
790 if (solver_show_working) {
791 printf("%*sadjacent possible elimination, (%d,%d) %s (%d,%d):\n",
792 solver_recurse_depth*4, "",
793 x+1, y+1, isadjacent ? "|" : "!|", nx+1, ny+1);
794 printf("%*s ruling out %d at (%d,%d)\n",
795 solver_recurse_depth*4, "", n+1, nx+1, ny+1);
796 }
797#endif
798 cube(nx, ny, n+1) = false;
799 nchanged++;
800 }
801 }
802 }
803 }
804
805 return nchanged;
806}
807
808static int solver_easy(struct latin_solver *solver, void *vctx)
809{
810 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
811 if (ctx->state->mode == MODE_ADJACENT)
812 return solver_adjacent(solver, vctx);
813 else
814 return solver_links(solver, vctx);
815}
816
817static int solver_set(struct latin_solver *solver, void *vctx)
818{
819 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
820 if (ctx->state->mode == MODE_ADJACENT)
821 return solver_adjacent_set(solver, vctx);
822 else
823 return 0;
824}
825
826#define SOLVER(upper,title,func,lower) func,
827static usersolver_t const unequal_solvers[] = { DIFFLIST(SOLVER) };
828
829static bool unequal_valid(struct latin_solver *solver, void *vctx)
830{
831 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
832 if (ctx->state->mode == MODE_ADJACENT) {
833 int o = solver->o;
834 int x, y, nx, ny, v, nv, i;
835
836 for (x = 0; x+1 < o; x++) {
837 for (y = 0; y+1 < o; y++) {
838 v = grid(x, y);
839 for (i = 0; i < 4; i++) {
840 bool is_adj, should_be_adj;
841
842 should_be_adj =
843 (GRID(ctx->state, flags, x, y) & adjthan[i].f);
844
845 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
846 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
847 continue;
848
849 nv = grid(nx, ny);
850 is_adj = (labs(v - nv) == 1);
851
852 if (is_adj && !should_be_adj) {
853#ifdef STANDALONE_SOLVER
854 if (solver_show_working)
855 printf("%*s(%d,%d):%d and (%d,%d):%d have "
856 "adjacent values, but should not\n",
857 solver_recurse_depth*4, "",
858 x+1, y+1, v, nx+1, ny+1, nv);
859#endif
860 return false;
861 }
862
863 if (!is_adj && should_be_adj) {
864#ifdef STANDALONE_SOLVER
865 if (solver_show_working)
866 printf("%*s(%d,%d):%d and (%d,%d):%d do not have "
867 "adjacent values, but should\n",
868 solver_recurse_depth*4, "",
869 x+1, y+1, v, nx+1, ny+1, nv);
870#endif
871 return false;
872 }
873 }
874 }
875 }
876 } else {
877 int i;
878 for (i = 0; i < ctx->nlinks; i++) {
879 struct solver_link *link = &ctx->links[i];
880 int gv = grid(link->gx, link->gy);
881 int lv = grid(link->lx, link->ly);
882 if (gv <= lv) {
883#ifdef STANDALONE_SOLVER
884 if (solver_show_working)
885 printf("%*s(%d,%d):%d should be greater than (%d,%d):%d, "
886 "but is not\n", solver_recurse_depth*4, "",
887 link->gx+1, link->gy+1, gv,
888 link->lx+1, link->ly+1, lv);
889#endif
890 return false;
891 }
892 }
893 }
894 return true;
895}
896
897static int solver_state(game_state *state, int maxdiff)
898{
899 struct solver_ctx *ctx = new_ctx(state);
900 struct latin_solver solver;
901 int diff;
902
903 if (latin_solver_alloc(&solver, state->nums, state->order))
904 diff = latin_solver_main(&solver, maxdiff,
905 DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
906 DIFF_EXTREME, DIFF_RECURSIVE,
907 unequal_solvers, unequal_valid, ctx,
908 clone_ctx, free_ctx);
909 else
910 diff = DIFF_IMPOSSIBLE;
911
912 memcpy(state->hints, solver.cube, state->order*state->order*state->order);
913
914 free_ctx(ctx);
915
916 latin_solver_free(&solver);
917
918 if (diff == DIFF_IMPOSSIBLE)
919 return -1;
920 if (diff == DIFF_UNFINISHED)
921 return 0;
922 if (diff == DIFF_AMBIGUOUS)
923 return 2;
924 return 1;
925}
926
927static game_state *solver_hint(const game_state *state, int *diff_r,
928 int mindiff, int maxdiff)
929{
930 game_state *ret = dup_game(state);
931 int diff, r = 0;
932
933 for (diff = mindiff; diff <= maxdiff; diff++) {
934 r = solver_state(ret, diff);
935 debug(("solver_state after %s %d", unequal_diffnames[diff], r));
936 if (r != 0) goto done;
937 }
938
939done:
940 if (diff_r) *diff_r = (r > 0) ? diff : -1;
941 return ret;
942}
943
944/* ----------------------------------------------------------
945 * Game generation.
946 */
947
948static char *latin_desc(digit *sq, size_t order)
949{
950 int o2 = order*order, i;
951 char *soln = snewn(o2+2, char);
952
953 soln[0] = 'S';
954 for (i = 0; i < o2; i++)
955 soln[i+1] = n2c(sq[i], order);
956 soln[o2+1] = '\0';
957
958 return soln;
959}
960
961/* returns true if it placed (or could have placed) clue. */
962static bool gg_place_clue(game_state *state, int ccode, digit *latin, bool checkonly)
963{
964 int loc = ccode / 5, which = ccode % 5;
965 int x = loc % state->order, y = loc / state->order;
966
967 assert(loc < state->order*state->order);
968
969 if (which == 4) { /* add number */
970 if (state->nums[loc] != 0) {
971#ifdef STANDALONE_SOLVER
972 if (state->nums[loc] != latin[loc]) {
973 printf("inconsistency for (%d,%d): state %d latin %d\n",
974 x+1, y+1, state->nums[loc], latin[loc]);
975 }
976#endif
977 assert(state->nums[loc] == latin[loc]);
978 return false;
979 }
980 if (!checkonly) {
981 state->nums[loc] = latin[loc];
982 }
983 } else { /* add flag */
984 int lx, ly, lloc;
985
986 if (state->mode == MODE_ADJACENT)
987 return false; /* never add flag clues in adjacent mode
988 (they're always all present) */
989
990 if (state->flags[loc] & adjthan[which].f)
991 return false; /* already has flag. */
992
993 lx = x + adjthan[which].dx;
994 ly = y + adjthan[which].dy;
995 if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order)
996 return false; /* flag compares to off grid */
997
998 lloc = loc + adjthan[which].dx + adjthan[which].dy*state->order;
999 if (latin[loc] <= latin[lloc])
1000 return false; /* flag would be incorrect */
1001
1002 if (!checkonly) {
1003 state->flags[loc] |= adjthan[which].f;
1004 }
1005 }
1006 return true;
1007}
1008
1009/* returns true if it removed (or could have removed) the clue. */
1010static bool gg_remove_clue(game_state *state, int ccode, bool checkonly)
1011{
1012 int loc = ccode / 5, which = ccode % 5;
1013#ifdef STANDALONE_SOLVER
1014 int x = loc % state->order, y = loc / state->order;
1015#endif
1016
1017 assert(loc < state->order*state->order);
1018
1019 if (which == 4) { /* remove number. */
1020 if (state->nums[loc] == 0) return false;
1021 if (!checkonly) {
1022#ifdef STANDALONE_SOLVER
1023 if (solver_show_working)
1024 printf("gg_remove_clue: removing %d at (%d,%d)",
1025 state->nums[loc], x+1, y+1);
1026#endif
1027 state->nums[loc] = 0;
1028 }
1029 } else { /* remove flag */
1030 if (state->mode == MODE_ADJACENT)
1031 return false; /* never remove clues in adjacent mode. */
1032
1033 if (!(state->flags[loc] & adjthan[which].f)) return false;
1034 if (!checkonly) {
1035#ifdef STANDALONE_SOLVER
1036 if (solver_show_working)
1037 printf("gg_remove_clue: removing %c at (%d,%d)",
1038 adjthan[which].c, x+1, y+1);
1039#endif
1040 state->flags[loc] &= ~adjthan[which].f;
1041 }
1042 }
1043 return true;
1044}
1045
1046static int gg_best_clue(game_state *state, int *scratch, digit *latin)
1047{
1048 int ls = state->order * state->order * 5;
1049 int maxposs = 0, minclues = 5, best = -1, i, j;
1050 int nposs, nclues, loc;
1051
1052#ifdef STANDALONE_SOLVER
1053 if (solver_show_working) {
1054 game_debug(state);
1055 latin_solver_debug(state->hints, state->order);
1056 }
1057#endif
1058
1059 for (i = ls; i-- > 0 ;) {
1060 if (!gg_place_clue(state, scratch[i], latin, true)) continue;
1061
1062 loc = scratch[i] / 5;
1063 for (j = nposs = 0; j < state->order; j++) {
1064 if (state->hints[loc*state->order + j]) nposs++;
1065 }
1066 for (j = nclues = 0; j < 4; j++) {
1067 if (state->flags[loc] & adjthan[j].f) nclues++;
1068 }
1069 if ((nposs > maxposs) ||
1070 (nposs == maxposs && nclues < minclues)) {
1071 best = i; maxposs = nposs; minclues = nclues;
1072#ifdef STANDALONE_SOLVER
1073 if (solver_show_working) {
1074 int x = loc % state->order, y = loc / state->order;
1075 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
1076 best, x+1, y+1, nposs, nclues);
1077 }
1078#endif
1079 }
1080 }
1081 /* if we didn't solve, we must have 1 clue to place! */
1082 assert(best != -1);
1083 return best;
1084}
1085
1086#ifdef STANDALONE_SOLVER
1087static int maxtries;
1088#define MAXTRIES maxtries
1089#else
1090#define MAXTRIES 50
1091#endif
1092static int gg_solved;
1093
1094static int game_assemble(game_state *new, int *scratch, digit *latin,
1095 int difficulty)
1096{
1097 game_state *copy = dup_game(new);
1098 int best;
1099
1100 if (difficulty >= DIFF_RECURSIVE) {
1101 /* We mustn't use any solver that might guess answers;
1102 * if it guesses wrongly but solves, gg_place_clue will
1103 * get mighty confused. We will always trim clues down
1104 * (making it more difficult) in game_strip, which doesn't
1105 * have this problem. */
1106 difficulty = DIFF_RECURSIVE-1;
1107 }
1108
1109#ifdef STANDALONE_SOLVER
1110 if (solver_show_working) {
1111 game_debug(new);
1112 latin_solver_debug(new->hints, new->order);
1113 }
1114#endif
1115
1116 while(1) {
1117 gg_solved++;
1118 if (solver_state(copy, difficulty) == 1) break;
1119
1120 best = gg_best_clue(copy, scratch, latin);
1121 gg_place_clue(new, scratch[best], latin, false);
1122 gg_place_clue(copy, scratch[best], latin, false);
1123 }
1124 free_game(copy);
1125#ifdef STANDALONE_SOLVER
1126 if (solver_show_working) {
1127 char *dbg = game_text_format(new);
1128 printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
1129 sfree(dbg);
1130 }
1131#endif
1132 return 0;
1133}
1134
1135static void game_strip(game_state *new, int *scratch, digit *latin,
1136 int difficulty)
1137{
1138 int o = new->order, o2 = o*o, lscratch = o2*5, i;
1139 game_state *copy = blank_game(new->order, new->mode);
1140
1141 /* For each symbol (if it exists in new), try and remove it and
1142 * solve again; if we couldn't solve without it put it back. */
1143 for (i = 0; i < lscratch; i++) {
1144 if (!gg_remove_clue(new, scratch[i], false)) continue;
1145
1146 memcpy(copy->nums, new->nums, o2 * sizeof(digit));
1147 memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
1148 gg_solved++;
1149 if (solver_state(copy, difficulty) != 1) {
1150 /* put clue back, we can't solve without it. */
1151 bool ret = gg_place_clue(new, scratch[i], latin, false);
1152 assert(ret);
1153 } else {
1154#ifdef STANDALONE_SOLVER
1155 if (solver_show_working)
1156 printf("game_strip: clue was redundant.");
1157#endif
1158 }
1159 }
1160 free_game(copy);
1161#ifdef STANDALONE_SOLVER
1162 if (solver_show_working) {
1163 char *dbg = game_text_format(new);
1164 debug(("game_strip: done, %d solver iterations.", gg_solved));
1165 debug(("%s", dbg));
1166 sfree(dbg);
1167 }
1168#endif
1169}
1170
1171static void add_adjacent_flags(game_state *state, digit *latin)
1172{
1173 int x, y, o = state->order;
1174
1175 /* All clues in adjacent mode are always present (the only variables are
1176 * the numbers). This adds all the flags to state based on the supplied
1177 * latin square. */
1178
1179 for (y = 0; y < o; y++) {
1180 for (x = 0; x < o; x++) {
1181 if (x < (o-1) && (abs(latin[y*o+x] - latin[y*o+x+1]) == 1)) {
1182 GRID(state, flags, x, y) |= F_ADJ_RIGHT;
1183 GRID(state, flags, x+1, y) |= F_ADJ_LEFT;
1184 }
1185 if (y < (o-1) && (abs(latin[y*o+x] - latin[(y+1)*o+x]) == 1)) {
1186 GRID(state, flags, x, y) |= F_ADJ_DOWN;
1187 GRID(state, flags, x, y+1) |= F_ADJ_UP;
1188 }
1189 }
1190 }
1191}
1192
1193static char *new_game_desc(const game_params *params_in, random_state *rs,
1194 char **aux, bool interactive)
1195{
1196 game_params params_copy = *params_in; /* structure copy */
1197 game_params *params = ¶ms_copy;
1198 digit *sq = NULL;
1199 int i, x, y, retlen, k, nsol;
1200 int o2 = params->order * params->order, ntries = 1;
1201 int *scratch, lscratch = o2*5;
1202 char *ret, buf[80];
1203 game_state *state = blank_game(params->order, params->mode);
1204
1205 /* Generate a list of 'things to strip' (randomised later) */
1206 scratch = snewn(lscratch, int);
1207 /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1208 for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1209
1210generate:
1211#ifdef STANDALONE_SOLVER
1212 if (solver_show_working)
1213 printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1214 unequal_diffnames[params->diff], ntries);
1215#endif
1216 if (sq) sfree(sq);
1217 sq = latin_generate(params->order, rs);
1218 latin_debug(sq, params->order);
1219 /* Separately shuffle the numeric and inequality clues */
1220 shuffle(scratch, lscratch/5, sizeof(int), rs);
1221 shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1222
1223 memset(state->nums, 0, o2 * sizeof(digit));
1224 memset(state->flags, 0, o2 * sizeof(unsigned int));
1225
1226 if (state->mode == MODE_ADJACENT) {
1227 /* All adjacency flags are always present. */
1228 add_adjacent_flags(state, sq);
1229 }
1230
1231 gg_solved = 0;
1232 if (game_assemble(state, scratch, sq, params->diff) < 0)
1233 goto generate;
1234 game_strip(state, scratch, sq, params->diff);
1235
1236 if (params->diff > 0) {
1237 game_state *copy = dup_game(state);
1238 nsol = solver_state(copy, params->diff-1);
1239 free_game(copy);
1240 if (nsol > 0) {
1241#ifdef STANDALONE_SOLVER
1242 if (solver_show_working)
1243 printf("game_assemble: puzzle as generated is too easy.\n");
1244#endif
1245 if (ntries < MAXTRIES) {
1246 ntries++;
1247 goto generate;
1248 }
1249#ifdef STANDALONE_SOLVER
1250 if (solver_show_working)
1251 printf("Unable to generate %s %dx%d after %d attempts.\n",
1252 unequal_diffnames[params->diff],
1253 params->order, params->order, MAXTRIES);
1254#endif
1255 params->diff--;
1256 }
1257 }
1258#ifdef STANDALONE_SOLVER
1259 if (solver_show_working)
1260 printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1261 unequal_diffnames[params->diff], ntries, gg_solved);
1262#endif
1263
1264 ret = NULL; retlen = 0;
1265 for (y = 0; y < params->order; y++) {
1266 for (x = 0; x < params->order; x++) {
1267 unsigned int f = GRID(state, flags, x, y);
1268 k = sprintf(buf, "%d%s%s%s%s,",
1269 GRID(state, nums, x, y),
1270 (f & F_ADJ_UP) ? "U" : "",
1271 (f & F_ADJ_RIGHT) ? "R" : "",
1272 (f & F_ADJ_DOWN) ? "D" : "",
1273 (f & F_ADJ_LEFT) ? "L" : "");
1274
1275 ret = sresize(ret, retlen + k + 1, char);
1276 strcpy(ret + retlen, buf);
1277 retlen += k;
1278 }
1279 }
1280 *aux = latin_desc(sq, params->order);
1281
1282 free_game(state);
1283 sfree(sq);
1284 sfree(scratch);
1285
1286 return ret;
1287}
1288
1289static game_state *load_game(const game_params *params, const char *desc,
1290 const char **why_r)
1291{
1292 game_state *state = blank_game(params->order, params->mode);
1293 const char *p = desc;
1294 int i = 0, n, o = params->order, x, y;
1295 const char *why = NULL;
1296
1297 while (*p) {
1298 while (*p >= 'a' && *p <= 'z') {
1299 i += *p - 'a' + 1;
1300 p++;
1301 }
1302 if (i >= o*o) {
1303 why = "Too much data to fill grid"; goto fail;
1304 }
1305
1306 if (*p < '0' || *p > '9') {
1307 why = "Expecting number in game description"; goto fail;
1308 }
1309 n = atoi(p);
1310 if (n < 0 || n > o) {
1311 why = "Out-of-range number in game description"; goto fail;
1312 }
1313 state->nums[i] = (digit)n;
1314 while (*p >= '0' && *p <= '9') p++; /* skip number */
1315
1316 if (state->nums[i] != 0)
1317 state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1318
1319 while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1320 switch (*p) {
1321 case 'U': state->flags[i] |= F_ADJ_UP; break;
1322 case 'R': state->flags[i] |= F_ADJ_RIGHT; break;
1323 case 'D': state->flags[i] |= F_ADJ_DOWN; break;
1324 case 'L': state->flags[i] |= F_ADJ_LEFT; break;
1325 default: why = "Expecting flag URDL in game description"; goto fail;
1326 }
1327 p++;
1328 }
1329 i++;
1330 if (i < o*o && *p != ',') {
1331 why = "Missing separator"; goto fail;
1332 }
1333 if (*p == ',') p++;
1334 }
1335 if (i < o*o) {
1336 why = "Not enough data to fill grid"; goto fail;
1337 }
1338 i = 0;
1339 for (y = 0; y < o; y++) {
1340 for (x = 0; x < o; x++) {
1341 for (n = 0; n < 4; n++) {
1342 if (GRID(state, flags, x, y) & adjthan[n].f) {
1343 int nx = x + adjthan[n].dx;
1344 int ny = y + adjthan[n].dy;
1345 /* a flag must not point us off the grid. */
1346 if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1347 why = "Flags go off grid"; goto fail;
1348 }
1349 if (params->mode == MODE_ADJACENT) {
1350 /* if one cell is adjacent to another, the other must
1351 * also be adjacent to the first. */
1352 if (!(GRID(state, flags, nx, ny) & adjthan[n].fo)) {
1353 why = "Flags contradicting each other"; goto fail;
1354 }
1355 } else {
1356 /* if one cell is GT another, the other must _not_ also
1357 * be GT the first. */
1358 if (GRID(state, flags, nx, ny) & adjthan[n].fo) {
1359 why = "Flags contradicting each other"; goto fail;
1360 }
1361 }
1362 }
1363 }
1364 }
1365 }
1366
1367 return state;
1368
1369fail:
1370 free_game(state);
1371 if (why_r) *why_r = why;
1372 return NULL;
1373}
1374
1375static key_label *game_request_keys(const game_params *params, int *nkeys)
1376{
1377 int i;
1378 int order = params->order;
1379 char off = (order > 9) ? '0' : '1';
1380 key_label *keys = snewn(order + 1, key_label);
1381 *nkeys = order + 1;
1382
1383 for(i = 0; i < order; i++) {
1384 if (i==10) off = 'a'-10;
1385 keys[i].button = i + off;
1386 keys[i].label = NULL;
1387 }
1388 keys[order].button = '\b';
1389 keys[order].label = NULL;
1390
1391 return keys;
1392}
1393
1394static game_state *new_game(midend *me, const game_params *params,
1395 const char *desc)
1396{
1397 game_state *state = load_game(params, desc, NULL);
1398 if (!state) {
1399 assert("Unable to load ?validated game.");
1400 return NULL;
1401 }
1402 return state;
1403}
1404
1405static const char *validate_desc(const game_params *params, const char *desc)
1406{
1407 const char *why = NULL;
1408 game_state *dummy = load_game(params, desc, &why);
1409 if (dummy) {
1410 free_game(dummy);
1411 assert(!why);
1412 } else
1413 assert(why);
1414 return why;
1415}
1416
1417static char *solve_game(const game_state *state, const game_state *currstate,
1418 const char *aux, const char **error)
1419{
1420 game_state *solved;
1421 int r;
1422 char *ret = NULL;
1423
1424 if (aux) return dupstr(aux);
1425
1426 solved = dup_game(state);
1427 for (r = 0; r < state->order*state->order; r++) {
1428 if (!(solved->flags[r] & F_IMMUTABLE))
1429 solved->nums[r] = 0;
1430 }
1431 r = solver_state(solved, DIFFCOUNT-1); /* always use full solver */
1432 if (r > 0) ret = latin_desc(solved->nums, solved->order);
1433 free_game(solved);
1434 return ret;
1435}
1436
1437/* ----------------------------------------------------------
1438 * Game UI input processing.
1439 */
1440
1441struct game_ui {
1442 int hx, hy; /* as for solo.c, highlight pos */
1443 bool hshow, hpencil, hcursor; /* show state, type, and ?cursor. */
1444
1445 /*
1446 * User preference option: if the user right-clicks in a square
1447 * and presses a number key to add/remove a pencil mark, do we
1448 * hide the mouse highlight again afterwards?
1449 *
1450 * Historically our answer was yes. The Android port prefers no.
1451 * There are advantages both ways, depending how much you dislike
1452 * the highlight cluttering your view. So it's a preference.
1453 */
1454 bool pencil_keep_highlight;
1455};
1456
1457static game_ui *new_ui(const game_state *state)
1458{
1459 game_ui *ui = snew(game_ui);
1460
1461 ui->hx = ui->hy = 0;
1462 ui->hpencil = false;
1463 ui->hshow = ui->hcursor = getenv_bool("PUZZLES_SHOW_CURSOR", false);
1464
1465 ui->pencil_keep_highlight = false;
1466
1467 return ui;
1468}
1469
1470static void free_ui(game_ui *ui)
1471{
1472 sfree(ui);
1473}
1474
1475static config_item *get_prefs(game_ui *ui)
1476{
1477 config_item *ret;
1478
1479 ret = snewn(N_PREF_ITEMS+1, config_item);
1480
1481 ret[PREF_PENCIL_KEEP_HIGHLIGHT].name =
1482 "Keep mouse highlight after changing a pencil mark";
1483 ret[PREF_PENCIL_KEEP_HIGHLIGHT].kw = "pencil-keep-highlight";
1484 ret[PREF_PENCIL_KEEP_HIGHLIGHT].type = C_BOOLEAN;
1485 ret[PREF_PENCIL_KEEP_HIGHLIGHT].u.boolean.bval = ui->pencil_keep_highlight;
1486
1487 ret[N_PREF_ITEMS].name = NULL;
1488 ret[N_PREF_ITEMS].type = C_END;
1489
1490 return ret;
1491}
1492
1493static void set_prefs(game_ui *ui, const config_item *cfg)
1494{
1495 ui->pencil_keep_highlight = cfg[PREF_PENCIL_KEEP_HIGHLIGHT].u.boolean.bval;
1496}
1497
1498static void game_changed_state(game_ui *ui, const game_state *oldstate,
1499 const game_state *newstate)
1500{
1501 /* See solo.c; if we were pencil-mode highlighting and
1502 * somehow a square has just been properly filled, cancel
1503 * pencil mode. */
1504 if (ui->hshow && ui->hpencil && !ui->hcursor &&
1505 GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1506 ui->hshow = false;
1507 }
1508}
1509
1510static const char *current_key_label(const game_ui *ui,
1511 const game_state *state, int button)
1512{
1513 if (ui->hshow && IS_CURSOR_SELECT(button))
1514 return ui->hpencil ? "Ink" : "Pencil";
1515 return "";
1516}
1517
1518struct game_drawstate {
1519 int tilesize, order;
1520 bool started;
1521 Mode mode;
1522 digit *nums; /* copy of nums, o^2 */
1523 unsigned char *hints; /* copy of hints, o^3 */
1524 unsigned int *flags; /* o^2 */
1525
1526 int hx, hy;
1527 bool hshow, hpencil; /* as for game_ui. */
1528 bool hflash;
1529};
1530
1531static char *interpret_move(const game_state *state, game_ui *ui,
1532 const game_drawstate *ds,
1533 int ox, int oy, int button)
1534{
1535 int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1536 char buf[80];
1537 bool shift_or_control = button & (MOD_SHFT | MOD_CTRL);
1538
1539 button = STRIP_BUTTON_MODIFIERS(button);
1540
1541 if (x >= 0 && x < ds->order && y >= 0 && y < ds->order && IS_MOUSE_DOWN(button)) {
1542 if (oy - COORD(y) > TILE_SIZE && ox - COORD(x) > TILE_SIZE)
1543 return NULL;
1544
1545 if (oy - COORD(y) > TILE_SIZE) {
1546 if (GRID(state, flags, x, y) & F_ADJ_DOWN)
1547 sprintf(buf, "F%d,%d,%d", x, y, F_SPENT_DOWN);
1548 else if (y + 1 < ds->order && GRID(state, flags, x, y + 1) & F_ADJ_UP)
1549 sprintf(buf, "F%d,%d,%d", x, y + 1, F_SPENT_UP);
1550 else return NULL;
1551 return dupstr(buf);
1552 }
1553
1554 if (ox - COORD(x) > TILE_SIZE) {
1555 if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
1556 sprintf(buf, "F%d,%d,%d", x, y, F_SPENT_RIGHT);
1557 else if (x + 1 < ds->order && GRID(state, flags, x + 1, y) & F_ADJ_LEFT)
1558 sprintf(buf, "F%d,%d,%d", x + 1, y, F_SPENT_LEFT);
1559 else return NULL;
1560 return dupstr(buf);
1561 }
1562
1563 if (button == LEFT_BUTTON) {
1564 /* normal highlighting for non-immutable squares */
1565 if (GRID(state, flags, x, y) & F_IMMUTABLE)
1566 ui->hshow = false;
1567 else if (x == ui->hx && y == ui->hy &&
1568 ui->hshow && !ui->hpencil)
1569 ui->hshow = false;
1570 else {
1571 ui->hx = x; ui->hy = y; ui->hpencil = false;
1572 ui->hshow = true;
1573 }
1574 ui->hcursor = false;
1575 return MOVE_UI_UPDATE;
1576 }
1577 if (button == RIGHT_BUTTON) {
1578 /* pencil highlighting for non-filled squares */
1579 if (GRID(state, nums, x, y) != 0)
1580 ui->hshow = false;
1581 else if (x == ui->hx && y == ui->hy &&
1582 ui->hshow && ui->hpencil)
1583 ui->hshow = false;
1584 else {
1585 ui->hx = x; ui->hy = y; ui->hpencil = true;
1586 ui->hshow = true;
1587 }
1588 ui->hcursor = false;
1589 return MOVE_UI_UPDATE;
1590 }
1591 }
1592
1593 if (IS_CURSOR_MOVE(button)) {
1594 if (shift_or_control) {
1595 int nx = ui->hx, ny = ui->hy, i;
1596 bool self;
1597 move_cursor(button, &nx, &ny, ds->order, ds->order, false, NULL);
1598 ui->hshow = true;
1599 ui->hcursor = true;
1600
1601 for (i = 0; i < 4 && (nx != ui->hx + adjthan[i].dx ||
1602 ny != ui->hy + adjthan[i].dy); ++i);
1603
1604 if (i == 4)
1605 return MOVE_UI_UPDATE; /* invalid direction, i.e. out of
1606 * the board */
1607
1608 if (!(GRID(state, flags, ui->hx, ui->hy) & adjthan[i].f ||
1609 GRID(state, flags, nx, ny ) & adjthan[i].fo))
1610 return MOVE_UI_UPDATE; /* no clue to toggle */
1611
1612 if (state->mode == MODE_ADJACENT)
1613 self = (adjthan[i].dx >= 0 && adjthan[i].dy >= 0);
1614 else
1615 self = (GRID(state, flags, ui->hx, ui->hy) & adjthan[i].f);
1616
1617 if (self)
1618 sprintf(buf, "F%d,%d,%u", ui->hx, ui->hy,
1619 ADJ_TO_SPENT(adjthan[i].f));
1620 else
1621 sprintf(buf, "F%d,%d,%u", nx, ny,
1622 ADJ_TO_SPENT(adjthan[i].fo));
1623
1624 return dupstr(buf);
1625 } else {
1626 ui->hcursor = true;
1627 return move_cursor(button, &ui->hx, &ui->hy, ds->order, ds->order,
1628 false, &ui->hshow);
1629 }
1630 }
1631 if (ui->hshow && IS_CURSOR_SELECT(button)) {
1632 ui->hpencil = !ui->hpencil;
1633 ui->hcursor = true;
1634 return MOVE_UI_UPDATE;
1635 }
1636
1637 n = c2n(button, state->order);
1638 if (ui->hshow && n >= 0 && n <= ds->order) {
1639 debug(("button %d, cbutton %d", button, (int)((char)button)));
1640
1641 debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1642 n, ui->hx, ui->hy, ui->hpencil,
1643 GRID(state, flags, ui->hx, ui->hy),
1644 GRID(state, nums, ui->hx, ui->hy)));
1645
1646 if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE)
1647 return NULL; /* can't edit immutable square (!) */
1648 if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0)
1649 return NULL; /* can't change hints on filled square (!) */
1650
1651 /*
1652 * If you ask to fill a square with what it already contains,
1653 * or blank it when it's already empty, that has no effect...
1654 */
1655 if ((!ui->hpencil || n == 0) &&
1656 GRID(state, nums, ui->hx, ui->hy) == n) {
1657 bool anypencil = false;
1658 int i;
1659 for (i = 0; i < state->order; i++)
1660 anypencil = anypencil || HINT(state, ui->hx, ui->hy, i);
1661 if (!anypencil) {
1662 /* ... expect to remove the cursor in mouse mode. */
1663 if (!ui->hcursor) {
1664 ui->hshow = false;
1665 return MOVE_UI_UPDATE;
1666 }
1667 return NULL;
1668 }
1669 }
1670
1671 sprintf(buf, "%c%d,%d,%d",
1672 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1673
1674 /*
1675 * Hide the highlight after a keypress, if it was mouse-
1676 * generated. Also, don't hide it if this move has changed
1677 * pencil marks and the user preference says not to hide the
1678 * highlight in that situation.
1679 */
1680 if (!ui->hcursor && !(ui->hpencil && ui->pencil_keep_highlight))
1681 ui->hshow = false;
1682
1683 return dupstr(buf);
1684 }
1685
1686 if (button == 'H' || button == 'h')
1687 return dupstr("H");
1688 if (button == 'M' || button == 'm')
1689 return dupstr("M");
1690
1691 return NULL;
1692}
1693
1694static game_state *execute_move(const game_state *state, const char *move)
1695{
1696 game_state *ret = NULL;
1697 int x, y, n, i;
1698
1699 debug(("execute_move: %s", move));
1700
1701 if ((move[0] == 'P' || move[0] == 'R') &&
1702 sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1703 x >= 0 && x < state->order && y >= 0 && y < state->order &&
1704 n >= 0 && n <= state->order) {
1705 ret = dup_game(state);
1706 if (move[0] == 'P' && n > 0)
1707 HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1);
1708 else {
1709 GRID(ret, nums, x, y) = n;
1710 for (i = 0; i < state->order; i++)
1711 HINT(ret, x, y, i) = 0;
1712
1713 /* real change to grid; check for completion */
1714 if (!ret->completed && check_complete(ret->nums, ret, true) > 0)
1715 ret->completed = true;
1716 }
1717 return ret;
1718 } else if (move[0] == 'S') {
1719 const char *p;
1720
1721 ret = dup_game(state);
1722 ret->cheated = true;
1723
1724 p = move+1;
1725 for (i = 0; i < state->order*state->order; i++) {
1726 n = c2n((int)*p, state->order);
1727 if (!*p || n <= 0 || n > state->order)
1728 goto badmove;
1729 ret->nums[i] = n;
1730 p++;
1731 }
1732 if (*p) goto badmove;
1733 if (!ret->completed && check_complete(ret->nums, ret, true) > 0)
1734 ret->completed = true;
1735 return ret;
1736 } else if (move[0] == 'M') {
1737 ret = dup_game(state);
1738 for (x = 0; x < state->order; x++) {
1739 for (y = 0; y < state->order; y++) {
1740 for (n = 0; n < state->order; n++) {
1741 HINT(ret, x, y, n) = 1;
1742 }
1743 }
1744 }
1745 return ret;
1746 } else if (move[0] == 'H') {
1747 ret = solver_hint(state, NULL, DIFF_EASY, DIFF_EASY);
1748 check_complete(ret->nums, ret, true);
1749 return ret;
1750 } else if (move[0] == 'F' && sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1751 x >= 0 && x < state->order && y >= 0 && y < state->order &&
1752 (n & ~F_SPENT_MASK) == 0) {
1753 ret = dup_game(state);
1754 GRID(ret, flags, x, y) ^= n;
1755 return ret;
1756 }
1757
1758badmove:
1759 if (ret) free_game(ret);
1760 return NULL;
1761}
1762
1763/* ----------------------------------------------------------------------
1764 * Drawing/printing routines.
1765 */
1766
1767#define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1768
1769static void game_compute_size(const game_params *params, int tilesize,
1770 const game_ui *ui, int *x, int *y)
1771{
1772 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1773 struct { int tilesize, order; } ads, *ds = &ads;
1774 ads.tilesize = tilesize;
1775 ads.order = params->order;
1776
1777 *x = *y = DRAW_SIZE;
1778}
1779
1780static void game_set_size(drawing *dr, game_drawstate *ds,
1781 const game_params *params, int tilesize)
1782{
1783 ds->tilesize = tilesize;
1784}
1785
1786static float *game_colours(frontend *fe, int *ncolours)
1787{
1788 float *ret = snewn(3 * NCOLOURS, float);
1789 int i;
1790
1791 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1792
1793 for (i = 0; i < 3; i++) {
1794 ret[COL_TEXT * 3 + i] = 0.0F;
1795 ret[COL_GRID * 3 + i] = 0.5F;
1796 }
1797
1798 /* Lots of these were taken from solo.c. */
1799 ret[COL_GUESS * 3 + 0] = 0.0F;
1800 ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1801 ret[COL_GUESS * 3 + 2] = 0.0F;
1802
1803 ret[COL_ERROR * 3 + 0] = 1.0F;
1804 ret[COL_ERROR * 3 + 1] = 0.0F;
1805 ret[COL_ERROR * 3 + 2] = 0.0F;
1806
1807 ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1808 ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1809 ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1810
1811 *ncolours = NCOLOURS;
1812 return ret;
1813}
1814
1815static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1816{
1817 struct game_drawstate *ds = snew(struct game_drawstate);
1818 int o2 = state->order*state->order, o3 = o2*state->order;
1819
1820 ds->tilesize = 0;
1821 ds->order = state->order;
1822 ds->mode = state->mode;
1823
1824 ds->nums = snewn(o2, digit);
1825 ds->hints = snewn(o3, unsigned char);
1826 ds->flags = snewn(o2, unsigned int);
1827 memset(ds->nums, 0, o2*sizeof(digit));
1828 memset(ds->hints, 0, o3);
1829 memset(ds->flags, 0, o2*sizeof(unsigned int));
1830
1831 ds->hx = ds->hy = 0;
1832 ds->started = false;
1833 ds->hshow = false;
1834 ds->hpencil = false;
1835 ds->hflash = false;
1836
1837 return ds;
1838}
1839
1840static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1841{
1842 sfree(ds->nums);
1843 sfree(ds->hints);
1844 sfree(ds->flags);
1845 sfree(ds);
1846}
1847
1848static void draw_gt(drawing *dr, int ox, int oy,
1849 int dx1, int dy1, int dx2, int dy2, int col)
1850{
1851 int coords[12];
1852 int xdx = (dx1+dx2 ? 0 : 1), xdy = (dx1+dx2 ? 1 : 0);
1853 coords[0] = ox + xdx;
1854 coords[1] = oy + xdy;
1855 coords[2] = ox + xdx + dx1;
1856 coords[3] = oy + xdy + dy1;
1857 coords[4] = ox + xdx + dx1 + dx2;
1858 coords[5] = oy + xdy + dy1 + dy2;
1859 coords[6] = ox - xdx + dx1 + dx2;
1860 coords[7] = oy - xdy + dy1 + dy2;
1861 coords[8] = ox - xdx + dx1;
1862 coords[9] = oy - xdy + dy1;
1863 coords[10] = ox - xdx;
1864 coords[11] = oy - xdy;
1865 draw_polygon(dr, coords, 6, col, col);
1866}
1867
1868#define COLOUR(direction) (f & (F_ERROR_##direction) ? COL_ERROR : \
1869 f & (F_SPENT_##direction) ? COL_SPENT : fg)
1870
1871static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy,
1872 unsigned int f, int bg, int fg)
1873{
1874 int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4;
1875
1876 /* Draw all the greater-than signs emanating from this tile. */
1877
1878 if (f & F_ADJ_UP) {
1879 if (bg >= 0) draw_rect(dr, ox, oy - g, TILE_SIZE, g, bg);
1880 draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2, COLOUR(UP));
1881 draw_update(dr, ox, oy-g, TILE_SIZE, g);
1882 }
1883 if (f & F_ADJ_RIGHT) {
1884 if (bg >= 0) draw_rect(dr, ox + TILE_SIZE, oy, g, TILE_SIZE, bg);
1885 draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2, COLOUR(RIGHT));
1886 draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1887 }
1888 if (f & F_ADJ_DOWN) {
1889 if (bg >= 0) draw_rect(dr, ox, oy + TILE_SIZE, TILE_SIZE, g, bg);
1890 draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2, COLOUR(DOWN));
1891 draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1892 }
1893 if (f & F_ADJ_LEFT) {
1894 if (bg >= 0) draw_rect(dr, ox - g, oy, g, TILE_SIZE, bg);
1895 draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2, COLOUR(LEFT));
1896 draw_update(dr, ox-g, oy, g, TILE_SIZE);
1897 }
1898}
1899
1900static void draw_adjs(drawing *dr, game_drawstate *ds, int ox, int oy,
1901 unsigned int f, int bg, int fg)
1902{
1903 int g = GAP_SIZE, g38 = 3*(g+1)/8, g4 = (g+1)/4;
1904
1905 /* Draw all the adjacency bars relevant to this tile; we only have
1906 * to worry about F_ADJ_RIGHT and F_ADJ_DOWN.
1907 *
1908 * If we _only_ have the error flag set (i.e. it's not supposed to be
1909 * adjacent, but adjacent numbers were entered) draw an outline red bar.
1910 */
1911
1912 if (f & (F_ADJ_RIGHT|F_ERROR_RIGHT)) {
1913 if (f & F_ADJ_RIGHT) {
1914 draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COLOUR(RIGHT));
1915 } else {
1916 draw_rect_outline(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COL_ERROR);
1917 }
1918 } else if (bg >= 0) {
1919 draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, bg);
1920 }
1921 draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1922
1923 if (f & (F_ADJ_DOWN|F_ERROR_DOWN)) {
1924 if (f & F_ADJ_DOWN) {
1925 draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COLOUR(DOWN));
1926 } else {
1927 draw_rect_outline(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COL_ERROR);
1928 }
1929 } else if (bg >= 0) {
1930 draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, bg);
1931 }
1932 draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1933}
1934
1935static void draw_furniture(drawing *dr, game_drawstate *ds,
1936 const game_state *state, const game_ui *ui,
1937 int x, int y, bool hflash)
1938{
1939 int ox = COORD(x), oy = COORD(y), bg;
1940 bool hon;
1941 unsigned int f = GRID(state, flags, x, y);
1942
1943 bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1944
1945 hon = (ui->hshow && x == ui->hx && y == ui->hy);
1946
1947 /* Clear square. */
1948 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1949 (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1950
1951 /* Draw the highlight (pencil or full), if we're the highlight */
1952 if (hon && ui->hpencil) {
1953 int coords[6];
1954 coords[0] = ox;
1955 coords[1] = oy;
1956 coords[2] = ox + TILE_SIZE/2;
1957 coords[3] = oy;
1958 coords[4] = ox;
1959 coords[5] = oy + TILE_SIZE/2;
1960 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1961 }
1962
1963 /* Draw the square outline (which is the cursor, if we're the cursor). */
1964 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
1965
1966 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1967
1968 /* Draw the adjacent clue signs. */
1969 if (ds->mode == MODE_ADJACENT)
1970 draw_adjs(dr, ds, ox, oy, f, COL_BACKGROUND, COL_GRID);
1971 else
1972 draw_gts(dr, ds, ox, oy, f, COL_BACKGROUND, COL_TEXT);
1973}
1974
1975static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1976{
1977 int ox = COORD(x), oy = COORD(y);
1978 unsigned int f = GRID(ds,flags,x,y);
1979 char str[2];
1980
1981 /* (can assume square has just been cleared) */
1982
1983 /* Draw number, choosing appropriate colour */
1984 str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1985 str[1] = '\0';
1986 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1987 FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1988 (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1989}
1990
1991static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1992{
1993 int ox = COORD(x), oy = COORD(y);
1994 int nhints, i, j, hw, hh, hmax, fontsz;
1995 char str[2];
1996
1997 /* (can assume square has just been cleared) */
1998
1999 /* Draw hints; steal ingenious algorithm (basically)
2000 * from solo.c:draw_number() */
2001 for (i = nhints = 0; i < ds->order; i++) {
2002 if (HINT(ds, x, y, i)) nhints++;
2003 }
2004
2005 for (hw = 1; hw * hw < nhints; hw++);
2006 if (hw < 3) hw = 3;
2007 hh = (nhints + hw - 1) / hw;
2008 if (hh < 2) hh = 2;
2009 hmax = max(hw, hh);
2010 fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
2011
2012 for (i = j = 0; i < ds->order; i++) {
2013 if (HINT(ds,x,y,i)) {
2014 int hx = j % hw, hy = j / hw;
2015
2016 str[0] = n2c(i+1, ds->order);
2017 str[1] = '\0';
2018 draw_text(dr,
2019 ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
2020 oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
2021 FONT_VARIABLE, fontsz,
2022 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
2023 j++;
2024 }
2025 }
2026}
2027
2028static void game_redraw(drawing *dr, game_drawstate *ds,
2029 const game_state *oldstate, const game_state *state,
2030 int dir, const game_ui *ui,
2031 float animtime, float flashtime)
2032{
2033 int x, y, i;
2034 bool hchanged = false, stale, hflash = false;
2035
2036 debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
2037
2038 if (flashtime > 0 &&
2039 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
2040 hflash = true;
2041
2042 if (!ds->started) {
2043 draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
2044 draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
2045 }
2046 if (ds->hx != ui->hx || ds->hy != ui->hy ||
2047 ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
2048 hchanged = true;
2049
2050 for (x = 0; x < ds->order; x++) {
2051 for (y = 0; y < ds->order; y++) {
2052 if (!ds->started)
2053 stale = true;
2054 else if (hflash != ds->hflash)
2055 stale = true;
2056 else
2057 stale = false;
2058
2059 if (hchanged) {
2060 if ((x == ui->hx && y == ui->hy) ||
2061 (x == ds->hx && y == ds->hy))
2062 stale = true;
2063 }
2064
2065 if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
2066 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
2067 stale = true;
2068 }
2069 if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
2070 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
2071 stale = true;
2072 }
2073 if (GRID(ds, nums, x, y) == 0) {
2074 /* We're not a number square (therefore we might
2075 * display hints); do we need to update? */
2076 for (i = 0; i < ds->order; i++) {
2077 if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
2078 HINT(ds, x, y, i) = HINT(state, x, y, i);
2079 stale = true;
2080 }
2081 }
2082 }
2083 if (stale) {
2084 draw_furniture(dr, ds, state, ui, x, y, hflash);
2085 if (GRID(ds, nums, x, y) > 0)
2086 draw_num(dr, ds, x, y);
2087 else
2088 draw_hints(dr, ds, x, y);
2089 }
2090 }
2091 }
2092 ds->hx = ui->hx; ds->hy = ui->hy;
2093 ds->hshow = ui->hshow;
2094 ds->hpencil = ui->hpencil;
2095
2096 ds->started = true;
2097 ds->hflash = hflash;
2098}
2099
2100static float game_anim_length(const game_state *oldstate,
2101 const game_state *newstate, int dir, game_ui *ui)
2102{
2103 return 0.0F;
2104}
2105
2106static float game_flash_length(const game_state *oldstate,
2107 const game_state *newstate, int dir, game_ui *ui)
2108{
2109 if (!oldstate->completed && newstate->completed &&
2110 !oldstate->cheated && !newstate->cheated)
2111 return FLASH_TIME;
2112 return 0.0F;
2113}
2114
2115static void game_get_cursor_location(const game_ui *ui,
2116 const game_drawstate *ds,
2117 const game_state *state,
2118 const game_params *params,
2119 int *x, int *y, int *w, int *h)
2120{
2121 if(ui->hshow) {
2122 *x = COORD(ui->hx);
2123 *y = COORD(ui->hy);
2124 *w = *h = TILE_SIZE;
2125 }
2126}
2127
2128static int game_status(const game_state *state)
2129{
2130 return state->completed ? +1 : 0;
2131}
2132
2133static void game_print_size(const game_params *params, const game_ui *ui,
2134 float *x, float *y)
2135{
2136 int pw, ph;
2137
2138 /* 10mm squares by default, roughly the same as Grauniad. */
2139 game_compute_size(params, 1000, ui, &pw, &ph);
2140 *x = pw / 100.0F;
2141 *y = ph / 100.0F;
2142}
2143
2144static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
2145 int tilesize)
2146{
2147 int ink = print_mono_colour(dr, 0);
2148 int x, y, o = state->order, ox, oy, n;
2149 char str[2];
2150
2151 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2152 game_drawstate ads, *ds = &ads;
2153 game_set_size(dr, ds, NULL, tilesize);
2154
2155 print_line_width(dr, 2 * TILE_SIZE / 40);
2156
2157 /* Squares, numbers, gt signs */
2158 for (y = 0; y < o; y++) {
2159 for (x = 0; x < o; x++) {
2160 ox = COORD(x); oy = COORD(y);
2161 n = GRID(state, nums, x, y);
2162
2163 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
2164
2165 str[0] = n ? n2c(n, state->order) : ' ';
2166 str[1] = '\0';
2167 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
2168 FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
2169 ink, str);
2170
2171 if (state->mode == MODE_ADJACENT)
2172 draw_adjs(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
2173 else
2174 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
2175 }
2176 }
2177}
2178
2179/* ----------------------------------------------------------------------
2180 * Housekeeping.
2181 */
2182
2183#ifdef COMBINED
2184#define thegame unequal
2185#endif
2186
2187const struct game thegame = {
2188 "Unequal", "games.unequal", "unequal",
2189 default_params,
2190 game_fetch_preset, NULL,
2191 decode_params,
2192 encode_params,
2193 free_params,
2194 dup_params,
2195 true, game_configure, custom_params,
2196 validate_params,
2197 new_game_desc,
2198 validate_desc,
2199 new_game,
2200 dup_game,
2201 free_game,
2202 true, solve_game,
2203 true, game_can_format_as_text_now, game_text_format,
2204 get_prefs, set_prefs,
2205 new_ui,
2206 free_ui,
2207 NULL, /* encode_ui */
2208 NULL, /* decode_ui */
2209 game_request_keys,
2210 game_changed_state,
2211 current_key_label,
2212 interpret_move,
2213 execute_move,
2214 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2215 game_colours,
2216 game_new_drawstate,
2217 game_free_drawstate,
2218 game_redraw,
2219 game_anim_length,
2220 game_flash_length,
2221 game_get_cursor_location,
2222 game_status,
2223 true, false, game_print_size, game_print,
2224 false, /* wants_statusbar */
2225 false, NULL, /* timing_state */
2226 REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */
2227};
2228
2229/* ----------------------------------------------------------------------
2230 * Standalone solver.
2231 */
2232
2233#ifdef STANDALONE_SOLVER
2234
2235#include <time.h>
2236#include <stdarg.h>
2237
2238static const char *quis = NULL;
2239
2240#if 0 /* currently unused */
2241
2242static void debug_printf(const char *fmt, ...)
2243{
2244 char buf[4096];
2245 va_list ap;
2246
2247 va_start(ap, fmt);
2248 vsprintf(buf, fmt, ap);
2249 puts(buf);
2250 va_end(ap);
2251}
2252
2253static void game_printf(game_state *state)
2254{
2255 char *dbg = game_text_format(state);
2256 printf("%s", dbg);
2257 sfree(dbg);
2258}
2259
2260static void game_printf_wide(game_state *state)
2261{
2262 int x, y, i, n;
2263
2264 for (y = 0; y < state->order; y++) {
2265 for (x = 0; x < state->order; x++) {
2266 n = GRID(state, nums, x, y);
2267 for (i = 0; i < state->order; i++) {
2268 if (n > 0)
2269 printf("%c", n2c(n, state->order));
2270 else if (HINT(state, x, y, i))
2271 printf("%c", n2c(i+1, state->order));
2272 else
2273 printf(".");
2274 }
2275 printf(" ");
2276 }
2277 printf("\n");
2278 }
2279 printf("\n");
2280}
2281
2282#endif
2283
2284static void pdiff(int diff)
2285{
2286 if (diff == DIFF_IMPOSSIBLE)
2287 printf("Game is impossible.\n");
2288 else if (diff == DIFF_UNFINISHED)
2289 printf("Game has incomplete.\n");
2290 else if (diff == DIFF_AMBIGUOUS)
2291 printf("Game has multiple solutions.\n");
2292 else
2293 printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
2294}
2295
2296static int solve(game_params *p, char *desc, int debug)
2297{
2298 game_state *state = new_game(NULL, p, desc);
2299 struct solver_ctx *ctx = new_ctx(state);
2300 struct latin_solver solver;
2301 int diff;
2302
2303 solver_show_working = debug;
2304 game_debug(state);
2305
2306 if (latin_solver_alloc(&solver, state->nums, state->order))
2307 diff = latin_solver_main(&solver, DIFF_RECURSIVE,
2308 DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
2309 DIFF_EXTREME, DIFF_RECURSIVE,
2310 unequal_solvers, unequal_valid, ctx,
2311 clone_ctx, free_ctx);
2312 else
2313 diff = DIFF_IMPOSSIBLE;
2314
2315 free_ctx(ctx);
2316
2317 latin_solver_free(&solver);
2318
2319 if (debug) pdiff(diff);
2320
2321 game_debug(state);
2322 free_game(state);
2323 return diff;
2324}
2325
2326static void check(game_params *p)
2327{
2328 const char *msg = validate_params(p, true);
2329 if (msg) {
2330 fprintf(stderr, "%s: %s", quis, msg);
2331 exit(1);
2332 }
2333}
2334
2335static int gen(game_params *p, random_state *rs, int debug)
2336{
2337 char *desc, *aux;
2338 int diff;
2339
2340 check(p);
2341
2342 solver_show_working = debug;
2343 desc = new_game_desc(p, rs, &aux, false);
2344 diff = solve(p, desc, debug);
2345 sfree(aux);
2346 sfree(desc);
2347
2348 return diff;
2349}
2350
2351static void soak(game_params *p, random_state *rs)
2352{
2353 time_t tt_start, tt_now, tt_last;
2354 char *aux, *desc;
2355 game_state *st;
2356 int n = 0, neasy = 0, realdiff = p->diff;
2357
2358 check(p);
2359
2360 solver_show_working = 0;
2361 maxtries = 1;
2362
2363 tt_start = tt_now = time(NULL);
2364
2365 printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2366 p->mode == MODE_ADJACENT ? "adjacent" : "unequal",
2367 p->order, p->order, unequal_diffnames[p->diff]);
2368
2369 while (1) {
2370 p->diff = realdiff;
2371 desc = new_game_desc(p, rs, &aux, false);
2372 st = new_game(NULL, p, desc);
2373 solver_state(st, DIFF_RECURSIVE);
2374 free_game(st);
2375 sfree(aux);
2376 sfree(desc);
2377
2378 n++;
2379 if (realdiff != p->diff) neasy++;
2380
2381 tt_last = time(NULL);
2382 if (tt_last > tt_now) {
2383 tt_now = tt_last;
2384 printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2385 n, (double)n / ((double)tt_now - tt_start),
2386 neasy, (double)neasy*100.0/(double)n,
2387 (double)(n - neasy) / ((double)tt_now - tt_start));
2388 }
2389 }
2390}
2391
2392static void usage_exit(const char *msg)
2393{
2394 if (msg)
2395 fprintf(stderr, "%s: %s\n", quis, msg);
2396 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
2397 exit(1);
2398}
2399
2400int main(int argc, const char *argv[])
2401{
2402 random_state *rs;
2403 time_t seed = time(NULL);
2404 int do_soak = 0, diff;
2405
2406 game_params *p;
2407
2408 maxtries = 50;
2409
2410 quis = argv[0];
2411 while (--argc > 0) {
2412 const char *p = *++argv;
2413 if (!strcmp(p, "--soak"))
2414 do_soak = 1;
2415 else if (!strcmp(p, "--seed")) {
2416 if (argc == 0)
2417 usage_exit("--seed needs an argument");
2418 seed = (time_t)atoi(*++argv);
2419 argc--;
2420 } else if (*p == '-')
2421 usage_exit("unrecognised option");
2422 else
2423 break;
2424 }
2425 rs = random_new((void*)&seed, sizeof(time_t));
2426
2427 if (do_soak == 1) {
2428 if (argc != 1) usage_exit("only one argument for --soak");
2429 p = default_params();
2430 decode_params(p, *argv);
2431 soak(p, rs);
2432 } else if (argc > 0) {
2433 int i;
2434 for (i = 0; i < argc; i++) {
2435 const char *id = *argv++;
2436 char *desc = strchr(id, ':');
2437 const char *err;
2438 p = default_params();
2439 if (desc) {
2440 *desc++ = '\0';
2441 decode_params(p, id);
2442 err = validate_desc(p, desc);
2443 if (err) {
2444 fprintf(stderr, "%s: %s\n", quis, err);
2445 exit(1);
2446 }
2447 solve(p, desc, 1);
2448 } else {
2449 decode_params(p, id);
2450 diff = gen(p, rs, 1);
2451 }
2452 }
2453 } else {
2454 while(1) {
2455 p = default_params();
2456 p->order = random_upto(rs, 7) + 3;
2457 p->diff = random_upto(rs, 4);
2458 diff = gen(p, rs, 0);
2459 pdiff(diff);
2460 }
2461 }
2462
2463 return 0;
2464}
2465
2466#endif
2467
2468/* vim: set shiftwidth=4 tabstop=8: */