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, COL_SPENT = 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
75 #define F_SPENT_UP 1024
76 #define F_SPENT_RIGHT 2048
77 #define F_SPENT_DOWN 4096
78 #define F_SPENT_LEFT 8192
80 #define ADJ_TO_SPENT(x) ((x) << 9)
82 #define F_ERROR_MASK (F_ERROR|F_ERROR_UP|F_ERROR_RIGHT|F_ERROR_DOWN|F_ERROR_LEFT)
85 int order, completed, cheated, adjacent;
86 digit *nums; /* actual numbers (size order^2) */
87 unsigned char *hints; /* remaining possiblities (size order^3) */
88 unsigned int *flags; /* flags (size order^2) */
91 /* ----------------------------------------------------------
92 * Game parameters and presets
95 /* Steal the method from map.c for difficulty levels. */
97 A(LATIN,Trivial,NULL,t) \
98 A(EASY,Easy,solver_easy, e) \
99 A(SET,Tricky,solver_set, k) \
100 A(EXTREME,Extreme,NULL,x) \
101 A(RECURSIVE,Recursive,NULL,r)
103 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
104 #define TITLE(upper,title,func,lower) #title,
105 #define ENCODE(upper,title,func,lower) #lower
106 #define CONFIG(upper,title,func,lower) ":" #title
107 enum { DIFFLIST(ENUM) DIFFCOUNT, DIFF_IMPOSSIBLE = diff_impossible, DIFF_AMBIGUOUS = diff_ambiguous, DIFF_UNFINISHED = diff_unfinished };
108 static char const *const unequal_diffnames[] = { DIFFLIST(TITLE) };
109 static char const unequal_diffchars[] = DIFFLIST(ENCODE);
110 #define DIFFCONFIG DIFFLIST(CONFIG)
112 #define DEFAULT_PRESET 0
114 const static struct game_params unequal_presets[] = {
119 { 5, DIFF_EXTREME, 0 },
123 { 6, DIFF_EXTREME, 0 },
126 { 7, DIFF_EXTREME, 0 }
129 static int game_fetch_preset(int i, char **name, game_params **params)
134 if (i < 0 || i >= lenof(unequal_presets))
137 ret = snew(game_params);
138 *ret = unequal_presets[i]; /* structure copy */
140 sprintf(buf, "%s: %dx%d %s",
141 ret->adjacent ? "Adjacent" : "Unequal",
142 ret->order, ret->order,
143 unequal_diffnames[ret->diff]);
150 static game_params *default_params(void)
155 if (!game_fetch_preset(DEFAULT_PRESET, &name, &ret)) return NULL;
160 static void free_params(game_params *params)
165 static game_params *dup_params(const game_params *params)
167 game_params *ret = snew(game_params);
168 *ret = *params; /* structure copy */
172 static void decode_params(game_params *ret, char const *string)
174 char const *p = string;
176 ret->order = atoi(p);
177 while (*p && isdigit((unsigned char)*p)) p++;
188 ret->diff = DIFFCOUNT+1; /* ...which is invalid */
190 for (i = 0; i < DIFFCOUNT; i++) {
191 if (*p == unequal_diffchars[i])
199 static char *encode_params(const game_params *params, int full)
203 sprintf(ret, "%d", params->order);
204 if (params->adjacent)
205 sprintf(ret + strlen(ret), "a");
207 sprintf(ret + strlen(ret), "d%c", unequal_diffchars[params->diff]);
212 static config_item *game_configure(const game_params *params)
217 ret = snewn(4, config_item);
219 ret[0].name = "Mode";
220 ret[0].type = C_CHOICES;
221 ret[0].u.choices.choicenames = ":Unequal:Adjacent";
222 ret[0].u.choices.selected = params->adjacent;
224 ret[1].name = "Size (s*s)";
225 ret[1].type = C_STRING;
226 sprintf(buf, "%d", params->order);
227 ret[1].u.string.sval = dupstr(buf);
229 ret[2].name = "Difficulty";
230 ret[2].type = C_CHOICES;
231 ret[2].u.choices.choicenames = DIFFCONFIG;
232 ret[2].u.choices.selected = params->diff;
240 static game_params *custom_params(const config_item *cfg)
242 game_params *ret = snew(game_params);
244 ret->adjacent = cfg[0].u.choices.selected;
245 ret->order = atoi(cfg[1].u.string.sval);
246 ret->diff = cfg[2].u.choices.selected;
251 static const char *validate_params(const game_params *params, int full)
253 if (params->order < 3 || params->order > 32)
254 return "Order must be between 3 and 32";
255 if (params->diff >= DIFFCOUNT)
256 return "Unknown difficulty rating";
257 if (params->order < 5 && params->adjacent &&
258 params->diff >= DIFF_SET)
259 return "Order must be at least 5 for Adjacent puzzles of this difficulty.";
263 /* ----------------------------------------------------------
264 * Various utility functions
267 static const struct { unsigned int f, fo, fe; int dx, dy; char c, ac; } adjthan[] = {
268 { F_ADJ_UP, F_ADJ_DOWN, F_ERROR_UP, 0, -1, '^', '-' },
269 { F_ADJ_RIGHT, F_ADJ_LEFT, F_ERROR_RIGHT, 1, 0, '>', '|' },
270 { F_ADJ_DOWN, F_ADJ_UP, F_ERROR_DOWN, 0, 1, 'v', '-' },
271 { F_ADJ_LEFT, F_ADJ_RIGHT, F_ERROR_LEFT, -1, 0, '<', '|' }
274 static game_state *blank_game(int order, int adjacent)
276 game_state *state = snew(game_state);
277 int o2 = order*order, o3 = o2*order;
279 state->order = order;
280 state->adjacent = adjacent;
281 state->completed = state->cheated = 0;
283 state->nums = snewn(o2, digit);
284 state->hints = snewn(o3, unsigned char);
285 state->flags = snewn(o2, unsigned int);
287 memset(state->nums, 0, o2 * sizeof(digit));
288 memset(state->hints, 0, o3);
289 memset(state->flags, 0, o2 * sizeof(unsigned int));
294 static game_state *dup_game(const game_state *state)
296 game_state *ret = blank_game(state->order, state->adjacent);
297 int o2 = state->order*state->order, o3 = o2*state->order;
299 memcpy(ret->nums, state->nums, o2 * sizeof(digit));
300 memcpy(ret->hints, state->hints, o3);
301 memcpy(ret->flags, state->flags, o2 * sizeof(unsigned int));
306 static void free_game(game_state *state)
314 #define CHECKG(x,y) grid[(y)*o+(x)]
316 /* Returns 0 if it finds an error, 1 otherwise. */
317 static int check_num_adj(digit *grid, game_state *state,
318 int x, int y, int me)
320 unsigned int f = GRID(state, flags, x, y);
321 int ret = 1, i, o = state->order;
323 for (i = 0; i < 4; i++) {
324 int dx = adjthan[i].dx, dy = adjthan[i].dy, n, dn;
326 if (x+dx < 0 || x+dx >= o || y+dy < 0 || y+dy >= o)
330 dn = CHECKG(x+dx, y+dy);
333 if (dn == 0) continue;
335 if (state->adjacent) {
338 if ((f & adjthan[i].f) && (gd != 1)) {
339 debug(("check_adj error (%d,%d):%d should be | (%d,%d):%d",
340 x, y, n, x+dx, y+dy, dn));
341 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
344 if (!(f & adjthan[i].f) && (gd == 1)) {
345 debug(("check_adj error (%d,%d):%d should not be | (%d,%d):%d",
346 x, y, n, x+dx, y+dy, dn));
347 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
352 if ((f & adjthan[i].f) && (n <= dn)) {
353 debug(("check_adj error (%d,%d):%d not > (%d,%d):%d",
354 x, y, n, x+dx, y+dy, dn));
355 if (me) GRID(state, flags, x, y) |= adjthan[i].fe;
363 /* Returns 0 if it finds an error, 1 otherwise. */
364 static int check_num_error(digit *grid, game_state *state,
365 int x, int y, int mark_errors)
367 int o = state->order;
368 int xx, yy, val = CHECKG(x,y), ret = 1;
372 /* check for dups in same column. */
373 for (yy = 0; yy < state->order; yy++) {
374 if (yy == y) continue;
375 if (CHECKG(x,yy) == val) ret = 0;
378 /* check for dups in same row. */
379 for (xx = 0; xx < state->order; xx++) {
380 if (xx == x) continue;
381 if (CHECKG(xx,y) == val) ret = 0;
385 debug(("check_num_error (%d,%d) duplicate %d", x, y, val));
386 if (mark_errors) GRID(state, flags, x, y) |= F_ERROR;
391 /* Returns: -1 for 'wrong'
393 * 1 for 'complete and correct'
395 static int check_complete(digit *grid, game_state *state, int mark_errors)
397 int x, y, ret = 1, o = state->order;
400 assert(grid == state->nums);
402 for (x = 0; x < state->order; x++) {
403 for (y = 0; y < state->order; y++) {
405 GRID(state, flags, x, y) &= ~F_ERROR_MASK;
406 if (grid[y*o+x] == 0) {
409 if (!check_num_error(grid, state, x, y, mark_errors)) ret = -1;
410 if (!check_num_adj(grid, state, x, y, mark_errors)) ret = -1;
414 if (ret == 1 && latin_check(grid, o))
419 static char n2c(digit n, int order) {
420 if (n == 0) return ' ';
422 if (n < 10) return '0' + n;
424 if (n < 11) return '0' + n-1;
426 if (n <= 26) return 'A' + n;
431 /* should be 'digit', but includes -1 for 'not a digit'.
432 * Includes keypresses (0 especially) for interpret_move. */
433 static int c2n(int c, int order) {
434 if (c < 0 || c > 0xff)
436 if (c == ' ' || c == '\b')
439 if (c >= '0' && c <= '9')
440 return (int)(c - '0');
442 if (c >= '0' && c <= '9')
443 return (int)(c - '0' + 1);
444 if (c >= 'A' && c <= 'Z')
445 return (int)(c - 'A' + 11);
446 if (c >= 'a' && c <= 'z')
447 return (int)(c - 'a' + 11);
452 static int game_can_format_as_text_now(const game_params *params)
457 static char *game_text_format(const game_state *state)
462 len = (state->order*2) * (state->order*2-1) + 1;
463 ret = snewn(len, char);
466 for (y = 0; y < state->order; y++) {
467 for (x = 0; x < state->order; x++) {
468 n = GRID(state, nums, x, y);
469 *p++ = n > 0 ? n2c(n, state->order) : '.';
471 if (x < (state->order-1)) {
472 if (state->adjacent) {
473 *p++ = (GRID(state, flags, x, y) & F_ADJ_RIGHT) ? '|' : ' ';
475 if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
477 else if (GRID(state, flags, x+1, y) & F_ADJ_LEFT)
486 if (y < (state->order-1)) {
487 for (x = 0; x < state->order; x++) {
488 if (state->adjacent) {
489 *p++ = (GRID(state, flags, x, y) & F_ADJ_DOWN) ? '-' : ' ';
491 if (GRID(state, flags, x, y) & F_ADJ_DOWN)
493 else if (GRID(state, flags, x, y+1) & F_ADJ_UP)
499 if (x < state->order-1)
507 assert(p - ret == len);
511 #ifdef STANDALONE_SOLVER
512 static void game_debug(game_state *state)
514 char *dbg = game_text_format(state);
520 /* ----------------------------------------------------------
525 int len, gx, gy, lx, ly;
532 struct solver_link *links;
535 static void solver_add_link(struct solver_ctx *ctx,
536 int gx, int gy, int lx, int ly, int len)
538 if (ctx->alinks < ctx->nlinks+1) {
539 ctx->alinks = ctx->alinks*2 + 1;
540 /*debug(("resizing ctx->links, new size %d", ctx->alinks));*/
541 ctx->links = sresize(ctx->links, ctx->alinks, struct solver_link);
543 ctx->links[ctx->nlinks].gx = gx;
544 ctx->links[ctx->nlinks].gy = gy;
545 ctx->links[ctx->nlinks].lx = lx;
546 ctx->links[ctx->nlinks].ly = ly;
547 ctx->links[ctx->nlinks].len = len;
549 /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d",
550 len, lx, ly, gx, gy, ctx->nlinks));*/
553 static struct solver_ctx *new_ctx(game_state *state)
555 struct solver_ctx *ctx = snew(struct solver_ctx);
556 int o = state->order;
560 ctx->nlinks = ctx->alinks = 0;
564 if (state->adjacent) return ctx; /* adjacent mode doesn't use links. */
566 for (x = 0; x < o; x++) {
567 for (y = 0; y < o; y++) {
568 f = GRID(state, flags, x, y);
569 for (i = 0; i < 4; i++) {
570 if (f & adjthan[i].f)
571 solver_add_link(ctx, x, y, x+adjthan[i].dx, y+adjthan[i].dy, 1);
579 static void *clone_ctx(void *vctx)
581 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
582 return new_ctx(ctx->state);
585 static void free_ctx(void *vctx)
587 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
588 if (ctx->links) sfree(ctx->links);
592 static void solver_nminmax(struct latin_solver *solver,
593 int x, int y, int *min_r, int *max_r,
594 unsigned char **ns_r)
596 int o = solver->o, min = o, max = 0, n;
599 assert(x >= 0 && y >= 0 && x < o && y < o);
601 ns = solver->cube + cubepos(x,y,1);
604 min = max = grid(x,y)-1;
606 for (n = 0; n < o; n++) {
608 if (n > max) max = n;
609 if (n < min) min = n;
613 if (min_r) *min_r = min;
614 if (max_r) *max_r = max;
615 if (ns_r) *ns_r = ns;
618 static int solver_links(struct latin_solver *solver, void *vctx)
620 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
621 int i, j, lmin, gmax, nchanged = 0;
622 unsigned char *gns, *lns;
623 struct solver_link *link;
625 for (i = 0; i < ctx->nlinks; i++) {
626 link = &ctx->links[i];
627 solver_nminmax(solver, link->gx, link->gy, NULL, &gmax, &gns);
628 solver_nminmax(solver, link->lx, link->ly, &lmin, NULL, &lns);
630 for (j = 0; j < solver->o; j++) {
631 /* For the 'greater' end of the link, discount all numbers
632 * too small to satisfy the inequality. */
634 if (j < (lmin+link->len)) {
635 #ifdef STANDALONE_SOLVER
636 if (solver_show_working) {
637 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
638 solver_recurse_depth*4, "",
639 link->gx+1, link->gy+1, link->lx+1, link->ly+1);
640 printf("%*s ruling out %d at (%d,%d)\n",
641 solver_recurse_depth*4, "",
642 j+1, link->gx+1, link->gy+1);
645 cube(link->gx, link->gy, j+1) = FALSE;
649 /* For the 'lesser' end of the link, discount all numbers
650 * too large to satisfy inequality. */
652 if (j > (gmax-link->len)) {
653 #ifdef STANDALONE_SOLVER
654 if (solver_show_working) {
655 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
656 solver_recurse_depth*4, "",
657 link->gx+1, link->gy+1, link->lx+1, link->ly+1);
658 printf("%*s ruling out %d at (%d,%d)\n",
659 solver_recurse_depth*4, "",
660 j+1, link->lx+1, link->ly+1);
663 cube(link->lx, link->ly, j+1) = FALSE;
672 static int solver_adjacent(struct latin_solver *solver, void *vctx)
674 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
675 int nchanged = 0, x, y, i, n, o = solver->o, nx, ny, gd;
677 /* Update possible values based on known values and adjacency clues. */
679 for (x = 0; x < o; x++) {
680 for (y = 0; y < o; y++) {
681 if (grid(x, y) == 0) continue;
683 /* We have a definite number here. Make sure that any
684 * adjacent possibles reflect the adjacent/non-adjacent clue. */
686 for (i = 0; i < 4; i++) {
687 int isadjacent = (GRID(ctx->state, flags, x, y) & adjthan[i].f);
689 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
690 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
693 for (n = 0; n < o; n++) {
694 /* Continue past numbers the adjacent square _could_ be,
695 * given the clue we have. */
696 gd = abs((n+1) - grid(x, y));
697 if (isadjacent && (gd == 1)) continue;
698 if (!isadjacent && (gd != 1)) continue;
700 if (cube(nx, ny, n+1) == FALSE)
701 continue; /* already discounted this possibility. */
703 #ifdef STANDALONE_SOLVER
704 if (solver_show_working) {
705 printf("%*sadjacent elimination, (%d,%d):%d %s (%d,%d):\n",
706 solver_recurse_depth*4, "",
707 x+1, y+1, grid(x, y), isadjacent ? "|" : "!|", nx+1, ny+1);
708 printf("%*s ruling out %d at (%d,%d)\n",
709 solver_recurse_depth*4, "", n+1, nx+1, ny+1);
712 cube(nx, ny, n+1) = FALSE;
722 static int solver_adjacent_set(struct latin_solver *solver, void *vctx)
724 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
725 int x, y, i, n, nn, o = solver->o, nx, ny, gd;
726 int nchanged = 0, *scratch = snewn(o, int);
728 /* Update possible values based on other possible values
729 * of adjacent squares, and adjacency clues. */
731 for (x = 0; x < o; x++) {
732 for (y = 0; y < o; y++) {
733 for (i = 0; i < 4; i++) {
734 int isadjacent = (GRID(ctx->state, flags, x, y) & adjthan[i].f);
736 nx = x + adjthan[i].dx, ny = y + adjthan[i].dy;
737 if (nx < 0 || ny < 0 || nx >= o || ny >= o)
740 /* We know the current possibles for the square (x,y)
741 * and also the adjacency clue from (x,y) to (nx,ny).
742 * Construct a maximum set of possibles for (nx,ny)
743 * in scratch, based on these constraints... */
745 memset(scratch, 0, o*sizeof(int));
747 for (n = 0; n < o; n++) {
748 if (cube(x, y, n+1) == FALSE) continue;
750 for (nn = 0; nn < o; nn++) {
751 if (n == nn) continue;
754 if (isadjacent && (gd != 1)) continue;
755 if (!isadjacent && (gd == 1)) continue;
761 /* ...and remove any possibilities for (nx,ny) that are
762 * currently set but are not indicated in scratch. */
763 for (n = 0; n < o; n++) {
764 if (scratch[n] == 1) continue;
765 if (cube(nx, ny, n+1) == FALSE) continue;
767 #ifdef STANDALONE_SOLVER
768 if (solver_show_working) {
769 printf("%*sadjacent possible elimination, (%d,%d) %s (%d,%d):\n",
770 solver_recurse_depth*4, "",
771 x+1, y+1, isadjacent ? "|" : "!|", nx+1, ny+1);
772 printf("%*s ruling out %d at (%d,%d)\n",
773 solver_recurse_depth*4, "", n+1, nx+1, ny+1);
776 cube(nx, ny, n+1) = FALSE;
786 static int solver_easy(struct latin_solver *solver, void *vctx)
788 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
789 if (ctx->state->adjacent)
790 return solver_adjacent(solver, vctx);
792 return solver_links(solver, vctx);
795 static int solver_set(struct latin_solver *solver, void *vctx)
797 struct solver_ctx *ctx = (struct solver_ctx *)vctx;
798 if (ctx->state->adjacent)
799 return solver_adjacent_set(solver, vctx);
804 #define SOLVER(upper,title,func,lower) func,
805 static usersolver_t const unequal_solvers[] = { DIFFLIST(SOLVER) };
807 static int solver_state(game_state *state, int maxdiff)
809 struct solver_ctx *ctx = new_ctx(state);
810 struct latin_solver solver;
813 latin_solver_alloc(&solver, state->nums, state->order);
815 diff = latin_solver_main(&solver, maxdiff,
816 DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
817 DIFF_EXTREME, DIFF_RECURSIVE,
818 unequal_solvers, ctx, clone_ctx, free_ctx);
820 memcpy(state->hints, solver.cube, state->order*state->order*state->order);
824 latin_solver_free(&solver);
826 if (diff == DIFF_IMPOSSIBLE)
828 if (diff == DIFF_UNFINISHED)
830 if (diff == DIFF_AMBIGUOUS)
835 static game_state *solver_hint(const game_state *state, int *diff_r,
836 int mindiff, int maxdiff)
838 game_state *ret = dup_game(state);
841 for (diff = mindiff; diff <= maxdiff; diff++) {
842 r = solver_state(ret, diff);
843 debug(("solver_state after %s %d", unequal_diffnames[diff], r));
844 if (r != 0) goto done;
848 if (diff_r) *diff_r = (r > 0) ? diff : -1;
852 /* ----------------------------------------------------------
856 static char *latin_desc(digit *sq, size_t order)
858 int o2 = order*order, i;
859 char *soln = snewn(o2+2, char);
862 for (i = 0; i < o2; i++)
863 soln[i+1] = n2c(sq[i], order);
869 /* returns non-zero if it placed (or could have placed) clue. */
870 static int gg_place_clue(game_state *state, int ccode, digit *latin, int checkonly)
872 int loc = ccode / 5, which = ccode % 5;
873 int x = loc % state->order, y = loc / state->order;
875 assert(loc < state->order*state->order);
877 if (which == 4) { /* add number */
878 if (state->nums[loc] != 0) {
879 #ifdef STANDALONE_SOLVER
880 if (state->nums[loc] != latin[loc]) {
881 printf("inconsistency for (%d,%d): state %d latin %d\n",
882 x+1, y+1, state->nums[loc], latin[loc]);
885 assert(state->nums[loc] == latin[loc]);
889 state->nums[loc] = latin[loc];
891 } else { /* add flag */
895 return 0; /* never add flag clues in adjacent mode (they're always
898 if (state->flags[loc] & adjthan[which].f)
899 return 0; /* already has flag. */
901 lx = x + adjthan[which].dx;
902 ly = y + adjthan[which].dy;
903 if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order)
904 return 0; /* flag compares to off grid */
906 lloc = loc + adjthan[which].dx + adjthan[which].dy*state->order;
907 if (latin[loc] <= latin[lloc])
908 return 0; /* flag would be incorrect */
911 state->flags[loc] |= adjthan[which].f;
917 /* returns non-zero if it removed (or could have removed) the clue. */
918 static int gg_remove_clue(game_state *state, int ccode, int checkonly)
920 int loc = ccode / 5, which = ccode % 5;
921 #ifdef STANDALONE_SOLVER
922 int x = loc % state->order, y = loc / state->order;
925 assert(loc < state->order*state->order);
927 if (which == 4) { /* remove number. */
928 if (state->nums[loc] == 0) return 0;
930 #ifdef STANDALONE_SOLVER
931 if (solver_show_working)
932 printf("gg_remove_clue: removing %d at (%d,%d)",
933 state->nums[loc], x+1, y+1);
935 state->nums[loc] = 0;
937 } else { /* remove flag */
939 return 0; /* never remove clues in adjacent mode. */
941 if (!(state->flags[loc] & adjthan[which].f)) return 0;
943 #ifdef STANDALONE_SOLVER
944 if (solver_show_working)
945 printf("gg_remove_clue: removing %c at (%d,%d)",
946 adjthan[which].c, x+1, y+1);
948 state->flags[loc] &= ~adjthan[which].f;
954 static int gg_best_clue(game_state *state, int *scratch, digit *latin)
956 int ls = state->order * state->order * 5;
957 int maxposs = 0, minclues = 5, best = -1, i, j;
958 int nposs, nclues, loc;
960 #ifdef STANDALONE_SOLVER
961 if (solver_show_working) {
963 latin_solver_debug(state->hints, state->order);
967 for (i = ls; i-- > 0 ;) {
968 if (!gg_place_clue(state, scratch[i], latin, 1)) continue;
970 loc = scratch[i] / 5;
971 for (j = nposs = 0; j < state->order; j++) {
972 if (state->hints[loc*state->order + j]) nposs++;
974 for (j = nclues = 0; j < 4; j++) {
975 if (state->flags[loc] & adjthan[j].f) nclues++;
977 if ((nposs > maxposs) ||
978 (nposs == maxposs && nclues < minclues)) {
979 best = i; maxposs = nposs; minclues = nclues;
980 #ifdef STANDALONE_SOLVER
981 if (solver_show_working) {
982 int x = loc % state->order, y = loc / state->order;
983 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
984 best, x+1, y+1, nposs, nclues);
989 /* if we didn't solve, we must have 1 clue to place! */
994 #ifdef STANDALONE_SOLVER
996 #define MAXTRIES maxtries
1002 static int game_assemble(game_state *new, int *scratch, digit *latin,
1005 game_state *copy = dup_game(new);
1008 if (difficulty >= DIFF_RECURSIVE) {
1009 /* We mustn't use any solver that might guess answers;
1010 * if it guesses wrongly but solves, gg_place_clue will
1011 * get mighty confused. We will always trim clues down
1012 * (making it more difficult) in game_strip, which doesn't
1013 * have this problem. */
1014 difficulty = DIFF_RECURSIVE-1;
1017 #ifdef STANDALONE_SOLVER
1018 if (solver_show_working) {
1020 latin_solver_debug(new->hints, new->order);
1026 if (solver_state(copy, difficulty) == 1) break;
1028 best = gg_best_clue(copy, scratch, latin);
1029 gg_place_clue(new, scratch[best], latin, 0);
1030 gg_place_clue(copy, scratch[best], latin, 0);
1033 #ifdef STANDALONE_SOLVER
1034 if (solver_show_working) {
1035 char *dbg = game_text_format(new);
1036 printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
1043 static void game_strip(game_state *new, int *scratch, digit *latin,
1046 int o = new->order, o2 = o*o, lscratch = o2*5, i;
1047 game_state *copy = blank_game(new->order, new->adjacent);
1049 /* For each symbol (if it exists in new), try and remove it and
1050 * solve again; if we couldn't solve without it put it back. */
1051 for (i = 0; i < lscratch; i++) {
1052 if (!gg_remove_clue(new, scratch[i], 0)) continue;
1054 memcpy(copy->nums, new->nums, o2 * sizeof(digit));
1055 memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
1057 if (solver_state(copy, difficulty) != 1) {
1058 /* put clue back, we can't solve without it. */
1059 int ret = gg_place_clue(new, scratch[i], latin, 0);
1062 #ifdef STANDALONE_SOLVER
1063 if (solver_show_working)
1064 printf("game_strip: clue was redundant.");
1069 #ifdef STANDALONE_SOLVER
1070 if (solver_show_working) {
1071 char *dbg = game_text_format(new);
1072 debug(("game_strip: done, %d solver iterations.", gg_solved));
1079 static void add_adjacent_flags(game_state *state, digit *latin)
1081 int x, y, o = state->order;
1083 /* All clues in adjacent mode are always present (the only variables are
1084 * the numbers). This adds all the flags to state based on the supplied
1087 for (y = 0; y < o; y++) {
1088 for (x = 0; x < o; x++) {
1089 if (x < (o-1) && (abs(latin[y*o+x] - latin[y*o+x+1]) == 1)) {
1090 GRID(state, flags, x, y) |= F_ADJ_RIGHT;
1091 GRID(state, flags, x+1, y) |= F_ADJ_LEFT;
1093 if (y < (o-1) && (abs(latin[y*o+x] - latin[(y+1)*o+x]) == 1)) {
1094 GRID(state, flags, x, y) |= F_ADJ_DOWN;
1095 GRID(state, flags, x, y+1) |= F_ADJ_UP;
1101 static char *new_game_desc(const game_params *params_in, random_state *rs,
1102 char **aux, int interactive)
1104 game_params params_copy = *params_in; /* structure copy */
1105 game_params *params = ¶ms_copy;
1107 int i, x, y, retlen, k, nsol;
1108 int o2 = params->order * params->order, ntries = 1;
1109 int *scratch, lscratch = o2*5;
1111 game_state *state = blank_game(params->order, params->adjacent);
1113 /* Generate a list of 'things to strip' (randomised later) */
1114 scratch = snewn(lscratch, int);
1115 /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1116 for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1119 #ifdef STANDALONE_SOLVER
1120 if (solver_show_working)
1121 printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1122 unequal_diffnames[params->diff], ntries);
1125 sq = latin_generate(params->order, rs);
1126 latin_debug(sq, params->order);
1127 /* Separately shuffle the numeric and inequality clues */
1128 shuffle(scratch, lscratch/5, sizeof(int), rs);
1129 shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1131 memset(state->nums, 0, o2 * sizeof(digit));
1132 memset(state->flags, 0, o2 * sizeof(unsigned int));
1134 if (state->adjacent) {
1135 /* All adjacency flags are always present. */
1136 add_adjacent_flags(state, sq);
1140 if (game_assemble(state, scratch, sq, params->diff) < 0)
1142 game_strip(state, scratch, sq, params->diff);
1144 if (params->diff > 0) {
1145 game_state *copy = dup_game(state);
1146 nsol = solver_state(copy, params->diff-1);
1149 #ifdef STANDALONE_SOLVER
1150 if (solver_show_working)
1151 printf("game_assemble: puzzle as generated is too easy.\n");
1153 if (ntries < MAXTRIES) {
1157 #ifdef STANDALONE_SOLVER
1158 if (solver_show_working)
1159 printf("Unable to generate %s %dx%d after %d attempts.\n",
1160 unequal_diffnames[params->diff],
1161 params->order, params->order, MAXTRIES);
1166 #ifdef STANDALONE_SOLVER
1167 if (solver_show_working)
1168 printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1169 unequal_diffnames[params->diff], ntries, gg_solved);
1172 ret = NULL; retlen = 0;
1173 for (y = 0; y < params->order; y++) {
1174 for (x = 0; x < params->order; x++) {
1175 unsigned int f = GRID(state, flags, x, y);
1176 k = sprintf(buf, "%d%s%s%s%s,",
1177 GRID(state, nums, x, y),
1178 (f & F_ADJ_UP) ? "U" : "",
1179 (f & F_ADJ_RIGHT) ? "R" : "",
1180 (f & F_ADJ_DOWN) ? "D" : "",
1181 (f & F_ADJ_LEFT) ? "L" : "");
1183 ret = sresize(ret, retlen + k + 1, char);
1184 strcpy(ret + retlen, buf);
1188 *aux = latin_desc(sq, params->order);
1197 static game_state *load_game(const game_params *params, const char *desc,
1200 game_state *state = blank_game(params->order, params->adjacent);
1201 const char *p = desc;
1202 int i = 0, n, o = params->order, x, y;
1206 while (*p >= 'a' && *p <= 'z') {
1211 why = "Too much data to fill grid"; goto fail;
1214 if (*p < '0' || *p > '9') {
1215 why = "Expecting number in game description"; goto fail;
1218 if (n < 0 || n > o) {
1219 why = "Out-of-range number in game description"; goto fail;
1221 state->nums[i] = (digit)n;
1222 while (*p >= '0' && *p <= '9') p++; /* skip number */
1224 if (state->nums[i] != 0)
1225 state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1227 while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1229 case 'U': state->flags[i] |= F_ADJ_UP; break;
1230 case 'R': state->flags[i] |= F_ADJ_RIGHT; break;
1231 case 'D': state->flags[i] |= F_ADJ_DOWN; break;
1232 case 'L': state->flags[i] |= F_ADJ_LEFT; break;
1233 default: why = "Expecting flag URDL in game description"; goto fail;
1238 if (i < o*o && *p != ',') {
1239 why = "Missing separator"; goto fail;
1244 why = "Not enough data to fill grid"; goto fail;
1247 for (y = 0; y < o; y++) {
1248 for (x = 0; x < o; x++) {
1249 for (n = 0; n < 4; n++) {
1250 if (GRID(state, flags, x, y) & adjthan[n].f) {
1251 int nx = x + adjthan[n].dx;
1252 int ny = y + adjthan[n].dy;
1253 /* a flag must not point us off the grid. */
1254 if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1255 why = "Flags go off grid"; goto fail;
1257 if (params->adjacent) {
1258 /* if one cell is adjacent to another, the other must
1259 * also be adjacent to the first. */
1260 if (!(GRID(state, flags, nx, ny) & adjthan[n].fo)) {
1261 why = "Flags contradicting each other"; goto fail;
1264 /* if one cell is GT another, the other must _not_ also
1265 * be GT the first. */
1266 if (GRID(state, flags, nx, ny) & adjthan[n].fo) {
1267 why = "Flags contradicting each other"; goto fail;
1279 if (why_r) *why_r = why;
1283 static game_state *new_game(midend *me, const game_params *params,
1286 game_state *state = load_game(params, desc, NULL);
1288 assert("Unable to load ?validated game.");
1294 static const char *validate_desc(const game_params *params, const char *desc)
1297 game_state *dummy = load_game(params, desc, &why);
1306 static char *solve_game(const game_state *state, const game_state *currstate,
1307 const char *aux, const char **error)
1313 if (aux) return dupstr(aux);
1315 solved = dup_game(state);
1316 for (r = 0; r < state->order*state->order; r++) {
1317 if (!(solved->flags[r] & F_IMMUTABLE))
1318 solved->nums[r] = 0;
1320 r = solver_state(solved, DIFFCOUNT-1); /* always use full solver */
1321 if (r > 0) ret = latin_desc(solved->nums, solved->order);
1326 /* ----------------------------------------------------------
1327 * Game UI input processing.
1331 int hx, hy; /* as for solo.c, highlight pos */
1332 int hshow, hpencil, hcursor; /* show state, type, and ?cursor. */
1335 static game_ui *new_ui(const game_state *state)
1337 game_ui *ui = snew(game_ui);
1339 ui->hx = ui->hy = 0;
1340 ui->hpencil = ui->hshow = ui->hcursor = 0;
1345 static void free_ui(game_ui *ui)
1350 static char *encode_ui(const game_ui *ui)
1355 static void decode_ui(game_ui *ui, const char *encoding)
1359 static void game_changed_state(game_ui *ui, const game_state *oldstate,
1360 const game_state *newstate)
1362 /* See solo.c; if we were pencil-mode highlighting and
1363 * somehow a square has just been properly filled, cancel
1365 if (ui->hshow && ui->hpencil && !ui->hcursor &&
1366 GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1371 struct game_drawstate {
1372 int tilesize, order, started, adjacent;
1373 digit *nums; /* copy of nums, o^2 */
1374 unsigned char *hints; /* copy of hints, o^3 */
1375 unsigned int *flags; /* o^2 */
1377 int hx, hy, hshow, hpencil; /* as for game_ui. */
1381 static char *interpret_move(const game_state *state, game_ui *ui,
1382 const game_drawstate *ds,
1383 int ox, int oy, int button)
1385 int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1387 int shift_or_control = button & (MOD_SHFT | MOD_CTRL);
1389 button &= ~MOD_MASK;
1391 if (x >= 0 && x < ds->order && y >= 0 && y < ds->order && IS_MOUSE_DOWN(button)) {
1392 if (oy - COORD(y) > TILE_SIZE && ox - COORD(x) > TILE_SIZE)
1395 if (oy - COORD(y) > TILE_SIZE) {
1396 if (GRID(state, flags, x, y) & F_ADJ_DOWN)
1397 sprintf(buf, "F%d,%d,%d", x, y, F_SPENT_DOWN);
1398 else if (y + 1 < ds->order && GRID(state, flags, x, y + 1) & F_ADJ_UP)
1399 sprintf(buf, "F%d,%d,%d", x, y + 1, F_SPENT_UP);
1404 if (ox - COORD(x) > TILE_SIZE) {
1405 if (GRID(state, flags, x, y) & F_ADJ_RIGHT)
1406 sprintf(buf, "F%d,%d,%d", x, y, F_SPENT_RIGHT);
1407 else if (x + 1 < ds->order && GRID(state, flags, x + 1, y) & F_ADJ_LEFT)
1408 sprintf(buf, "F%d,%d,%d", x + 1, y, F_SPENT_LEFT);
1413 if (button == LEFT_BUTTON) {
1414 /* normal highlighting for non-immutable squares */
1415 if (GRID(state, flags, x, y) & F_IMMUTABLE)
1417 else if (x == ui->hx && y == ui->hy &&
1418 ui->hshow && ui->hpencil == 0)
1421 ui->hx = x; ui->hy = y; ui->hpencil = 0;
1427 if (button == RIGHT_BUTTON) {
1428 /* pencil highlighting for non-filled squares */
1429 if (GRID(state, nums, x, y) != 0)
1431 else if (x == ui->hx && y == ui->hy &&
1432 ui->hshow && ui->hpencil)
1435 ui->hx = x; ui->hy = y; ui->hpencil = 1;
1443 if (IS_CURSOR_MOVE(button)) {
1444 if (shift_or_control) {
1445 int nx = ui->hx, ny = ui->hy, i, self;
1446 move_cursor(button, &nx, &ny, ds->order, ds->order, FALSE);
1447 ui->hshow = ui->hcursor = 1;
1449 for (i = 0; i < 4 && (nx != ui->hx + adjthan[i].dx ||
1450 ny != ui->hy + adjthan[i].dy); ++i);
1453 return UI_UPDATE; /* invalid direction, i.e. out of
1456 if (!(GRID(state, flags, ui->hx, ui->hy) & adjthan[i].f ||
1457 GRID(state, flags, nx, ny ) & adjthan[i].fo))
1458 return UI_UPDATE; /* no clue to toggle */
1460 if (state->adjacent)
1461 self = (adjthan[i].dx >= 0 && adjthan[i].dy >= 0);
1463 self = (GRID(state, flags, ui->hx, ui->hy) & adjthan[i].f);
1466 sprintf(buf, "F%d,%d,%d", ui->hx, ui->hy,
1467 ADJ_TO_SPENT(adjthan[i].f));
1469 sprintf(buf, "F%d,%d,%d", nx, ny,
1470 ADJ_TO_SPENT(adjthan[i].fo));
1474 move_cursor(button, &ui->hx, &ui->hy, ds->order, ds->order, FALSE);
1475 ui->hshow = ui->hcursor = 1;
1479 if (ui->hshow && IS_CURSOR_SELECT(button)) {
1480 ui->hpencil = 1 - ui->hpencil;
1485 n = c2n(button, state->order);
1486 if (ui->hshow && n >= 0 && n <= ds->order) {
1487 debug(("button %d, cbutton %d", button, (int)((char)button)));
1489 debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1490 n, ui->hx, ui->hy, ui->hpencil,
1491 GRID(state, flags, ui->hx, ui->hy),
1492 GRID(state, nums, ui->hx, ui->hy)));
1494 if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE)
1495 return NULL; /* can't edit immutable square (!) */
1496 if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0)
1497 return NULL; /* can't change hints on filled square (!) */
1500 sprintf(buf, "%c%d,%d,%d",
1501 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1503 if (!ui->hcursor) ui->hshow = 0;
1508 if (button == 'H' || button == 'h')
1510 if (button == 'M' || button == 'm')
1516 static game_state *execute_move(const game_state *state, const char *move)
1518 game_state *ret = NULL;
1521 debug(("execute_move: %s", move));
1523 if ((move[0] == 'P' || move[0] == 'R') &&
1524 sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1525 x >= 0 && x < state->order && y >= 0 && y < state->order &&
1526 n >= 0 && n <= state->order) {
1527 ret = dup_game(state);
1528 if (move[0] == 'P' && n > 0)
1529 HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1);
1531 GRID(ret, nums, x, y) = n;
1532 for (i = 0; i < state->order; i++)
1533 HINT(ret, x, y, i) = 0;
1535 /* real change to grid; check for completion */
1536 if (!ret->completed && check_complete(ret->nums, ret, 1) > 0)
1537 ret->completed = TRUE;
1540 } else if (move[0] == 'S') {
1543 ret = dup_game(state);
1544 ret->completed = ret->cheated = TRUE;
1547 for (i = 0; i < state->order*state->order; i++) {
1548 n = c2n((int)*p, state->order);
1549 if (!*p || n <= 0 || n > state->order)
1554 if (*p) goto badmove;
1555 rc = check_complete(ret->nums, ret, 1);
1558 } else if (move[0] == 'M') {
1559 ret = dup_game(state);
1560 for (x = 0; x < state->order; x++) {
1561 for (y = 0; y < state->order; y++) {
1562 for (n = 0; n < state->order; n++) {
1563 HINT(ret, x, y, n) = 1;
1568 } else if (move[0] == 'H') {
1569 return solver_hint(state, NULL, DIFF_EASY, DIFF_EASY);
1570 } else if (move[0] == 'F' && sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1571 x >= 0 && x < state->order && y >= 0 && y < state->order) {
1572 ret = dup_game(state);
1573 GRID(ret, flags, x, y) ^= n;
1578 if (ret) free_game(ret);
1582 /* ----------------------------------------------------------------------
1583 * Drawing/printing routines.
1586 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1588 static void game_compute_size(const game_params *params, int tilesize,
1591 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1592 struct { int tilesize, order; } ads, *ds = &ads;
1593 ads.tilesize = tilesize;
1594 ads.order = params->order;
1596 *x = *y = DRAW_SIZE;
1599 static void game_set_size(drawing *dr, game_drawstate *ds,
1600 const game_params *params, int tilesize)
1602 ds->tilesize = tilesize;
1605 static float *game_colours(frontend *fe, int *ncolours)
1607 float *ret = snewn(3 * NCOLOURS, float);
1610 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1612 for (i = 0; i < 3; i++) {
1613 ret[COL_TEXT * 3 + i] = 0.0F;
1614 ret[COL_GRID * 3 + i] = 0.5F;
1617 /* Lots of these were taken from solo.c. */
1618 ret[COL_GUESS * 3 + 0] = 0.0F;
1619 ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1620 ret[COL_GUESS * 3 + 2] = 0.0F;
1622 ret[COL_ERROR * 3 + 0] = 1.0F;
1623 ret[COL_ERROR * 3 + 1] = 0.0F;
1624 ret[COL_ERROR * 3 + 2] = 0.0F;
1626 ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1627 ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1628 ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1630 *ncolours = NCOLOURS;
1634 static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1636 struct game_drawstate *ds = snew(struct game_drawstate);
1637 int o2 = state->order*state->order, o3 = o2*state->order;
1640 ds->order = state->order;
1641 ds->adjacent = state->adjacent;
1643 ds->nums = snewn(o2, digit);
1644 ds->hints = snewn(o3, unsigned char);
1645 ds->flags = snewn(o2, unsigned int);
1646 memset(ds->nums, 0, o2*sizeof(digit));
1647 memset(ds->hints, 0, o3);
1648 memset(ds->flags, 0, o2*sizeof(unsigned int));
1650 ds->hx = ds->hy = 0;
1651 ds->started = ds->hshow = ds->hpencil = ds->hflash = 0;
1656 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1664 static void draw_gt(drawing *dr, int ox, int oy,
1665 int dx1, int dy1, int dx2, int dy2, int col)
1668 int xdx = (dx1+dx2 ? 0 : 1), xdy = (dx1+dx2 ? 1 : 0);
1669 coords[0] = ox + xdx;
1670 coords[1] = oy + xdy;
1671 coords[2] = ox + xdx + dx1;
1672 coords[3] = oy + xdy + dy1;
1673 coords[4] = ox + xdx + dx1 + dx2;
1674 coords[5] = oy + xdy + dy1 + dy2;
1675 coords[6] = ox - xdx + dx1 + dx2;
1676 coords[7] = oy - xdy + dy1 + dy2;
1677 coords[8] = ox - xdx + dx1;
1678 coords[9] = oy - xdy + dy1;
1679 coords[10] = ox - xdx;
1680 coords[11] = oy - xdy;
1681 draw_polygon(dr, coords, 6, col, col);
1684 #define COLOUR(direction) (f & (F_ERROR_##direction) ? COL_ERROR : \
1685 f & (F_SPENT_##direction) ? COL_SPENT : fg)
1687 static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy,
1688 unsigned int f, int bg, int fg)
1690 int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4;
1692 /* Draw all the greater-than signs emanating from this tile. */
1695 if (bg >= 0) draw_rect(dr, ox, oy - g, TILE_SIZE, g, bg);
1696 draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2, COLOUR(UP));
1697 draw_update(dr, ox, oy-g, TILE_SIZE, g);
1699 if (f & F_ADJ_RIGHT) {
1700 if (bg >= 0) draw_rect(dr, ox + TILE_SIZE, oy, g, TILE_SIZE, bg);
1701 draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2, COLOUR(RIGHT));
1702 draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1704 if (f & F_ADJ_DOWN) {
1705 if (bg >= 0) draw_rect(dr, ox, oy + TILE_SIZE, TILE_SIZE, g, bg);
1706 draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2, COLOUR(DOWN));
1707 draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1709 if (f & F_ADJ_LEFT) {
1710 if (bg >= 0) draw_rect(dr, ox - g, oy, g, TILE_SIZE, bg);
1711 draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2, COLOUR(LEFT));
1712 draw_update(dr, ox-g, oy, g, TILE_SIZE);
1716 static void draw_adjs(drawing *dr, game_drawstate *ds, int ox, int oy,
1717 unsigned int f, int bg, int fg)
1719 int g = GAP_SIZE, g38 = 3*(g+1)/8, g4 = (g+1)/4;
1721 /* Draw all the adjacency bars relevant to this tile; we only have
1722 * to worry about F_ADJ_RIGHT and F_ADJ_DOWN.
1724 * If we _only_ have the error flag set (i.e. it's not supposed to be
1725 * adjacent, but adjacent numbers were entered) draw an outline red bar.
1728 if (f & (F_ADJ_RIGHT|F_ERROR_RIGHT)) {
1729 if (f & F_ADJ_RIGHT) {
1730 draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COLOUR(RIGHT));
1732 draw_rect_outline(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, COL_ERROR);
1734 } else if (bg >= 0) {
1735 draw_rect(dr, ox+TILE_SIZE+g38, oy, g4, TILE_SIZE, bg);
1737 draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1739 if (f & (F_ADJ_DOWN|F_ERROR_DOWN)) {
1740 if (f & F_ADJ_DOWN) {
1741 draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COLOUR(DOWN));
1743 draw_rect_outline(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, COL_ERROR);
1745 } else if (bg >= 0) {
1746 draw_rect(dr, ox, oy+TILE_SIZE+g38, TILE_SIZE, g4, bg);
1748 draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1751 static void draw_furniture(drawing *dr, game_drawstate *ds,
1752 const game_state *state, const game_ui *ui,
1753 int x, int y, int hflash)
1755 int ox = COORD(x), oy = COORD(y), bg, hon;
1756 unsigned int f = GRID(state, flags, x, y);
1758 bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1760 hon = (ui->hshow && x == ui->hx && y == ui->hy);
1763 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1764 (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1766 /* Draw the highlight (pencil or full), if we're the highlight */
1767 if (hon && ui->hpencil) {
1771 coords[2] = ox + TILE_SIZE/2;
1774 coords[5] = oy + TILE_SIZE/2;
1775 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1778 /* Draw the square outline (which is the cursor, if we're the cursor). */
1779 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, COL_GRID);
1781 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1783 /* Draw the adjacent clue signs. */
1785 draw_adjs(dr, ds, ox, oy, f, COL_BACKGROUND, COL_GRID);
1787 draw_gts(dr, ds, ox, oy, f, COL_BACKGROUND, COL_TEXT);
1790 static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1792 int ox = COORD(x), oy = COORD(y);
1793 unsigned int f = GRID(ds,flags,x,y);
1796 /* (can assume square has just been cleared) */
1798 /* Draw number, choosing appropriate colour */
1799 str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1801 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1802 FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1803 (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1806 static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1808 int ox = COORD(x), oy = COORD(y);
1809 int nhints, i, j, hw, hh, hmax, fontsz;
1812 /* (can assume square has just been cleared) */
1814 /* Draw hints; steal ingenious algorithm (basically)
1815 * from solo.c:draw_number() */
1816 for (i = nhints = 0; i < ds->order; i++) {
1817 if (HINT(ds, x, y, i)) nhints++;
1820 for (hw = 1; hw * hw < nhints; hw++);
1822 hh = (nhints + hw - 1) / hw;
1825 fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
1827 for (i = j = 0; i < ds->order; i++) {
1828 if (HINT(ds,x,y,i)) {
1829 int hx = j % hw, hy = j / hw;
1831 str[0] = n2c(i+1, ds->order);
1834 ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
1835 oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
1836 FONT_VARIABLE, fontsz,
1837 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1843 static void game_redraw(drawing *dr, game_drawstate *ds,
1844 const game_state *oldstate, const game_state *state,
1845 int dir, const game_ui *ui,
1846 float animtime, float flashtime)
1848 int x, y, i, hchanged = 0, stale, hflash = 0;
1850 debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
1852 if (flashtime > 0 &&
1853 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
1857 draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
1858 draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
1860 if (ds->hx != ui->hx || ds->hy != ui->hy ||
1861 ds->hshow != ui->hshow || ds->hpencil != ui->hpencil)
1864 for (x = 0; x < ds->order; x++) {
1865 for (y = 0; y < ds->order; y++) {
1868 else if (hflash != ds->hflash)
1874 if ((x == ui->hx && y == ui->hy) ||
1875 (x == ds->hx && y == ds->hy))
1879 if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
1880 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
1883 if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
1884 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
1887 if (GRID(ds, nums, x, y) == 0) {
1888 /* We're not a number square (therefore we might
1889 * display hints); do we need to update? */
1890 for (i = 0; i < ds->order; i++) {
1891 if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
1892 HINT(ds, x, y, i) = HINT(state, x, y, i);
1898 draw_furniture(dr, ds, state, ui, x, y, hflash);
1899 if (GRID(ds, nums, x, y) > 0)
1900 draw_num(dr, ds, x, y);
1902 draw_hints(dr, ds, x, y);
1906 ds->hx = ui->hx; ds->hy = ui->hy;
1907 ds->hshow = ui->hshow;
1908 ds->hpencil = ui->hpencil;
1911 ds->hflash = hflash;
1914 static float game_anim_length(const game_state *oldstate,
1915 const game_state *newstate, int dir, game_ui *ui)
1920 static float game_flash_length(const game_state *oldstate,
1921 const game_state *newstate, int dir, game_ui *ui)
1923 if (!oldstate->completed && newstate->completed &&
1924 !oldstate->cheated && !newstate->cheated)
1929 static int game_status(const game_state *state)
1931 return state->completed ? +1 : 0;
1934 static int game_timing_state(const game_state *state, game_ui *ui)
1939 static void game_print_size(const game_params *params, float *x, float *y)
1943 /* 10mm squares by default, roughly the same as Grauniad. */
1944 game_compute_size(params, 1000, &pw, &ph);
1949 static void game_print(drawing *dr, const game_state *state, int tilesize)
1951 int ink = print_mono_colour(dr, 0);
1952 int x, y, o = state->order, ox, oy, n;
1955 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1956 game_drawstate ads, *ds = &ads;
1957 game_set_size(dr, ds, NULL, tilesize);
1959 print_line_width(dr, 2 * TILE_SIZE / 40);
1961 /* Squares, numbers, gt signs */
1962 for (y = 0; y < o; y++) {
1963 for (x = 0; x < o; x++) {
1964 ox = COORD(x); oy = COORD(y);
1965 n = GRID(state, nums, x, y);
1967 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1969 str[0] = n ? n2c(n, state->order) : ' ';
1971 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1972 FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1975 if (state->adjacent)
1976 draw_adjs(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1978 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), -1, ink);
1983 /* ----------------------------------------------------------------------
1988 #define thegame unequal
1991 const struct game thegame = {
1992 "Unequal", "games.unequal", "unequal",
1994 game_fetch_preset, NULL,
1999 TRUE, game_configure, custom_params,
2007 TRUE, game_can_format_as_text_now, game_text_format,
2015 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2018 game_free_drawstate,
2023 TRUE, FALSE, game_print_size, game_print,
2024 FALSE, /* wants_statusbar */
2025 FALSE, game_timing_state,
2026 REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */
2029 /* ----------------------------------------------------------------------
2030 * Standalone solver.
2033 #ifdef STANDALONE_SOLVER
2038 const char *quis = NULL;
2040 #if 0 /* currently unused */
2042 static void debug_printf(char *fmt, ...)
2048 vsprintf(buf, fmt, ap);
2053 static void game_printf(game_state *state)
2055 char *dbg = game_text_format(state);
2060 static void game_printf_wide(game_state *state)
2064 for (y = 0; y < state->order; y++) {
2065 for (x = 0; x < state->order; x++) {
2066 n = GRID(state, nums, x, y);
2067 for (i = 0; i < state->order; i++) {
2069 printf("%c", n2c(n, state->order));
2070 else if (HINT(state, x, y, i))
2071 printf("%c", n2c(i+1, state->order));
2084 static void pdiff(int diff)
2086 if (diff == DIFF_IMPOSSIBLE)
2087 printf("Game is impossible.\n");
2088 else if (diff == DIFF_UNFINISHED)
2089 printf("Game has incomplete.\n");
2090 else if (diff == DIFF_AMBIGUOUS)
2091 printf("Game has multiple solutions.\n");
2093 printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
2096 static int solve(game_params *p, char *desc, int debug)
2098 game_state *state = new_game(NULL, p, desc);
2099 struct solver_ctx *ctx = new_ctx(state);
2100 struct latin_solver solver;
2103 solver_show_working = debug;
2106 latin_solver_alloc(&solver, state->nums, state->order);
2108 diff = latin_solver_main(&solver, DIFF_RECURSIVE,
2109 DIFF_LATIN, DIFF_SET, DIFF_EXTREME,
2110 DIFF_EXTREME, DIFF_RECURSIVE,
2111 unequal_solvers, ctx, clone_ctx, free_ctx);
2115 latin_solver_free(&solver);
2117 if (debug) pdiff(diff);
2124 static void check(game_params *p)
2126 const char *msg = validate_params(p, 1);
2128 fprintf(stderr, "%s: %s", quis, msg);
2133 static int gen(game_params *p, random_state *rs, int debug)
2140 solver_show_working = debug;
2141 desc = new_game_desc(p, rs, &aux, 0);
2142 diff = solve(p, desc, debug);
2149 static void soak(game_params *p, random_state *rs)
2151 time_t tt_start, tt_now, tt_last;
2154 int n = 0, neasy = 0, realdiff = p->diff;
2158 solver_show_working = 0;
2161 tt_start = tt_now = time(NULL);
2163 printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2164 p->adjacent ? "adjacent" : "unequal",
2165 p->order, p->order, unequal_diffnames[p->diff]);
2169 desc = new_game_desc(p, rs, &aux, 0);
2170 st = new_game(NULL, p, desc);
2171 solver_state(st, DIFF_RECURSIVE);
2177 if (realdiff != p->diff) neasy++;
2179 tt_last = time(NULL);
2180 if (tt_last > tt_now) {
2182 printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2183 n, (double)n / ((double)tt_now - tt_start),
2184 neasy, (double)neasy*100.0/(double)n,
2185 (double)(n - neasy) / ((double)tt_now - tt_start));
2190 static void usage_exit(const char *msg)
2193 fprintf(stderr, "%s: %s\n", quis, msg);
2194 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
2198 int main(int argc, const char *argv[])
2201 time_t seed = time(NULL);
2202 int do_soak = 0, diff;
2209 while (--argc > 0) {
2210 const char *p = *++argv;
2211 if (!strcmp(p, "--soak"))
2213 else if (!strcmp(p, "--seed")) {
2215 usage_exit("--seed needs an argument");
2216 seed = (time_t)atoi(*++argv);
2218 } else if (*p == '-')
2219 usage_exit("unrecognised option");
2223 rs = random_new((void*)&seed, sizeof(time_t));
2226 if (argc != 1) usage_exit("only one argument for --soak");
2227 p = default_params();
2228 decode_params(p, *argv);
2230 } else if (argc > 0) {
2232 for (i = 0; i < argc; i++) {
2233 const char *id = *argv++;
2234 char *desc = strchr(id, ':');
2236 p = default_params();
2239 decode_params(p, id);
2240 err = validate_desc(p, desc);
2242 fprintf(stderr, "%s: %s\n", quis, err);
2247 decode_params(p, id);
2248 diff = gen(p, rs, 1);
2253 p = default_params();
2254 p->order = random_upto(rs, 7) + 3;
2255 p->diff = random_upto(rs, 4);
2256 diff = gen(p, rs, 0);
2266 /* vim: set shiftwidth=4 tabstop=8: */