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