4 * Implementation of 'Futoshiki', a puzzle featured in the Guardian.
7 * add multiple-links-on-same-col/row solver nous
8 * Optimise set solver to use bit operations instead
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,
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,
27 #include "latin.h" /* contains typedef for digit */
29 /* ----------------------------------------------------------
30 * Constant and structure definitions
33 #define FLASH_TIME 0.4F
35 #define PREFERRED_TILE_SIZE 32
37 #define TILE_SIZE (ds->tilesize)
38 #define GAP_SIZE (TILE_SIZE/2)
39 #define SQUARE_SIZE (TILE_SIZE + GAP_SIZE)
41 #define BORDER (TILE_SIZE / 2)
43 #define COORD(x) ( (x) * SQUARE_SIZE + BORDER )
44 #define FROMCOORD(x) ( ((x) - BORDER + SQUARE_SIZE) / SQUARE_SIZE - 1 )
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)
53 COL_TEXT, COL_GUESS, COL_ERROR, COL_PENCIL,
54 COL_HIGHLIGHT, COL_LOWLIGHT,
59 int order; /* Size of latin square */
60 int diff; /* Difficulty */
61 int adjacent; /* Puzzle indicators are 'adjacent number'
62 not 'greater-than'. */
65 #define F_IMMUTABLE 1 /* passed in as game description */
72 #define F_ERROR_RIGHT 128
73 #define F_ERROR_DOWN 256
74 #define F_ERROR_LEFT 512
76 #define F_ERROR_MASK (F_ERROR|F_ERROR_UP|F_ERROR_RIGHT|F_ERROR_DOWN|F_ERROR_LEFT)
79 int order, completed, cheated, adjacent;
80 digit *nums; /* actual numbers (size order^2) */
81 unsigned char *hints; /* remaining possiblities (size order^3) */
82 unsigned int *flags; /* flags (size order^2) */
85 /* ----------------------------------------------------------
86 * Game parameters and presets
89 /* Steal the method from map.c for difficulty levels. */
94 A(EXTREME,Extreme,x) \
95 A(RECURSIVE,Recursive,r)
97 #define ENUM(upper,title,lower) DIFF_ ## upper,
98 #define TITLE(upper,title,lower) #title,
99 #define ENCODE(upper,title,lower) #lower
100 #define CONFIG(upper,title,lower) ":" #title
101 enum { DIFFLIST(ENUM) DIFF_IMPOSSIBLE = diff_impossible, DIFF_AMBIGUOUS = diff_ambiguous, DIFF_UNFINISHED = diff_unfinished };
102 static char const *const unequal_diffnames[] = { DIFFLIST(TITLE) };
103 static char const unequal_diffchars[] = DIFFLIST(ENCODE);
104 #define DIFFCOUNT lenof(unequal_diffchars)
105 #define DIFFCONFIG DIFFLIST(CONFIG)
107 #define DEFAULT_PRESET 0
109 const static struct game_params unequal_presets[] = {
114 { 5, DIFF_EXTREME, 0 },
118 { 6, DIFF_EXTREME, 0 },
121 { 7, DIFF_EXTREME, 0 }
124 static int game_fetch_preset(int i, char **name, game_params **params)
129 if (i < 0 || i >= lenof(unequal_presets))
132 ret = snew(game_params);
133 *ret = unequal_presets[i]; /* structure copy */
135 sprintf(buf, "%s: %dx%d %s",
136 ret->adjacent ? "Adjacent" : "Unequal",
137 ret->order, ret->order,
138 unequal_diffnames[ret->diff]);
145 static game_params *default_params(void)
150 if (!game_fetch_preset(DEFAULT_PRESET, &name, &ret)) return NULL;
155 static void free_params(game_params *params)
160 static game_params *dup_params(game_params *params)
162 game_params *ret = snew(game_params);
163 *ret = *params; /* structure copy */
167 static void decode_params(game_params *ret, char const *string)
169 char const *p = string;
171 ret->order = atoi(p);
172 while (*p && isdigit((unsigned char)*p)) p++;
183 ret->diff = DIFFCOUNT+1; /* ...which is invalid */
185 for (i = 0; i < DIFFCOUNT; i++) {
186 if (*p == unequal_diffchars[i])
194 static char *encode_params(game_params *params, int full)
198 sprintf(ret, "%d", params->order);
199 if (params->adjacent)
200 sprintf(ret + strlen(ret), "a");
202 sprintf(ret + strlen(ret), "d%c", unequal_diffchars[params->diff]);
207 static config_item *game_configure(game_params *params)
212 ret = snewn(4, config_item);
214 ret[0].name = "Mode";
215 ret[0].type = C_CHOICES;
216 ret[0].sval = ":Unequal:Adjacent";
217 ret[0].ival = params->adjacent;
219 ret[1].name = "Size (s*s)";
220 ret[1].type = C_STRING;
221 sprintf(buf, "%d", params->order);
222 ret[1].sval = dupstr(buf);
225 ret[2].name = "Difficulty";
226 ret[2].type = C_CHOICES;
227 ret[2].sval = DIFFCONFIG;
228 ret[2].ival = params->diff;
238 static game_params *custom_params(config_item *cfg)
240 game_params *ret = snew(game_params);
242 ret->adjacent = cfg[0].ival;
243 ret->order = atoi(cfg[1].sval);
244 ret->diff = cfg[2].ival;
249 static char *validate_params(game_params *params, int full)
251 if (params->order < 3 || params->order > 32)
252 return "Order must be between 3 and 32";
253 if (params->diff >= DIFFCOUNT)
254 return "Unknown difficulty rating";
255 if (params->order < 5 && params->adjacent &&
256 params->diff >= DIFF_SET)
257 return "Order must be at least 5 for Adjacent puzzles of this difficulty.";
261 /* ----------------------------------------------------------
262 * Various utility functions
265 static const struct { unsigned int f, fo, fe; int dx, dy; char c, ac; } adjthan[] = {
266 { F_ADJ_UP, F_ADJ_DOWN, F_ERROR_UP, 0, -1, '^', '-' },
267 { F_ADJ_RIGHT, F_ADJ_LEFT, F_ERROR_RIGHT, 1, 0, '>', '|' },
268 { F_ADJ_DOWN, F_ADJ_UP, F_ERROR_DOWN, 0, 1, 'v', '-' },
269 { F_ADJ_LEFT, F_ADJ_RIGHT, F_ERROR_LEFT, -1, 0, '<', '|' }
272 static game_state *blank_game(int order, int adjacent)
274 game_state *state = snew(game_state);
275 int o2 = order*order, o3 = o2*order;
277 state->order = order;
278 state->adjacent = adjacent;
279 state->completed = state->cheated = 0;
281 state->nums = snewn(o2, digit);
282 state->hints = snewn(o3, unsigned char);
283 state->flags = snewn(o2, unsigned int);
285 memset(state->nums, 0, o2 * sizeof(digit));
286 memset(state->hints, 0, o3);
287 memset(state->flags, 0, o2 * sizeof(unsigned int));
292 static game_state *dup_game(game_state *state)
294 game_state *ret = blank_game(state->order, state->adjacent);
295 int o2 = state->order*state->order, o3 = o2*state->order;
297 memcpy(ret->nums, state->nums, o2 * sizeof(digit));
298 memcpy(ret->hints, state->hints, o3);
299 memcpy(ret->flags, state->flags, o2 * sizeof(unsigned int));
304 static void free_game(game_state *state)
312 #define CHECKG(x,y) grid[(y)*o+(x)]
314 /* Returns 0 if it finds an error, 1 otherwise. */
315 static int check_num_adj(digit *grid, game_state *state,
316 int x, int y, int me)
318 unsigned int f = GRID(state, flags, x, y);
319 int ret = 1, i, o = state->order;
321 for (i = 0; i < 4; i++) {
322 int dx = adjthan[i].dx, dy = adjthan[i].dy, n, dn;
324 if (x+dx < 0 || x+dx >= o || y+dy < 0 || y+dy >= o)
328 dn = CHECKG(x+dx, y+dy);
331 if (dn == 0) continue;
333 if (state->adjacent) {
336 if ((f & adjthan[i].f) && (gd != 1)) {
337 debug(("check_adj error (%d,%d):%d should be | (%d,%d):%d",
338 x, y, n, x+dx, y+dy, dn));
339 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
342 if (!(f & adjthan[i].f) && (gd == 1)) {
343 debug(("check_adj error (%d,%d):%d should not be | (%d,%d):%d",
344 x, y, n, x+dx, y+dy, dn));
345 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
350 if ((f & adjthan[i].f) && (n <= dn)) {
351 debug(("check_adj error (%d,%d):%d not > (%d,%d):%d",
352 x, y, n, x+dx, y+dy, dn));
353 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
361 /* Returns 0 if it finds an error, 1 otherwise. */
362 static int check_num_error(digit *grid, game_state *state,
363 int x, int y, int mark_errors)
365 int o = state->order;
366 int xx, yy, val = CHECKG(x,y), ret = 1;
370 /* check for dups in same column. */
371 for (yy = 0; yy < state->order; yy++) {
372 if (yy == y) continue;
373 if (CHECKG(x,yy) == val) ret = 0;
376 /* check for dups in same row. */
377 for (xx = 0; xx < state->order; xx++) {
378 if (xx == x) continue;
379 if (CHECKG(xx,y) == val) ret = 0;
383 debug(("check_num_error (%d,%d) duplicate %d", x, y, val));
384 if (mark_errors) GRID(state, flags, x, y) |= F_ERROR;
389 /* Returns: -1 for 'wrong'
391 * 1 for 'complete and correct'
393 static int check_complete(digit *grid, game_state *state, int mark_errors)
395 int x, y, ret = 1, o = state->order;
398 assert(grid == state->nums);
400 for (x = 0; x < state->order; x++) {
401 for (y = 0; y < state->order; y++) {
403 GRID(state, flags, x, y) &= ~F_ERROR_MASK;
404 if (grid[y*o+x] == 0) {
407 if (!check_num_error(grid, state, x, y, mark_errors)) ret = -1;
408 if (!check_num_adj(grid, state, x, y, mark_errors)) ret = -1;
412 if (ret == 1 && latin_check(grid, o))
417 static char n2c(digit n, int order) {
418 if (n == 0) return ' ';
420 if (n < 10) return '0' + n;
422 if (n < 11) return '0' + n-1;
424 if (n <= 26) return 'A' + n;
429 /* should be 'digit', but includes -1 for 'not a digit'.
430 * Includes keypresses (0 especially) for interpret_move. */
431 static int c2n(int c, int order) {
432 if (c < 0 || c > 0xff)
434 if (c == ' ' || c == '\b')
437 if (c >= '0' && c <= '9')
438 return (int)(c - '0');
440 if (c >= '0' && c <= '9')
441 return (int)(c - '0' + 1);
442 if (c >= 'A' && c <= 'Z')
443 return (int)(c - 'A' + 11);
444 if (c >= 'a' && c <= 'z')
445 return (int)(c - 'a' + 11);
450 static int game_can_format_as_text_now(game_params *params)
455 static char *game_text_format(game_state *state)
460 len = (state->order*2) * (state->order*2-1) + 1;
461 ret = snewn(len, char);
464 for (y = 0; y < state->order; y++) {
465 for (x = 0; x < state->order; x++) {
466 n = GRID(state, nums, x, y);
467 *p++ = n > 0 ? n2c(n, state->order) : '.';
469 if (x < (state->order-1)) {
470 if (state->adjacent) {
471 *p++ = (GRID(state, flags, x, y) & F_ADJ_RIGHT) ? '|' : ' ';
473 if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
475 else if (GRID(state, flags, x+1, y) & F_ADJ_LEFT)
484 if (y < (state->order-1)) {
485 for (x = 0; x < state->order; x++) {
486 if (state->adjacent) {
487 *p++ = (GRID(state, flags, x, y) & F_ADJ_DOWN) ? '-' : ' ';
489 if (GRID(state, flags, x, y) & F_ADJ_DOWN)
491 else if (GRID(state, flags, x, y+1) & F_ADJ_UP)
497 if (x < state->order-1)
505 assert(p - ret == len);
509 #ifdef STANDALONE_SOLVER
510 static void game_debug(game_state *state)
512 char *dbg = game_text_format(state);
518 /* ----------------------------------------------------------
523 int len, gx, gy, lx, ly;
526 typedef struct game_solver {
527 struct latin_solver latin; /* keep first in struct! */
532 struct solver_link *links;
536 static void solver_debug(game_solver *solver, int wide)
538 #ifdef STANDALONE_SOLVER
539 if (solver_show_working) {
541 game_debug(solver->state);
543 latin_solver_debug(solver->latin.cube, solver->latin.o);
549 static void solver_add_link(game_solver *solver,
550 int gx, int gy, int lx, int ly, int len)
552 if (solver->alinks < solver->nlinks+1) {
553 solver->alinks = solver->alinks*2 + 1;
554 /*debug(("resizing solver->links, new size %d", solver->alinks));*/
555 solver->links = sresize(solver->links, solver->alinks, struct solver_link);
557 solver->links[solver->nlinks].gx = gx;
558 solver->links[solver->nlinks].gy = gy;
559 solver->links[solver->nlinks].lx = lx;
560 solver->links[solver->nlinks].ly = ly;
561 solver->links[solver->nlinks].len = len;
563 /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d",
564 len, lx, ly, gx, gy, solver->nlinks));*/
567 static game_solver *new_solver(digit *grid, game_state *state)
569 game_solver *solver = snew(game_solver);
570 int o = state->order;
574 latin_solver_alloc(&solver->latin, grid, o);
576 solver->nlinks = solver->alinks = 0;
577 solver->links = NULL;
578 solver->state = state;
580 if (state->adjacent) return solver; /* adjacent mode doesn't use links. */
582 for (x = 0; x < o; x++) {
583 for (y = 0; y < o; y++) {
584 f = GRID(state, flags, x, y);
585 for (i = 0; i < 4; i++) {
586 if (f & adjthan[i].f)
587 solver_add_link(solver, x, y, x+adjthan[i].dx, y+adjthan[i].dy, 1);
595 static void free_solver(game_solver *solver)
597 if (solver->links) sfree(solver->links);
598 latin_solver_free(&solver->latin);
602 static void solver_nminmax(game_solver *usolver,
603 int x, int y, int *min_r, int *max_r,
604 unsigned char **ns_r)
606 struct latin_solver *solver = &usolver->latin;
607 int o = usolver->latin.o, min = o, max = 0, n;
610 assert(x >= 0 && y >= 0 && x < o && y < o);
612 ns = solver->cube + cubepos(x,y,1);
615 min = max = grid(x,y)-1;
617 for (n = 0; n < o; n++) {
619 if (n > max) max = n;
620 if (n < min) min = n;
624 if (min_r) *min_r = min;
625 if (max_r) *max_r = max;
626 if (ns_r) *ns_r = ns;
629 static int solver_links(game_solver *usolver)
631 int i, j, lmin, gmax, nchanged = 0;
632 unsigned char *gns, *lns;
633 struct solver_link *link;
634 struct latin_solver *solver = &usolver->latin;
636 for (i = 0; i < usolver->nlinks; i++) {
637 link = &usolver->links[i];
638 solver_nminmax(usolver, link->gx, link->gy, NULL, &gmax, &gns);
639 solver_nminmax(usolver, link->lx, link->ly, &lmin, NULL, &lns);
641 for (j = 0; j < solver->o; j++) {
642 /* For the 'greater' end of the link, discount all numbers
643 * too small to satisfy the inequality. */
645 if (j < (lmin+link->len)) {
646 #ifdef STANDALONE_SOLVER
647 if (solver_show_working) {
648 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
649 solver_recurse_depth*4, "",
650 link->gx, link->gy, link->lx, link->ly);
651 printf("%*s ruling out %d at (%d,%d)\n",
652 solver_recurse_depth*4, "",
653 j+1, link->gx, link->gy);
656 cube(link->gx, link->gy, j+1) = FALSE;
660 /* For the 'lesser' end of the link, discount all numbers
661 * too large to satisfy inequality. */
663 if (j > (gmax-link->len)) {
664 #ifdef STANDALONE_SOLVER
665 if (solver_show_working) {
666 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
667 solver_recurse_depth*4, "",
668 link->gx, link->gy, link->lx, link->ly);
669 printf("%*s ruling out %d at (%d,%d)\n",
670 solver_recurse_depth*4, "",
671 j+1, link->lx, link->ly);
674 cube(link->lx, link->ly, j+1) = FALSE;
683 static int solver_adjacent(game_solver *usolver)
685 struct latin_solver *solver = &usolver->latin;
686 int nchanged = 0, x, y, i, n, o = usolver->latin.o, nx, ny, gd;
688 /* Update possible values based on known values and adjacency clues. */
690 for (x = 0; x < o; x++) {
691 for (y = 0; y < o; y++) {
692 if (grid(x, y) == 0) continue;
694 /* We have a definite number here. Make sure that any
695 * adjacent possibles reflect the adjacent/non-adjacent clue. */
697 for (i = 0; i < 4; i++) {
698 int isadjacent = (GRID(usolver->state, flags, x, y) & adjthan[i].f);
700 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
701 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
704 for (n = 0; n < o; n++) {
705 /* Continue past numbers the adjacent square _could_ be,
706 * given the clue we have. */
707 gd = abs((n+1) - grid(x, y));
708 if (isadjacent && (gd == 1)) continue;
709 if (!isadjacent && (gd != 1)) continue;
711 if (cube(nx, ny, n+1) == FALSE)
712 continue; /* already discounted this possibility. */
714 #ifdef STANDALONE_SOLVER
715 if (solver_show_working) {
716 printf("%*sadjacent elimination, (%d,%d):%d %s (%d,%d):\n",
717 solver_recurse_depth*4, "",
718 x, y, grid(x, y), isadjacent ? "|" : "!|", nx, ny);
719 printf("%*s ruling out %d at (%d,%d)\n",
720 solver_recurse_depth*4, "", n+1, nx, ny);
723 cube(nx, ny, n+1) = FALSE;
733 static int solver_adjacent_set(game_solver *usolver)
735 struct latin_solver *solver = &usolver->latin;
736 int x, y, i, n, nn, o = usolver->latin.o, nx, ny, gd;
737 int nchanged = 0, *scratch = snewn(o, int);
739 /* Update possible values based on other possible values
740 * of adjacent squares, and adjacency clues. */
742 for (x = 0; x < o; x++) {
743 for (y = 0; y < o; y++) {
744 for (i = 0; i < o; i++) {
745 int isadjacent = (GRID(usolver->state, flags, x, y) & adjthan[i].f);
747 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
748 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
751 /* We know the current possibles for the square (x,y)
752 * and also the adjacency clue from (x,y) to (nx,ny).
753 * Construct a maximum set of possibles for (nx,ny)
754 * in scratch, based on these constraints... */
756 memset(scratch, 0, o*sizeof(int));
758 for (n = 0; n < o; n++) {
759 if (cube(x, y, n+1) == FALSE) continue;
761 for (nn = 0; nn < o; nn++) {
762 if (n == nn) continue;
765 if (isadjacent && (gd != 1)) continue;
766 if (!isadjacent && (gd == 1)) continue;
772 /* ...and remove any possibilities for (nx,ny) that are
773 * currently set but are not indicated in scratch. */
774 for (n = 0; n < o; n++) {
775 if (scratch[n] == 1) continue;
776 if (cube(nx, ny, n+1) == FALSE) continue;
778 #ifdef STANDALONE_SOLVER
779 if (solver_show_working) {
780 printf("%*sadjacent possible elimination, (%d,%d) %s (%d,%d):\n",
781 solver_recurse_depth*4, "",
782 x, y, isadjacent ? "|" : "!|", nx, ny);
783 printf("%*s ruling out %d at (%d,%d)\n",
784 solver_recurse_depth*4, "", n+1, nx, ny);
787 cube(nx, ny, n+1) = FALSE;
797 static int solver_grid(digit *grid, int o, int maxdiff, void *ctx)
799 game_state *state = (game_state *)ctx;
801 struct latin_solver *lsolver;
802 struct latin_solver_scratch *scratch;
803 int ret, diff = DIFF_LATIN;
805 assert(maxdiff <= DIFF_RECURSIVE);
807 assert(state->order == o);
808 solver = new_solver(grid, state);
810 lsolver = &solver->latin;
811 scratch = latin_solver_new_scratch(lsolver);
815 ret = latin_solver_diff_simple(lsolver);
817 diff = DIFF_IMPOSSIBLE;
819 } else if (ret > 0) {
820 diff = max(diff, DIFF_LATIN);
824 if (maxdiff <= DIFF_LATIN)
827 if (state->adjacent) {
828 /* Adjacent-specific: set possibles from known numbers
829 * and adjacency clues. */
830 ret = solver_adjacent(solver);
832 /* Unequal-specific: set possibles from chains of
834 ret = solver_links(solver);
837 diff = DIFF_IMPOSSIBLE;
839 } else if (ret > 0) {
840 diff = max(diff, DIFF_EASY);
844 if (maxdiff <= DIFF_EASY)
847 /* Row- and column-wise set elimination */
848 ret = latin_solver_diff_set(lsolver, scratch, 0);
850 diff = DIFF_IMPOSSIBLE;
852 } else if (ret > 0) {
853 diff = max(diff, DIFF_SET);
857 if (state->adjacent) {
858 /* Adjacent-specific: set possibles from other possibles
859 * and adjacency clues. */
860 ret = solver_adjacent_set(solver);
862 diff = DIFF_IMPOSSIBLE;
864 } else if (ret > 0) {
865 diff = max(diff, DIFF_SET);
870 if (maxdiff <= DIFF_SET)
873 ret = latin_solver_diff_set(lsolver, scratch, 1);
875 diff = DIFF_IMPOSSIBLE;
877 } else if (ret > 0) {
878 diff = max(diff, DIFF_EXTREME);
885 if (latin_solver_forcing(lsolver, scratch)) {
886 diff = max(diff, DIFF_EXTREME);
891 * If we reach here, we have made no deductions in this
892 * iteration, so the algorithm terminates.
897 * Last chance: if we haven't fully solved the puzzle yet, try
898 * recursing based on guesses for a particular square. We pick
899 * one of the most constrained empty squares we can find, which
900 * has the effect of pruning the search tree as much as
903 if (maxdiff == DIFF_RECURSIVE) {
904 int nsol = latin_solver_recurse(lsolver, DIFF_RECURSIVE, solver_grid, ctx);
905 if (nsol < 0) diff = DIFF_IMPOSSIBLE;
906 else if (nsol == 1) diff = DIFF_RECURSIVE;
907 else if (nsol > 1) diff = DIFF_AMBIGUOUS;
908 /* if nsol == 0 then we were complete anyway
909 * (and thus don't need to change diff) */
911 int cc = check_complete(grid, state, 0);
912 if (cc == -1) diff = DIFF_IMPOSSIBLE;
913 if (cc == 0) diff = DIFF_UNFINISHED;
918 #ifdef STANDALONE_SOLVER
919 if (solver_show_working)
920 printf("%*s%s found\n",
921 solver_recurse_depth*4, "",
922 diff == DIFF_IMPOSSIBLE ? "no solution (impossible)" :
923 diff == DIFF_UNFINISHED ? "no solution (unfinished)" :
924 diff == DIFF_AMBIGUOUS ? "multiple solutions" :
928 latin_solver_free_scratch(scratch);
929 memcpy(state->hints, solver->latin.cube, o*o*o);
935 static int solver_state(game_state *state, int maxdiff)
937 int diff = solver_grid(state->nums, state->order, maxdiff, (void*)state);
939 if (diff == DIFF_IMPOSSIBLE)
941 if (diff == DIFF_UNFINISHED)
943 if (diff == DIFF_AMBIGUOUS)
948 static game_state *solver_hint(game_state *state, int *diff_r, int mindiff, int maxdiff)
950 game_state *ret = dup_game(state);
953 for (diff = mindiff; diff <= maxdiff; diff++) {
954 r = solver_state(ret, diff);
955 debug(("solver_state after %s %d", unequal_diffnames[diff], r));
956 if (r != 0) goto done;
960 if (diff_r) *diff_r = (r > 0) ? diff : -1;
964 /* ----------------------------------------------------------
968 static char *latin_desc(digit *sq, size_t order)
970 int o2 = order*order, i;
971 char *soln = snewn(o2+2, char);
974 for (i = 0; i < o2; i++)
975 soln[i+1] = n2c(sq[i], order);
981 /* returns non-zero if it placed (or could have placed) clue. */
982 static int gg_place_clue(game_state *state, int ccode, digit *latin, int checkonly)
984 int loc = ccode / 5, which = ccode % 5;
985 int x = loc % state->order, y = loc / state->order;
987 assert(loc < state->order*state->order);
989 if (which == 4) { /* add number */
990 if (state->nums[loc] != 0) {
991 #ifdef STANDALONE_SOLVER
992 if (state->nums[loc] != latin[loc]) {
993 printf("inconsistency for (%d,%d): state %d latin %d\n",
994 x, y, state->nums[loc], latin[loc]);
997 assert(state->nums[loc] == latin[loc]);
1001 state->nums[loc] = latin[loc];
1003 } else { /* add flag */
1006 if (state->adjacent)
1007 return 0; /* never add flag clues in adjacent mode (they're always
1010 if (state->flags[loc] & adjthan[which].f)
1011 return 0; /* already has flag. */
1013 lx = x + adjthan[which].dx;
1014 ly = y + adjthan[which].dy;
1015 if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order)
1016 return 0; /* flag compares to off grid */
1018 lloc = loc + adjthan[which].dx + adjthan[which].dy*state->order;
1019 if (latin[loc] <= latin[lloc])
1020 return 0; /* flag would be incorrect */
1023 state->flags[loc] |= adjthan[which].f;
1029 /* returns non-zero if it removed (or could have removed) the clue. */
1030 static int gg_remove_clue(game_state *state, int ccode, int checkonly)
1032 int loc = ccode / 5, which = ccode % 5;
1033 #ifdef STANDALONE_SOLVER
1034 int x = loc % state->order, y = loc / state->order;
1037 assert(loc < state->order*state->order);
1039 if (which == 4) { /* remove number. */
1040 if (state->nums[loc] == 0) return 0;
1042 #ifdef STANDALONE_SOLVER
1043 if (solver_show_working)
1044 printf("gg_remove_clue: removing %d at (%d,%d)",
1045 state->nums[loc], x, y);
1047 state->nums[loc] = 0;
1049 } else { /* remove flag */
1050 if (state->adjacent)
1051 return 0; /* never remove clues in adjacent mode. */
1053 if (!(state->flags[loc] & adjthan[which].f)) return 0;
1055 #ifdef STANDALONE_SOLVER
1056 if (solver_show_working)
1057 printf("gg_remove_clue: removing %c at (%d,%d)",
1058 adjthan[which].c, x, y);
1060 state->flags[loc] &= ~adjthan[which].f;
1066 static int gg_best_clue(game_state *state, int *scratch, digit *latin)
1068 int ls = state->order * state->order * 5;
1069 int maxposs = 0, minclues = 5, best = -1, i, j;
1070 int nposs, nclues, loc, x, y;
1072 #ifdef STANDALONE_SOLVER
1073 if (solver_show_working) {
1075 latin_solver_debug(state->hints, state->order);
1079 for (i = ls; i-- > 0 ;) {
1080 if (!gg_place_clue(state, scratch[i], latin, 1)) continue;
1082 loc = scratch[i] / 5;
1083 x = loc % state->order; y = loc / state->order;
1084 for (j = nposs = 0; j < state->order; j++) {
1085 if (state->hints[loc*state->order + j]) nposs++;
1087 for (j = nclues = 0; j < 4; j++) {
1088 if (state->flags[loc] & adjthan[j].f) nclues++;
1090 if ((nposs > maxposs) ||
1091 (nposs == maxposs && nclues < minclues)) {
1092 best = i; maxposs = nposs; minclues = nclues;
1093 #ifdef STANDALONE_SOLVER
1094 if (solver_show_working)
1095 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
1096 best, x, y, nposs, nclues);
1100 /* if we didn't solve, we must have 1 clue to place! */
1105 #ifdef STANDALONE_SOLVER
1107 #define MAXTRIES maxtries
1113 static int game_assemble(game_state *new, int *scratch, digit *latin,
1116 game_state *copy = dup_game(new);
1119 if (difficulty >= DIFF_RECURSIVE) {
1120 /* We mustn't use any solver that might guess answers;
1121 * if it guesses wrongly but solves, gg_place_clue will
1122 * get mighty confused. We will always trim clues down
1123 * (making it more difficult) in game_strip, which doesn't
1124 * have this problem. */
1125 difficulty = DIFF_RECURSIVE-1;
1128 #ifdef STANDALONE_SOLVER
1129 if (solver_show_working) {
1131 latin_solver_debug(new->hints, new->order);
1137 if (solver_state(copy, difficulty) == 1) break;
1139 best = gg_best_clue(copy, scratch, latin);
1140 gg_place_clue(new, scratch[best], latin, 0);
1141 gg_place_clue(copy, scratch[best], latin, 0);
1144 #ifdef STANDALONE_SOLVER
1145 if (solver_show_working) {
1146 char *dbg = game_text_format(new);
1147 printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
1154 static void game_strip(game_state *new, int *scratch, digit *latin,
1157 int o = new->order, o2 = o*o, lscratch = o2*5, i;
1158 game_state *copy = blank_game(new->order, new->adjacent);
1160 /* For each symbol (if it exists in new), try and remove it and
1161 * solve again; if we couldn't solve without it put it back. */
1162 for (i = 0; i < lscratch; i++) {
1163 if (!gg_remove_clue(new, scratch[i], 0)) continue;
1165 memcpy(copy->nums, new->nums, o2 * sizeof(digit));
1166 memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
1168 if (solver_state(copy, difficulty) != 1) {
1169 /* put clue back, we can't solve without it. */
1170 int ret = gg_place_clue(new, scratch[i], latin, 0);
1173 #ifdef STANDALONE_SOLVER
1174 if (solver_show_working)
1175 printf("game_strip: clue was redundant.");
1180 #ifdef STANDALONE_SOLVER
1181 if (solver_show_working) {
1182 char *dbg = game_text_format(new);
1183 debug(("game_strip: done, %d solver iterations.", gg_solved));
1190 static void add_adjacent_flags(game_state *state, digit *latin)
1192 int x, y, o = state->order;
1194 /* All clues in adjacent mode are always present (the only variables are
1195 * the numbers). This adds all the flags to state based on the supplied
1198 for (y = 0; y < o; y++) {
1199 for (x = 0; x < o; x++) {
1200 if (x < (o-1) && (abs(latin[y*o+x] - latin[y*o+x+1]) == 1)) {
1201 GRID(state, flags, x, y) |= F_ADJ_RIGHT;
1202 GRID(state, flags, x+1, y) |= F_ADJ_LEFT;
1204 if (y < (o-1) && (abs(latin[y*o+x] - latin[(y+1)*o+x]) == 1)) {
1205 GRID(state, flags, x, y) |= F_ADJ_DOWN;
1206 GRID(state, flags, x, y+1) |= F_ADJ_UP;
1212 static char *new_game_desc(game_params *params, random_state *rs,
1213 char **aux, int interactive)
1216 int i, x, y, retlen, k, nsol;
1217 int o2 = params->order * params->order, ntries = 1;
1218 int *scratch, lscratch = o2*5;
1220 game_state *state = blank_game(params->order, params->adjacent);
1222 /* Generate a list of 'things to strip' (randomised later) */
1223 scratch = snewn(lscratch, int);
1224 /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1225 for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1228 #ifdef STANDALONE_SOLVER
1229 if (solver_show_working)
1230 printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1231 unequal_diffnames[params->diff], ntries);
1234 sq = latin_generate(params->order, rs);
1235 latin_debug(sq, params->order);
1236 /* Separately shuffle the numeric and inequality clues */
1237 shuffle(scratch, lscratch/5, sizeof(int), rs);
1238 shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1240 memset(state->nums, 0, o2 * sizeof(digit));
1241 memset(state->flags, 0, o2 * sizeof(unsigned int));
1243 if (state->adjacent) {
1244 /* All adjacency flags are always present. */
1245 add_adjacent_flags(state, sq);
1249 if (game_assemble(state, scratch, sq, params->diff) < 0)
1251 game_strip(state, scratch, sq, params->diff);
1253 if (params->diff > 0) {
1254 game_state *copy = dup_game(state);
1255 nsol = solver_state(copy, params->diff-1);
1258 #ifdef STANDALONE_SOLVER
1259 if (solver_show_working)
1260 printf("game_assemble: puzzle as generated is too easy.\n");
1262 if (ntries < MAXTRIES) {
1266 #ifdef STANDALONE_SOLVER
1267 if (solver_show_working)
1268 printf("Unable to generate %s %dx%d after %d attempts.\n",
1269 unequal_diffnames[params->diff],
1270 params->order, params->order, MAXTRIES);
1275 #ifdef STANDALONE_SOLVER
1276 if (solver_show_working)
1277 printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1278 unequal_diffnames[params->diff], ntries, gg_solved);
1281 ret = NULL; retlen = 0;
1282 for (y = 0; y < params->order; y++) {
1283 for (x = 0; x < params->order; x++) {
1284 unsigned int f = GRID(state, flags, x, y);
1285 k = sprintf(buf, "%d%s%s%s%s,",
1286 GRID(state, nums, x, y),
1287 (f & F_ADJ_UP) ? "U" : "",
1288 (f & F_ADJ_RIGHT) ? "R" : "",
1289 (f & F_ADJ_DOWN) ? "D" : "",
1290 (f & F_ADJ_LEFT) ? "L" : "");
1292 ret = sresize(ret, retlen + k + 1, char);
1293 strcpy(ret + retlen, buf);
1297 *aux = latin_desc(sq, params->order);
1306 static game_state *load_game(game_params *params, char *desc,
1309 game_state *state = blank_game(params->order, params->adjacent);
1311 int i = 0, n, o = params->order, x, y;
1315 while (*p >= 'a' && *p <= 'z') {
1320 why = "Too much data to fill grid"; goto fail;
1323 if (*p < '0' && *p > '9') {
1324 why = "Expecting number in game description"; goto fail;
1327 if (n < 0 || n > o) {
1328 why = "Out-of-range number in game description"; goto fail;
1330 state->nums[i] = (digit)n;
1331 while (*p >= '0' && *p <= '9') p++; /* skip number */
1333 if (state->nums[i] != 0)
1334 state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1336 while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1338 case 'U': state->flags[i] |= F_ADJ_UP; break;
1339 case 'R': state->flags[i] |= F_ADJ_RIGHT; break;
1340 case 'D': state->flags[i] |= F_ADJ_DOWN; break;
1341 case 'L': state->flags[i] |= F_ADJ_LEFT; break;
1342 default: why = "Expecting flag URDL in game description"; goto fail;
1347 if (i < o*o && *p != ',') {
1348 why = "Missing separator"; goto fail;
1353 why = "Not enough data to fill grid"; goto fail;
1356 for (y = 0; y < o; y++) {
1357 for (x = 0; x < o; x++) {
1358 for (n = 0; n < 4; n++) {
1359 if (GRID(state, flags, x, y) & adjthan[n].f) {
1360 int nx = x + adjthan[n].dx;
1361 int ny = y + adjthan[n].dy;
1362 /* a flag must not point us off the grid. */
1363 if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1364 why = "Flags go off grid"; goto fail;
1366 if (params->adjacent) {
1367 /* if one cell is adjacent to another, the other must
1368 * also be adjacent to the first. */
1369 if (!(GRID(state, flags, nx, ny) & adjthan[n].fo)) {
1370 why = "Flags contradicting each other"; goto fail;
1373 /* if one cell is GT another, the other must _not_ also
1374 * be GT the first. */
1375 if (GRID(state, flags, nx, ny) & adjthan[n].fo) {
1376 why = "Flags contradicting each other"; goto fail;
1388 if (why_r) *why_r = why;
1392 static game_state *new_game(midend *me, game_params *params, char *desc)
1394 game_state *state = load_game(params, desc, NULL);
1396 assert("Unable to load ?validated game.");
1402 static char *validate_desc(game_params *params, char *desc)
1405 game_state *dummy = load_game(params, desc, &why);
1414 static char *solve_game(game_state *state, game_state *currstate,
1415 char *aux, char **error)
1421 if (aux) return dupstr(aux);
1423 solved = dup_game(state);
1424 for (r = 0; r < state->order*state->order; r++) {
1425 if (!(solved->flags[r] & F_IMMUTABLE))
1426 solved->nums[r] = 0;
1428 r = solver_state(solved, DIFFCOUNT);
1429 if (r > 0) ret = latin_desc(solved->nums, solved->order);
1434 /* ----------------------------------------------------------
1435 * Game UI input processing.
1439 int hx, hy; /* as for solo.c, highlight pos */
1440 int hshow, hpencil, hcursor; /* show state, type, and ?cursor. */
1443 static game_ui *new_ui(game_state *state)
1445 game_ui *ui = snew(game_ui);
1447 ui->hx = ui->hy = 0;
1448 ui->hpencil = ui->hshow = ui->hcursor = 0;
1453 static void free_ui(game_ui *ui)
1458 static char *encode_ui(game_ui *ui)
1463 static void decode_ui(game_ui *ui, char *encoding)
1467 static void game_changed_state(game_ui *ui, game_state *oldstate,
1468 game_state *newstate)
1470 /* See solo.c; if we were pencil-mode highlighting and
1471 * somehow a square has just been properly filled, cancel
1473 if (ui->hshow && ui->hpencil && !ui->hcursor &&
1474 GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1479 struct game_drawstate {
1480 int tilesize, order, started, adjacent;
1481 digit *nums; /* copy of nums, o^2 */
1482 unsigned char *hints; /* copy of hints, o^3 */
1483 unsigned int *flags; /* o^2 */
1485 int hx, hy, hshow, hpencil; /* as for game_ui. */
1489 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1490 int ox, int oy, int button)
1492 int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1495 button &= ~MOD_MASK;
1497 if (x >= 0 && x < ds->order && ((ox - COORD(x)) <= TILE_SIZE) &&
1498 y >= 0 && y < ds->order && ((oy - COORD(y)) <= TILE_SIZE)) {
1499 if (button == LEFT_BUTTON) {
1500 /* normal highlighting for non-immutable squares */
1501 if (GRID(state, flags, x, y) & F_IMMUTABLE)
1503 else if (x == ui->hx && y == ui->hy &&
1504 ui->hshow && ui->hpencil == 0)
1507 ui->hx = x; ui->hy = y; ui->hpencil = 0;
1513 if (button == RIGHT_BUTTON) {
1514 /* pencil highlighting for non-filled squares */
1515 if (GRID(state, nums, x, y) != 0)
1517 else if (x == ui->hx && y == ui->hy &&
1518 ui->hshow && ui->hpencil)
1521 ui->hx = x; ui->hy = y; ui->hpencil = 1;
1529 if (IS_CURSOR_MOVE(button)) {
1530 move_cursor(button, &ui->hx, &ui->hy, ds->order, ds->order, 0);
1531 ui->hshow = ui->hcursor = 1;
1534 if (ui->hshow && IS_CURSOR_SELECT(button)) {
1535 ui->hpencil = 1 - ui->hpencil;
1542 debug(("button %d, cbutton %d", button, (int)((char)button)));
1543 n = c2n(button, state->order);
1545 debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1546 n, ui->hx, ui->hy, ui->hpencil,
1547 GRID(state, flags, ui->hx, ui->hy),
1548 GRID(state, nums, ui->hx, ui->hy)));
1550 if (n < 0 || n > ds->order)
1551 return NULL; /* out of range */
1552 if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE)
1553 return NULL; /* can't edit immutable square (!) */
1554 if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0)
1555 return NULL; /* can't change hints on filled square (!) */
1558 sprintf(buf, "%c%d,%d,%d",
1559 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1561 if (!ui->hcursor) ui->hshow = 0;
1566 if (button == 'H' || button == 'h')
1568 if (button == 'M' || button == 'm')
1574 static game_state *execute_move(game_state *state, char *move)
1576 game_state *ret = NULL;
1579 debug(("execute_move: %s", move));
1581 if ((move[0] == 'P' || move[0] == 'R') &&
1582 sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1583 x >= 0 && x < state->order && y >= 0 && y < state->order &&
1584 n >= 0 && n <= state->order) {
1585 ret = dup_game(state);
1586 if (move[0] == 'P' && n > 0)
1587 HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1);
1589 GRID(ret, nums, x, y) = n;
1590 for (i = 0; i < state->order; i++)
1591 HINT(ret, x, y, i) = 0;
1593 /* real change to grid; check for completion */
1594 if (!ret->completed && check_complete(ret->nums, ret, 1) > 0)
1595 ret->completed = TRUE;
1598 } else if (move[0] == 'S') {
1601 ret = dup_game(state);
1602 ret->completed = ret->cheated = TRUE;
1605 for (i = 0; i < state->order*state->order; i++) {
1606 n = c2n((int)*p, state->order);
1607 if (!*p || n <= 0 || n > state->order)
1612 if (*p) goto badmove;
1613 rc = check_complete(ret->nums, ret, 1);
1616 } else if (move[0] == 'M') {
1617 ret = dup_game(state);
1618 for (x = 0; x < state->order; x++) {
1619 for (y = 0; y < state->order; y++) {
1620 for (n = 0; n < state->order; n++) {
1621 HINT(ret, x, y, n) = 1;
1626 } else if (move[0] == 'H') {
1627 return solver_hint(state, NULL, DIFF_EASY, DIFF_EASY);
1631 if (ret) free_game(ret);
1635 /* ----------------------------------------------------------------------
1636 * Drawing/printing routines.
1639 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1641 static void game_compute_size(game_params *params, int tilesize,
1644 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1645 struct { int tilesize, order; } ads, *ds = &ads;
1646 ads.tilesize = tilesize;
1647 ads.order = params->order;
1649 *x = *y = DRAW_SIZE;
1652 static void game_set_size(drawing *dr, game_drawstate *ds,
1653 game_params *params, int tilesize)
1655 ds->tilesize = tilesize;
1658 static float *game_colours(frontend *fe, int *ncolours)
1660 float *ret = snewn(3 * NCOLOURS, float);
1663 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1665 for (i = 0; i < 3; i++) {
1666 ret[COL_TEXT * 3 + i] = 0.0F;
1667 ret[COL_GRID * 3 + i] = 0.5F;
1670 /* Lots of these were taken from solo.c. */
1671 ret[COL_GUESS * 3 + 0] = 0.0F;
1672 ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1673 ret[COL_GUESS * 3 + 2] = 0.0F;
1675 ret[COL_ERROR * 3 + 0] = 1.0F;
1676 ret[COL_ERROR * 3 + 1] = 0.0F;
1677 ret[COL_ERROR * 3 + 2] = 0.0F;
1679 ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1680 ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1681 ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1683 *ncolours = NCOLOURS;
1687 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1689 struct game_drawstate *ds = snew(struct game_drawstate);
1690 int o2 = state->order*state->order, o3 = o2*state->order;
1693 ds->order = state->order;
1694 ds->adjacent = state->adjacent;
1696 ds->nums = snewn(o2, digit);
1697 ds->hints = snewn(o3, unsigned char);
1698 ds->flags = snewn(o2, unsigned int);
1699 memset(ds->nums, 0, o2*sizeof(digit));
1700 memset(ds->hints, 0, o3);
1701 memset(ds->flags, 0, o2*sizeof(unsigned int));
1703 ds->hx = ds->hy = 0;
1704 ds->started = ds->hshow = ds->hpencil = ds->hflash = 0;
1709 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1717 static void draw_gt(drawing *dr, int ox, int oy,
1718 int dx1, int dy1, int dx2, int dy2, int col)
1720 draw_line(dr, ox, oy, ox+dx1, oy+dy1, col);
1721 draw_line(dr, ox+dx1, oy+dy1, ox+dx1+dx2, oy+dy1+dy2, col);
1724 static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy,
1725 unsigned int f, int col)
1727 int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4;
1729 /* Draw all the greater-than signs emanating from this tile. */
1732 draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2,
1733 (f & F_ERROR_UP) ? COL_ERROR : col);
1734 draw_update(dr, ox, oy-g, TILE_SIZE, g);
1736 if (f & F_ADJ_RIGHT) {
1737 draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2,
1738 (f & F_ERROR_RIGHT) ? COL_ERROR : col);
1739 draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1741 if (f & F_ADJ_DOWN) {
1742 draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2,
1743 (f & F_ERROR_DOWN) ? COL_ERROR : col);
1744 draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1746 if (f & F_ADJ_LEFT) {
1747 draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2,
1748 (f & F_ERROR_LEFT) ? COL_ERROR : col);
1749 draw_update(dr, ox-g, oy, g, TILE_SIZE);
1753 static void draw_adjs(drawing *dr, game_drawstate *ds, int ox, int oy,
1754 unsigned int f, int col)
1756 int g = GAP_SIZE, g38 = 3*(g+1)/8, g4 = (g+1)/4;
1758 /* Draw all the adjacency bars relevant to this tile; we only have
1759 * to worry about F_ADJ_RIGHT and F_ADJ_DOWN.
1761 * If we _only_ have the error flag set (i.e. it's not supposed to be
1762 * adjacent, but adjacent numbers were entered) draw an outline red bar.
1765 if (f & (F_ADJ_RIGHT|F_ERROR_RIGHT)) {
1766 if (f & F_ADJ_RIGHT) {
1767 draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE,
1768 (f & F_ERROR_RIGHT) ? COL_ERROR : col);
1770 draw_rect_outline(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COL_ERROR);
1773 draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COL_BACKGROUND);
1775 draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1777 if (f & (F_ADJ_DOWN|F_ERROR_DOWN)) {
1778 if (f & F_ADJ_DOWN) {
1779 draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4,
1780 (f & F_ERROR_DOWN) ? COL_ERROR : col);
1782 draw_rect_outline(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COL_ERROR);
1785 draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COL_BACKGROUND);
1787 draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1790 static void draw_furniture(drawing *dr, game_drawstate *ds, game_state *state,
1791 game_ui *ui, int x, int y, int hflash)
1793 int ox = COORD(x), oy = COORD(y), bg, hon;
1794 unsigned int f = GRID(state, flags, x, y);
1796 bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1798 hon = (ui->hshow && x == ui->hx && y == ui->hy);
1801 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1802 (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1804 /* Draw the highlight (pencil or full), if we're the highlight */
1805 if (hon && ui->hpencil) {
1809 coords[2] = ox + TILE_SIZE/2;
1812 coords[5] = oy + TILE_SIZE/2;
1813 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1816 /* Draw the square outline (which is the cursor, if we're the cursor). */
1817 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
1819 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1821 /* Draw the adjacent clue signs. */
1823 draw_adjs(dr, ds, ox, oy, f, COL_GRID);
1825 draw_gts(dr, ds, ox, oy, f, COL_TEXT);
1828 static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1830 int ox = COORD(x), oy = COORD(y);
1831 unsigned int f = GRID(ds,flags,x,y);
1834 /* (can assume square has just been cleared) */
1836 /* Draw number, choosing appropriate colour */
1837 str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1839 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1840 FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1841 (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1844 static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1846 int ox = COORD(x), oy = COORD(y);
1847 int nhints, i, j, hw, hh, hmax, fontsz;
1850 /* (can assume square has just been cleared) */
1852 /* Draw hints; steal ingenious algorithm (basically)
1853 * from solo.c:draw_number() */
1854 for (i = nhints = 0; i < ds->order; i++) {
1855 if (HINT(ds, x, y, i)) nhints++;
1858 for (hw = 1; hw * hw < nhints; hw++);
1860 hh = (nhints + hw - 1) / hw;
1863 fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
1865 for (i = j = 0; i < ds->order; i++) {
1866 if (HINT(ds,x,y,i)) {
1867 int hx = j % hw, hy = j / hw;
1869 str[0] = n2c(i+1, ds->order);
1872 ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
1873 oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
1874 FONT_VARIABLE, fontsz,
1875 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1881 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1882 game_state *state, int dir, game_ui *ui,
1883 float animtime, float flashtime)
1885 int x, y, i, hchanged = 0, stale, hflash = 0;
1887 debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
1889 if (flashtime > 0 &&
1890 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
1894 draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
1895 draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
1897 if (ds->hx != ui->hx || ds->hy != ui->hy ||
1898 ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
1901 for (x = 0; x < ds->order; x++) {
1902 for (y = 0; y < ds->order; y++) {
1905 else if (hflash != ds->hflash)
1911 if ((x == ui->hx && y == ui->hy) ||
1912 (x == ds->hx && y == ds->hy))
1916 if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
1917 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
1920 if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
1921 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
1924 if (GRID(ds, nums, x, y) == 0) {
1925 /* We're not a number square (therefore we might
1926 * display hints); do we need to update? */
1927 for (i = 0; i < ds->order; i++) {
1928 if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
1929 HINT(ds, x, y, i) = HINT(state, x, y, i);
1935 draw_furniture(dr, ds, state, ui, x, y, hflash);
1936 if (GRID(ds, nums, x, y) > 0)
1937 draw_num(dr, ds, x, y);
1939 draw_hints(dr, ds, x, y);
1943 ds->hx = ui->hx; ds->hy = ui->hy;
1944 ds->hshow = ui->hshow;
1945 ds->hpencil = ui->hpencil;
1948 ds->hflash = hflash;
1951 static float game_anim_length(game_state *oldstate, game_state *newstate,
1952 int dir, game_ui *ui)
1957 static float game_flash_length(game_state *oldstate, game_state *newstate,
1958 int dir, game_ui *ui)
1960 if (!oldstate->completed && newstate->completed &&
1961 !oldstate->cheated && !newstate->cheated)
1966 static int game_timing_state(game_state *state, game_ui *ui)
1971 static void game_print_size(game_params *params, float *x, float *y)
1975 /* 10mm squares by default, roughly the same as Grauniad. */
1976 game_compute_size(params, 1000, &pw, &ph);
1981 static void game_print(drawing *dr, game_state *state, int tilesize)
1983 int ink = print_mono_colour(dr, 0);
1984 int x, y, o = state->order, ox, oy, n;
1987 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1988 game_drawstate ads, *ds = &ads;
1989 game_set_size(dr, ds, NULL, tilesize);
1991 print_line_width(dr, 2 * TILE_SIZE / 40);
1993 /* Squares, numbers, gt signs */
1994 for (y = 0; y < o; y++) {
1995 for (x = 0; x < o; x++) {
1996 ox = COORD(x); oy = COORD(y);
1997 n = GRID(state, nums, x, y);
1999 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
2001 str[0] = n ? n2c(n, state->order) : ' ';
2003 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
2004 FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
2008 draw_adjs(dr, ds, ox, oy, GRID(state, flags, x, y), ink);
2010 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), ink);
2015 /* ----------------------------------------------------------------------
2020 #define thegame unequal
2023 const struct game thegame = {
2024 "Unequal", "games.unequal", "unequal",
2031 TRUE, game_configure, custom_params,
2039 TRUE, game_can_format_as_text_now, game_text_format,
2047 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2050 game_free_drawstate,
2054 TRUE, FALSE, game_print_size, game_print,
2055 FALSE, /* wants_statusbar */
2056 FALSE, game_timing_state,
2057 REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */
2060 /* ----------------------------------------------------------------------
2061 * Standalone solver.
2064 #ifdef STANDALONE_SOLVER
2069 const char *quis = NULL;
2071 #if 0 /* currently unused */
2073 static void debug_printf(char *fmt, ...)
2079 vsprintf(buf, fmt, ap);
2084 static void game_printf(game_state *state)
2086 char *dbg = game_text_format(state);
2091 static void game_printf_wide(game_state *state)
2095 for (y = 0; y < state->order; y++) {
2096 for (x = 0; x < state->order; x++) {
2097 n = GRID(state, nums, x, y);
2098 for (i = 0; i < state->order; i++) {
2100 printf("%c", n2c(n, state->order));
2101 else if (HINT(state, x, y, i))
2102 printf("%c", n2c(i+1, state->order));
2115 static void pdiff(int diff)
2117 if (diff == DIFF_IMPOSSIBLE)
2118 printf("Game is impossible.\n");
2119 else if (diff == DIFF_UNFINISHED)
2120 printf("Game has incomplete.\n");
2121 else if (diff == DIFF_AMBIGUOUS)
2122 printf("Game has multiple solutions.\n");
2124 printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
2127 static int solve(game_params *p, char *desc, int debug)
2129 game_state *st = new_game(NULL, p, desc);
2132 solver_show_working = debug;
2135 diff = solver_grid(st->nums, st->order, DIFF_RECURSIVE, (void*)st);
2136 if (debug) pdiff(diff);
2143 static void check(game_params *p)
2145 char *msg = validate_params(p, 1);
2147 fprintf(stderr, "%s: %s", quis, msg);
2152 static int gen(game_params *p, random_state *rs, int debug)
2159 solver_show_working = debug;
2160 desc = new_game_desc(p, rs, &aux, 0);
2161 diff = solve(p, desc, debug);
2168 static void soak(game_params *p, random_state *rs)
2170 time_t tt_start, tt_now, tt_last;
2173 int n = 0, neasy = 0, realdiff = p->diff;
2177 solver_show_working = 0;
2180 tt_start = tt_now = time(NULL);
2182 printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2183 p->adjacent ? "adjacent" : "unequal",
2184 p->order, p->order, unequal_diffnames[p->diff]);
2188 desc = new_game_desc(p, rs, &aux, 0);
2189 st = new_game(NULL, p, desc);
2190 solver_state(st, DIFF_RECURSIVE);
2196 if (realdiff != p->diff) neasy++;
2198 tt_last = time(NULL);
2199 if (tt_last > tt_now) {
2201 printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2202 n, (double)n / ((double)tt_now - tt_start),
2203 neasy, (double)neasy*100.0/(double)n,
2204 (double)(n - neasy) / ((double)tt_now - tt_start));
2209 static void usage_exit(const char *msg)
2212 fprintf(stderr, "%s: %s\n", quis, msg);
2213 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
2217 int main(int argc, const char *argv[])
2220 time_t seed = time(NULL);
2221 int do_soak = 0, diff;
2228 while (--argc > 0) {
2229 const char *p = *++argv;
2230 if (!strcmp(p, "--soak"))
2232 else if (!strcmp(p, "--seed")) {
2234 usage_exit("--seed needs an argument");
2235 seed = (time_t)atoi(*++argv);
2237 } else if (*p == '-')
2238 usage_exit("unrecognised option");
2242 rs = random_new((void*)&seed, sizeof(time_t));
2245 if (argc != 1) usage_exit("only one argument for --soak");
2246 p = default_params();
2247 decode_params(p, *argv);
2249 } else if (argc > 0) {
2251 for (i = 0; i < argc; i++) {
2252 const char *id = *argv++;
2253 char *desc = strchr(id, ':'), *err;
2254 p = default_params();
2257 decode_params(p, id);
2258 err = validate_desc(p, desc);
2260 fprintf(stderr, "%s: %s\n", quis, err);
2265 decode_params(p, id);
2266 diff = gen(p, rs, 1);
2271 p = default_params();
2272 p->order = random_upto(rs, 7) + 3;
2273 p->diff = random_upto(rs, 4);
2274 diff = gen(p, rs, 0);
2284 /* vim: set shiftwidth=4 tabstop=8: */