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
= 0; i
< ls
; i
++) {
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].",
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 assert(gg_place_clue(new, scratch
[i
], latin
, 0) == 1);
976 #ifdef STANDALONE_SOLVER
977 if (solver_show_working
)
978 printf("game_strip: clue was redundant.");
983 #ifdef STANDALONE_SOLVER
984 if (solver_show_working
) {
985 char *dbg
= game_text_format(new);
986 debug(("game_strip: done, %d solver iterations.", gg_solved
));
993 static char *new_game_desc(game_params
*params
, random_state
*rs
,
994 char **aux
, int interactive
)
997 int i
, x
, y
, retlen
, k
, nsol
;
998 int o2
= params
->order
* params
->order
, ntries
= 0;
999 int *scratch
, lscratch
= o2
*5;
1001 game_state
*state
= blank_game(params
->order
);
1003 /* Generate a list of 'things to strip' (randomised later) */
1004 scratch
= snewn(lscratch
, int);
1005 for (i
= 0; i
< lscratch
; i
++) scratch
[i
] = i
;
1008 #ifdef STANDALONE_SOLVER
1009 if (solver_show_working
)
1010 printf("new_game_desc: generating %s puzzle, ntries so far %d",
1011 unequal_diffnames
[params
->diff
], ntries
);
1014 sq
= latin_generate(params
->order
, rs
);
1015 latin_debug(sq
, params
->order
);
1016 shuffle(scratch
, lscratch
, sizeof(int), rs
);
1018 memset(state
->nums
, 0, o2
* sizeof(digit
));
1019 memset(state
->flags
, 0, o2
* sizeof(unsigned int));
1022 if (game_assemble(state
, scratch
, sq
, params
->diff
) < 0)
1024 game_strip(state
, scratch
, sq
, params
->diff
);
1026 if (params
->diff
> 0) {
1027 game_state
*copy
= dup_game(state
);
1028 nsol
= solver_state(copy
, params
->diff
-1);
1031 #ifdef STANDALONE_SOLVER
1032 if (solver_show_working
)
1033 printf("game_assemble: puzzle as generated is too easy.");
1035 if (ntries
< MAXTRIES
) {
1039 #ifdef STANDALONE_SOLVER
1040 if (solver_show_working
)
1041 printf("Unable to generate %s %dx%d after %d attempts.",
1042 unequal_diffnames
[params
->diff
],
1043 params
->order
, params
->order
, MAXTRIES
);
1048 #ifdef STANDALONE_SOLVER
1049 if (solver_show_working
)
1050 printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).",
1051 unequal_diffnames
[params
->diff
], ntries
, gg_solved
);
1054 ret
= NULL
; retlen
= 0;
1055 for (y
= 0; y
< params
->order
; y
++) {
1056 for (x
= 0; x
< params
->order
; x
++) {
1057 unsigned int f
= GRID(state
, flags
, x
, y
);
1058 k
= sprintf(buf
, "%d%s%s%s%s,",
1059 GRID(state
, nums
, x
, y
),
1060 (f
& F_GT_UP
) ?
"U" : "",
1061 (f
& F_GT_RIGHT
) ?
"R" : "",
1062 (f
& F_GT_DOWN
) ?
"D" : "",
1063 (f
& F_GT_LEFT
) ?
"L" : "");
1065 ret
= sresize(ret
, retlen
+ k
+ 1, char);
1066 strcpy(ret
+ retlen
, buf
);
1070 *aux
= latin_desc(sq
, params
->order
);
1079 static game_state
*load_game(game_params
*params
, char *desc
,
1082 game_state
*state
= blank_game(params
->order
);
1084 int i
= 0, n
, o
= params
->order
, x
, y
;
1088 while (*p
>= 'a' && *p
<= 'z') {
1093 why
= "Too much data to fill grid"; goto fail
;
1096 if (*p
< '0' && *p
> '9') {
1097 why
= "Expecting number in game description"; goto fail
;
1100 if (n
< 0 || n
> o
) {
1101 why
= "Out-of-range number in game description"; goto fail
;
1103 state
->nums
[i
] = (digit
)n
;
1104 while (*p
>= '0' && *p
<= '9') p
++; /* skip number */
1106 if (state
->nums
[i
] != 0)
1107 state
->flags
[i
] |= F_IMMUTABLE
; /* === number set by game description */
1109 while (*p
== 'U' || *p
== 'R' || *p
== 'D' || *p
== 'L') {
1111 case 'U': state
->flags
[i
] |= F_GT_UP
; break;
1112 case 'R': state
->flags
[i
] |= F_GT_RIGHT
; break;
1113 case 'D': state
->flags
[i
] |= F_GT_DOWN
; break;
1114 case 'L': state
->flags
[i
] |= F_GT_LEFT
; break;
1115 default: why
= "Expecting flag URDL in game description"; goto fail
;
1120 if (i
< o
*o
&& *p
!= ',') {
1121 why
= "Missing separator"; goto fail
;
1126 why
= "Not enough data to fill grid"; goto fail
;
1129 for (y
= 0; y
< o
; y
++) {
1130 for (x
= 0; x
< o
; x
++) {
1131 for (n
= 0; n
< 4; n
++) {
1132 if (GRID(state
, flags
, x
, y
) & gtthan
[n
].f
) {
1133 int nx
= x
+ gtthan
[n
].dx
;
1134 int ny
= y
+ gtthan
[n
].dy
;
1135 /* a flag must not point us off the grid. */
1136 if (nx
< 0 || ny
< 0 || nx
>= o
|| ny
>= o
) {
1137 why
= "Flags go off grid"; goto fail
;
1139 /* if one cell is GT another, the other must not also
1140 * be GT the first. */
1141 if (GRID(state
, flags
, nx
, ny
) & gtthan
[n
].fo
) {
1142 why
= "Flags contradicting each other"; goto fail
;
1153 if (why_r
) *why_r
= why
;
1157 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1159 game_state
*state
= load_game(params
, desc
, NULL
);
1161 assert("Unable to load ?validated game.");
1167 static char *validate_desc(game_params
*params
, char *desc
)
1170 game_state
*dummy
= load_game(params
, desc
, &why
);
1179 static char *solve_game(game_state
*state
, game_state
*currstate
,
1180 char *aux
, char **error
)
1186 if (aux
) return dupstr(aux
);
1188 solved
= dup_game(state
);
1189 for (r
= 0; r
< state
->order
*state
->order
; r
++) {
1190 if (!(solved
->flags
[r
] & F_IMMUTABLE
))
1191 solved
->nums
[r
] = 0;
1193 r
= solver_state(solved
, DIFFCOUNT
);
1194 if (r
> 0) ret
= latin_desc(solved
->nums
, solved
->order
);
1199 /* ----------------------------------------------------------
1200 * Game UI input processing.
1204 int hx
, hy
, hpencil
; /* as for solo.c, highlight pos and type */
1205 int cx
, cy
; /* cursor position (-1,-1 for none) */
1208 static game_ui
*new_ui(game_state
*state
)
1210 game_ui
*ui
= snew(game_ui
);
1212 ui
->hx
= ui
->hy
= -1;
1215 ui
->cx
= ui
->cy
= -1;
1220 static void free_ui(game_ui
*ui
)
1225 static char *encode_ui(game_ui
*ui
)
1230 static void decode_ui(game_ui
*ui
, char *encoding
)
1234 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1235 game_state
*newstate
)
1237 /* See solo.c; if we were pencil-mode highlighting and
1238 * somehow a square has just been properly filled, cancel
1240 if (ui
->hx
>= 0 && ui
->hy
>= 0 && ui
->hpencil
&&
1241 GRID(newstate
, nums
, ui
->hx
, ui
->hy
) != 0) {
1242 ui
->hx
= ui
->hy
= -1;
1246 struct game_drawstate
{
1247 int tilesize
, order
, started
;
1248 digit
*nums
; /* copy of nums, o^2 */
1249 unsigned char *hints
; /* copy of hints, o^3 */
1250 unsigned int *flags
; /* o^2 */
1252 int hx
, hy
, hpencil
;
1257 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1258 int ox
, int oy
, int button
)
1260 int x
= FROMCOORD(ox
), y
= FROMCOORD(oy
), n
;
1263 button
&= ~MOD_MASK
;
1265 if (x
>= 0 && x
< ds
->order
&& y
>= 0 && y
< ds
->order
) {
1266 if (button
== LEFT_BUTTON
) {
1267 /* normal highlighting for non-immutable squares */
1268 if (GRID(state
, flags
, x
, y
) & F_IMMUTABLE
)
1269 ui
->hx
= ui
->hy
= -1;
1270 else if (x
== ui
->hx
&& y
== ui
->hy
&& ui
->hpencil
== 0)
1271 ui
->hx
= ui
->hy
= -1;
1273 ui
->hx
= x
; ui
->hy
= y
; ui
->hpencil
= 0;
1277 if (button
== RIGHT_BUTTON
) {
1278 /* pencil highlighting for non-filled squares */
1279 if (GRID(state
, nums
, x
, y
) != 0)
1280 ui
->hx
= ui
->hy
= -1;
1281 else if (x
== ui
->hx
&& y
== ui
->hy
&& ui
->hpencil
)
1282 ui
->hx
= ui
->hy
= -1;
1284 ui
->hx
= x
; ui
->hy
= y
; ui
->hpencil
= 1;
1289 if (button
== 'H' || button
== 'h')
1292 if (ui
->hx
!= -1 && ui
->hy
!= -1) {
1293 debug(("button %d, cbutton %d", button
, (int)((char)button
)));
1294 n
= c2n(button
, state
->order
);
1296 debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1297 n
, ui
->hx
, ui
->hy
, ui
->hpencil
,
1298 GRID(state
, flags
, ui
->hx
, ui
->hy
),
1299 GRID(state
, nums
, ui
->hx
, ui
->hy
)));
1301 if (n
< 0 || n
> ds
->order
)
1302 return NULL
; /* out of range */
1303 if (GRID(state
, flags
, ui
->hx
, ui
->hy
) & F_IMMUTABLE
)
1304 return NULL
; /* can't edit immutable square (!) */
1305 if (ui
->hpencil
&& GRID(state
, nums
, ui
->hx
, ui
->hy
) > 0)
1306 return NULL
; /* can't change hints on filled square (!) */
1309 sprintf(buf
, "%c%d,%d,%d",
1310 (char)(ui
->hpencil
&& n
> 0 ?
'P' : 'R'), ui
->hx
, ui
->hy
, n
);
1312 ui
->hx
= ui
->hy
= -1;
1319 static game_state
*execute_move(game_state
*state
, char *move
)
1321 game_state
*ret
= NULL
;
1324 debug(("execute_move: %s", move
));
1326 if ((move
[0] == 'P' || move
[0] == 'R') &&
1327 sscanf(move
+1, "%d,%d,%d", &x
, &y
, &n
) == 3 &&
1328 x
>= 0 && x
< state
->order
&& y
>= 0 && y
< state
->order
&&
1329 n
>= 0 && n
<= state
->order
) {
1330 ret
= dup_game(state
);
1331 if (move
[0] == 'P' && n
> 0)
1332 HINT(ret
, x
, y
, n
-1) = !HINT(ret
, x
, y
, n
-1);
1334 GRID(ret
, nums
, x
, y
) = n
;
1335 for (i
= 0; i
< state
->order
; i
++)
1336 HINT(ret
, x
, y
, i
) = 0;
1338 /* real change to grid; check for completion */
1339 if (!ret
->completed
&& check_complete(ret
->nums
, ret
, 1) > 0)
1340 ret
->completed
= TRUE
;
1343 } else if (move
[0] == 'S') {
1346 ret
= dup_game(state
);
1347 ret
->completed
= ret
->cheated
= TRUE
;
1350 for (i
= 0; i
< state
->order
*state
->order
; i
++) {
1351 n
= c2n((int)*p
, state
->order
);
1352 if (!*p
|| n
<= 0 || n
> state
->order
)
1357 if (*p
) goto badmove
;
1358 assert(check_complete(ret
->nums
, ret
, 1) > 0);
1360 } else if (move
[0] == 'H') {
1361 return solver_hint(state
, NULL
, DIFF_EASY
, DIFF_EASY
);
1365 if (ret
) free_game(ret
);
1369 /* ----------------------------------------------------------------------
1370 * Drawing/printing routines.
1373 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1375 static void game_compute_size(game_params
*params
, int tilesize
,
1378 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1379 struct { int tilesize
, order
; } ads
, *ds
= &ads
;
1380 ads
.tilesize
= tilesize
;
1381 ads
.order
= params
->order
;
1383 *x
= *y
= DRAW_SIZE
;
1386 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1387 game_params
*params
, int tilesize
)
1389 ds
->tilesize
= tilesize
;
1392 static float *game_colours(frontend
*fe
, int *ncolours
)
1394 float *ret
= snewn(3 * NCOLOURS
, float);
1397 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1399 for (i
= 0; i
< 3; i
++) {
1400 ret
[COL_TEXT
* 3 + i
] = 0.0F
;
1401 ret
[COL_GRID
* 3 + i
] = 0.5F
;
1404 /* Lots of these were taken from solo.c. */
1405 ret
[COL_GUESS
* 3 + 0] = 0.0F
;
1406 ret
[COL_GUESS
* 3 + 1] = 0.6F
* ret
[COL_BACKGROUND
* 3 + 1];
1407 ret
[COL_GUESS
* 3 + 2] = 0.0F
;
1409 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1410 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1411 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1413 ret
[COL_PENCIL
* 3 + 0] = 0.5F
* ret
[COL_BACKGROUND
* 3 + 0];
1414 ret
[COL_PENCIL
* 3 + 1] = 0.5F
* ret
[COL_BACKGROUND
* 3 + 1];
1415 ret
[COL_PENCIL
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2];
1417 *ncolours
= NCOLOURS
;
1421 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1423 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1424 int o2
= state
->order
*state
->order
, o3
= o2
*state
->order
;
1427 ds
->order
= state
->order
;
1429 ds
->nums
= snewn(o2
, digit
);
1430 ds
->hints
= snewn(o3
, unsigned char);
1431 ds
->flags
= snewn(o2
, unsigned int);
1432 memset(ds
->nums
, 0, o2
*sizeof(digit
));
1433 memset(ds
->hints
, 0, o3
);
1434 memset(ds
->flags
, 0, o2
*sizeof(unsigned int));
1436 ds
->hx
= ds
->hy
= ds
->cx
= ds
->cy
= -1;
1437 ds
->started
= ds
->hpencil
= ds
->hflash
= 0;
1442 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1450 static void draw_gt(drawing
*dr
, int ox
, int oy
,
1451 int dx1
, int dy1
, int dx2
, int dy2
, int col
)
1453 draw_line(dr
, ox
, oy
, ox
+dx1
, oy
+dy1
, col
);
1454 draw_line(dr
, ox
+dx1
, oy
+dy1
, ox
+dx1
+dx2
, oy
+dy1
+dy2
, col
);
1457 static void draw_gts(drawing
*dr
, game_drawstate
*ds
, int ox
, int oy
,
1458 unsigned int f
, int col
, int needsupdate
)
1460 int g
= GAP_SIZE
, g2
= (g
+1)/2, g4
= (g
+1)/4;
1463 draw_gt(dr
, ox
+g2
, oy
-g4
, g2
, -g2
, g2
, g2
,
1464 (f
& F_ERROR_UP
) ? COL_ERROR
: col
);
1465 if (needsupdate
) draw_update(dr
, ox
, oy
-g
, TILE_SIZE
, g
);
1467 if (f
& F_GT_RIGHT
) {
1468 draw_gt(dr
, ox
+TILE_SIZE
+g4
, oy
+g2
, g2
, g2
, -g2
, g2
,
1469 (f
& F_ERROR_RIGHT
) ? COL_ERROR
: col
);
1470 if (needsupdate
) draw_update(dr
, ox
+TILE_SIZE
, oy
, g
, TILE_SIZE
);
1472 if (f
& F_GT_DOWN
) {
1473 draw_gt(dr
, ox
+g2
, oy
+TILE_SIZE
+g4
, g2
, g2
, g2
, -g2
,
1474 (f
& F_ERROR_DOWN
) ? COL_ERROR
: col
);
1475 if (needsupdate
) draw_update(dr
, ox
, oy
+TILE_SIZE
, TILE_SIZE
, g
);
1477 if (f
& F_GT_LEFT
) {
1478 draw_gt(dr
, ox
-g4
, oy
+g2
, -g2
, g2
, g2
, g2
,
1479 (f
& F_ERROR_LEFT
) ? COL_ERROR
: col
);
1480 if (needsupdate
) draw_update(dr
, ox
-g
, oy
, g
, TILE_SIZE
);
1484 static void draw_furniture(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
1485 game_ui
*ui
, int x
, int y
, int hflash
)
1487 int ox
= COORD(x
), oy
= COORD(y
), bg
, hon
, con
;
1488 unsigned int f
= GRID(state
, flags
, x
, y
);
1490 bg
= hflash ? COL_HIGHLIGHT
: COL_BACKGROUND
;
1492 hon
= (x
== ui
->hx
&& y
== ui
->hy
);
1493 con
= (x
== ui
->cx
&& y
== ui
->cy
);
1496 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
,
1497 (hon
&& !ui
->hpencil
) ? COL_HIGHLIGHT
: bg
);
1499 /* Draw the highlight (pencil or full), if we're the highlight */
1500 if (hon
&& ui
->hpencil
) {
1504 coords
[2] = ox
+ TILE_SIZE
/2;
1507 coords
[5] = oy
+ TILE_SIZE
/2;
1508 draw_polygon(dr
, coords
, 3, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
1511 /* Draw the square outline (which is the cursor, if we're the cursor). */
1512 draw_rect_outline(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
,
1513 con ? COL_GUESS
: COL_GRID
);
1515 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
1517 /* Draw the GT signs. */
1518 draw_gts(dr
, ds
, ox
, oy
, f
, COL_TEXT
, 1);
1521 static void draw_num(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
1523 int ox
= COORD(x
), oy
= COORD(y
);
1524 unsigned int f
= GRID(ds
,flags
,x
,y
);
1527 /* (can assume square has just been cleared) */
1529 /* Draw number, choosing appropriate colour */
1530 str
[0] = n2c(GRID(ds
, nums
, x
, y
), ds
->order
);
1532 draw_text(dr
, ox
+ TILE_SIZE
/2, oy
+ TILE_SIZE
/2,
1533 FONT_VARIABLE
, 3*TILE_SIZE
/4, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1534 (f
& F_IMMUTABLE
) ? COL_TEXT
: (f
& F_ERROR
) ? COL_ERROR
: COL_GUESS
, str
);
1537 static void draw_hints(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
1539 int ox
= COORD(x
), oy
= COORD(y
);
1540 int nhints
, i
, j
, hw
, hh
, hmax
, fontsz
;
1543 /* (can assume square has just been cleared) */
1545 /* Draw hints; steal ingenious algorithm (basically)
1546 * from solo.c:draw_number() */
1547 for (i
= nhints
= 0; i
< ds
->order
; i
++) {
1548 if (HINT(ds
, x
, y
, i
)) nhints
++;
1551 for (hw
= 1; hw
* hw
< nhints
; hw
++);
1553 hh
= (nhints
+ hw
- 1) / hw
;
1556 fontsz
= TILE_SIZE
/(hmax
*(11-hmax
)/8);
1558 for (i
= j
= 0; i
< ds
->order
; i
++) {
1559 if (HINT(ds
,x
,y
,i
)) {
1560 int hx
= j
% hw
, hy
= j
/ hw
;
1562 str
[0] = n2c(i
+1, ds
->order
);
1565 ox
+ (4*hx
+3) * TILE_SIZE
/ (4*hw
+2),
1566 oy
+ (4*hy
+3) * TILE_SIZE
/ (4*hh
+2),
1567 FONT_VARIABLE
, fontsz
,
1568 ALIGN_VCENTRE
| ALIGN_HCENTRE
, COL_PENCIL
, str
);
1574 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1575 game_state
*state
, int dir
, game_ui
*ui
,
1576 float animtime
, float flashtime
)
1578 int x
, y
, i
, hchanged
= 0, cchanged
= 0, stale
, hflash
= 0;
1580 debug(("highlight old (%d,%d), new (%d,%d)", ds
->hx
, ds
->hy
, ui
->hx
, ui
->hy
));
1582 if (flashtime
> 0 &&
1583 (flashtime
<= FLASH_TIME
/3 || flashtime
>= FLASH_TIME
*2/3))
1587 draw_rect(dr
, 0, 0, DRAW_SIZE
, DRAW_SIZE
, COL_BACKGROUND
);
1588 draw_update(dr
, 0, 0, DRAW_SIZE
, DRAW_SIZE
);
1590 if (ds
->hx
!= ui
->hx
|| ds
->hy
!= ui
->hy
|| ds
->hpencil
!= ui
->hpencil
)
1592 if (ds
->cx
!= ui
->cx
|| ds
->cy
!= ui
->cy
)
1595 for (x
= 0; x
< ds
->order
; x
++) {
1596 for (y
= 0; y
< ds
->order
; y
++) {
1599 else if (hflash
!= ds
->hflash
)
1605 if ((x
== ui
->hx
&& y
== ui
->hy
) ||
1606 (x
== ds
->hx
&& y
== ds
->hy
))
1610 if ((x
== ui
->cx
&& y
== ui
->cy
) ||
1611 (x
== ds
->cx
&& y
== ds
->cy
))
1615 if (GRID(state
, nums
, x
, y
) != GRID(ds
, nums
, x
, y
)) {
1616 GRID(ds
, nums
, x
, y
) = GRID(state
, nums
, x
, y
);
1619 if (GRID(state
, flags
, x
, y
) != GRID(ds
, flags
, x
, y
)) {
1620 GRID(ds
, flags
, x
, y
) = GRID(state
, flags
, x
, y
);
1623 if (GRID(ds
, nums
, x
, y
) == 0) {
1624 /* We're not a number square (therefore we might
1625 * display hints); do we need to update? */
1626 for (i
= 0; i
< ds
->order
; i
++) {
1627 if (HINT(state
, x
, y
, i
) != HINT(ds
, x
, y
, i
)) {
1628 HINT(ds
, x
, y
, i
) = HINT(state
, x
, y
, i
);
1634 draw_furniture(dr
, ds
, state
, ui
, x
, y
, hflash
);
1635 if (GRID(ds
, nums
, x
, y
) > 0)
1636 draw_num(dr
, ds
, x
, y
);
1638 draw_hints(dr
, ds
, x
, y
);
1642 ds
->hx
= ui
->hx
; ds
->hy
= ui
->hy
; ds
->hpencil
= ui
->hpencil
;
1643 ds
->cx
= ui
->cx
; ds
->cy
= ui
->cy
;
1645 ds
->hflash
= hflash
;
1648 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1649 int dir
, game_ui
*ui
)
1654 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1655 int dir
, game_ui
*ui
)
1657 if (!oldstate
->completed
&& newstate
->completed
&&
1658 !oldstate
->cheated
&& !newstate
->cheated
)
1663 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1668 static void game_print_size(game_params
*params
, float *x
, float *y
)
1672 /* 10mm squares by default, roughly the same as Grauniad. */
1673 game_compute_size(params
, 1000, &pw
, &ph
);
1678 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1680 int ink
= print_mono_colour(dr
, 0);
1681 int x
, y
, o
= state
->order
, ox
, oy
, n
;
1684 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1685 game_drawstate ads
, *ds
= &ads
;
1686 game_set_size(dr
, ds
, NULL
, tilesize
);
1688 print_line_width(dr
, 2 * TILE_SIZE
/ 40);
1690 /* Squares, numbers, gt signs */
1691 for (y
= 0; y
< o
; y
++) {
1692 for (x
= 0; x
< o
; x
++) {
1693 ox
= COORD(x
); oy
= COORD(y
);
1694 n
= GRID(state
, nums
, x
, y
);
1696 draw_rect_outline(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, ink
);
1698 str
[0] = n ?
n2c(n
, state
->order
) : ' ';
1700 draw_text(dr
, ox
+ TILE_SIZE
/2, oy
+ TILE_SIZE
/2,
1701 FONT_VARIABLE
, TILE_SIZE
/2, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1704 draw_gts(dr
, ds
, ox
, oy
, GRID(state
, flags
, x
, y
), ink
, 1);
1709 /* ----------------------------------------------------------------------
1714 #define thegame unequal
1717 const struct game thegame
= {
1718 "Unequal", "games.unequal", "unequal",
1725 TRUE
, game_configure
, custom_params
,
1733 TRUE
, game_text_format
,
1741 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1744 game_free_drawstate
,
1748 TRUE
, FALSE
, game_print_size
, game_print
,
1749 FALSE
, /* wants_statusbar */
1750 FALSE
, game_timing_state
,
1754 /* ----------------------------------------------------------------------
1755 * Standalone solver.
1758 #ifdef STANDALONE_SOLVER
1763 const char *quis
= NULL
;
1765 #if 0 /* currently unused */
1767 static void debug_printf(char *fmt
, ...)
1773 vsprintf(buf
, fmt
, ap
);
1778 static void game_printf(game_state
*state
)
1780 char *dbg
= game_text_format(state
);
1785 static void game_printf_wide(game_state
*state
)
1789 for (y
= 0; y
< state
->order
; y
++) {
1790 for (x
= 0; x
< state
->order
; x
++) {
1791 n
= GRID(state
, nums
, x
, y
);
1792 for (i
= 0; i
< state
->order
; i
++) {
1794 printf("%c", n2c(n
, state
->order
));
1795 else if (HINT(state
, x
, y
, i
))
1796 printf("%c", n2c(i
+1, state
->order
));
1809 static void pdiff(int diff
)
1811 if (diff
== DIFF_IMPOSSIBLE
)
1812 printf("Game is impossible.\n");
1813 else if (diff
== DIFF_UNFINISHED
)
1814 printf("Game has incomplete.\n");
1815 else if (diff
== DIFF_AMBIGUOUS
)
1816 printf("Game has multiple solutions.\n");
1818 printf("Game has difficulty %s.\n", unequal_diffnames
[diff
]);
1821 static int solve(game_params
*p
, char *desc
, int debug
)
1823 game_state
*st
= new_game(NULL
, p
, desc
);
1826 solver_show_working
= debug
;
1829 diff
= solver_grid(st
->nums
, st
->order
, DIFF_RECURSIVE
, (void*)st
);
1830 if (debug
) pdiff(diff
);
1837 static void check(game_params
*p
)
1839 char *msg
= validate_params(p
, 1);
1841 fprintf(stderr
, "%s: %s", quis
, msg
);
1846 static int gen(game_params
*p
, random_state
*rs
, int debug
)
1853 solver_show_working
= debug
;
1854 desc
= new_game_desc(p
, rs
, &aux
, 0);
1855 diff
= solve(p
, desc
, debug
);
1862 static void soak(game_params
*p
, random_state
*rs
)
1864 time_t tt_start
, tt_now
, tt_last
;
1867 int n
= 0, neasy
= 0, realdiff
= p
->diff
;
1871 solver_show_working
= 0;
1874 tt_start
= tt_now
= time(NULL
);
1876 printf("Soak-generating a %dx%d grid, difficulty %s.\n",
1877 p
->order
, p
->order
, unequal_diffnames
[p
->diff
]);
1881 desc
= new_game_desc(p
, rs
, &aux
, 0);
1882 st
= new_game(NULL
, p
, desc
);
1883 solver_state(st
, DIFF_RECURSIVE
);
1889 if (realdiff
!= p
->diff
) neasy
++;
1891 tt_last
= time(NULL
);
1892 if (tt_last
> tt_now
) {
1894 printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
1895 n
, (double)n
/ ((double)tt_now
- tt_start
),
1896 neasy
, (double)neasy
*100.0/(double)n
,
1897 (double)(n
- neasy
) / ((double)tt_now
- tt_start
));
1902 static void usage_exit(const char *msg
)
1905 fprintf(stderr
, "%s: %s\n", quis
, msg
);
1906 fprintf(stderr
, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis
);
1910 int main(int argc
, const char *argv
[])
1913 time_t seed
= time(NULL
);
1914 int do_soak
= 0, diff
;
1921 while (--argc
> 0) {
1922 const char *p
= *++argv
;
1923 if (!strcmp(p
, "--soak"))
1925 else if (!strcmp(p
, "--seed")) {
1927 usage_exit("--seed needs an argument");
1928 seed
= (time_t)atoi(*++argv
);
1930 } else if (*p
== '-')
1931 usage_exit("unrecognised option");
1935 rs
= random_new((void*)&seed
, sizeof(time_t));
1938 if (argc
!= 1) usage_exit("only one argument for --soak");
1939 p
= default_params();
1940 decode_params(p
, *argv
);
1942 } else if (argc
> 0) {
1944 for (i
= 0; i
< argc
; i
++) {
1945 const char *id
= *argv
++;
1946 char *desc
= strchr(id
, ':'), *err
;
1947 p
= default_params();
1950 decode_params(p
, id
);
1951 err
= validate_desc(p
, desc
);
1953 fprintf(stderr
, "%s: %s\n", quis
, err
);
1958 decode_params(p
, id
);
1959 diff
= gen(p
, rs
, 1);
1964 p
= default_params();
1965 p
->order
= random_upto(rs
, 7) + 3;
1966 p
->diff
= random_upto(rs
, 4);
1967 diff
= gen(p
, rs
, 0);
1977 /* vim: set shiftwidth=4 tabstop=8: */