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