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: */