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,
62 #define F_IMMUTABLE 1 /* passed in as game description */
69 #define F_ERROR_RIGHT 128
70 #define F_ERROR_DOWN 256
71 #define F_ERROR_LEFT 512
73 #define F_ERROR_MASK (F_ERROR|F_ERROR_UP|F_ERROR_RIGHT|F_ERROR_DOWN|F_ERROR_LEFT)
76 int order, completed, cheated;
77 digit *nums; /* actual numbers (size order^2) */
78 unsigned char *hints; /* remaining possiblities (size order^3) */
79 unsigned int *flags; /* flags (size order^2) */
82 /* ----------------------------------------------------------
83 * Game parameters and presets
86 /* Steal the method from map.c for difficulty levels. */
91 A(EXTREME,Extreme,x) \
92 A(RECURSIVE,Recursive,r)
94 #define ENUM(upper,title,lower) DIFF_ ## upper,
95 #define TITLE(upper,title,lower) #title,
96 #define ENCODE(upper,title,lower) #lower
97 #define CONFIG(upper,title,lower) ":" #title
98 enum { DIFFLIST(ENUM) DIFF_IMPOSSIBLE = diff_impossible, DIFF_AMBIGUOUS = diff_ambiguous, DIFF_UNFINISHED = diff_unfinished };
99 static char const *const unequal_diffnames[] = { DIFFLIST(TITLE) };
100 static char const unequal_diffchars[] = DIFFLIST(ENCODE);
101 #define DIFFCOUNT lenof(unequal_diffchars)
102 #define DIFFCONFIG DIFFLIST(CONFIG)
104 #define DEFAULT_PRESET 0
106 const static struct game_params unequal_presets[] = {
118 static int game_fetch_preset(int i, char **name, game_params **params)
123 if (i < 0 || i >= lenof(unequal_presets))
126 ret = snew(game_params);
127 *ret = unequal_presets[i]; /* structure copy */
129 sprintf(buf, "%dx%d %s", ret->order, ret->order,
130 unequal_diffnames[ret->diff]);
137 static game_params *default_params(void)
142 if (!game_fetch_preset(DEFAULT_PRESET, &name, &ret)) return NULL;
147 static void free_params(game_params *params)
152 static game_params *dup_params(game_params *params)
154 game_params *ret = snew(game_params);
155 *ret = *params; /* structure copy */
159 static void decode_params(game_params *ret, char const *string)
161 char const *p = string;
163 ret->order = atoi(p);
164 while (*p && isdigit((unsigned char)*p)) p++;
169 ret->diff = DIFFCOUNT+1; /* ...which is invalid */
171 for (i = 0; i < DIFFCOUNT; i++) {
172 if (*p == unequal_diffchars[i])
180 static char *encode_params(game_params *params, int full)
184 sprintf(ret, "%d", params->order);
186 sprintf(ret + strlen(ret), "d%c", unequal_diffchars[params->diff]);
191 static config_item *game_configure(game_params *params)
196 ret = snewn(3, config_item);
198 ret[0].name = "Size (s*s)";
199 ret[0].type = C_STRING;
200 sprintf(buf, "%d", params->order);
201 ret[0].sval = dupstr(buf);
204 ret[1].name = "Difficulty";
205 ret[1].type = C_CHOICES;
206 ret[1].sval = DIFFCONFIG;
207 ret[1].ival = params->diff;
217 static game_params *custom_params(config_item *cfg)
219 game_params *ret = snew(game_params);
221 ret->order = atoi(cfg[0].sval);
222 ret->diff = cfg[1].ival;
227 static char *validate_params(game_params *params, int full)
229 if (params->order < 3 || params->order > 32)
230 return "Order must be between 3 and 32";
231 if (params->diff >= DIFFCOUNT)
232 return "Unknown difficulty rating.";
236 /* ----------------------------------------------------------
237 * Various utility functions
240 static const struct { unsigned int f, fo, fe; int dx, dy; char c; } gtthan[] = {
241 { F_GT_UP, F_GT_DOWN, F_ERROR_UP, 0, -1, '^' },
242 { F_GT_RIGHT, F_GT_LEFT, F_ERROR_RIGHT, 1, 0, '>' },
243 { F_GT_DOWN, F_GT_UP, F_ERROR_DOWN, 0, 1, 'v' },
244 { F_GT_LEFT, F_GT_RIGHT, F_ERROR_LEFT, -1, 0, '<' }
247 static game_state *blank_game(int order)
249 game_state *state = snew(game_state);
250 int o2 = order*order, o3 = o2*order;
252 state->order = order;
253 state->completed = state->cheated = 0;
255 state->nums = snewn(o2, digit);
256 state->hints = snewn(o3, unsigned char);
257 state->flags = snewn(o2, unsigned int);
259 memset(state->nums, 0, o2 * sizeof(digit));
260 memset(state->hints, 0, o3);
261 memset(state->flags, 0, o2 * sizeof(unsigned int));
266 static game_state *dup_game(game_state *state)
268 game_state *ret = blank_game(state->order);
269 int o2 = state->order*state->order, o3 = o2*state->order;
271 memcpy(ret->nums, state->nums, o2 * sizeof(digit));
272 memcpy(ret->hints, state->hints, o3);
273 memcpy(ret->flags, state->flags, o2 * sizeof(unsigned int));
278 static void free_game(game_state *state)
286 #define CHECKG(x,y) grid[(y)*o+(x)]
288 /* Returns 0 if it finds an error, 1 otherwise. */
289 static int check_gt(digit *grid, game_state *state,
290 int x, int y, int dx, int dy)
292 int o = state->order;
293 int n = CHECKG(x,y), dn = CHECKG(x+dx, y+dy);
296 if (dn == 0) return 1;
299 debug(("check_gt error (%d,%d) (%d,%d)", x, y, x+dx, y+dy));
305 /* Returns 0 if it finds an error, 1 otherwise. */
306 static int check_num_gt(digit *grid, game_state *state,
307 int x, int y, int me)
309 unsigned int f = GRID(state, flags, x, y);
312 for (i = 0; i < 4; i++) {
313 if ((f & gtthan[i].f) &&
314 !check_gt(grid, state, x, y, gtthan[i].dx, gtthan[i].dy)) {
315 if (me) GRID(state, flags, x, y) |= gtthan[i].fe;
322 /* Returns 0 if it finds an error, 1 otherwise. */
323 static int check_num_error(digit *grid, game_state *state,
324 int x, int y, int mark_errors)
326 int o = state->order;
327 int xx, yy, val = CHECKG(x,y), ret = 1;
331 /* check for dups in same column. */
332 for (yy = 0; yy < state->order; yy++) {
333 if (yy == y) continue;
334 if (CHECKG(x,yy) == val) ret = 0;
337 /* check for dups in same row. */
338 for (xx = 0; xx < state->order; xx++) {
339 if (xx == x) continue;
340 if (CHECKG(xx,y) == val) ret = 0;
344 debug(("check_num_error (%d,%d) duplicate %d", x, y, val));
345 if (mark_errors) GRID(state, flags, x, y) |= F_ERROR;
350 /* Returns: -1 for 'wrong'
352 * 1 for 'complete and correct'
354 static int check_complete(digit *grid, game_state *state, int mark_errors)
356 int x, y, ret = 1, o = state->order;
359 assert(grid == state->nums);
361 for (x = 0; x < state->order; x++) {
362 for (y = 0; y < state->order; y++) {
364 GRID(state, flags, x, y) &= ~F_ERROR_MASK;
365 if (grid[y*o+x] == 0) {
368 if (!check_num_error(grid, state, x, y, mark_errors)) ret = -1;
369 if (!check_num_gt(grid, state, x, y, mark_errors)) ret = -1;
373 if (ret == 1 && latin_check(grid, o))
378 static char n2c(digit n, int order) {
379 if (n == 0) return ' ';
381 if (n < 10) return '0' + n;
383 if (n < 11) return '0' + n-1;
385 if (n <= 26) return 'A' + n;
390 /* should be 'digit', but includes -1 for 'not a digit'.
391 * Includes keypresses (0 especially) for interpret_move. */
392 static int c2n(int c, int order) {
393 if (c < 0 || c > 0xff)
395 if (c == ' ' || c == '\010' || c == '\177')
398 if (c >= '1' && c <= '9')
399 return (int)(c - '0');
401 if (c >= '0' && c <= '9')
402 return (int)(c - '0' + 1);
403 if (c >= 'A' && c <= 'Z')
404 return (int)(c - 'A' + 11);
405 if (c >= 'a' && c <= 'z')
406 return (int)(c - 'a' + 11);
411 static char *game_text_format(game_state *state)
416 len = (state->order*2) * (state->order*2-1) + 1;
417 ret = snewn(len, char);
420 for (y = 0; y < state->order; y++) {
421 for (x = 0; x < state->order; x++) {
422 n = GRID(state, nums, x, y);
423 *p++ = n > 0 ? n2c(n, state->order) : '.';
425 if (x < (state->order-1)) {
426 if (GRID(state, flags, x, y) & F_GT_RIGHT)
428 else if (GRID(state, flags, x+1, y) & F_GT_LEFT)
436 if (y < (state->order-1)) {
437 for (x = 0; x < state->order; x++) {
438 if (GRID(state, flags, x, y) & F_GT_DOWN)
440 else if (GRID(state, flags, x, y+1) & F_GT_UP)
445 if (x < state->order-1)
453 assert(p - ret == len);
457 #ifdef STANDALONE_SOLVER
458 static void game_debug(game_state *state)
460 char *dbg = game_text_format(state);
466 /* ----------------------------------------------------------
471 int len, gx, gy, lx, ly;
474 typedef struct game_solver {
475 struct latin_solver latin; /* keep first in struct! */
480 struct solver_link *links;
484 static void solver_debug(game_solver *solver, int wide)
486 #ifdef STANDALONE_SOLVER
487 if (solver_show_working) {
489 game_debug(solver->state);
491 latin_solver_debug(solver->latin.cube, solver->latin.o);
497 static void solver_add_link(game_solver *solver,
498 int gx, int gy, int lx, int ly, int len)
500 if (solver->alinks < solver->nlinks+1) {
501 solver->alinks = solver->alinks*2 + 1;
502 /*debug(("resizing solver->links, new size %d", solver->alinks));*/
503 solver->links = sresize(solver->links, solver->alinks, struct solver_link);
505 solver->links[solver->nlinks].gx = gx;
506 solver->links[solver->nlinks].gy = gy;
507 solver->links[solver->nlinks].lx = lx;
508 solver->links[solver->nlinks].ly = ly;
509 solver->links[solver->nlinks].len = len;
511 /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d",
512 len, lx, ly, gx, gy, solver->nlinks));*/
515 static game_solver *new_solver(digit *grid, game_state *state)
517 game_solver *solver = snew(game_solver);
518 int o = state->order;
522 latin_solver_alloc(&solver->latin, grid, o);
524 solver->nlinks = solver->alinks = 0;
525 solver->links = NULL;
527 for (x = 0; x < o; x++) {
528 for (y = 0; y < o; y++) {
529 f = GRID(state, flags, x, y);
530 for (i = 0; i < 4; i++) {
532 solver_add_link(solver, x, y, x+gtthan[i].dx, y+gtthan[i].dy, 1);
540 static void free_solver(game_solver *solver)
542 if (solver->links) sfree(solver->links);
543 latin_solver_free(&solver->latin);
547 static void solver_nminmax(game_solver *usolver,
548 int x, int y, int *min_r, int *max_r,
549 unsigned char **ns_r)
551 struct latin_solver *solver = &usolver->latin;
552 int o = usolver->latin.o, min = o, max = 0, n;
555 assert(x >= 0 && y >= 0 && x < o && y < o);
557 ns = solver->cube + cubepos(x,y,1);
560 min = max = grid(x,y)-1;
562 for (n = 0; n < o; n++) {
564 if (n > max) max = n;
565 if (n < min) min = n;
569 if (min_r) *min_r = min;
570 if (max_r) *max_r = max;
571 if (ns_r) *ns_r = ns;
574 static int solver_links(game_solver *usolver)
576 int i, j, lmin, gmax, nchanged = 0;
577 unsigned char *gns, *lns;
578 struct solver_link *link;
579 struct latin_solver *solver = &usolver->latin;
581 for (i = 0; i < usolver->nlinks; i++) {
582 link = &usolver->links[i];
583 solver_nminmax(usolver, link->gx, link->gy, NULL, &gmax, &gns);
584 solver_nminmax(usolver, link->lx, link->ly, &lmin, NULL, &lns);
586 for (j = 0; j < solver->o; j++) {
587 /* For the 'greater' end of the link, discount all numbers
588 * too small to satisfy the inequality. */
590 if (j < (lmin+link->len)) {
591 #ifdef STANDALONE_SOLVER
592 if (solver_show_working) {
593 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
594 solver_recurse_depth*4, "",
595 link->gx, link->gy, link->lx, link->ly);
596 printf("%*s ruling out %d at (%d,%d)\n",
597 solver_recurse_depth*4, "",
598 j+1, link->gx, link->gy);
601 cube(link->gx, link->gy, j+1) = FALSE;
605 /* For the 'lesser' end of the link, discount all numbers
606 * too large to satisfy inequality. */
608 if (j > (gmax-link->len)) {
609 #ifdef STANDALONE_SOLVER
610 if (solver_show_working) {
611 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
612 solver_recurse_depth*4, "",
613 link->gx, link->gy, link->lx, link->ly);
614 printf("%*s ruling out %d at (%d,%d)\n",
615 solver_recurse_depth*4, "",
616 j+1, link->lx, link->ly);
619 cube(link->lx, link->ly, j+1) = FALSE;
628 static int solver_grid(digit *grid, int o, int maxdiff, void *ctx)
630 game_state *state = (game_state *)ctx;
632 struct latin_solver *lsolver;
633 struct latin_solver_scratch *scratch;
634 int ret, diff = DIFF_LATIN;
636 assert(maxdiff <= DIFF_RECURSIVE);
638 assert(state->order == o);
639 solver = new_solver(grid, state);
641 lsolver = &solver->latin;
642 scratch = latin_solver_new_scratch(lsolver);
646 ret = latin_solver_diff_simple(lsolver);
648 diff = DIFF_IMPOSSIBLE;
650 } else if (ret > 0) {
651 diff = max(diff, DIFF_LATIN);
655 if (maxdiff <= DIFF_LATIN)
658 /* This bit is unequal-specific */
659 ret = solver_links(solver);
661 diff = DIFF_IMPOSSIBLE;
663 } else if (ret > 0) {
664 diff = max(diff, DIFF_EASY);
668 if (maxdiff <= DIFF_EASY)
671 /* Row- and column-wise set elimination */
672 ret = latin_solver_diff_set(lsolver, scratch, 0);
674 diff = DIFF_IMPOSSIBLE;
676 } else if (ret > 0) {
677 diff = max(diff, DIFF_SET);
681 if (maxdiff <= DIFF_SET)
684 ret = latin_solver_diff_set(lsolver, scratch, 1);
686 diff = DIFF_IMPOSSIBLE;
688 } else if (ret > 0) {
689 diff = max(diff, DIFF_EXTREME);
696 if (latin_solver_forcing(lsolver, scratch)) {
697 diff = max(diff, DIFF_EXTREME);
702 * If we reach here, we have made no deductions in this
703 * iteration, so the algorithm terminates.
708 * Last chance: if we haven't fully solved the puzzle yet, try
709 * recursing based on guesses for a particular square. We pick
710 * one of the most constrained empty squares we can find, which
711 * has the effect of pruning the search tree as much as
714 if (maxdiff == DIFF_RECURSIVE) {
715 int nsol = latin_solver_recurse(lsolver, DIFF_RECURSIVE, solver_grid, ctx);
716 if (nsol < 0) diff = DIFF_IMPOSSIBLE;
717 else if (nsol == 1) diff = DIFF_RECURSIVE;
718 else if (nsol > 1) diff = DIFF_AMBIGUOUS;
719 /* if nsol == 0 then we were complete anyway
720 * (and thus don't need to change diff) */
722 int cc = check_complete(grid, state, 0);
723 if (cc == -1) diff = DIFF_IMPOSSIBLE;
724 if (cc == 0) diff = DIFF_UNFINISHED;
729 #ifdef STANDALONE_SOLVER
730 if (solver_show_working)
731 printf("%*s%s found\n",
732 solver_recurse_depth*4, "",
733 diff == DIFF_IMPOSSIBLE ? "no solution (impossible)" :
734 diff == DIFF_UNFINISHED ? "no solution (unfinished)" :
735 diff == DIFF_AMBIGUOUS ? "multiple solutions" :
739 latin_solver_free_scratch(scratch);
740 memcpy(state->hints, solver->latin.cube, o*o*o);
746 static int solver_state(game_state *state, int maxdiff)
748 int diff = solver_grid(state->nums, state->order, maxdiff, (void*)state);
750 if (diff == DIFF_IMPOSSIBLE)
752 if (diff == DIFF_UNFINISHED)
754 if (diff == DIFF_AMBIGUOUS)
759 static game_state *solver_hint(game_state *state, int *diff_r, int mindiff, int maxdiff)
761 game_state *ret = dup_game(state);
764 for (diff = mindiff; diff <= maxdiff; diff++) {
765 r = solver_state(ret, diff);
766 debug(("solver_state after %s %d", unequal_diffnames[diff], r));
767 if (r != 0) goto done;
771 if (diff_r) *diff_r = (r > 0) ? diff : -1;
775 /* ----------------------------------------------------------
779 static char *latin_desc(digit *sq, size_t order)
781 int o2 = order*order, i;
782 char *soln = snewn(o2+2, char);
785 for (i = 0; i < o2; i++)
786 soln[i+1] = n2c(sq[i], order);
792 /* returns non-zero if it placed (or could have placed) clue. */
793 static int gg_place_clue(game_state *state, int ccode, digit *latin, int checkonly)
795 int loc = ccode / 5, which = ccode % 5;
796 int x = loc % state->order, y = loc / state->order;
798 assert(loc < state->order*state->order);
800 if (which == 4) { /* add number */
801 if (state->nums[loc] != 0) {
802 #ifdef STANDALONE_SOLVER
803 if (state->nums[loc] != latin[loc]) {
804 printf("inconsistency for (%d,%d): state %d latin %d\n",
805 x, y, state->nums[loc], latin[loc]);
808 assert(state->nums[loc] == latin[loc]);
812 state->nums[loc] = latin[loc];
814 } else { /* add flag */
817 if (state->flags[loc] & gtthan[which].f)
818 return 0; /* already has flag. */
820 lx = x + gtthan[which].dx;
821 ly = y + gtthan[which].dy;
822 if (lx < 0 || ly < 0 || lx >= state->order || ly >= state->order)
823 return 0; /* flag compares to off grid */
825 lloc = loc + gtthan[which].dx + gtthan[which].dy*state->order;
826 if (latin[loc] <= latin[lloc])
827 return 0; /* flag would be incorrect */
830 state->flags[loc] |= gtthan[which].f;
836 /* returns non-zero if it removed (or could have removed) the clue. */
837 static int gg_remove_clue(game_state *state, int ccode, int checkonly)
839 int loc = ccode / 5, which = ccode % 5;
840 #ifdef STANDALONE_SOLVER
841 int x = loc % state->order, y = loc / state->order;
844 assert(loc < state->order*state->order);
846 if (which == 4) { /* remove number. */
847 if (state->nums[loc] == 0) return 0;
849 #ifdef STANDALONE_SOLVER
850 if (solver_show_working)
851 printf("gg_remove_clue: removing %d at (%d,%d)",
852 state->nums[loc], x, y);
854 state->nums[loc] = 0;
856 } else { /* remove flag */
857 if (!(state->flags[loc] & gtthan[which].f)) return 0;
859 #ifdef STANDALONE_SOLVER
860 if (solver_show_working)
861 printf("gg_remove_clue: removing %c at (%d,%d)",
862 gtthan[which].c, x, y);
864 state->flags[loc] &= ~gtthan[which].f;
870 static int gg_best_clue(game_state *state, int *scratch, digit *latin)
872 int ls = state->order * state->order * 5;
873 int maxposs = 0, minclues = 5, best = -1, i, j;
874 int nposs, nclues, loc, x, y;
876 #ifdef STANDALONE_SOLVER
877 if (solver_show_working) {
879 latin_solver_debug(state->hints, state->order);
883 for (i = ls; i-- > 0 ;) {
884 if (!gg_place_clue(state, scratch[i], latin, 1)) continue;
886 loc = scratch[i] / 5;
887 x = loc % state->order; y = loc / state->order;
888 for (j = nposs = 0; j < state->order; j++) {
889 if (state->hints[loc*state->order + j]) nposs++;
891 for (j = nclues = 0; j < 4; j++) {
892 if (state->flags[loc] & gtthan[j].f) nclues++;
894 if ((nposs > maxposs) ||
895 (nposs == maxposs && nclues < minclues)) {
896 best = i; maxposs = nposs; minclues = nclues;
897 #ifdef STANDALONE_SOLVER
898 if (solver_show_working)
899 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
900 best, x, y, nposs, nclues);
904 /* if we didn't solve, we must have 1 clue to place! */
909 #ifdef STANDALONE_SOLVER
911 #define MAXTRIES maxtries
917 static int game_assemble(game_state *new, int *scratch, digit *latin,
920 game_state *copy = dup_game(new);
923 if (difficulty >= DIFF_RECURSIVE) {
924 /* We mustn't use any solver that might guess answers;
925 * if it guesses wrongly but solves, gg_place_clue will
926 * get mighty confused. We will always trim clues down
927 * (making it more difficult) in game_strip, which doesn't
928 * have this problem. */
929 difficulty = DIFF_RECURSIVE-1;
932 #ifdef STANDALONE_SOLVER
933 if (solver_show_working) {
935 latin_solver_debug(new->hints, new->order);
941 if (solver_state(copy, difficulty) == 1) break;
943 best = gg_best_clue(copy, scratch, latin);
944 gg_place_clue(new, scratch[best], latin, 0);
945 gg_place_clue(copy, scratch[best], latin, 0);
948 #ifdef STANDALONE_SOLVER
949 if (solver_show_working) {
950 char *dbg = game_text_format(new);
951 printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved, dbg);
958 static void game_strip(game_state *new, int *scratch, digit *latin,
961 int o = new->order, o2 = o*o, lscratch = o2*5, i;
962 game_state *copy = blank_game(new->order);
964 /* For each symbol (if it exists in new), try and remove it and
965 * solve again; if we couldn't solve without it put it back. */
966 for (i = 0; i < lscratch; i++) {
967 if (!gg_remove_clue(new, scratch[i], 0)) continue;
969 memcpy(copy->nums, new->nums, o2 * sizeof(digit));
970 memcpy(copy->flags, new->flags, o2 * sizeof(unsigned int));
972 if (solver_state(copy, difficulty) != 1) {
973 /* put clue back, we can't solve without it. */
974 int ret = gg_place_clue(new, scratch[i], latin, 0);
977 #ifdef STANDALONE_SOLVER
978 if (solver_show_working)
979 printf("game_strip: clue was redundant.");
984 #ifdef STANDALONE_SOLVER
985 if (solver_show_working) {
986 char *dbg = game_text_format(new);
987 debug(("game_strip: done, %d solver iterations.", gg_solved));
994 static char *new_game_desc(game_params *params, random_state *rs,
995 char **aux, int interactive)
998 int i, x, y, retlen, k, nsol;
999 int o2 = params->order * params->order, ntries = 1;
1000 int *scratch, lscratch = o2*5;
1002 game_state *state = blank_game(params->order);
1004 /* Generate a list of 'things to strip' (randomised later) */
1005 scratch = snewn(lscratch, int);
1006 /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1007 for (i = 0; i < lscratch; i++) scratch[i] = (i%o2)*5 + 4 - (i/o2);
1010 #ifdef STANDALONE_SOLVER
1011 if (solver_show_working)
1012 printf("new_game_desc: generating %s puzzle, ntries so far %d",
1013 unequal_diffnames[params->diff], ntries);
1016 sq = latin_generate(params->order, rs);
1017 latin_debug(sq, params->order);
1018 /* Separately shuffle the numeric and inequality clues */
1019 shuffle(scratch, lscratch/5, sizeof(int), rs);
1020 shuffle(scratch+lscratch/5, 4*lscratch/5, sizeof(int), rs);
1022 memset(state->nums, 0, o2 * sizeof(digit));
1023 memset(state->flags, 0, o2 * sizeof(unsigned int));
1026 if (game_assemble(state, scratch, sq, params->diff) < 0)
1028 game_strip(state, scratch, sq, params->diff);
1030 if (params->diff > 0) {
1031 game_state *copy = dup_game(state);
1032 nsol = solver_state(copy, params->diff-1);
1035 #ifdef STANDALONE_SOLVER
1036 if (solver_show_working)
1037 printf("game_assemble: puzzle as generated is too easy.\n");
1039 if (ntries < MAXTRIES) {
1043 #ifdef STANDALONE_SOLVER
1044 if (solver_show_working)
1045 printf("Unable to generate %s %dx%d after %d attempts.\n",
1046 unequal_diffnames[params->diff],
1047 params->order, params->order, MAXTRIES);
1052 #ifdef STANDALONE_SOLVER
1053 if (solver_show_working)
1054 printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1055 unequal_diffnames[params->diff], ntries, gg_solved);
1058 ret = NULL; retlen = 0;
1059 for (y = 0; y < params->order; y++) {
1060 for (x = 0; x < params->order; x++) {
1061 unsigned int f = GRID(state, flags, x, y);
1062 k = sprintf(buf, "%d%s%s%s%s,",
1063 GRID(state, nums, x, y),
1064 (f & F_GT_UP) ? "U" : "",
1065 (f & F_GT_RIGHT) ? "R" : "",
1066 (f & F_GT_DOWN) ? "D" : "",
1067 (f & F_GT_LEFT) ? "L" : "");
1069 ret = sresize(ret, retlen + k + 1, char);
1070 strcpy(ret + retlen, buf);
1074 *aux = latin_desc(sq, params->order);
1083 static game_state *load_game(game_params *params, char *desc,
1086 game_state *state = blank_game(params->order);
1088 int i = 0, n, o = params->order, x, y;
1092 while (*p >= 'a' && *p <= 'z') {
1097 why = "Too much data to fill grid"; goto fail;
1100 if (*p < '0' && *p > '9') {
1101 why = "Expecting number in game description"; goto fail;
1104 if (n < 0 || n > o) {
1105 why = "Out-of-range number in game description"; goto fail;
1107 state->nums[i] = (digit)n;
1108 while (*p >= '0' && *p <= '9') p++; /* skip number */
1110 if (state->nums[i] != 0)
1111 state->flags[i] |= F_IMMUTABLE; /* === number set by game description */
1113 while (*p == 'U' || *p == 'R' || *p == 'D' || *p == 'L') {
1115 case 'U': state->flags[i] |= F_GT_UP; break;
1116 case 'R': state->flags[i] |= F_GT_RIGHT; break;
1117 case 'D': state->flags[i] |= F_GT_DOWN; break;
1118 case 'L': state->flags[i] |= F_GT_LEFT; break;
1119 default: why = "Expecting flag URDL in game description"; goto fail;
1124 if (i < o*o && *p != ',') {
1125 why = "Missing separator"; goto fail;
1130 why = "Not enough data to fill grid"; goto fail;
1133 for (y = 0; y < o; y++) {
1134 for (x = 0; x < o; x++) {
1135 for (n = 0; n < 4; n++) {
1136 if (GRID(state, flags, x, y) & gtthan[n].f) {
1137 int nx = x + gtthan[n].dx;
1138 int ny = y + gtthan[n].dy;
1139 /* a flag must not point us off the grid. */
1140 if (nx < 0 || ny < 0 || nx >= o || ny >= o) {
1141 why = "Flags go off grid"; goto fail;
1143 /* if one cell is GT another, the other must not also
1144 * be GT the first. */
1145 if (GRID(state, flags, nx, ny) & gtthan[n].fo) {
1146 why = "Flags contradicting each other"; goto fail;
1157 if (why_r) *why_r = why;
1161 static game_state *new_game(midend *me, game_params *params, char *desc)
1163 game_state *state = load_game(params, desc, NULL);
1165 assert("Unable to load ?validated game.");
1171 static char *validate_desc(game_params *params, char *desc)
1174 game_state *dummy = load_game(params, desc, &why);
1183 static char *solve_game(game_state *state, game_state *currstate,
1184 char *aux, char **error)
1190 if (aux) return dupstr(aux);
1192 solved = dup_game(state);
1193 for (r = 0; r < state->order*state->order; r++) {
1194 if (!(solved->flags[r] & F_IMMUTABLE))
1195 solved->nums[r] = 0;
1197 r = solver_state(solved, DIFFCOUNT);
1198 if (r > 0) ret = latin_desc(solved->nums, solved->order);
1203 /* ----------------------------------------------------------
1204 * Game UI input processing.
1208 int hx, hy, hpencil; /* as for solo.c, highlight pos and type */
1209 int cx, cy; /* cursor position (-1,-1 for none) */
1212 static game_ui *new_ui(game_state *state)
1214 game_ui *ui = snew(game_ui);
1216 ui->hx = ui->hy = -1;
1219 ui->cx = ui->cy = -1;
1224 static void free_ui(game_ui *ui)
1229 static char *encode_ui(game_ui *ui)
1234 static void decode_ui(game_ui *ui, char *encoding)
1238 static void game_changed_state(game_ui *ui, game_state *oldstate,
1239 game_state *newstate)
1241 /* See solo.c; if we were pencil-mode highlighting and
1242 * somehow a square has just been properly filled, cancel
1244 if (ui->hx >= 0 && ui->hy >= 0 && ui->hpencil &&
1245 GRID(newstate, nums, ui->hx, ui->hy) != 0) {
1246 ui->hx = ui->hy = -1;
1250 struct game_drawstate {
1251 int tilesize, order, started;
1252 digit *nums; /* copy of nums, o^2 */
1253 unsigned char *hints; /* copy of hints, o^3 */
1254 unsigned int *flags; /* o^2 */
1256 int hx, hy, hpencil;
1261 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1262 int ox, int oy, int button)
1264 int x = FROMCOORD(ox), y = FROMCOORD(oy), n;
1267 button &= ~MOD_MASK;
1269 if (x >= 0 && x < ds->order && ((ox - COORD(x)) <= TILE_SIZE) &&
1270 y >= 0 && y < ds->order && ((oy - COORD(y)) <= TILE_SIZE)) {
1271 if (button == LEFT_BUTTON) {
1272 /* normal highlighting for non-immutable squares */
1273 if (GRID(state, flags, x, y) & F_IMMUTABLE)
1274 ui->hx = ui->hy = -1;
1275 else if (x == ui->hx && y == ui->hy && ui->hpencil == 0)
1276 ui->hx = ui->hy = -1;
1278 ui->hx = x; ui->hy = y; ui->hpencil = 0;
1282 if (button == RIGHT_BUTTON) {
1283 /* pencil highlighting for non-filled squares */
1284 if (GRID(state, nums, x, y) != 0)
1285 ui->hx = ui->hy = -1;
1286 else if (x == ui->hx && y == ui->hy && ui->hpencil)
1287 ui->hx = ui->hy = -1;
1289 ui->hx = x; ui->hy = y; ui->hpencil = 1;
1294 if (button == 'H' || button == 'h')
1297 if (ui->hx != -1 && ui->hy != -1) {
1298 debug(("button %d, cbutton %d", button, (int)((char)button)));
1299 n = c2n(button, state->order);
1301 debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1302 n, ui->hx, ui->hy, ui->hpencil,
1303 GRID(state, flags, ui->hx, ui->hy),
1304 GRID(state, nums, ui->hx, ui->hy)));
1306 if (n < 0 || n > ds->order)
1307 return NULL; /* out of range */
1308 if (GRID(state, flags, ui->hx, ui->hy) & F_IMMUTABLE)
1309 return NULL; /* can't edit immutable square (!) */
1310 if (ui->hpencil && GRID(state, nums, ui->hx, ui->hy) > 0)
1311 return NULL; /* can't change hints on filled square (!) */
1314 sprintf(buf, "%c%d,%d,%d",
1315 (char)(ui->hpencil && n > 0 ? 'P' : 'R'), ui->hx, ui->hy, n);
1317 ui->hx = ui->hy = -1;
1324 static game_state *execute_move(game_state *state, char *move)
1326 game_state *ret = NULL;
1329 debug(("execute_move: %s", move));
1331 if ((move[0] == 'P' || move[0] == 'R') &&
1332 sscanf(move+1, "%d,%d,%d", &x, &y, &n) == 3 &&
1333 x >= 0 && x < state->order && y >= 0 && y < state->order &&
1334 n >= 0 && n <= state->order) {
1335 ret = dup_game(state);
1336 if (move[0] == 'P' && n > 0)
1337 HINT(ret, x, y, n-1) = !HINT(ret, x, y, n-1);
1339 GRID(ret, nums, x, y) = n;
1340 for (i = 0; i < state->order; i++)
1341 HINT(ret, x, y, i) = 0;
1343 /* real change to grid; check for completion */
1344 if (!ret->completed && check_complete(ret->nums, ret, 1) > 0)
1345 ret->completed = TRUE;
1348 } else if (move[0] == 'S') {
1351 ret = dup_game(state);
1352 ret->completed = ret->cheated = TRUE;
1355 for (i = 0; i < state->order*state->order; i++) {
1356 n = c2n((int)*p, state->order);
1357 if (!*p || n <= 0 || n > state->order)
1362 if (*p) goto badmove;
1363 rc = check_complete(ret->nums, ret, 1);
1366 } else if (move[0] == 'H') {
1367 return solver_hint(state, NULL, DIFF_EASY, DIFF_EASY);
1371 if (ret) free_game(ret);
1375 /* ----------------------------------------------------------------------
1376 * Drawing/printing routines.
1379 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1381 static void game_compute_size(game_params *params, int tilesize,
1384 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1385 struct { int tilesize, order; } ads, *ds = &ads;
1386 ads.tilesize = tilesize;
1387 ads.order = params->order;
1389 *x = *y = DRAW_SIZE;
1392 static void game_set_size(drawing *dr, game_drawstate *ds,
1393 game_params *params, int tilesize)
1395 ds->tilesize = tilesize;
1398 static float *game_colours(frontend *fe, int *ncolours)
1400 float *ret = snewn(3 * NCOLOURS, float);
1403 game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT);
1405 for (i = 0; i < 3; i++) {
1406 ret[COL_TEXT * 3 + i] = 0.0F;
1407 ret[COL_GRID * 3 + i] = 0.5F;
1410 /* Lots of these were taken from solo.c. */
1411 ret[COL_GUESS * 3 + 0] = 0.0F;
1412 ret[COL_GUESS * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1413 ret[COL_GUESS * 3 + 2] = 0.0F;
1415 ret[COL_ERROR * 3 + 0] = 1.0F;
1416 ret[COL_ERROR * 3 + 1] = 0.0F;
1417 ret[COL_ERROR * 3 + 2] = 0.0F;
1419 ret[COL_PENCIL * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1420 ret[COL_PENCIL * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1421 ret[COL_PENCIL * 3 + 2] = ret[COL_BACKGROUND * 3 + 2];
1423 *ncolours = NCOLOURS;
1427 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1429 struct game_drawstate *ds = snew(struct game_drawstate);
1430 int o2 = state->order*state->order, o3 = o2*state->order;
1433 ds->order = state->order;
1435 ds->nums = snewn(o2, digit);
1436 ds->hints = snewn(o3, unsigned char);
1437 ds->flags = snewn(o2, unsigned int);
1438 memset(ds->nums, 0, o2*sizeof(digit));
1439 memset(ds->hints, 0, o3);
1440 memset(ds->flags, 0, o2*sizeof(unsigned int));
1442 ds->hx = ds->hy = ds->cx = ds->cy = -1;
1443 ds->started = ds->hpencil = ds->hflash = 0;
1448 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1456 static void draw_gt(drawing *dr, int ox, int oy,
1457 int dx1, int dy1, int dx2, int dy2, int col)
1459 draw_line(dr, ox, oy, ox+dx1, oy+dy1, col);
1460 draw_line(dr, ox+dx1, oy+dy1, ox+dx1+dx2, oy+dy1+dy2, col);
1463 static void draw_gts(drawing *dr, game_drawstate *ds, int ox, int oy,
1464 unsigned int f, int col, int needsupdate)
1466 int g = GAP_SIZE, g2 = (g+1)/2, g4 = (g+1)/4;
1469 draw_gt(dr, ox+g2, oy-g4, g2, -g2, g2, g2,
1470 (f & F_ERROR_UP) ? COL_ERROR : col);
1471 if (needsupdate) draw_update(dr, ox, oy-g, TILE_SIZE, g);
1473 if (f & F_GT_RIGHT) {
1474 draw_gt(dr, ox+TILE_SIZE+g4, oy+g2, g2, g2, -g2, g2,
1475 (f & F_ERROR_RIGHT) ? COL_ERROR : col);
1476 if (needsupdate) draw_update(dr, ox+TILE_SIZE, oy, g, TILE_SIZE);
1478 if (f & F_GT_DOWN) {
1479 draw_gt(dr, ox+g2, oy+TILE_SIZE+g4, g2, g2, g2, -g2,
1480 (f & F_ERROR_DOWN) ? COL_ERROR : col);
1481 if (needsupdate) draw_update(dr, ox, oy+TILE_SIZE, TILE_SIZE, g);
1483 if (f & F_GT_LEFT) {
1484 draw_gt(dr, ox-g4, oy+g2, -g2, g2, g2, g2,
1485 (f & F_ERROR_LEFT) ? COL_ERROR : col);
1486 if (needsupdate) draw_update(dr, ox-g, oy, g, TILE_SIZE);
1490 static void draw_furniture(drawing *dr, game_drawstate *ds, game_state *state,
1491 game_ui *ui, int x, int y, int hflash)
1493 int ox = COORD(x), oy = COORD(y), bg, hon, con;
1494 unsigned int f = GRID(state, flags, x, y);
1496 bg = hflash ? COL_HIGHLIGHT : COL_BACKGROUND;
1498 hon = (x == ui->hx && y == ui->hy);
1499 con = (x == ui->cx && y == ui->cy);
1502 draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1503 (hon && !ui->hpencil) ? COL_HIGHLIGHT : bg);
1505 /* Draw the highlight (pencil or full), if we're the highlight */
1506 if (hon && ui->hpencil) {
1510 coords[2] = ox + TILE_SIZE/2;
1513 coords[5] = oy + TILE_SIZE/2;
1514 draw_polygon(dr, coords, 3, COL_HIGHLIGHT, COL_HIGHLIGHT);
1517 /* Draw the square outline (which is the cursor, if we're the cursor). */
1518 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE,
1519 con ? COL_GUESS : COL_GRID);
1521 draw_update(dr, ox, oy, TILE_SIZE, TILE_SIZE);
1523 /* Draw the GT signs. */
1524 draw_gts(dr, ds, ox, oy, f, COL_TEXT, 1);
1527 static void draw_num(drawing *dr, game_drawstate *ds, int x, int y)
1529 int ox = COORD(x), oy = COORD(y);
1530 unsigned int f = GRID(ds,flags,x,y);
1533 /* (can assume square has just been cleared) */
1535 /* Draw number, choosing appropriate colour */
1536 str[0] = n2c(GRID(ds, nums, x, y), ds->order);
1538 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1539 FONT_VARIABLE, 3*TILE_SIZE/4, ALIGN_VCENTRE | ALIGN_HCENTRE,
1540 (f & F_IMMUTABLE) ? COL_TEXT : (f & F_ERROR) ? COL_ERROR : COL_GUESS, str);
1543 static void draw_hints(drawing *dr, game_drawstate *ds, int x, int y)
1545 int ox = COORD(x), oy = COORD(y);
1546 int nhints, i, j, hw, hh, hmax, fontsz;
1549 /* (can assume square has just been cleared) */
1551 /* Draw hints; steal ingenious algorithm (basically)
1552 * from solo.c:draw_number() */
1553 for (i = nhints = 0; i < ds->order; i++) {
1554 if (HINT(ds, x, y, i)) nhints++;
1557 for (hw = 1; hw * hw < nhints; hw++);
1559 hh = (nhints + hw - 1) / hw;
1562 fontsz = TILE_SIZE/(hmax*(11-hmax)/8);
1564 for (i = j = 0; i < ds->order; i++) {
1565 if (HINT(ds,x,y,i)) {
1566 int hx = j % hw, hy = j / hw;
1568 str[0] = n2c(i+1, ds->order);
1571 ox + (4*hx+3) * TILE_SIZE / (4*hw+2),
1572 oy + (4*hy+3) * TILE_SIZE / (4*hh+2),
1573 FONT_VARIABLE, fontsz,
1574 ALIGN_VCENTRE | ALIGN_HCENTRE, COL_PENCIL, str);
1580 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1581 game_state *state, int dir, game_ui *ui,
1582 float animtime, float flashtime)
1584 int x, y, i, hchanged = 0, cchanged = 0, stale, hflash = 0;
1586 debug(("highlight old (%d,%d), new (%d,%d)", ds->hx, ds->hy, ui->hx, ui->hy));
1588 if (flashtime > 0 &&
1589 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3))
1593 draw_rect(dr, 0, 0, DRAW_SIZE, DRAW_SIZE, COL_BACKGROUND);
1594 draw_update(dr, 0, 0, DRAW_SIZE, DRAW_SIZE);
1596 if (ds->hx != ui->hx || ds->hy != ui->hy || ds->hpencil != ui->hpencil)
1598 if (ds->cx != ui->cx || ds->cy != ui->cy)
1601 for (x = 0; x < ds->order; x++) {
1602 for (y = 0; y < ds->order; y++) {
1605 else if (hflash != ds->hflash)
1611 if ((x == ui->hx && y == ui->hy) ||
1612 (x == ds->hx && y == ds->hy))
1616 if ((x == ui->cx && y == ui->cy) ||
1617 (x == ds->cx && y == ds->cy))
1621 if (GRID(state, nums, x, y) != GRID(ds, nums, x, y)) {
1622 GRID(ds, nums, x, y) = GRID(state, nums, x, y);
1625 if (GRID(state, flags, x, y) != GRID(ds, flags, x, y)) {
1626 GRID(ds, flags, x, y) = GRID(state, flags, x, y);
1629 if (GRID(ds, nums, x, y) == 0) {
1630 /* We're not a number square (therefore we might
1631 * display hints); do we need to update? */
1632 for (i = 0; i < ds->order; i++) {
1633 if (HINT(state, x, y, i) != HINT(ds, x, y, i)) {
1634 HINT(ds, x, y, i) = HINT(state, x, y, i);
1640 draw_furniture(dr, ds, state, ui, x, y, hflash);
1641 if (GRID(ds, nums, x, y) > 0)
1642 draw_num(dr, ds, x, y);
1644 draw_hints(dr, ds, x, y);
1648 ds->hx = ui->hx; ds->hy = ui->hy; ds->hpencil = ui->hpencil;
1649 ds->cx = ui->cx; ds->cy = ui->cy;
1651 ds->hflash = hflash;
1654 static float game_anim_length(game_state *oldstate, game_state *newstate,
1655 int dir, game_ui *ui)
1660 static float game_flash_length(game_state *oldstate, game_state *newstate,
1661 int dir, game_ui *ui)
1663 if (!oldstate->completed && newstate->completed &&
1664 !oldstate->cheated && !newstate->cheated)
1669 static int game_timing_state(game_state *state, game_ui *ui)
1674 static void game_print_size(game_params *params, float *x, float *y)
1678 /* 10mm squares by default, roughly the same as Grauniad. */
1679 game_compute_size(params, 1000, &pw, &ph);
1684 static void game_print(drawing *dr, game_state *state, int tilesize)
1686 int ink = print_mono_colour(dr, 0);
1687 int x, y, o = state->order, ox, oy, n;
1690 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1691 game_drawstate ads, *ds = &ads;
1692 game_set_size(dr, ds, NULL, tilesize);
1694 print_line_width(dr, 2 * TILE_SIZE / 40);
1696 /* Squares, numbers, gt signs */
1697 for (y = 0; y < o; y++) {
1698 for (x = 0; x < o; x++) {
1699 ox = COORD(x); oy = COORD(y);
1700 n = GRID(state, nums, x, y);
1702 draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink);
1704 str[0] = n ? n2c(n, state->order) : ' ';
1706 draw_text(dr, ox + TILE_SIZE/2, oy + TILE_SIZE/2,
1707 FONT_VARIABLE, TILE_SIZE/2, ALIGN_VCENTRE | ALIGN_HCENTRE,
1710 draw_gts(dr, ds, ox, oy, GRID(state, flags, x, y), ink, 1);
1715 /* ----------------------------------------------------------------------
1720 #define thegame unequal
1723 const struct game thegame = {
1724 "Unequal", "games.unequal", "unequal",
1731 TRUE, game_configure, custom_params,
1739 TRUE, game_text_format,
1747 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1750 game_free_drawstate,
1754 TRUE, FALSE, game_print_size, game_print,
1755 FALSE, /* wants_statusbar */
1756 FALSE, game_timing_state,
1757 REQUIRE_RBUTTON | REQUIRE_NUMPAD, /* flags */
1760 /* ----------------------------------------------------------------------
1761 * Standalone solver.
1764 #ifdef STANDALONE_SOLVER
1769 const char *quis = NULL;
1771 #if 0 /* currently unused */
1773 static void debug_printf(char *fmt, ...)
1779 vsprintf(buf, fmt, ap);
1784 static void game_printf(game_state *state)
1786 char *dbg = game_text_format(state);
1791 static void game_printf_wide(game_state *state)
1795 for (y = 0; y < state->order; y++) {
1796 for (x = 0; x < state->order; x++) {
1797 n = GRID(state, nums, x, y);
1798 for (i = 0; i < state->order; i++) {
1800 printf("%c", n2c(n, state->order));
1801 else if (HINT(state, x, y, i))
1802 printf("%c", n2c(i+1, state->order));
1815 static void pdiff(int diff)
1817 if (diff == DIFF_IMPOSSIBLE)
1818 printf("Game is impossible.\n");
1819 else if (diff == DIFF_UNFINISHED)
1820 printf("Game has incomplete.\n");
1821 else if (diff == DIFF_AMBIGUOUS)
1822 printf("Game has multiple solutions.\n");
1824 printf("Game has difficulty %s.\n", unequal_diffnames[diff]);
1827 static int solve(game_params *p, char *desc, int debug)
1829 game_state *st = new_game(NULL, p, desc);
1832 solver_show_working = debug;
1835 diff = solver_grid(st->nums, st->order, DIFF_RECURSIVE, (void*)st);
1836 if (debug) pdiff(diff);
1843 static void check(game_params *p)
1845 char *msg = validate_params(p, 1);
1847 fprintf(stderr, "%s: %s", quis, msg);
1852 static int gen(game_params *p, random_state *rs, int debug)
1859 solver_show_working = debug;
1860 desc = new_game_desc(p, rs, &aux, 0);
1861 diff = solve(p, desc, debug);
1868 static void soak(game_params *p, random_state *rs)
1870 time_t tt_start, tt_now, tt_last;
1873 int n = 0, neasy = 0, realdiff = p->diff;
1877 solver_show_working = 0;
1880 tt_start = tt_now = time(NULL);
1882 printf("Soak-generating a %dx%d grid, difficulty %s.\n",
1883 p->order, p->order, unequal_diffnames[p->diff]);
1887 desc = new_game_desc(p, rs, &aux, 0);
1888 st = new_game(NULL, p, desc);
1889 solver_state(st, DIFF_RECURSIVE);
1895 if (realdiff != p->diff) neasy++;
1897 tt_last = time(NULL);
1898 if (tt_last > tt_now) {
1900 printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
1901 n, (double)n / ((double)tt_now - tt_start),
1902 neasy, (double)neasy*100.0/(double)n,
1903 (double)(n - neasy) / ((double)tt_now - tt_start));
1908 static void usage_exit(const char *msg)
1911 fprintf(stderr, "%s: %s\n", quis, msg);
1912 fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
1916 int main(int argc, const char *argv[])
1919 time_t seed = time(NULL);
1920 int do_soak = 0, diff;
1927 while (--argc > 0) {
1928 const char *p = *++argv;
1929 if (!strcmp(p, "--soak"))
1931 else if (!strcmp(p, "--seed")) {
1933 usage_exit("--seed needs an argument");
1934 seed = (time_t)atoi(*++argv);
1936 } else if (*p == '-')
1937 usage_exit("unrecognised option");
1941 rs = random_new((void*)&seed, sizeof(time_t));
1944 if (argc != 1) usage_exit("only one argument for --soak");
1945 p = default_params();
1946 decode_params(p, *argv);
1948 } else if (argc > 0) {
1950 for (i = 0; i < argc; i++) {
1951 const char *id = *argv++;
1952 char *desc = strchr(id, ':'), *err;
1953 p = default_params();
1956 decode_params(p, id);
1957 err = validate_desc(p, desc);
1959 fprintf(stderr, "%s: %s\n", quis, err);
1964 decode_params(p, id);
1965 diff = gen(p, rs, 1);
1970 p = default_params();
1971 p->order = random_upto(rs, 7) + 3;
1972 p->diff = random_upto(rs, 4);
1973 diff = gen(p, rs, 0);
1983 /* vim: set shiftwidth=4 tabstop=8: */