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. */
91 A(LATIN,Trivial,NULL,t) \
92 A(EASY,Easy,solver_easy, e) \
93 A(SET,Tricky,solver_set, k) \
94 A(EXTREME,Extreme,NULL,x) \
95 A(RECURSIVE,Recursive,NULL,r)
97 #define ENUM(upper,title,func,lower) DIFF_ ## upper,
98 #define TITLE(upper,title,func,lower) #title,
99 #define ENCODE(upper,title,func,lower) #lower
100 #define CONFIG(upper,title,func,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
;
530 struct solver_link
*links
;
533 static void solver_add_link(struct solver_ctx
*ctx
,
534 int gx
, int gy
, int lx
, int ly
, int len
)
536 if (ctx
->alinks
< ctx
->nlinks
+1) {
537 ctx
->alinks
= ctx
->alinks
*2 + 1;
538 /*debug(("resizing ctx->links, new size %d", ctx->alinks));*/
539 ctx
->links
= sresize(ctx
->links
, ctx
->alinks
, struct solver_link
);
541 ctx
->links
[ctx
->nlinks
].gx
= gx
;
542 ctx
->links
[ctx
->nlinks
].gy
= gy
;
543 ctx
->links
[ctx
->nlinks
].lx
= lx
;
544 ctx
->links
[ctx
->nlinks
].ly
= ly
;
545 ctx
->links
[ctx
->nlinks
].len
= len
;
547 /*debug(("Adding new link: len %d (%d,%d) < (%d,%d), nlinks now %d",
548 len, lx, ly, gx, gy, ctx->nlinks));*/
551 static struct solver_ctx
*new_ctx(game_state
*state
)
553 struct solver_ctx
*ctx
= snew(struct solver_ctx
);
554 int o
= state
->order
;
558 ctx
->nlinks
= ctx
->alinks
= 0;
562 if (state
->adjacent
) return ctx
; /* adjacent mode doesn't use links. */
564 for (x
= 0; x
< o
; x
++) {
565 for (y
= 0; y
< o
; y
++) {
566 f
= GRID(state
, flags
, x
, y
);
567 for (i
= 0; i
< 4; i
++) {
568 if (f
& adjthan
[i
].f
)
569 solver_add_link(ctx
, x
, y
, x
+adjthan
[i
].dx
, y
+adjthan
[i
].dy
, 1);
577 static void *clone_ctx(void *vctx
)
579 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
580 return new_ctx(ctx
->state
);
583 static void free_ctx(void *vctx
)
585 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
586 if (ctx
->links
) sfree(ctx
->links
);
590 static void solver_nminmax(struct latin_solver
*solver
,
591 int x
, int y
, int *min_r
, int *max_r
,
592 unsigned char **ns_r
)
594 int o
= solver
->o
, min
= o
, max
= 0, n
;
597 assert(x
>= 0 && y
>= 0 && x
< o
&& y
< o
);
599 ns
= solver
->cube
+ cubepos(x
,y
,1);
602 min
= max
= grid(x
,y
)-1;
604 for (n
= 0; n
< o
; n
++) {
606 if (n
> max
) max
= n
;
607 if (n
< min
) min
= n
;
611 if (min_r
) *min_r
= min
;
612 if (max_r
) *max_r
= max
;
613 if (ns_r
) *ns_r
= ns
;
616 static int solver_links(struct latin_solver
*solver
, void *vctx
)
618 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
619 int i
, j
, lmin
, gmax
, nchanged
= 0;
620 unsigned char *gns
, *lns
;
621 struct solver_link
*link
;
623 for (i
= 0; i
< ctx
->nlinks
; i
++) {
624 link
= &ctx
->links
[i
];
625 solver_nminmax(solver
, link
->gx
, link
->gy
, NULL
, &gmax
, &gns
);
626 solver_nminmax(solver
, link
->lx
, link
->ly
, &lmin
, NULL
, &lns
);
628 for (j
= 0; j
< solver
->o
; j
++) {
629 /* For the 'greater' end of the link, discount all numbers
630 * too small to satisfy the inequality. */
632 if (j
< (lmin
+link
->len
)) {
633 #ifdef STANDALONE_SOLVER
634 if (solver_show_working
) {
635 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
636 solver_recurse_depth
*4, "",
637 link
->gx
+1, link
->gy
+1, link
->lx
+1, link
->ly
+1);
638 printf("%*s ruling out %d at (%d,%d)\n",
639 solver_recurse_depth
*4, "",
640 j
+1, link
->gx
+1, link
->gy
+1);
643 cube(link
->gx
, link
->gy
, j
+1) = FALSE
;
647 /* For the 'lesser' end of the link, discount all numbers
648 * too large to satisfy inequality. */
650 if (j
> (gmax
-link
->len
)) {
651 #ifdef STANDALONE_SOLVER
652 if (solver_show_working
) {
653 printf("%*slink elimination, (%d,%d) > (%d,%d):\n",
654 solver_recurse_depth
*4, "",
655 link
->gx
+1, link
->gy
+1, link
->lx
+1, link
->ly
+1);
656 printf("%*s ruling out %d at (%d,%d)\n",
657 solver_recurse_depth
*4, "",
658 j
+1, link
->lx
+1, link
->ly
+1);
661 cube(link
->lx
, link
->ly
, j
+1) = FALSE
;
670 static int solver_adjacent(struct latin_solver
*solver
, void *vctx
)
672 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
673 int nchanged
= 0, x
, y
, i
, n
, o
= solver
->o
, nx
, ny
, gd
;
675 /* Update possible values based on known values and adjacency clues. */
677 for (x
= 0; x
< o
; x
++) {
678 for (y
= 0; y
< o
; y
++) {
679 if (grid(x
, y
) == 0) continue;
681 /* We have a definite number here. Make sure that any
682 * adjacent possibles reflect the adjacent/non-adjacent clue. */
684 for (i
= 0; i
< 4; i
++) {
685 int isadjacent
= (GRID(ctx
->state
, flags
, x
, y
) & adjthan
[i
].f
);
687 nx
= x
+ adjthan
[i
].dx
, ny
= y
+ adjthan
[i
].dy
;
688 if (nx
< 0 || ny
< 0 || nx
>= o
|| ny
>= o
)
691 for (n
= 0; n
< o
; n
++) {
692 /* Continue past numbers the adjacent square _could_ be,
693 * given the clue we have. */
694 gd
= abs((n
+1) - grid(x
, y
));
695 if (isadjacent
&& (gd
== 1)) continue;
696 if (!isadjacent
&& (gd
!= 1)) continue;
698 if (cube(nx
, ny
, n
+1) == FALSE
)
699 continue; /* already discounted this possibility. */
701 #ifdef STANDALONE_SOLVER
702 if (solver_show_working
) {
703 printf("%*sadjacent elimination, (%d,%d):%d %s (%d,%d):\n",
704 solver_recurse_depth
*4, "",
705 x
+1, y
+1, grid(x
, y
), isadjacent ?
"|" : "!|", nx
+1, ny
+1);
706 printf("%*s ruling out %d at (%d,%d)\n",
707 solver_recurse_depth
*4, "", n
+1, nx
+1, ny
+1);
710 cube(nx
, ny
, n
+1) = FALSE
;
720 static int solver_adjacent_set(struct latin_solver
*solver
, void *vctx
)
722 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
723 int x
, y
, i
, n
, nn
, o
= solver
->o
, nx
, ny
, gd
;
724 int nchanged
= 0, *scratch
= snewn(o
, int);
726 /* Update possible values based on other possible values
727 * of adjacent squares, and adjacency clues. */
729 for (x
= 0; x
< o
; x
++) {
730 for (y
= 0; y
< o
; y
++) {
731 for (i
= 0; i
< o
; i
++) {
732 int isadjacent
= (GRID(ctx
->state
, flags
, x
, y
) & adjthan
[i
].f
);
734 nx
= x
+ adjthan
[i
].dx
, ny
= y
+ adjthan
[i
].dy
;
735 if (nx
< 0 || ny
< 0 || nx
>= o
|| ny
>= o
)
738 /* We know the current possibles for the square (x,y)
739 * and also the adjacency clue from (x,y) to (nx,ny).
740 * Construct a maximum set of possibles for (nx,ny)
741 * in scratch, based on these constraints... */
743 memset(scratch
, 0, o
*sizeof(int));
745 for (n
= 0; n
< o
; n
++) {
746 if (cube(x
, y
, n
+1) == FALSE
) continue;
748 for (nn
= 0; nn
< o
; nn
++) {
749 if (n
== nn
) continue;
752 if (isadjacent
&& (gd
!= 1)) continue;
753 if (!isadjacent
&& (gd
== 1)) continue;
759 /* ...and remove any possibilities for (nx,ny) that are
760 * currently set but are not indicated in scratch. */
761 for (n
= 0; n
< o
; n
++) {
762 if (scratch
[n
] == 1) continue;
763 if (cube(nx
, ny
, n
+1) == FALSE
) continue;
765 #ifdef STANDALONE_SOLVER
766 if (solver_show_working
) {
767 printf("%*sadjacent possible elimination, (%d,%d) %s (%d,%d):\n",
768 solver_recurse_depth
*4, "",
769 x
+1, y
+1, isadjacent ?
"|" : "!|", nx
+1, ny
+1);
770 printf("%*s ruling out %d at (%d,%d)\n",
771 solver_recurse_depth
*4, "", n
+1, nx
+1, ny
+1);
774 cube(nx
, ny
, n
+1) = FALSE
;
784 static int solver_easy(struct latin_solver
*solver
, void *vctx
)
786 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
787 if (ctx
->state
->adjacent
)
788 return solver_adjacent(solver
, vctx
);
790 return solver_links(solver
, vctx
);
793 static int solver_set(struct latin_solver
*solver
, void *vctx
)
795 struct solver_ctx
*ctx
= (struct solver_ctx
*)vctx
;
796 if (ctx
->state
->adjacent
)
797 return solver_adjacent_set(solver
, vctx
);
802 #define SOLVER(upper,title,func,lower) func,
803 static usersolver_t
const unequal_solvers
[] = { DIFFLIST(SOLVER
) };
805 static int solver_state(game_state
*state
, int maxdiff
)
807 struct solver_ctx
*ctx
= new_ctx(state
);
808 struct latin_solver solver
;
811 latin_solver_alloc(&solver
, state
->nums
, state
->order
);
813 diff
= latin_solver_main(&solver
, maxdiff
,
814 DIFF_LATIN
, DIFF_SET
, DIFF_EXTREME
,
815 DIFF_EXTREME
, DIFF_RECURSIVE
,
816 unequal_solvers
, ctx
, clone_ctx
, free_ctx
);
818 memcpy(state
->hints
, solver
.cube
, state
->order
*state
->order
*state
->order
);
822 latin_solver_free(&solver
);
824 if (diff
== DIFF_IMPOSSIBLE
)
826 if (diff
== DIFF_UNFINISHED
)
828 if (diff
== DIFF_AMBIGUOUS
)
833 static game_state
*solver_hint(game_state
*state
, int *diff_r
, int mindiff
, int maxdiff
)
835 game_state
*ret
= dup_game(state
);
838 for (diff
= mindiff
; diff
<= maxdiff
; diff
++) {
839 r
= solver_state(ret
, diff
);
840 debug(("solver_state after %s %d", unequal_diffnames
[diff
], r
));
841 if (r
!= 0) goto done
;
845 if (diff_r
) *diff_r
= (r
> 0) ? diff
: -1;
849 /* ----------------------------------------------------------
853 static char *latin_desc(digit
*sq
, size_t order
)
855 int o2
= order
*order
, i
;
856 char *soln
= snewn(o2
+2, char);
859 for (i
= 0; i
< o2
; i
++)
860 soln
[i
+1] = n2c(sq
[i
], order
);
866 /* returns non-zero if it placed (or could have placed) clue. */
867 static int gg_place_clue(game_state
*state
, int ccode
, digit
*latin
, int checkonly
)
869 int loc
= ccode
/ 5, which
= ccode
% 5;
870 int x
= loc
% state
->order
, y
= loc
/ state
->order
;
872 assert(loc
< state
->order
*state
->order
);
874 if (which
== 4) { /* add number */
875 if (state
->nums
[loc
] != 0) {
876 #ifdef STANDALONE_SOLVER
877 if (state
->nums
[loc
] != latin
[loc
]) {
878 printf("inconsistency for (%d,%d): state %d latin %d\n",
879 x
+1, y
+1, state
->nums
[loc
], latin
[loc
]);
882 assert(state
->nums
[loc
] == latin
[loc
]);
886 state
->nums
[loc
] = latin
[loc
];
888 } else { /* add flag */
892 return 0; /* never add flag clues in adjacent mode (they're always
895 if (state
->flags
[loc
] & adjthan
[which
].f
)
896 return 0; /* already has flag. */
898 lx
= x
+ adjthan
[which
].dx
;
899 ly
= y
+ adjthan
[which
].dy
;
900 if (lx
< 0 || ly
< 0 || lx
>= state
->order
|| ly
>= state
->order
)
901 return 0; /* flag compares to off grid */
903 lloc
= loc
+ adjthan
[which
].dx
+ adjthan
[which
].dy
*state
->order
;
904 if (latin
[loc
] <= latin
[lloc
])
905 return 0; /* flag would be incorrect */
908 state
->flags
[loc
] |= adjthan
[which
].f
;
914 /* returns non-zero if it removed (or could have removed) the clue. */
915 static int gg_remove_clue(game_state
*state
, int ccode
, int checkonly
)
917 int loc
= ccode
/ 5, which
= ccode
% 5;
918 #ifdef STANDALONE_SOLVER
919 int x
= loc
% state
->order
, y
= loc
/ state
->order
;
922 assert(loc
< state
->order
*state
->order
);
924 if (which
== 4) { /* remove number. */
925 if (state
->nums
[loc
] == 0) return 0;
927 #ifdef STANDALONE_SOLVER
928 if (solver_show_working
)
929 printf("gg_remove_clue: removing %d at (%d,%d)",
930 state
->nums
[loc
], x
+1, y
+1);
932 state
->nums
[loc
] = 0;
934 } else { /* remove flag */
936 return 0; /* never remove clues in adjacent mode. */
938 if (!(state
->flags
[loc
] & adjthan
[which
].f
)) return 0;
940 #ifdef STANDALONE_SOLVER
941 if (solver_show_working
)
942 printf("gg_remove_clue: removing %c at (%d,%d)",
943 adjthan
[which
].c
, x
+1, y
+1);
945 state
->flags
[loc
] &= ~adjthan
[which
].f
;
951 static int gg_best_clue(game_state
*state
, int *scratch
, digit
*latin
)
953 int ls
= state
->order
* state
->order
* 5;
954 int maxposs
= 0, minclues
= 5, best
= -1, i
, j
;
955 int nposs
, nclues
, loc
, x
, y
;
957 #ifdef STANDALONE_SOLVER
958 if (solver_show_working
) {
960 latin_solver_debug(state
->hints
, state
->order
);
964 for (i
= ls
; i
-- > 0 ;) {
965 if (!gg_place_clue(state
, scratch
[i
], latin
, 1)) continue;
967 loc
= scratch
[i
] / 5;
968 x
= loc
% state
->order
; y
= loc
/ state
->order
;
969 for (j
= nposs
= 0; j
< state
->order
; j
++) {
970 if (state
->hints
[loc
*state
->order
+ j
]) nposs
++;
972 for (j
= nclues
= 0; j
< 4; j
++) {
973 if (state
->flags
[loc
] & adjthan
[j
].f
) nclues
++;
975 if ((nposs
> maxposs
) ||
976 (nposs
== maxposs
&& nclues
< minclues
)) {
977 best
= i
; maxposs
= nposs
; minclues
= nclues
;
978 #ifdef STANDALONE_SOLVER
979 if (solver_show_working
)
980 printf("gg_best_clue: b%d (%d,%d) new best [%d poss, %d clues].\n",
981 best
, x
+1, y
+1, nposs
, nclues
);
985 /* if we didn't solve, we must have 1 clue to place! */
990 #ifdef STANDALONE_SOLVER
992 #define MAXTRIES maxtries
998 static int game_assemble(game_state
*new, int *scratch
, digit
*latin
,
1001 game_state
*copy
= dup_game(new);
1004 if (difficulty
>= DIFF_RECURSIVE
) {
1005 /* We mustn't use any solver that might guess answers;
1006 * if it guesses wrongly but solves, gg_place_clue will
1007 * get mighty confused. We will always trim clues down
1008 * (making it more difficult) in game_strip, which doesn't
1009 * have this problem. */
1010 difficulty
= DIFF_RECURSIVE
-1;
1013 #ifdef STANDALONE_SOLVER
1014 if (solver_show_working
) {
1016 latin_solver_debug(new->hints
, new->order
);
1022 if (solver_state(copy
, difficulty
) == 1) break;
1024 best
= gg_best_clue(copy
, scratch
, latin
);
1025 gg_place_clue(new, scratch
[best
], latin
, 0);
1026 gg_place_clue(copy
, scratch
[best
], latin
, 0);
1029 #ifdef STANDALONE_SOLVER
1030 if (solver_show_working
) {
1031 char *dbg
= game_text_format(new);
1032 printf("game_assemble: done, %d solver iterations:\n%s\n", gg_solved
, dbg
);
1039 static void game_strip(game_state
*new, int *scratch
, digit
*latin
,
1042 int o
= new->order
, o2
= o
*o
, lscratch
= o2
*5, i
;
1043 game_state
*copy
= blank_game(new->order
, new->adjacent
);
1045 /* For each symbol (if it exists in new), try and remove it and
1046 * solve again; if we couldn't solve without it put it back. */
1047 for (i
= 0; i
< lscratch
; i
++) {
1048 if (!gg_remove_clue(new, scratch
[i
], 0)) continue;
1050 memcpy(copy
->nums
, new->nums
, o2
* sizeof(digit
));
1051 memcpy(copy
->flags
, new->flags
, o2
* sizeof(unsigned int));
1053 if (solver_state(copy
, difficulty
) != 1) {
1054 /* put clue back, we can't solve without it. */
1055 int ret
= gg_place_clue(new, scratch
[i
], latin
, 0);
1058 #ifdef STANDALONE_SOLVER
1059 if (solver_show_working
)
1060 printf("game_strip: clue was redundant.");
1065 #ifdef STANDALONE_SOLVER
1066 if (solver_show_working
) {
1067 char *dbg
= game_text_format(new);
1068 debug(("game_strip: done, %d solver iterations.", gg_solved
));
1075 static void add_adjacent_flags(game_state
*state
, digit
*latin
)
1077 int x
, y
, o
= state
->order
;
1079 /* All clues in adjacent mode are always present (the only variables are
1080 * the numbers). This adds all the flags to state based on the supplied
1083 for (y
= 0; y
< o
; y
++) {
1084 for (x
= 0; x
< o
; x
++) {
1085 if (x
< (o
-1) && (abs(latin
[y
*o
+x
] - latin
[y
*o
+x
+1]) == 1)) {
1086 GRID(state
, flags
, x
, y
) |= F_ADJ_RIGHT
;
1087 GRID(state
, flags
, x
+1, y
) |= F_ADJ_LEFT
;
1089 if (y
< (o
-1) && (abs(latin
[y
*o
+x
] - latin
[(y
+1)*o
+x
]) == 1)) {
1090 GRID(state
, flags
, x
, y
) |= F_ADJ_DOWN
;
1091 GRID(state
, flags
, x
, y
+1) |= F_ADJ_UP
;
1097 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1098 char **aux
, int interactive
)
1101 int i
, x
, y
, retlen
, k
, nsol
;
1102 int o2
= params
->order
* params
->order
, ntries
= 1;
1103 int *scratch
, lscratch
= o2
*5;
1105 game_state
*state
= blank_game(params
->order
, params
->adjacent
);
1107 /* Generate a list of 'things to strip' (randomised later) */
1108 scratch
= snewn(lscratch
, int);
1109 /* Put the numbers (4 mod 5) before the inequalities (0-3 mod 5) */
1110 for (i
= 0; i
< lscratch
; i
++) scratch
[i
] = (i
%o2
)*5 + 4 - (i
/o2
);
1113 #ifdef STANDALONE_SOLVER
1114 if (solver_show_working
)
1115 printf("new_game_desc: generating %s puzzle, ntries so far %d\n",
1116 unequal_diffnames
[params
->diff
], ntries
);
1119 sq
= latin_generate(params
->order
, rs
);
1120 latin_debug(sq
, params
->order
);
1121 /* Separately shuffle the numeric and inequality clues */
1122 shuffle(scratch
, lscratch
/5, sizeof(int), rs
);
1123 shuffle(scratch
+lscratch
/5, 4*lscratch
/5, sizeof(int), rs
);
1125 memset(state
->nums
, 0, o2
* sizeof(digit
));
1126 memset(state
->flags
, 0, o2
* sizeof(unsigned int));
1128 if (state
->adjacent
) {
1129 /* All adjacency flags are always present. */
1130 add_adjacent_flags(state
, sq
);
1134 if (game_assemble(state
, scratch
, sq
, params
->diff
) < 0)
1136 game_strip(state
, scratch
, sq
, params
->diff
);
1138 if (params
->diff
> 0) {
1139 game_state
*copy
= dup_game(state
);
1140 nsol
= solver_state(copy
, params
->diff
-1);
1143 #ifdef STANDALONE_SOLVER
1144 if (solver_show_working
)
1145 printf("game_assemble: puzzle as generated is too easy.\n");
1147 if (ntries
< MAXTRIES
) {
1151 #ifdef STANDALONE_SOLVER
1152 if (solver_show_working
)
1153 printf("Unable to generate %s %dx%d after %d attempts.\n",
1154 unequal_diffnames
[params
->diff
],
1155 params
->order
, params
->order
, MAXTRIES
);
1160 #ifdef STANDALONE_SOLVER
1161 if (solver_show_working
)
1162 printf("new_game_desc: generated %s puzzle; %d attempts (%d solver).\n",
1163 unequal_diffnames
[params
->diff
], ntries
, gg_solved
);
1166 ret
= NULL
; retlen
= 0;
1167 for (y
= 0; y
< params
->order
; y
++) {
1168 for (x
= 0; x
< params
->order
; x
++) {
1169 unsigned int f
= GRID(state
, flags
, x
, y
);
1170 k
= sprintf(buf
, "%d%s%s%s%s,",
1171 GRID(state
, nums
, x
, y
),
1172 (f
& F_ADJ_UP
) ?
"U" : "",
1173 (f
& F_ADJ_RIGHT
) ?
"R" : "",
1174 (f
& F_ADJ_DOWN
) ?
"D" : "",
1175 (f
& F_ADJ_LEFT
) ?
"L" : "");
1177 ret
= sresize(ret
, retlen
+ k
+ 1, char);
1178 strcpy(ret
+ retlen
, buf
);
1182 *aux
= latin_desc(sq
, params
->order
);
1191 static game_state
*load_game(game_params
*params
, char *desc
,
1194 game_state
*state
= blank_game(params
->order
, params
->adjacent
);
1196 int i
= 0, n
, o
= params
->order
, x
, y
;
1200 while (*p
>= 'a' && *p
<= 'z') {
1205 why
= "Too much data to fill grid"; goto fail
;
1208 if (*p
< '0' && *p
> '9') {
1209 why
= "Expecting number in game description"; goto fail
;
1212 if (n
< 0 || n
> o
) {
1213 why
= "Out-of-range number in game description"; goto fail
;
1215 state
->nums
[i
] = (digit
)n
;
1216 while (*p
>= '0' && *p
<= '9') p
++; /* skip number */
1218 if (state
->nums
[i
] != 0)
1219 state
->flags
[i
] |= F_IMMUTABLE
; /* === number set by game description */
1221 while (*p
== 'U' || *p
== 'R' || *p
== 'D' || *p
== 'L') {
1223 case 'U': state
->flags
[i
] |= F_ADJ_UP
; break;
1224 case 'R': state
->flags
[i
] |= F_ADJ_RIGHT
; break;
1225 case 'D': state
->flags
[i
] |= F_ADJ_DOWN
; break;
1226 case 'L': state
->flags
[i
] |= F_ADJ_LEFT
; break;
1227 default: why
= "Expecting flag URDL in game description"; goto fail
;
1232 if (i
< o
*o
&& *p
!= ',') {
1233 why
= "Missing separator"; goto fail
;
1238 why
= "Not enough data to fill grid"; goto fail
;
1241 for (y
= 0; y
< o
; y
++) {
1242 for (x
= 0; x
< o
; x
++) {
1243 for (n
= 0; n
< 4; n
++) {
1244 if (GRID(state
, flags
, x
, y
) & adjthan
[n
].f
) {
1245 int nx
= x
+ adjthan
[n
].dx
;
1246 int ny
= y
+ adjthan
[n
].dy
;
1247 /* a flag must not point us off the grid. */
1248 if (nx
< 0 || ny
< 0 || nx
>= o
|| ny
>= o
) {
1249 why
= "Flags go off grid"; goto fail
;
1251 if (params
->adjacent
) {
1252 /* if one cell is adjacent to another, the other must
1253 * also be adjacent to the first. */
1254 if (!(GRID(state
, flags
, nx
, ny
) & adjthan
[n
].fo
)) {
1255 why
= "Flags contradicting each other"; goto fail
;
1258 /* if one cell is GT another, the other must _not_ also
1259 * be GT the first. */
1260 if (GRID(state
, flags
, nx
, ny
) & adjthan
[n
].fo
) {
1261 why
= "Flags contradicting each other"; goto fail
;
1273 if (why_r
) *why_r
= why
;
1277 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1279 game_state
*state
= load_game(params
, desc
, NULL
);
1281 assert("Unable to load ?validated game.");
1287 static char *validate_desc(game_params
*params
, char *desc
)
1290 game_state
*dummy
= load_game(params
, desc
, &why
);
1299 static char *solve_game(game_state
*state
, game_state
*currstate
,
1300 char *aux
, char **error
)
1306 if (aux
) return dupstr(aux
);
1308 solved
= dup_game(state
);
1309 for (r
= 0; r
< state
->order
*state
->order
; r
++) {
1310 if (!(solved
->flags
[r
] & F_IMMUTABLE
))
1311 solved
->nums
[r
] = 0;
1313 r
= solver_state(solved
, DIFFCOUNT
);
1314 if (r
> 0) ret
= latin_desc(solved
->nums
, solved
->order
);
1319 /* ----------------------------------------------------------
1320 * Game UI input processing.
1324 int hx
, hy
; /* as for solo.c, highlight pos */
1325 int hshow
, hpencil
, hcursor
; /* show state, type, and ?cursor. */
1328 static game_ui
*new_ui(game_state
*state
)
1330 game_ui
*ui
= snew(game_ui
);
1332 ui
->hx
= ui
->hy
= 0;
1333 ui
->hpencil
= ui
->hshow
= ui
->hcursor
= 0;
1338 static void free_ui(game_ui
*ui
)
1343 static char *encode_ui(game_ui
*ui
)
1348 static void decode_ui(game_ui
*ui
, char *encoding
)
1352 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1353 game_state
*newstate
)
1355 /* See solo.c; if we were pencil-mode highlighting and
1356 * somehow a square has just been properly filled, cancel
1358 if (ui
->hshow
&& ui
->hpencil
&& !ui
->hcursor
&&
1359 GRID(newstate
, nums
, ui
->hx
, ui
->hy
) != 0) {
1364 struct game_drawstate
{
1365 int tilesize
, order
, started
, adjacent
;
1366 digit
*nums
; /* copy of nums, o^2 */
1367 unsigned char *hints
; /* copy of hints, o^3 */
1368 unsigned int *flags
; /* o^2 */
1370 int hx
, hy
, hshow
, hpencil
; /* as for game_ui. */
1374 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1375 int ox
, int oy
, int button
)
1377 int x
= FROMCOORD(ox
), y
= FROMCOORD(oy
), n
;
1380 button
&= ~MOD_MASK
;
1382 if (x
>= 0 && x
< ds
->order
&& ((ox
- COORD(x
)) <= TILE_SIZE
) &&
1383 y
>= 0 && y
< ds
->order
&& ((oy
- COORD(y
)) <= TILE_SIZE
)) {
1384 if (button
== LEFT_BUTTON
) {
1385 /* normal highlighting for non-immutable squares */
1386 if (GRID(state
, flags
, x
, y
) & F_IMMUTABLE
)
1388 else if (x
== ui
->hx
&& y
== ui
->hy
&&
1389 ui
->hshow
&& ui
->hpencil
== 0)
1392 ui
->hx
= x
; ui
->hy
= y
; ui
->hpencil
= 0;
1398 if (button
== RIGHT_BUTTON
) {
1399 /* pencil highlighting for non-filled squares */
1400 if (GRID(state
, nums
, x
, y
) != 0)
1402 else if (x
== ui
->hx
&& y
== ui
->hy
&&
1403 ui
->hshow
&& ui
->hpencil
)
1406 ui
->hx
= x
; ui
->hy
= y
; ui
->hpencil
= 1;
1414 if (IS_CURSOR_MOVE(button
)) {
1415 move_cursor(button
, &ui
->hx
, &ui
->hy
, ds
->order
, ds
->order
, 0);
1416 ui
->hshow
= ui
->hcursor
= 1;
1419 if (ui
->hshow
&& IS_CURSOR_SELECT(button
)) {
1420 ui
->hpencil
= 1 - ui
->hpencil
;
1427 debug(("button %d, cbutton %d", button
, (int)((char)button
)));
1428 n
= c2n(button
, state
->order
);
1430 debug(("n %d, h (%d,%d) p %d flags 0x%x nums %d",
1431 n
, ui
->hx
, ui
->hy
, ui
->hpencil
,
1432 GRID(state
, flags
, ui
->hx
, ui
->hy
),
1433 GRID(state
, nums
, ui
->hx
, ui
->hy
)));
1435 if (n
< 0 || n
> ds
->order
)
1436 return NULL
; /* out of range */
1437 if (GRID(state
, flags
, ui
->hx
, ui
->hy
) & F_IMMUTABLE
)
1438 return NULL
; /* can't edit immutable square (!) */
1439 if (ui
->hpencil
&& GRID(state
, nums
, ui
->hx
, ui
->hy
) > 0)
1440 return NULL
; /* can't change hints on filled square (!) */
1443 sprintf(buf
, "%c%d,%d,%d",
1444 (char)(ui
->hpencil
&& n
> 0 ?
'P' : 'R'), ui
->hx
, ui
->hy
, n
);
1446 if (!ui
->hcursor
) ui
->hshow
= 0;
1451 if (button
== 'H' || button
== 'h')
1453 if (button
== 'M' || button
== 'm')
1459 static game_state
*execute_move(game_state
*state
, char *move
)
1461 game_state
*ret
= NULL
;
1464 debug(("execute_move: %s", move
));
1466 if ((move
[0] == 'P' || move
[0] == 'R') &&
1467 sscanf(move
+1, "%d,%d,%d", &x
, &y
, &n
) == 3 &&
1468 x
>= 0 && x
< state
->order
&& y
>= 0 && y
< state
->order
&&
1469 n
>= 0 && n
<= state
->order
) {
1470 ret
= dup_game(state
);
1471 if (move
[0] == 'P' && n
> 0)
1472 HINT(ret
, x
, y
, n
-1) = !HINT(ret
, x
, y
, n
-1);
1474 GRID(ret
, nums
, x
, y
) = n
;
1475 for (i
= 0; i
< state
->order
; i
++)
1476 HINT(ret
, x
, y
, i
) = 0;
1478 /* real change to grid; check for completion */
1479 if (!ret
->completed
&& check_complete(ret
->nums
, ret
, 1) > 0)
1480 ret
->completed
= TRUE
;
1483 } else if (move
[0] == 'S') {
1486 ret
= dup_game(state
);
1487 ret
->completed
= ret
->cheated
= TRUE
;
1490 for (i
= 0; i
< state
->order
*state
->order
; i
++) {
1491 n
= c2n((int)*p
, state
->order
);
1492 if (!*p
|| n
<= 0 || n
> state
->order
)
1497 if (*p
) goto badmove
;
1498 rc
= check_complete(ret
->nums
, ret
, 1);
1501 } else if (move
[0] == 'M') {
1502 ret
= dup_game(state
);
1503 for (x
= 0; x
< state
->order
; x
++) {
1504 for (y
= 0; y
< state
->order
; y
++) {
1505 for (n
= 0; n
< state
->order
; n
++) {
1506 HINT(ret
, x
, y
, n
) = 1;
1511 } else if (move
[0] == 'H') {
1512 return solver_hint(state
, NULL
, DIFF_EASY
, DIFF_EASY
);
1516 if (ret
) free_game(ret
);
1520 /* ----------------------------------------------------------------------
1521 * Drawing/printing routines.
1524 #define DRAW_SIZE (TILE_SIZE*ds->order + GAP_SIZE*(ds->order-1) + BORDER*2)
1526 static void game_compute_size(game_params
*params
, int tilesize
,
1529 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1530 struct { int tilesize
, order
; } ads
, *ds
= &ads
;
1531 ads
.tilesize
= tilesize
;
1532 ads
.order
= params
->order
;
1534 *x
= *y
= DRAW_SIZE
;
1537 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1538 game_params
*params
, int tilesize
)
1540 ds
->tilesize
= tilesize
;
1543 static float *game_colours(frontend
*fe
, int *ncolours
)
1545 float *ret
= snewn(3 * NCOLOURS
, float);
1548 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1550 for (i
= 0; i
< 3; i
++) {
1551 ret
[COL_TEXT
* 3 + i
] = 0.0F
;
1552 ret
[COL_GRID
* 3 + i
] = 0.5F
;
1555 /* Lots of these were taken from solo.c. */
1556 ret
[COL_GUESS
* 3 + 0] = 0.0F
;
1557 ret
[COL_GUESS
* 3 + 1] = 0.6F
* ret
[COL_BACKGROUND
* 3 + 1];
1558 ret
[COL_GUESS
* 3 + 2] = 0.0F
;
1560 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1561 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1562 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1564 ret
[COL_PENCIL
* 3 + 0] = 0.5F
* ret
[COL_BACKGROUND
* 3 + 0];
1565 ret
[COL_PENCIL
* 3 + 1] = 0.5F
* ret
[COL_BACKGROUND
* 3 + 1];
1566 ret
[COL_PENCIL
* 3 + 2] = ret
[COL_BACKGROUND
* 3 + 2];
1568 *ncolours
= NCOLOURS
;
1572 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1574 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1575 int o2
= state
->order
*state
->order
, o3
= o2
*state
->order
;
1578 ds
->order
= state
->order
;
1579 ds
->adjacent
= state
->adjacent
;
1581 ds
->nums
= snewn(o2
, digit
);
1582 ds
->hints
= snewn(o3
, unsigned char);
1583 ds
->flags
= snewn(o2
, unsigned int);
1584 memset(ds
->nums
, 0, o2
*sizeof(digit
));
1585 memset(ds
->hints
, 0, o3
);
1586 memset(ds
->flags
, 0, o2
*sizeof(unsigned int));
1588 ds
->hx
= ds
->hy
= 0;
1589 ds
->started
= ds
->hshow
= ds
->hpencil
= ds
->hflash
= 0;
1594 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1602 static void draw_gt(drawing
*dr
, int ox
, int oy
,
1603 int dx1
, int dy1
, int dx2
, int dy2
, int col
)
1605 draw_line(dr
, ox
, oy
, ox
+dx1
, oy
+dy1
, col
);
1606 draw_line(dr
, ox
+dx1
, oy
+dy1
, ox
+dx1
+dx2
, oy
+dy1
+dy2
, col
);
1609 static void draw_gts(drawing
*dr
, game_drawstate
*ds
, int ox
, int oy
,
1610 unsigned int f
, int col
)
1612 int g
= GAP_SIZE
, g2
= (g
+1)/2, g4
= (g
+1)/4;
1614 /* Draw all the greater-than signs emanating from this tile. */
1617 draw_gt(dr
, ox
+g2
, oy
-g4
, g2
, -g2
, g2
, g2
,
1618 (f
& F_ERROR_UP
) ? COL_ERROR
: col
);
1619 draw_update(dr
, ox
, oy
-g
, TILE_SIZE
, g
);
1621 if (f
& F_ADJ_RIGHT
) {
1622 draw_gt(dr
, ox
+TILE_SIZE
+g4
, oy
+g2
, g2
, g2
, -g2
, g2
,
1623 (f
& F_ERROR_RIGHT
) ? COL_ERROR
: col
);
1624 draw_update(dr
, ox
+TILE_SIZE
, oy
, g
, TILE_SIZE
);
1626 if (f
& F_ADJ_DOWN
) {
1627 draw_gt(dr
, ox
+g2
, oy
+TILE_SIZE
+g4
, g2
, g2
, g2
, -g2
,
1628 (f
& F_ERROR_DOWN
) ? COL_ERROR
: col
);
1629 draw_update(dr
, ox
, oy
+TILE_SIZE
, TILE_SIZE
, g
);
1631 if (f
& F_ADJ_LEFT
) {
1632 draw_gt(dr
, ox
-g4
, oy
+g2
, -g2
, g2
, g2
, g2
,
1633 (f
& F_ERROR_LEFT
) ? COL_ERROR
: col
);
1634 draw_update(dr
, ox
-g
, oy
, g
, TILE_SIZE
);
1638 static void draw_adjs(drawing
*dr
, game_drawstate
*ds
, int ox
, int oy
,
1639 unsigned int f
, int col
)
1641 int g
= GAP_SIZE
, g38
= 3*(g
+1)/8, g4
= (g
+1)/4;
1643 /* Draw all the adjacency bars relevant to this tile; we only have
1644 * to worry about F_ADJ_RIGHT and F_ADJ_DOWN.
1646 * If we _only_ have the error flag set (i.e. it's not supposed to be
1647 * adjacent, but adjacent numbers were entered) draw an outline red bar.
1650 if (f
& (F_ADJ_RIGHT
|F_ERROR_RIGHT
)) {
1651 if (f
& F_ADJ_RIGHT
) {
1652 draw_rect(dr
, ox
+TILE_SIZE
+g38
, oy
, g4
, TILE_SIZE
,
1653 (f
& F_ERROR_RIGHT
) ? COL_ERROR
: col
);
1655 draw_rect_outline(dr
, ox
+TILE_SIZE
+g38
, oy
, g4
, TILE_SIZE
, COL_ERROR
);
1658 draw_rect(dr
, ox
+TILE_SIZE
+g38
, oy
, g4
, TILE_SIZE
, COL_BACKGROUND
);
1660 draw_update(dr
, ox
+TILE_SIZE
, oy
, g
, TILE_SIZE
);
1662 if (f
& (F_ADJ_DOWN
|F_ERROR_DOWN
)) {
1663 if (f
& F_ADJ_DOWN
) {
1664 draw_rect(dr
, ox
, oy
+TILE_SIZE
+g38
, TILE_SIZE
, g4
,
1665 (f
& F_ERROR_DOWN
) ? COL_ERROR
: col
);
1667 draw_rect_outline(dr
, ox
, oy
+TILE_SIZE
+g38
, TILE_SIZE
, g4
, COL_ERROR
);
1670 draw_rect(dr
, ox
, oy
+TILE_SIZE
+g38
, TILE_SIZE
, g4
, COL_BACKGROUND
);
1672 draw_update(dr
, ox
, oy
+TILE_SIZE
, TILE_SIZE
, g
);
1675 static void draw_furniture(drawing
*dr
, game_drawstate
*ds
, game_state
*state
,
1676 game_ui
*ui
, int x
, int y
, int hflash
)
1678 int ox
= COORD(x
), oy
= COORD(y
), bg
, hon
;
1679 unsigned int f
= GRID(state
, flags
, x
, y
);
1681 bg
= hflash ? COL_HIGHLIGHT
: COL_BACKGROUND
;
1683 hon
= (ui
->hshow
&& x
== ui
->hx
&& y
== ui
->hy
);
1686 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
,
1687 (hon
&& !ui
->hpencil
) ? COL_HIGHLIGHT
: bg
);
1689 /* Draw the highlight (pencil or full), if we're the highlight */
1690 if (hon
&& ui
->hpencil
) {
1694 coords
[2] = ox
+ TILE_SIZE
/2;
1697 coords
[5] = oy
+ TILE_SIZE
/2;
1698 draw_polygon(dr
, coords
, 3, COL_HIGHLIGHT
, COL_HIGHLIGHT
);
1701 /* Draw the square outline (which is the cursor, if we're the cursor). */
1702 draw_rect_outline(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, COL_GRID
);
1704 draw_update(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
);
1706 /* Draw the adjacent clue signs. */
1708 draw_adjs(dr
, ds
, ox
, oy
, f
, COL_GRID
);
1710 draw_gts(dr
, ds
, ox
, oy
, f
, COL_TEXT
);
1713 static void draw_num(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
1715 int ox
= COORD(x
), oy
= COORD(y
);
1716 unsigned int f
= GRID(ds
,flags
,x
,y
);
1719 /* (can assume square has just been cleared) */
1721 /* Draw number, choosing appropriate colour */
1722 str
[0] = n2c(GRID(ds
, nums
, x
, y
), ds
->order
);
1724 draw_text(dr
, ox
+ TILE_SIZE
/2, oy
+ TILE_SIZE
/2,
1725 FONT_VARIABLE
, 3*TILE_SIZE
/4, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1726 (f
& F_IMMUTABLE
) ? COL_TEXT
: (f
& F_ERROR
) ? COL_ERROR
: COL_GUESS
, str
);
1729 static void draw_hints(drawing
*dr
, game_drawstate
*ds
, int x
, int y
)
1731 int ox
= COORD(x
), oy
= COORD(y
);
1732 int nhints
, i
, j
, hw
, hh
, hmax
, fontsz
;
1735 /* (can assume square has just been cleared) */
1737 /* Draw hints; steal ingenious algorithm (basically)
1738 * from solo.c:draw_number() */
1739 for (i
= nhints
= 0; i
< ds
->order
; i
++) {
1740 if (HINT(ds
, x
, y
, i
)) nhints
++;
1743 for (hw
= 1; hw
* hw
< nhints
; hw
++);
1745 hh
= (nhints
+ hw
- 1) / hw
;
1748 fontsz
= TILE_SIZE
/(hmax
*(11-hmax
)/8);
1750 for (i
= j
= 0; i
< ds
->order
; i
++) {
1751 if (HINT(ds
,x
,y
,i
)) {
1752 int hx
= j
% hw
, hy
= j
/ hw
;
1754 str
[0] = n2c(i
+1, ds
->order
);
1757 ox
+ (4*hx
+3) * TILE_SIZE
/ (4*hw
+2),
1758 oy
+ (4*hy
+3) * TILE_SIZE
/ (4*hh
+2),
1759 FONT_VARIABLE
, fontsz
,
1760 ALIGN_VCENTRE
| ALIGN_HCENTRE
, COL_PENCIL
, str
);
1766 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1767 game_state
*state
, int dir
, game_ui
*ui
,
1768 float animtime
, float flashtime
)
1770 int x
, y
, i
, hchanged
= 0, stale
, hflash
= 0;
1772 debug(("highlight old (%d,%d), new (%d,%d)", ds
->hx
, ds
->hy
, ui
->hx
, ui
->hy
));
1774 if (flashtime
> 0 &&
1775 (flashtime
<= FLASH_TIME
/3 || flashtime
>= FLASH_TIME
*2/3))
1779 draw_rect(dr
, 0, 0, DRAW_SIZE
, DRAW_SIZE
, COL_BACKGROUND
);
1780 draw_update(dr
, 0, 0, DRAW_SIZE
, DRAW_SIZE
);
1782 if (ds
->hx
!= ui
->hx
|| ds
->hy
!= ui
->hy
||
1783 ds
->hshow
!= ui
->hshow
|| ds
->hpencil
!= ui
->hpencil
)
1786 for (x
= 0; x
< ds
->order
; x
++) {
1787 for (y
= 0; y
< ds
->order
; y
++) {
1790 else if (hflash
!= ds
->hflash
)
1796 if ((x
== ui
->hx
&& y
== ui
->hy
) ||
1797 (x
== ds
->hx
&& y
== ds
->hy
))
1801 if (GRID(state
, nums
, x
, y
) != GRID(ds
, nums
, x
, y
)) {
1802 GRID(ds
, nums
, x
, y
) = GRID(state
, nums
, x
, y
);
1805 if (GRID(state
, flags
, x
, y
) != GRID(ds
, flags
, x
, y
)) {
1806 GRID(ds
, flags
, x
, y
) = GRID(state
, flags
, x
, y
);
1809 if (GRID(ds
, nums
, x
, y
) == 0) {
1810 /* We're not a number square (therefore we might
1811 * display hints); do we need to update? */
1812 for (i
= 0; i
< ds
->order
; i
++) {
1813 if (HINT(state
, x
, y
, i
) != HINT(ds
, x
, y
, i
)) {
1814 HINT(ds
, x
, y
, i
) = HINT(state
, x
, y
, i
);
1820 draw_furniture(dr
, ds
, state
, ui
, x
, y
, hflash
);
1821 if (GRID(ds
, nums
, x
, y
) > 0)
1822 draw_num(dr
, ds
, x
, y
);
1824 draw_hints(dr
, ds
, x
, y
);
1828 ds
->hx
= ui
->hx
; ds
->hy
= ui
->hy
;
1829 ds
->hshow
= ui
->hshow
;
1830 ds
->hpencil
= ui
->hpencil
;
1833 ds
->hflash
= hflash
;
1836 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1837 int dir
, game_ui
*ui
)
1842 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1843 int dir
, game_ui
*ui
)
1845 if (!oldstate
->completed
&& newstate
->completed
&&
1846 !oldstate
->cheated
&& !newstate
->cheated
)
1851 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1856 static void game_print_size(game_params
*params
, float *x
, float *y
)
1860 /* 10mm squares by default, roughly the same as Grauniad. */
1861 game_compute_size(params
, 1000, &pw
, &ph
);
1866 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1868 int ink
= print_mono_colour(dr
, 0);
1869 int x
, y
, o
= state
->order
, ox
, oy
, n
;
1872 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1873 game_drawstate ads
, *ds
= &ads
;
1874 game_set_size(dr
, ds
, NULL
, tilesize
);
1876 print_line_width(dr
, 2 * TILE_SIZE
/ 40);
1878 /* Squares, numbers, gt signs */
1879 for (y
= 0; y
< o
; y
++) {
1880 for (x
= 0; x
< o
; x
++) {
1881 ox
= COORD(x
); oy
= COORD(y
);
1882 n
= GRID(state
, nums
, x
, y
);
1884 draw_rect_outline(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, ink
);
1886 str
[0] = n ?
n2c(n
, state
->order
) : ' ';
1888 draw_text(dr
, ox
+ TILE_SIZE
/2, oy
+ TILE_SIZE
/2,
1889 FONT_VARIABLE
, TILE_SIZE
/2, ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1893 draw_adjs(dr
, ds
, ox
, oy
, GRID(state
, flags
, x
, y
), ink
);
1895 draw_gts(dr
, ds
, ox
, oy
, GRID(state
, flags
, x
, y
), ink
);
1900 /* ----------------------------------------------------------------------
1905 #define thegame unequal
1908 const struct game thegame
= {
1909 "Unequal", "games.unequal", "unequal",
1916 TRUE
, game_configure
, custom_params
,
1924 TRUE
, game_can_format_as_text_now
, game_text_format
,
1932 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1935 game_free_drawstate
,
1939 TRUE
, FALSE
, game_print_size
, game_print
,
1940 FALSE
, /* wants_statusbar */
1941 FALSE
, game_timing_state
,
1942 REQUIRE_RBUTTON
| REQUIRE_NUMPAD
, /* flags */
1945 /* ----------------------------------------------------------------------
1946 * Standalone solver.
1949 #ifdef STANDALONE_SOLVER
1954 const char *quis
= NULL
;
1956 #if 0 /* currently unused */
1958 static void debug_printf(char *fmt
, ...)
1964 vsprintf(buf
, fmt
, ap
);
1969 static void game_printf(game_state
*state
)
1971 char *dbg
= game_text_format(state
);
1976 static void game_printf_wide(game_state
*state
)
1980 for (y
= 0; y
< state
->order
; y
++) {
1981 for (x
= 0; x
< state
->order
; x
++) {
1982 n
= GRID(state
, nums
, x
, y
);
1983 for (i
= 0; i
< state
->order
; i
++) {
1985 printf("%c", n2c(n
, state
->order
));
1986 else if (HINT(state
, x
, y
, i
))
1987 printf("%c", n2c(i
+1, state
->order
));
2000 static void pdiff(int diff
)
2002 if (diff
== DIFF_IMPOSSIBLE
)
2003 printf("Game is impossible.\n");
2004 else if (diff
== DIFF_UNFINISHED
)
2005 printf("Game has incomplete.\n");
2006 else if (diff
== DIFF_AMBIGUOUS
)
2007 printf("Game has multiple solutions.\n");
2009 printf("Game has difficulty %s.\n", unequal_diffnames
[diff
]);
2012 static int solve(game_params
*p
, char *desc
, int debug
)
2014 game_state
*state
= new_game(NULL
, p
, desc
);
2015 struct solver_ctx
*ctx
= new_ctx(state
);
2016 struct latin_solver solver
;
2019 solver_show_working
= debug
;
2022 latin_solver_alloc(&solver
, state
->nums
, state
->order
);
2024 diff
= latin_solver_main(&solver
, DIFF_RECURSIVE
,
2025 DIFF_LATIN
, DIFF_SET
, DIFF_EXTREME
,
2026 DIFF_EXTREME
, DIFF_RECURSIVE
,
2027 unequal_solvers
, ctx
, clone_ctx
, free_ctx
);
2031 latin_solver_free(&solver
);
2033 if (debug
) pdiff(diff
);
2040 static void check(game_params
*p
)
2042 char *msg
= validate_params(p
, 1);
2044 fprintf(stderr
, "%s: %s", quis
, msg
);
2049 static int gen(game_params
*p
, random_state
*rs
, int debug
)
2056 solver_show_working
= debug
;
2057 desc
= new_game_desc(p
, rs
, &aux
, 0);
2058 diff
= solve(p
, desc
, debug
);
2065 static void soak(game_params
*p
, random_state
*rs
)
2067 time_t tt_start
, tt_now
, tt_last
;
2070 int n
= 0, neasy
= 0, realdiff
= p
->diff
;
2074 solver_show_working
= 0;
2077 tt_start
= tt_now
= time(NULL
);
2079 printf("Soak-generating an %s %dx%d grid, difficulty %s.\n",
2080 p
->adjacent ?
"adjacent" : "unequal",
2081 p
->order
, p
->order
, unequal_diffnames
[p
->diff
]);
2085 desc
= new_game_desc(p
, rs
, &aux
, 0);
2086 st
= new_game(NULL
, p
, desc
);
2087 solver_state(st
, DIFF_RECURSIVE
);
2093 if (realdiff
!= p
->diff
) neasy
++;
2095 tt_last
= time(NULL
);
2096 if (tt_last
> tt_now
) {
2098 printf("%d total, %3.1f/s; %d/%2.1f%% easy, %3.1f/s good.\n",
2099 n
, (double)n
/ ((double)tt_now
- tt_start
),
2100 neasy
, (double)neasy
*100.0/(double)n
,
2101 (double)(n
- neasy
) / ((double)tt_now
- tt_start
));
2106 static void usage_exit(const char *msg
)
2109 fprintf(stderr
, "%s: %s\n", quis
, msg
);
2110 fprintf(stderr
, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis
);
2114 int main(int argc
, const char *argv
[])
2117 time_t seed
= time(NULL
);
2118 int do_soak
= 0, diff
;
2125 while (--argc
> 0) {
2126 const char *p
= *++argv
;
2127 if (!strcmp(p
, "--soak"))
2129 else if (!strcmp(p
, "--seed")) {
2131 usage_exit("--seed needs an argument");
2132 seed
= (time_t)atoi(*++argv
);
2134 } else if (*p
== '-')
2135 usage_exit("unrecognised option");
2139 rs
= random_new((void*)&seed
, sizeof(time_t));
2142 if (argc
!= 1) usage_exit("only one argument for --soak");
2143 p
= default_params();
2144 decode_params(p
, *argv
);
2146 } else if (argc
> 0) {
2148 for (i
= 0; i
< argc
; i
++) {
2149 const char *id
= *argv
++;
2150 char *desc
= strchr(id
, ':'), *err
;
2151 p
= default_params();
2154 decode_params(p
, id
);
2155 err
= validate_desc(p
, desc
);
2157 fprintf(stderr
, "%s: %s\n", quis
, err
);
2162 decode_params(p
, id
);
2163 diff
= gen(p
, rs
, 1);
2168 p
= default_params();
2169 p
->order
= random_upto(rs
, 7) + 3;
2170 p
->diff
= random_upto(rs
, 4);
2171 diff
= gen(p
, rs
, 0);
2181 /* vim: set shiftwidth=4 tabstop=8: */