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