2 * singles.c: implementation of Hitori ('let me alone') from Nikoli.
4 * Make single-get able to fetch a specific puzzle ID from menneske.no?
6 * www.menneske.no solving methods:
9 * SC: if you circle a cell, any cells in same row/col with same no --> black
11 * SB: if you make a cell black, any cells around it --> white
12 * -- solver_op_blacken
13 * ST: 3 identical cells in row, centre is white and outer two black.
14 * SP: 2 identical cells with single-cell gap, middle cell is white.
15 * -- solver_singlesep (both ST and SP)
16 * PI: if you have a pair of same number in row/col, any other
17 * cells of same number must be black.
19 * CC: if you have a black on edge one cell away from corner, cell
20 * on edge diag. adjacent must be white.
21 * CE: if you have 2 black cells of triangle on edge, third cell must
23 * QM: if you have 3 black cells of diagonal square in middle, fourth
25 * -- solve_allblackbutone (CC, CE, and QM).
26 * QC: a corner with 4 identical numbers (or 2 and 2) must have the
27 * corner cell (and cell diagonal to that) black.
28 * TC: a corner with 3 identical numbers (with the L either way)
29 * must have the apex of L black, and other two white.
30 * DC: a corner with 2 identical numbers in domino can set a white
32 * -- solve_corners (QC, TC, DC)
33 * IP: pair with one-offset-pair force whites by offset pair
35 * MC: any cells diag. adjacent to black cells that would split board
36 * into separate white regions must be white.
37 * -- solve_removesplits
41 * TEP: 3 pairs of dominos parallel to side, can mark 4 white cells
43 * DEP: 2 pairs of dominos parallel to side, can mark 2 white cells.
44 * FI: if you have two sets of double-cells packed together, singles
45 * in that row/col must be white (qv. PI)
46 * QuM: four identical cells (or 2 and 2) in middle of grid only have
47 * two possible solutions each.
48 * FDE: doubles one row/column away from edge can force a white cell.
49 * FDM: doubles in centre (next to bits of diag. square) can force a white cell.
50 * MP: two pairs with same number between force number to black.
51 * CnC: if circling a cell leads to impossible board, cell is black.
52 * MC: if we have two possiblilities, can we force a white circle?
66 #ifdef STANDALONE_SOLVER
70 #define PREFERRED_TILE_SIZE 32
71 #define TILE_SIZE (ds->tilesize)
72 #define BORDER (TILE_SIZE / 2)
74 #define CRAD ((TILE_SIZE / 2) - 1)
75 #define TEXTSZ ((14*CRAD/10) - 1) /* 2 * sqrt(2) of CRAD */
77 #define COORD(x) ( (x) * TILE_SIZE + BORDER )
78 #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 )
80 #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h)
82 #define FLASH_TIME 0.7F
85 COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
,
86 COL_BLACK
, COL_WHITE
, COL_BLACKNUM
, COL_GRID
,
87 COL_CURSOR
, COL_ERROR
,
101 int w
, h
, n
, o
; /* n = w*h; o = max(w, h) */
102 int completed
, used_solve
, impossible
;
103 int *nums
; /* size w*h */
104 unsigned int *flags
; /* size w*h */
107 /* top, right, bottom, left */
108 static const int dxs
[4] = { 0, 1, 0, -1 };
109 static const int dys
[4] = { -1, 0, 1, 0 };
111 /* --- Game parameters and preset functions --- */
113 #define DIFFLIST(A) \
117 #define ENUM(upper,title,lower) DIFF_ ## upper,
118 #define TITLE(upper,title,lower) #title,
119 #define ENCODE(upper,title,lower) #lower
120 #define CONFIG(upper,title,lower) ":" #title
122 enum { DIFFLIST(ENUM
) DIFF_MAX
, DIFF_ANY
};
123 static char const *const singles_diffnames
[] = { DIFFLIST(TITLE
) };
124 static char const singles_diffchars
[] = DIFFLIST(ENCODE
);
125 #define DIFFCOUNT lenof(singles_diffchars)
126 #define DIFFCONFIG DIFFLIST(CONFIG)
128 static game_params
*default_params(void)
130 game_params
*ret
= snew(game_params
);
132 ret
->diff
= DIFF_EASY
;
137 static const struct game_params singles_presets
[] = {
139 { 5, 5, DIFF_TRICKY
},
141 { 6, 6, DIFF_TRICKY
},
143 { 8, 8, DIFF_TRICKY
},
144 { 10, 10, DIFF_EASY
},
145 { 10, 10, DIFF_TRICKY
},
146 { 12, 12, DIFF_EASY
},
147 { 12, 12, DIFF_TRICKY
}
150 static int game_fetch_preset(int i
, char **name
, game_params
**params
)
155 if (i
< 0 || i
>= lenof(singles_presets
))
158 ret
= default_params();
159 *ret
= singles_presets
[i
];
162 sprintf(buf
, "%dx%d %s", ret
->w
, ret
->h
, singles_diffnames
[ret
->diff
]);
168 static void free_params(game_params
*params
)
173 static game_params
*dup_params(game_params
*params
)
175 game_params
*ret
= snew(game_params
);
176 *ret
= *params
; /* structure copy */
180 static void decode_params(game_params
*ret
, char const *string
)
182 char const *p
= string
;
185 ret
->w
= ret
->h
= atoi(p
);
186 while (*p
&& isdigit((unsigned char)*p
)) p
++;
190 while (*p
&& isdigit((unsigned char)*p
)) p
++;
193 ret
->diff
= DIFF_MAX
; /* which is invalid */
195 for (i
= 0; i
< DIFFCOUNT
; i
++) {
196 if (*p
== singles_diffchars
[i
])
203 static char *encode_params(game_params
*params
, int full
)
208 sprintf(data
, "%dx%dd%c", params
->w
, params
->h
, singles_diffchars
[params
->diff
]);
210 sprintf(data
, "%dx%d", params
->w
, params
->h
);
215 static config_item
*game_configure(game_params
*params
)
220 ret
= snewn(4, config_item
);
222 ret
[0].name
= "Width";
223 ret
[0].type
= C_STRING
;
224 sprintf(buf
, "%d", params
->w
);
225 ret
[0].sval
= dupstr(buf
);
228 ret
[1].name
= "Height";
229 ret
[1].type
= C_STRING
;
230 sprintf(buf
, "%d", params
->h
);
231 ret
[1].sval
= dupstr(buf
);
234 ret
[2].name
= "Difficulty";
235 ret
[2].type
= C_CHOICES
;
236 ret
[2].sval
= DIFFCONFIG
;
237 ret
[2].ival
= params
->diff
;
247 static game_params
*custom_params(config_item
*cfg
)
249 game_params
*ret
= snew(game_params
);
251 ret
->w
= atoi(cfg
[0].sval
);
252 ret
->h
= atoi(cfg
[1].sval
);
253 ret
->diff
= cfg
[2].ival
;
258 static char *validate_params(game_params
*params
, int full
)
260 if (params
->w
< 2 || params
->h
< 2)
261 return "Width and neight must be at least two";
262 if (params
->w
> 10+26+26 || params
->h
> 10+26+26)
263 return "Puzzle is too large";
265 if (params
->diff
< 0 || params
->diff
>= DIFF_MAX
)
266 return "Unknown difficulty rating";
272 /* --- Game description string generation and unpicking --- */
274 static game_state
*blank_game(int w
, int h
)
276 game_state
*state
= snew(game_state
);
278 memset(state
, 0, sizeof(game_state
));
284 state
->completed
= state
->used_solve
= state
->impossible
= 0;
286 state
->nums
= snewn(state
->n
, int);
287 state
->flags
= snewn(state
->n
, unsigned int);
289 memset(state
->nums
, 0, state
->n
*sizeof(int));
290 memset(state
->flags
, 0, state
->n
*sizeof(unsigned int));
295 static game_state
*dup_game(game_state
*state
)
297 game_state
*ret
= blank_game(state
->w
, state
->h
);
299 ret
->completed
= state
->completed
;
300 ret
->used_solve
= state
->used_solve
;
301 ret
->impossible
= state
->impossible
;
303 memcpy(ret
->nums
, state
->nums
, state
->n
*sizeof(int));
304 memcpy(ret
->flags
, state
->flags
, state
->n
*sizeof(unsigned int));
309 static void free_game(game_state
*state
)
316 static char n2c(int num
) {
319 else if (num
< 10+26)
320 return 'a' + num
- 10;
322 return 'A' + num
- 10 - 26;
326 static int c2n(char c
) {
328 return (int)(c
- '0');
329 else if (c
>= 'a' && c
<= 'z')
330 return (int)(c
- 'a' + 10);
331 else if (c
>= 'A' && c
<= 'Z')
332 return (int)(c
- 'A' + 10 + 26);
336 static void unpick_desc(game_params
*params
, char *desc
,
337 game_state
**sout
, char **mout
)
339 game_state
*state
= blank_game(params
->w
, params
->h
);
343 if (strlen(desc
) != state
->n
) {
344 msg
= "Game description is wrong length";
347 for (i
= 0; i
< state
->n
; i
++) {
349 if (num
<= 0 || num
> state
->o
) {
350 msg
= "Game description contains unexpected characters";
353 state
->nums
[i
] = num
;
356 if (msg
) { /* sth went wrong. */
357 if (mout
) *mout
= msg
;
360 if (mout
) *mout
= NULL
;
361 if (sout
) *sout
= state
;
362 else free_game(state
);
366 static char *generate_desc(game_state
*state
, int issolve
)
368 char *ret
= snewn(state
->n
+1+(issolve?
1:0), char);
373 for (i
= 0; i
< state
->n
; i
++)
374 ret
[p
++] = n2c(state
->nums
[i
]);
379 /* --- Useful game functions (completion, etc.) --- */
381 static int game_can_format_as_text_now(game_params
*params
)
386 static char *game_text_format(game_state
*state
)
391 len
= (state
->w
)*2; /* one row ... */
392 len
= len
* (state
->h
*2); /* ... h rows, including gaps ... */
393 len
+= 1; /* ... final NL */
394 p
= ret
= snewn(len
, char);
396 for (y
= 0; y
< state
->h
; y
++) {
397 for (x
= 0; x
< state
->w
; x
++) {
399 if (x
> 0) *p
++ = ' ';
400 *p
++ = (state
->flags
[i
] & F_BLACK
) ?
'*' : n2c(state
->nums
[i
]);
403 for (x
= 0; x
< state
->w
; x
++) {
405 if (x
> 0) *p
++ = ' ';
406 *p
++ = (state
->flags
[i
] & F_CIRCLE
) ?
'~' : ' ';
411 assert(p
- ret
== len
);
416 static void debug_state(const char *desc
, game_state
*state
) {
417 char *dbg
= game_text_format(state
);
418 debug(("%s:\n%s", desc
, dbg
));
422 static void connect_if_same(game_state
*state
, int *dsf
, int i1
, int i2
)
426 if ((state
->flags
[i1
] & F_BLACK
) != (state
->flags
[i2
] & F_BLACK
))
429 c1
= dsf_canonify(dsf
, i1
);
430 c2
= dsf_canonify(dsf
, i2
);
431 dsf_merge(dsf
, c1
, c2
);
434 static void connect_dsf(game_state
*state
, int *dsf
)
438 /* Construct a dsf array for connected blocks; connections
439 * tracked to right and down. */
440 dsf_init(dsf
, state
->n
);
441 for (x
= 0; x
< state
->w
; x
++) {
442 for (y
= 0; y
< state
->h
; y
++) {
446 connect_if_same(state
, dsf
, i
, i
+1); /* right */
448 connect_if_same(state
, dsf
, i
, i
+state
->w
); /* down */
453 static int check_rowcol(game_state
*state
, int starti
, int di
, int sz
, int mark_errors
)
455 int nerr
= 0, n
, m
, i
, j
;
457 /* if any circled numbers have identical non-circled numbers on
458 * same row/column, error (non-circled)
459 * if any circled numbers in same column are same number, highlight them.
460 * if any rows/columns have >1 of same number, not complete. */
462 for (n
= 0, i
= starti
; n
< sz
; n
++, i
+= di
) {
463 if (state
->flags
[i
] & F_BLACK
) continue;
464 for (m
= n
+1, j
= i
+di
; m
< sz
; m
++, j
+= di
) {
465 if (state
->flags
[j
] & F_BLACK
) continue;
466 if (state
->nums
[i
] != state
->nums
[j
]) continue;
468 nerr
++; /* ok, we have two numbers the same in a row. */
469 if (!mark_errors
) continue;
471 /* If we have two circles in the same row around
472 * two identical numbers, they are _both_ wrong. */
473 if ((state
->flags
[i
] & F_CIRCLE
) &&
474 (state
->flags
[j
] & F_CIRCLE
)) {
475 state
->flags
[i
] |= F_ERROR
;
476 state
->flags
[j
] |= F_ERROR
;
478 /* Otherwise, if we have a circle, any other identical
479 * numbers in that row are obviously wrong. We don't
480 * highlight this, however, since it makes the process
481 * of solving the puzzle too easy (you circle a number
482 * and it promptly tells you which numbers to blacken! */
484 else if (state
->flags
[i
] & F_CIRCLE
)
485 state
->flags
[j
] |= F_ERROR
;
486 else if (state
->flags
[j
] & F_CIRCLE
)
487 state
->flags
[i
] |= F_ERROR
;
494 static int check_complete(game_state
*state
, int mark_errors
)
496 int *dsf
= snewn(state
->n
, int);
497 int x
, y
, i
, error
= 0, nwhite
, w
= state
->w
, h
= state
->h
;
500 for (i
= 0; i
< state
->n
; i
++)
501 state
->flags
[i
] &= ~F_ERROR
;
503 connect_dsf(state
, dsf
);
505 /* Mark any black squares in groups of >1 as errors.
506 * Count number of white squares. */
508 for (i
= 0; i
< state
->n
; i
++) {
509 if (state
->flags
[i
] & F_BLACK
) {
510 if (dsf_size(dsf
, i
) > 1) {
513 state
->flags
[i
] |= F_ERROR
;
519 /* Check attributes of white squares, row- and column-wise. */
520 for (x
= 0; x
< w
; x
++) /* check cols from (x,0) */
521 error
+= check_rowcol(state
, x
, w
, h
, mark_errors
);
522 for (y
= 0; y
< h
; y
++) /* check rows from (0,y) */
523 error
+= check_rowcol(state
, y
*w
, 1, w
, mark_errors
);
525 /* mark (all) white regions as an error if there is more than one.
526 * may want to make this less in-your-face (by only marking
527 * the smallest region as an error, for example -- but what if we
528 * have two regions of identical size?) */
529 for (i
= 0; i
< state
->n
; i
++) {
530 if (!(state
->flags
[i
] & F_BLACK
) &&
531 dsf_size(dsf
, i
) < nwhite
) {
534 state
->flags
[i
] |= F_ERROR
;
539 return (error
> 0) ?
0 : 1;
542 static char *game_state_diff(game_state
*src
, game_state
*dst
, int issolve
)
544 char *ret
= NULL
, buf
[80], c
;
545 int retlen
= 0, x
, y
, i
, k
;
546 unsigned int fmask
= F_BLACK
| F_CIRCLE
;
548 assert(src
->n
== dst
->n
);
551 ret
= sresize(ret
, 3, char);
552 ret
[0] = 'S'; ret
[1] = ';'; ret
[2] = '\0';
556 for (x
= 0; x
< dst
->w
; x
++) {
557 for (y
= 0; y
< dst
->h
; y
++) {
559 if ((src
->flags
[i
] & fmask
) != (dst
->flags
[i
] & fmask
)) {
560 assert((dst
->flags
[i
] & fmask
) != fmask
);
561 if (dst
->flags
[i
] & F_BLACK
)
563 else if (dst
->flags
[i
] & F_CIRCLE
)
567 k
= sprintf(buf
, "%c%d,%d;", (int)c
, x
, y
);
568 ret
= sresize(ret
, retlen
+ k
+ 1, char);
569 strcpy(ret
+ retlen
, buf
);
579 enum { BLACK
, CIRCLE
};
582 int x
, y
, op
; /* op one of BLACK or CIRCLE. */
583 const char *desc
; /* must be non-malloced. */
586 struct solver_state
{
587 struct solver_op
*ops
;
592 static struct solver_state
*solver_state_new(game_state
*state
)
594 struct solver_state
*ss
= snew(struct solver_state
);
597 ss
->n_ops
= ss
->n_alloc
= 0;
598 ss
->scratch
= snewn(state
->n
, int);
603 static void solver_state_free(struct solver_state
*ss
)
606 if (ss
->ops
) sfree(ss
->ops
);
610 static void solver_op_add(struct solver_state
*ss
, int x
, int y
, int op
, const char *desc
)
612 struct solver_op
*sop
;
614 if (ss
->n_alloc
< ss
->n_ops
+ 1) {
615 ss
->n_alloc
= (ss
->n_alloc
+ 1) * 2;
616 ss
->ops
= sresize(ss
->ops
, ss
->n_alloc
, struct solver_op
);
618 sop
= &(ss
->ops
[ss
->n_ops
++]);
619 sop
->x
= x
; sop
->y
= y
; sop
->op
= op
; sop
->desc
= desc
;
620 debug(("added solver op %s ('%s') at (%d,%d)",
621 op
== BLACK ?
"BLACK" : "CIRCLE", desc
, x
, y
));
624 static void solver_op_circle(game_state
*state
, struct solver_state
*ss
,
627 int i
= y
*state
->w
+ x
;
629 if (!INGRID(state
, x
, y
)) return;
630 if (state
->flags
[i
] & F_BLACK
) {
631 debug(("... solver wants to add auto-circle on black (%d,%d)", x
, y
));
632 state
->impossible
= 1;
635 /* Only add circle op if it's not already circled. */
636 if (!(state
->flags
[i
] & F_CIRCLE
)) {
637 solver_op_add(ss
, x
, y
, CIRCLE
, "SB - adjacent to black square");
641 static void solver_op_blacken(game_state
*state
, struct solver_state
*ss
,
642 int x
, int y
, int num
)
644 int i
= y
*state
->w
+ x
;
646 if (!INGRID(state
, x
, y
)) return;
647 if (state
->nums
[i
] != num
) return;
648 if (state
->flags
[i
] & F_CIRCLE
) {
649 debug(("... solver wants to add auto-black on circled(%d,%d)", x
, y
));
650 state
->impossible
= 1;
653 /* Only add black op if it's not already black. */
654 if (!(state
->flags
[i
] & F_BLACK
)) {
655 solver_op_add(ss
, x
, y
, BLACK
, "SC - number on same row/col as circled");
659 static int solver_ops_do(game_state
*state
, struct solver_state
*ss
)
661 int next_op
= 0, i
, x
, y
, n_ops
= 0;
664 /* Care here: solver_op_* may call solver_op_add which may extend the
667 while (next_op
< ss
->n_ops
) {
668 op
= ss
->ops
[next_op
++]; /* copy this away, it may get reallocated. */
669 i
= op
.y
*state
->w
+ op
.x
;
671 if (op
.op
== BLACK
) {
672 if (state
->flags
[i
] & F_CIRCLE
) {
673 debug(("Solver wants to blacken circled square (%d,%d)!", op
.x
, op
.y
));
674 state
->impossible
= 1;
677 if (!(state
->flags
[i
] & F_BLACK
)) {
678 debug(("... solver adding black at (%d,%d): %s", op
.x
, op
.y
, op
.desc
));
679 #ifdef STANDALONE_SOLVER
681 printf("Adding black at (%d,%d): %s\n", op
.x
, op
.y
, op
.desc
);
683 state
->flags
[i
] |= F_BLACK
;
684 /*debug_state("State after adding black", state);*/
686 solver_op_circle(state
, ss
, op
.x
-1, op
.y
);
687 solver_op_circle(state
, ss
, op
.x
+1, op
.y
);
688 solver_op_circle(state
, ss
, op
.x
, op
.y
-1);
689 solver_op_circle(state
, ss
, op
.x
, op
.y
+1);
692 if (state
->flags
[i
] & F_BLACK
) {
693 debug(("Solver wants to circle blackened square (%d,%d)!", op
.x
, op
.y
));
694 state
->impossible
= 1;
697 if (!(state
->flags
[i
] & F_CIRCLE
)) {
698 debug(("... solver adding circle at (%d,%d): %s", op
.x
, op
.y
, op
.desc
));
699 #ifdef STANDALONE_SOLVER
701 printf("Adding circle at (%d,%d): %s\n", op
.x
, op
.y
, op
.desc
);
703 state
->flags
[i
] |= F_CIRCLE
;
704 /*debug_state("State after adding circle", state);*/
706 for (x
= 0; x
< state
->w
; x
++) {
708 solver_op_blacken(state
, ss
, x
, op
.y
, state
->nums
[i
]);
710 for (y
= 0; y
< state
->h
; y
++) {
712 solver_op_blacken(state
, ss
, op
.x
, y
, state
->nums
[i
]);
721 /* If the grid has two identical numbers with one cell between them, the inner
722 * cell _must_ be white (and thus circled); (at least) one of the two must be
723 * black (since they're in the same column or row) and thus the middle cell is
724 * next to a black cell. */
725 static int solve_singlesep(game_state
*state
, struct solver_state
*ss
)
727 int x
, y
, i
, ir
, irr
, id
, idd
, n_ops
= ss
->n_ops
;
729 for (x
= 0; x
< state
->w
; x
++) {
730 for (y
= 0; y
< state
->h
; y
++) {
733 /* Cell two to our right? */
734 ir
= i
+ 1; irr
= ir
+ 1;
735 if (x
< (state
->w
-2) &&
736 state
->nums
[i
] == state
->nums
[irr
] &&
737 !(state
->flags
[ir
] & F_CIRCLE
)) {
738 solver_op_add(ss
, x
+1, y
, CIRCLE
, "SP/ST - between identical nums");
740 /* Cell two below us? */
741 id
= i
+ state
->w
; idd
= id
+ state
->w
;
742 if (y
< (state
->h
-2) &&
743 state
->nums
[i
] == state
->nums
[idd
] &&
744 !(state
->flags
[id
] & F_CIRCLE
)) {
745 solver_op_add(ss
, x
, y
+1, CIRCLE
, "SP/ST - between identical nums");
749 return ss
->n_ops
- n_ops
;
752 /* If we have two identical numbers next to each other (in a row or column),
753 * any other identical numbers in that column must be black. */
754 static int solve_doubles(game_state
*state
, struct solver_state
*ss
)
756 int x
, y
, i
, ii
, n_ops
= ss
->n_ops
, xy
;
758 for (y
= 0, i
= 0; y
< state
->h
; y
++) {
759 for (x
= 0; x
< state
->w
; x
++, i
++) {
760 assert(i
== y
*state
->w
+x
);
761 if (state
->flags
[i
] & F_BLACK
) continue;
763 ii
= i
+1; /* check cell to our right. */
764 if (x
< (state
->w
-1) &&
765 !(state
->flags
[ii
] & F_BLACK
) &&
766 state
->nums
[i
] == state
->nums
[ii
]) {
767 for (xy
= 0; xy
< state
->w
; xy
++) {
768 if (xy
== x
|| xy
== (x
+1)) continue;
769 if (state
->nums
[y
*state
->w
+ xy
] == state
->nums
[i
] &&
770 !(state
->flags
[y
*state
->w
+ xy
] & F_BLACK
))
771 solver_op_add(ss
, xy
, y
, BLACK
, "PI - same row as pair");
775 ii
= i
+state
->w
; /* check cell below us */
776 if (y
< (state
->h
-1) &&
777 !(state
->flags
[ii
] & F_BLACK
) &&
778 state
->nums
[i
] == state
->nums
[ii
]) {
779 for (xy
= 0; xy
< state
->h
; xy
++) {
780 if (xy
== y
|| xy
== (y
+1)) continue;
781 if (state
->nums
[xy
*state
->w
+ x
] == state
->nums
[i
] &&
782 !(state
->flags
[xy
*state
->w
+ x
] & F_BLACK
))
783 solver_op_add(ss
, x
, xy
, BLACK
, "PI - same col as pair");
788 return ss
->n_ops
- n_ops
;
791 /* If a white square has all-but-one possible adjacent squares black, the
792 * one square left over must be white. */
793 static int solve_allblackbutone(game_state
*state
, struct solver_state
*ss
)
795 int x
, y
, i
, n_ops
= ss
->n_ops
, xd
, yd
, id
, ifree
;
803 for (y
= 0, i
= 0; y
< state
->h
; y
++) {
804 for (x
= 0; x
< state
->w
; x
++, i
++) {
805 assert(i
== y
*state
->w
+x
);
806 if (state
->flags
[i
] & F_BLACK
) continue;
809 for (d
= 0; d
< 4; d
++) {
810 xd
= x
+ dxs
[d
]; yd
= y
+ dys
[d
]; id
= i
+ dis
[d
];
811 if (!INGRID(state
, xd
, yd
)) continue;
813 if (state
->flags
[id
] & F_CIRCLE
)
814 goto skip
; /* this cell already has a way out */
815 if (!(state
->flags
[id
] & F_BLACK
)) {
817 goto skip
; /* this cell has >1 white cell around it. */
822 solver_op_add(ss
, ifree
%state
->w
, ifree
/state
->w
, CIRCLE
,
823 "CC/CE/QM: white cell with single non-black around it");
825 debug(("White cell with no escape at (%d,%d)", x
, y
));
826 state
->impossible
= 1;
832 return ss
->n_ops
- n_ops
;
835 /* If we have 4 numbers the same in a 2x2 corner, the far corner and the
836 * diagonally-adjacent square must both be black.
837 * If we have 3 numbers the same in a 2x2 corner, the apex of the L
838 * thus formed must be black.
839 * If we have 2 numbers the same in a 2x2 corner, the non-same cell
840 * one away from the corner must be white. */
841 static void solve_corner(game_state
*state
, struct solver_state
*ss
,
842 int x
, int y
, int dx
, int dy
)
844 int is
[4], ns
[4], xx
, yy
, w
= state
->w
;
846 for (yy
= 0; yy
< 2; yy
++) {
847 for (xx
= 0; xx
< 2; xx
++) {
848 is
[yy
*2+xx
] = (y
+ dy
*yy
) * w
+ (x
+ dx
*xx
);
849 ns
[yy
*2+xx
] = state
->nums
[is
[yy
*2+xx
]];
851 } /* order is now (corner, side 1, side 2, inner) */
853 if (ns
[0] == ns
[1] && ns
[0] == ns
[2] && ns
[0] == ns
[3]) {
854 solver_op_add(ss
, is
[0]%w
, is
[0]/w
, BLACK
, "QC: corner with 4 matching");
855 solver_op_add(ss
, is
[3]%w
, is
[3]/w
, BLACK
, "QC: corner with 4 matching");
856 } else if (ns
[0] == ns
[1] && ns
[0] == ns
[2]) {
857 /* corner and 2 sides: apex is corner. */
858 solver_op_add(ss
, is
[0]%w
, is
[0]/w
, BLACK
, "TC: corner apex from 3 matching");
859 } else if (ns
[1] == ns
[2] && ns
[1] == ns
[3]) {
860 /* side, side, fourth: apex is fourth. */
861 solver_op_add(ss
, is
[3]%w
, is
[3]/w
, BLACK
, "TC: inside apex from 3 matching");
862 } else if (ns
[0] == ns
[1] || ns
[1] == ns
[3]) {
863 /* either way here we match the non-identical side. */
864 solver_op_add(ss
, is
[2]%w
, is
[2]/w
, CIRCLE
, "DC: corner with 2 matching");
865 } else if (ns
[0] == ns
[2] || ns
[2] == ns
[3]) {
867 solver_op_add(ss
, is
[1]%w
, is
[1]/w
, CIRCLE
, "DC: corner with 2 matching");
871 static int solve_corners(game_state
*state
, struct solver_state
*ss
)
873 int n_ops
= ss
->n_ops
;
875 solve_corner(state
, ss
, 0, 0, 1, 1);
876 solve_corner(state
, ss
, state
->w
-1, 0, -1, 1);
877 solve_corner(state
, ss
, state
->w
-1, state
->h
-1, -1, -1);
878 solve_corner(state
, ss
, 0, state
->h
-1, 1, -1);
880 return ss
->n_ops
- n_ops
;
883 /* If you have the following situation:
885 * ...x A x x y A x...
886 * ...x B x x B y x...
888 * then both squares marked 'y' must be white. One of the left-most A or B must
889 * be white (since two side-by-side black cells are disallowed), which means
890 * that the corresponding right-most A or B must be black (since you can't
891 * have two of the same number on one line); thus, the adjacent squares
892 * to that right-most A or B must be white, which include the two marked 'y'
894 * Obviously this works in any row or column. It also works if A == B.
895 * It doesn't work for the degenerate case:
898 * where the square marked 'y' isn't necessarily white (consider the left-most A
902 static void solve_offsetpair_pair(game_state
*state
, struct solver_state
*ss
,
903 int x1
, int y1
, int x2
, int y2
)
905 int ox
, oy
, w
= state
->w
, ax
, ay
, an
, d
, dx
[2], dy
[2], dn
, xd
, yd
;
907 if (x1
== x2
) { /* same column */
914 /* We try adjacent to (x1,y1) and the two diag. adjacent to (x2, y2).
915 * We expect to be called twice, once each way around. */
916 ax
= x1
+ox
; ay
= y1
+oy
;
917 assert(INGRID(state
, ax
, ay
));
918 an
= state
->nums
[ay
*w
+ ax
];
920 dx
[0] = x2
+ ox
+ oy
; dx
[1] = x2
+ ox
- oy
;
921 dy
[0] = y2
+ oy
+ ox
; dy
[1] = y2
+ oy
- ox
;
923 for (d
= 0; d
< 2; d
++) {
924 if (INGRID(state
, dx
[d
], dy
[d
]) && (dx
[d
] != ax
|| dy
[d
] != ay
)) {
925 /* The 'dx != ax || dy != ay' removes the degenerate case,
926 * mentioned above. */
927 dn
= state
->nums
[dy
[d
]*w
+ dx
[d
]];
929 /* We have a match; so (WLOG) the 'A' marked above are at
930 * (x1,y1) and (x2,y2), and the 'B' are at (ax,ay) and (dx,dy). */
931 debug(("Found offset-pair: %d at (%d,%d) and (%d,%d)",
932 state
->nums
[y1
*w
+ x1
], x1
, y1
, x2
, y2
));
933 debug((" and: %d at (%d,%d) and (%d,%d)",
934 an
, ax
, ay
, dx
[d
], dy
[d
]));
936 xd
= dx
[d
] - x2
; yd
= dy
[d
] - y2
;
937 solver_op_add(ss
, x2
+ xd
, y2
, CIRCLE
, "IP: next to offset-pair");
938 solver_op_add(ss
, x2
, y2
+ yd
, CIRCLE
, "IP: next to offset-pair");
944 static int solve_offsetpair(game_state
*state
, struct solver_state
*ss
)
946 int n_ops
= ss
->n_ops
, x
, xx
, y
, yy
, n1
, n2
;
948 for (x
= 0; x
< state
->w
-1; x
++) {
949 for (y
= 0; y
< state
->h
; y
++) {
950 n1
= state
->nums
[y
*state
->w
+ x
];
951 for (yy
= y
+1; yy
< state
->h
; yy
++) {
952 n2
= state
->nums
[yy
*state
->w
+ x
];
954 solve_offsetpair_pair(state
, ss
, x
, y
, x
, yy
);
955 solve_offsetpair_pair(state
, ss
, x
, yy
, x
, y
);
960 for (y
= 0; y
< state
->h
-1; y
++) {
961 for (x
= 0; x
< state
->w
; x
++) {
962 n1
= state
->nums
[y
*state
->w
+ x
];
963 for (xx
= x
+1; xx
< state
->w
; xx
++) {
964 n2
= state
->nums
[y
*state
->w
+ xx
];
966 solve_offsetpair_pair(state
, ss
, x
, y
, xx
, y
);
967 solve_offsetpair_pair(state
, ss
, xx
, y
, x
, y
);
972 return ss
->n_ops
- n_ops
;
975 static int solve_hassinglewhiteregion(game_state
*state
, struct solver_state
*ss
)
977 int i
, j
, nwhite
= 0, lwhite
= -1, szwhite
, start
, end
, next
, a
, d
, x
, y
;
979 for (i
= 0; i
< state
->n
; i
++) {
980 if (!(state
->flags
[i
] & F_BLACK
)) {
984 state
->flags
[i
] &= ~F_SCRATCH
;
987 debug(("solve_hassinglewhite: no white squares found!"));
988 state
->impossible
= 1;
991 /* We don't use connect_dsf here; it's too slow, and there's a quicker
992 * algorithm if all we want is the size of one region. */
993 /* Having written this, this algorithm is only about 5% faster than
995 memset(ss
->scratch
, -1, state
->n
* sizeof(int));
996 ss
->scratch
[0] = lwhite
;
997 state
->flags
[lwhite
] |= F_SCRATCH
;
998 start
= 0; end
= next
= 1;
999 while (start
< end
) {
1000 for (a
= start
; a
< end
; a
++) {
1001 i
= ss
->scratch
[a
]; assert(i
!= -1);
1002 for (d
= 0; d
< 4; d
++) {
1003 x
= (i
% state
->w
) + dxs
[d
];
1004 y
= (i
/ state
->w
) + dys
[d
];
1006 if (!INGRID(state
, x
, y
)) continue;
1007 if (state
->flags
[j
] & (F_BLACK
| F_SCRATCH
)) continue;
1008 ss
->scratch
[next
++] = j
;
1009 state
->flags
[j
] |= F_SCRATCH
;
1012 start
= end
; end
= next
;
1015 return (szwhite
== nwhite
) ?
1 : 0;
1018 static void solve_removesplits_check(game_state
*state
, struct solver_state
*ss
,
1021 int i
= y
*state
->w
+ x
, issingle
;
1023 if (!INGRID(state
, x
, y
)) return;
1024 if ((state
->flags
[i
] & F_CIRCLE
) || (state
->flags
[i
] & F_BLACK
))
1027 /* If putting a black square at (x,y) would make the white region
1028 * non-contiguous, it must be circled. */
1029 state
->flags
[i
] |= F_BLACK
;
1030 issingle
= solve_hassinglewhiteregion(state
, ss
);
1031 state
->flags
[i
] &= ~F_BLACK
;
1034 solver_op_add(ss
, x
, y
, CIRCLE
, "MC: black square here would split white region");
1037 /* For all black squares, search in squares diagonally adjacent to see if
1038 * we can rule out putting a black square there (because it would make the
1039 * white region non-contiguous). */
1040 /* This function is likely to be somewhat slow. */
1041 static int solve_removesplits(game_state
*state
, struct solver_state
*ss
)
1043 int i
, x
, y
, n_ops
= ss
->n_ops
;
1045 if (!solve_hassinglewhiteregion(state
, ss
)) {
1046 debug(("solve_removesplits: white region is not contiguous at start!"));
1047 state
->impossible
= 1;
1051 for (i
= 0; i
< state
->n
; i
++) {
1052 if (!(state
->flags
[i
] & F_BLACK
)) continue;
1054 x
= i
%state
->w
; y
= i
/state
->w
;
1055 solve_removesplits_check(state
, ss
, x
-1, y
-1);
1056 solve_removesplits_check(state
, ss
, x
+1, y
-1);
1057 solve_removesplits_check(state
, ss
, x
+1, y
+1);
1058 solve_removesplits_check(state
, ss
, x
-1, y
+1);
1060 return ss
->n_ops
- n_ops
;
1064 * This function performs a solver step that isn't implicit in the rules
1065 * of the game and is thus treated somewhat differently.
1067 * It marks cells whose number does not exist elsewhere in its row/column
1068 * with circles. As it happens the game generator here does mean that this
1069 * is always correct, but it's a solving method that people should not have
1070 * to rely upon (except in the hidden 'sneaky' difficulty setting) and so
1071 * all grids at 'tricky' and above are checked to make sure that the grid
1072 * is no easier if this solving step is performed beforehand.
1074 * Calling with ss=NULL just returns the number of sneaky deductions that
1075 * would have been made.
1077 static int solve_sneaky(game_state
*state
, struct solver_state
*ss
)
1079 int i
, ii
, x
, xx
, y
, yy
, nunique
= 0;
1081 /* Clear SCRATCH flags. */
1082 for (i
= 0; i
< state
->n
; i
++) state
->flags
[i
] &= ~F_SCRATCH
;
1084 for (x
= 0; x
< state
->w
; x
++) {
1085 for (y
= 0; y
< state
->h
; y
++) {
1088 /* Check for duplicate numbers on our row, mark (both) if so */
1089 for (xx
= x
; xx
< state
->w
; xx
++) {
1090 ii
= y
*state
->w
+ xx
;
1091 if (i
== ii
) continue;
1093 if (state
->nums
[i
] == state
->nums
[ii
]) {
1094 state
->flags
[i
] |= F_SCRATCH
;
1095 state
->flags
[ii
] |= F_SCRATCH
;
1099 /* Check for duplicate numbers on our col, mark (both) if so */
1100 for (yy
= y
; yy
< state
->h
; yy
++) {
1101 ii
= yy
*state
->w
+ x
;
1102 if (i
== ii
) continue;
1104 if (state
->nums
[i
] == state
->nums
[ii
]) {
1105 state
->flags
[i
] |= F_SCRATCH
;
1106 state
->flags
[ii
] |= F_SCRATCH
;
1112 /* Any cell with no marking has no duplicates on its row or column:
1113 * set its CIRCLE. */
1114 for (i
= 0; i
< state
->n
; i
++) {
1115 if (!(state
->flags
[i
] & F_SCRATCH
)) {
1116 if (ss
) solver_op_add(ss
, i
%state
->w
, i
/state
->w
, CIRCLE
,
1117 "SNEAKY: only one of its number in row and col");
1120 state
->flags
[i
] &= ~F_SCRATCH
;
1125 static int solve_specific(game_state
*state
, int diff
, int sneaky
)
1127 struct solver_state
*ss
= solver_state_new(state
);
1129 if (sneaky
) solve_sneaky(state
, ss
);
1131 /* Some solver operations we only have to perform once --
1132 * they're only based on the numbers available, and not black
1133 * squares or circles which may be added later. */
1135 solve_singlesep(state
, ss
); /* never sets impossible */
1136 solve_doubles(state
, ss
); /* ditto */
1137 solve_corners(state
, ss
); /* ditto */
1139 if (diff
>= DIFF_TRICKY
)
1140 solve_offsetpair(state
, ss
); /* ditto */
1143 if (ss
->n_ops
> 0) solver_ops_do(state
, ss
);
1144 if (state
->impossible
) break;
1146 if (solve_allblackbutone(state
, ss
) > 0) continue;
1147 if (state
->impossible
) break;
1149 if (diff
>= DIFF_TRICKY
) {
1150 if (solve_removesplits(state
, ss
) > 0) continue;
1151 if (state
->impossible
) break;
1157 solver_state_free(ss
);
1158 return state
->impossible ?
-1 : check_complete(state
, 0);
1161 static char *solve_game(game_state
*state
, game_state
*currstate
,
1162 char *aux
, char **error
)
1164 game_state
*solved
= dup_game(currstate
);
1167 if (solve_specific(solved
, DIFF_ANY
, 0) > 0) goto solved
;
1170 solved
= dup_game(state
);
1171 if (solve_specific(solved
, DIFF_ANY
, 0) > 0) goto solved
;
1174 *error
= "Unable to solve puzzle.";
1178 move
= game_state_diff(currstate
, solved
, 1);
1183 /* --- Game generation --- */
1185 /* A correctly completed Hitori board is essentially a latin square
1186 * (no duplicated numbers in any row or column) with black squares
1187 * added such that no black square touches another, and the white
1188 * squares make a contiguous region.
1190 * So we can generate it by:
1191 * constructing a latin square
1192 * adding black squares at random (minding the constraints)
1193 * altering the numbers under the new black squares such that
1194 the solver gets a headstart working out where they are.
1197 static int new_game_is_good(game_params
*params
,
1198 game_state
*state
, game_state
*tosolve
)
1200 int sret
, sret_easy
= 0;
1202 memcpy(tosolve
->nums
, state
->nums
, state
->n
* sizeof(int));
1203 memset(tosolve
->flags
, 0, state
->n
* sizeof(unsigned int));
1204 tosolve
->completed
= tosolve
->impossible
= 0;
1207 * We try and solve it twice, once at our requested difficulty level
1208 * (ensuring it's soluble at all) and once at the level below (if
1209 * it exists), which we hope to fail: if you can also solve it at
1210 * the level below then it's too easy and we have to try again.
1212 * With this puzzle in particular there's an extra finesse, which is
1213 * that we check that the generated puzzle isn't too easy _with
1214 * an extra solver step first_, which is the 'sneaky' mode of deductions
1215 * (asserting that any number which fulfils the latin-square rules
1216 * on its row/column must be white). This is an artefact of the
1217 * generation process and not implicit in the rules, so we don't want
1218 * people to be able to use it to make the puzzle easier.
1221 assert(params
->diff
< DIFF_MAX
);
1222 sret
= solve_specific(tosolve
, params
->diff
, 0);
1223 if (params
->diff
> DIFF_EASY
) {
1224 memset(tosolve
->flags
, 0, state
->n
* sizeof(unsigned int));
1225 tosolve
->completed
= tosolve
->impossible
= 0;
1227 /* this is the only time the 'sneaky' flag is set to 1. */
1228 sret_easy
= solve_specific(tosolve
, params
->diff
-1, 1);
1231 if (sret
<= 0 || sret_easy
> 0) {
1232 debug(("Generated puzzle %s at chosen difficulty %s",
1233 sret
<= 0 ?
"insoluble" : "too easy",
1234 singles_diffnames
[params
->diff
]));
1242 static int best_black_col(game_state
*state
, random_state
*rs
, int *scratch
,
1243 int i
, int *rownums
, int *colnums
)
1245 int w
= state
->w
, x
= i
%w
, y
= i
/w
, j
, o
= state
->o
;
1247 /* Randomise the list of numbers to try. */
1248 for (i
= 0; i
< o
; i
++) scratch
[i
] = i
;
1249 shuffle(scratch
, o
, sizeof(int), rs
);
1251 /* Try each number in turn, first giving preference to removing
1252 * latin-square characteristics (i.e. those numbers which only
1253 * occur once in a row/column). The '&&' here, although intuitively
1254 * wrong, results in a smaller number of 'sneaky' deductions on
1255 * solvable boards. */
1256 for (i
= 0; i
< o
; i
++) {
1258 if (rownums
[y
*o
+ j
-1] == 1 && colnums
[x
*o
+ j
-1] == 1)
1262 /* Then try each number in turn returning the first one that's
1263 * not actually unique in its row/column (see comment below) */
1264 for (i
= 0; i
< o
; i
++) {
1266 if (rownums
[y
*o
+ j
-1] != 0 || colnums
[x
*o
+ j
-1] != 0)
1269 assert(!"unable to place number under black cell.");
1273 /* Update column and row counts assuming this number will be placed. */
1274 rownums
[y
*o
+ j
-1] += 1;
1275 colnums
[x
*o
+ j
-1] += 1;
1279 static char *new_game_desc(game_params
*params
, random_state
*rs
,
1280 char **aux
, int interactive
)
1282 game_state
*state
= blank_game(params
->w
, params
->h
);
1283 game_state
*tosolve
= blank_game(params
->w
, params
->h
);
1284 int i
, j
, *scratch
, *rownums
, *colnums
, x
, y
, ntries
;
1285 int w
= state
->w
, h
= state
->h
, o
= state
->o
;
1288 struct solver_state
*ss
= solver_state_new(state
);
1290 scratch
= snewn(state
->n
, int);
1291 rownums
= snewn(h
*o
, int);
1292 colnums
= snewn(w
*o
, int);
1296 debug(("Starting game generation, size %dx%d", w
, h
));
1298 memset(state
->flags
, 0, state
->n
*sizeof(unsigned int));
1300 /* First, generate the latin rectangle.
1301 * The order of this, o, is max(w,h). */
1302 latin
= latin_generate_rect(w
, h
, rs
);
1303 for (i
= 0; i
< state
->n
; i
++)
1304 state
->nums
[i
] = (int)latin
[i
];
1306 debug_state("State after latin square", state
);
1308 /* Add black squares at random, using bits of solver as we go (to lay
1309 * white squares), until we can lay no more blacks. */
1310 for (i
= 0; i
< state
->n
; i
++)
1312 shuffle(scratch
, state
->n
, sizeof(int), rs
);
1313 for (j
= 0; j
< state
->n
; j
++) {
1315 if ((state
->flags
[i
] & F_CIRCLE
) || (state
->flags
[i
] & F_BLACK
)) {
1316 debug(("generator skipping (%d,%d): %s", i
%w
, i
/w
,
1317 (state
->flags
[i
] & F_CIRCLE
) ?
"CIRCLE" : "BLACK"));
1318 continue; /* solver knows this must be one or the other already. */
1321 /* Add a random black cell... */
1322 solver_op_add(ss
, i
%w
, i
/w
, BLACK
, "Generator: adding random black cell");
1323 solver_ops_do(state
, ss
);
1325 /* ... and do as well as we know how to lay down whites that are now forced. */
1326 solve_allblackbutone(state
, ss
);
1327 solver_ops_do(state
, ss
);
1329 solve_removesplits(state
, ss
);
1330 solver_ops_do(state
, ss
);
1332 if (state
->impossible
) {
1333 debug(("generator made impossible, restarting..."));
1337 debug_state("State after adding blacks", state
);
1339 /* Now we know which squares are white and which are black, we lay numbers
1340 * under black squares at random, except that the number must appear in
1341 * white cells at least once more in the same column or row as that [black]
1342 * square. That's necessary to avoid multiple solutions, where blackening
1343 * squares in the finished puzzle becomes optional. We use two arrays:
1345 * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW
1346 * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL
1349 memset(rownums
, 0, h
*o
* sizeof(int));
1350 memset(colnums
, 0, w
*o
* sizeof(int));
1351 for (i
= 0; i
< state
->n
; i
++) {
1352 if (state
->flags
[i
] & F_BLACK
) continue;
1355 rownums
[y
* o
+ j
-1] += 1;
1356 colnums
[x
* o
+ j
-1] += 1;
1361 for (i
= 0; i
< state
->n
; i
++) {
1362 if (!(state
->flags
[i
] & F_BLACK
)) continue;
1363 state
->nums
[i
] = best_black_col(state
, rs
, scratch
, i
, rownums
, colnums
);
1365 debug_state("State after adding numbers", state
);
1367 /* DIFF_ANY just returns whatever we first generated, for testing purposes. */
1368 if (params
->diff
!= DIFF_ANY
&&
1369 !new_game_is_good(params
, state
, tosolve
)) {
1371 if (ntries
> MAXTRIES
) {
1372 debug(("Ran out of randomisation attempts, re-generating."));
1375 debug(("Re-randomising numbers under black squares."));
1379 ret
= generate_desc(state
, 0);
1383 solver_state_free(ss
);
1391 static char *validate_desc(game_params
*params
, char *desc
)
1395 unpick_desc(params
, desc
, NULL
, &ret
);
1399 static game_state
*new_game(midend
*me
, game_params
*params
, char *desc
)
1401 game_state
*state
= NULL
;
1403 unpick_desc(params
, desc
, &state
, NULL
);
1404 if (!state
) assert(!"new_game failed to unpick");
1408 /* --- Game UI and move routines --- */
1412 int show_black_nums
;
1415 static game_ui
*new_ui(game_state
*state
)
1417 game_ui
*ui
= snew(game_ui
);
1419 ui
->cx
= ui
->cy
= ui
->cshow
= 0;
1420 ui
->show_black_nums
= 0;
1425 static void free_ui(game_ui
*ui
)
1430 static char *encode_ui(game_ui
*ui
)
1435 static void decode_ui(game_ui
*ui
, char *encoding
)
1439 static void game_changed_state(game_ui
*ui
, game_state
*oldstate
,
1440 game_state
*newstate
)
1442 if (!oldstate
->completed
&& newstate
->completed
)
1446 #define DS_BLACK 0x1
1447 #define DS_CIRCLE 0x2
1448 #define DS_CURSOR 0x4
1449 #define DS_BLACK_NUM 0x8
1450 #define DS_ERROR 0x10
1451 #define DS_FLASH 0x20
1452 #define DS_IMPOSSIBLE 0x40
1454 struct game_drawstate
{
1455 int tilesize
, started
, solved
;
1458 unsigned int *flags
;
1461 static char *interpret_move(game_state
*state
, game_ui
*ui
, game_drawstate
*ds
,
1462 int mx
, int my
, int button
)
1465 int i
, x
= FROMCOORD(mx
), y
= FROMCOORD(my
);
1466 enum { NONE
, TOGGLE_BLACK
, TOGGLE_CIRCLE
, UI
} action
= NONE
;
1468 if (IS_CURSOR_MOVE(button
)) {
1469 move_cursor(button
, &ui
->cx
, &ui
->cy
, state
->w
, state
->h
, 1);
1472 } else if (IS_CURSOR_SELECT(button
)) {
1473 x
= ui
->cx
; y
= ui
->cy
;
1478 if (button
== CURSOR_SELECT
) {
1479 action
= TOGGLE_BLACK
;
1480 } else if (button
== CURSOR_SELECT2
) {
1481 action
= TOGGLE_CIRCLE
;
1483 } else if (IS_MOUSE_DOWN(button
)) {
1488 if (!INGRID(state
, x
, y
)) {
1489 ui
->show_black_nums
= 1 - ui
->show_black_nums
;
1490 action
= UI
; /* this wants to be a per-game option. */
1491 } else if (button
== LEFT_BUTTON
) {
1492 action
= TOGGLE_BLACK
;
1493 } else if (button
== RIGHT_BUTTON
) {
1494 action
= TOGGLE_CIRCLE
;
1497 if (action
== UI
) return "";
1499 if (action
== TOGGLE_BLACK
|| action
== TOGGLE_CIRCLE
) {
1500 i
= y
* state
->w
+ x
;
1501 if (state
->flags
[i
] & (F_BLACK
| F_CIRCLE
))
1504 c
= (action
== TOGGLE_BLACK
) ?
'B' : 'C';
1505 sprintf(buf
, "%c%d,%d", (int)c
, x
, y
);
1512 static game_state
*execute_move(game_state
*state
, char *move
)
1514 game_state
*ret
= dup_game(state
);
1517 debug(("move: %s", move
));
1521 if (c
== 'B' || c
== 'C' || c
== 'E') {
1523 if (sscanf(move
, "%d,%d%n", &x
, &y
, &n
) != 2 ||
1524 !INGRID(state
, x
, y
))
1528 ret
->flags
[i
] &= ~(F_CIRCLE
| F_BLACK
); /* empty first, always. */
1530 ret
->flags
[i
] |= F_BLACK
;
1532 ret
->flags
[i
] |= F_CIRCLE
;
1534 } else if (c
== 'S') {
1536 ret
->used_solve
= 1;
1545 if (check_complete(ret
, 1)) ret
->completed
= 1;
1553 /* ----------------------------------------------------------------------
1557 static void game_compute_size(game_params
*params
, int tilesize
,
1560 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1561 struct { int tilesize
; } ads
, *ds
= &ads
;
1562 ads
.tilesize
= tilesize
;
1564 *x
= TILE_SIZE
* params
->w
+ 2 * BORDER
;
1565 *y
= TILE_SIZE
* params
->h
+ 2 * BORDER
;
1568 static void game_set_size(drawing
*dr
, game_drawstate
*ds
,
1569 game_params
*params
, int tilesize
)
1571 ds
->tilesize
= tilesize
;
1574 static float *game_colours(frontend
*fe
, int *ncolours
)
1576 float *ret
= snewn(3 * NCOLOURS
, float);
1579 game_mkhighlight(fe
, ret
, COL_BACKGROUND
, COL_HIGHLIGHT
, COL_LOWLIGHT
);
1580 for (i
= 0; i
< 3; i
++) {
1581 ret
[COL_BLACK
* 3 + i
] = 0.0F
;
1582 ret
[COL_BLACKNUM
* 3 + i
] = 0.4F
;
1583 ret
[COL_WHITE
* 3 + i
] = 1.0F
;
1584 ret
[COL_GRID
* 3 + i
] = ret
[COL_LOWLIGHT
* 3 + i
];
1586 ret
[COL_CURSOR
* 3 + 0] = 0.2F
;
1587 ret
[COL_CURSOR
* 3 + 1] = 0.8F
;
1588 ret
[COL_CURSOR
* 3 + 2] = 0.0F
;
1590 ret
[COL_ERROR
* 3 + 0] = 1.0F
;
1591 ret
[COL_ERROR
* 3 + 1] = 0.0F
;
1592 ret
[COL_ERROR
* 3 + 2] = 0.0F
;
1594 *ncolours
= NCOLOURS
;
1598 static game_drawstate
*game_new_drawstate(drawing
*dr
, game_state
*state
)
1600 struct game_drawstate
*ds
= snew(struct game_drawstate
);
1602 ds
->tilesize
= ds
->started
= ds
->solved
= 0;
1607 ds
->flags
= snewn(state
->n
, unsigned int);
1609 memset(ds
->flags
, 0, state
->n
*sizeof(unsigned int));
1614 static void game_free_drawstate(drawing
*dr
, game_drawstate
*ds
)
1620 static void tile_redraw(drawing
*dr
, game_drawstate
*ds
, int x
, int y
,
1621 int num
, unsigned int f
)
1623 int tcol
, bg
, dnum
, cx
, cy
, tsz
;
1627 bg
= (f
& DS_ERROR
) ? COL_ERROR
: COL_BLACK
;
1628 tcol
= COL_BLACKNUM
;
1629 dnum
= (f
& DS_BLACK_NUM
) ?
1 : 0;
1631 bg
= (f
& DS_FLASH
) ? COL_LOWLIGHT
: COL_BACKGROUND
;
1632 tcol
= (f
& DS_ERROR
) ? COL_ERROR
: COL_BLACK
;
1636 cx
= x
+ TILE_SIZE
/2; cy
= y
+ TILE_SIZE
/2;
1638 draw_rect(dr
, x
, y
, TILE_SIZE
, TILE_SIZE
, bg
);
1639 draw_rect_outline(dr
, x
, y
, TILE_SIZE
, TILE_SIZE
,
1640 (f
& DS_IMPOSSIBLE
) ? COL_ERROR
: COL_GRID
);
1642 if (f
& DS_CIRCLE
) {
1643 draw_circle(dr
, cx
, cy
, CRAD
, tcol
, tcol
);
1644 draw_circle(dr
, cx
, cy
, CRAD
-1, bg
, tcol
);
1648 sprintf(buf
, "%d", num
);
1649 if (strlen(buf
) == 1)
1652 tsz
= (CRAD
*2 - 1) / strlen(buf
);
1653 draw_text(dr
, cx
, cy
, FONT_VARIABLE
, tsz
,
1654 ALIGN_VCENTRE
| ALIGN_HCENTRE
, tcol
, buf
);
1658 draw_rect_corners(dr
, cx
, cy
, TEXTSZ
/2, COL_CURSOR
);
1660 draw_update(dr
, x
, y
, TILE_SIZE
, TILE_SIZE
);
1663 static void game_redraw(drawing
*dr
, game_drawstate
*ds
, game_state
*oldstate
,
1664 game_state
*state
, int dir
, game_ui
*ui
,
1665 float animtime
, float flashtime
)
1670 flash
= (int)(flashtime
* 5 / FLASH_TIME
) % 2;
1673 int wsz
= TILE_SIZE
* state
->w
+ 2 * BORDER
;
1674 int hsz
= TILE_SIZE
* state
->h
+ 2 * BORDER
;
1675 draw_rect(dr
, 0, 0, wsz
, hsz
, COL_BACKGROUND
);
1676 draw_rect_outline(dr
, COORD(0)-1, COORD(0)-1,
1677 TILE_SIZE
* state
->w
+ 2, TILE_SIZE
* state
->h
+ 2,
1679 draw_update(dr
, 0, 0, wsz
, hsz
);
1681 for (x
= 0; x
< state
->w
; x
++) {
1682 for (y
= 0; y
< state
->h
; y
++) {
1686 if (flash
) f
|= DS_FLASH
;
1687 if (state
->impossible
) f
|= DS_IMPOSSIBLE
;
1689 if (ui
->cshow
&& x
== ui
->cx
&& y
== ui
->cy
)
1691 if (state
->flags
[i
] & F_BLACK
) {
1693 if (ui
->show_black_nums
) f
|= DS_BLACK_NUM
;
1695 if (state
->flags
[i
] & F_CIRCLE
)
1697 if (state
->flags
[i
] & F_ERROR
)
1700 if (!ds
->started
|| ds
->flags
[i
] != f
) {
1701 tile_redraw(dr
, ds
, COORD(x
), COORD(y
),
1710 static float game_anim_length(game_state
*oldstate
, game_state
*newstate
,
1711 int dir
, game_ui
*ui
)
1716 static float game_flash_length(game_state
*oldstate
, game_state
*newstate
,
1717 int dir
, game_ui
*ui
)
1719 if (!oldstate
->completed
&&
1720 newstate
->completed
&& !newstate
->used_solve
)
1725 static int game_timing_state(game_state
*state
, game_ui
*ui
)
1730 static void game_print_size(game_params
*params
, float *x
, float *y
)
1734 /* 8mm squares by default. */
1735 game_compute_size(params
, 800, &pw
, &ph
);
1740 static void game_print(drawing
*dr
, game_state
*state
, int tilesize
)
1742 int ink
= print_mono_colour(dr
, 0);
1743 int paper
= print_mono_colour(dr
, 1);
1744 int x
, y
, ox
, oy
, i
;
1747 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1748 game_drawstate ads
, *ds
= &ads
;
1749 game_set_size(dr
, ds
, NULL
, tilesize
);
1751 print_line_width(dr
, 2 * TILE_SIZE
/ 40);
1753 for (x
= 0; x
< state
->w
; x
++) {
1754 for (y
= 0; y
< state
->h
; y
++) {
1755 ox
= COORD(x
); oy
= COORD(y
);
1758 if (state
->flags
[i
] & F_BLACK
) {
1759 draw_rect(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, ink
);
1761 draw_rect_outline(dr
, ox
, oy
, TILE_SIZE
, TILE_SIZE
, ink
);
1763 if (state
->flags
[i
] & DS_CIRCLE
)
1764 draw_circle(dr
, ox
+TILE_SIZE
/2, oy
+TILE_SIZE
/2, CRAD
,
1767 sprintf(buf
, "%d", state
->nums
[i
]);
1768 draw_text(dr
, ox
+TILE_SIZE
/2, oy
+TILE_SIZE
/2, FONT_VARIABLE
,
1769 TEXTSZ
/strlen(buf
), ALIGN_VCENTRE
| ALIGN_HCENTRE
,
1777 #define thegame singles
1780 const struct game thegame
= {
1781 "Singles", "games.singles", "singles",
1788 TRUE
, game_configure
, custom_params
,
1796 TRUE
, game_can_format_as_text_now
, game_text_format
,
1804 PREFERRED_TILE_SIZE
, game_compute_size
, game_set_size
,
1807 game_free_drawstate
,
1811 TRUE
, FALSE
, game_print_size
, game_print
,
1812 FALSE
, /* wants_statusbar */
1813 FALSE
, game_timing_state
,
1814 REQUIRE_RBUTTON
, /* flags */
1817 #ifdef STANDALONE_SOLVER
1822 static void start_soak(game_params
*p
, random_state
*rs
)
1824 time_t tt_start
, tt_now
, tt_last
;
1827 int i
, n
= 0, ndiff
[DIFF_MAX
], diff
, sret
, nblack
= 0, nsneaky
= 0;
1829 tt_start
= tt_now
= time(NULL
);
1831 printf("Soak-testing a %dx%d grid.\n", p
->w
, p
->h
);
1834 memset(ndiff
, 0, DIFF_MAX
* sizeof(int));
1838 desc
= new_game_desc(p
, rs
, &aux
, 0);
1839 s
= new_game(NULL
, p
, desc
);
1840 nsneaky
+= solve_sneaky(s
, NULL
);
1842 for (diff
= 0; diff
< DIFF_MAX
; diff
++) {
1843 memset(s
->flags
, 0, s
->n
* sizeof(unsigned int));
1844 s
->completed
= s
->impossible
= 0;
1845 sret
= solve_specific(s
, diff
, 0);
1849 } else if (sret
< 0)
1850 fprintf(stderr
, "Impossible! %s\n", desc
);
1852 for (i
= 0; i
< s
->n
; i
++) {
1853 if (s
->flags
[i
] & F_BLACK
) nblack
++;
1858 tt_last
= time(NULL
);
1859 if (tt_last
> tt_now
) {
1861 printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ",
1862 n
, (double)n
/ ((double)tt_now
- tt_start
),
1863 ((double)nblack
* 100.0) / (double)(n
* p
->w
* p
->h
),
1864 ((double)nsneaky
* 100.0) / (double)(n
* p
->w
* p
->h
));
1865 for (diff
= 0; diff
< DIFF_MAX
; diff
++) {
1866 if (diff
> 0) printf(", ");
1867 printf("%d (%3.1f%%) %s",
1868 ndiff
[diff
], (double)ndiff
[diff
] * 100.0 / (double)n
,
1869 singles_diffnames
[diff
]);
1876 int main(int argc
, char **argv
)
1878 char *id
= NULL
, *desc
, *desc_gen
= NULL
, *tgame
, *err
, *aux
;
1879 game_state
*s
= NULL
;
1880 game_params
*p
= NULL
;
1881 int soln
, soak
= 0, ret
= 1;
1882 time_t seed
= time(NULL
);
1883 random_state
*rs
= NULL
;
1885 setvbuf(stdout
, NULL
, _IONBF
, 0);
1887 while (--argc
> 0) {
1889 if (!strcmp(p
, "-v")) {
1891 } else if (!strcmp(p
, "--soak")) {
1893 } else if (!strcmp(p
, "--seed")) {
1895 fprintf(stderr
, "%s: --seed needs an argument", argv
[0]);
1898 seed
= (time_t)atoi(*++argv
);
1900 } else if (*p
== '-') {
1901 fprintf(stderr
, "%s: unrecognised option `%s'\n", argv
[0], p
);
1908 rs
= random_new((void*)&seed
, sizeof(time_t));
1911 fprintf(stderr
, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv
[0]);
1914 desc
= strchr(id
, ':');
1915 if (desc
) *desc
++ = '\0';
1917 p
= default_params();
1918 decode_params(p
, id
);
1919 err
= validate_params(p
, 1);
1921 fprintf(stderr
, "%s: %s", argv
[0], err
);
1927 fprintf(stderr
, "%s: --soak only needs params, not game desc.\n", argv
[0]);
1932 if (!desc
) desc
= desc_gen
= new_game_desc(p
, rs
, &aux
, 0);
1934 err
= validate_desc(p
, desc
);
1936 fprintf(stderr
, "%s: %s\n", argv
[0], err
);
1940 s
= new_game(NULL
, p
, desc
);
1943 tgame
= game_text_format(s
);
1944 fputs(tgame
, stdout
);
1948 soln
= solve_specific(s
, DIFF_ANY
, 0);
1949 tgame
= game_text_format(s
);
1950 fputs(tgame
, stdout
);
1952 printf("Game was %s.\n\n",
1953 soln
< 0 ?
"impossible" : soln
> 0 ?
"solved" : "not solved");
1958 if (desc_gen
) sfree(desc_gen
);
1959 if (p
) free_params(p
);
1960 if (s
) free_game(s
);
1961 if (rs
) random_free(rs
);
1969 /* vim: set shiftwidth=4 tabstop=8: */