diff options
Diffstat (limited to 'apps/plugins/puzzles/singles.c')
-rw-r--r-- | apps/plugins/puzzles/singles.c | 2004 |
1 files changed, 2004 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/singles.c b/apps/plugins/puzzles/singles.c new file mode 100644 index 0000000000..119be29122 --- /dev/null +++ b/apps/plugins/puzzles/singles.c | |||
@@ -0,0 +1,2004 @@ | |||
1 | /* | ||
2 | * singles.c: implementation of Hitori ('let me alone') from Nikoli. | ||
3 | * | ||
4 | * Make single-get able to fetch a specific puzzle ID from menneske.no? | ||
5 | * | ||
6 | * www.menneske.no solving methods: | ||
7 | * | ||
8 | * Done: | ||
9 | * SC: if you circle a cell, any cells in same row/col with same no --> black | ||
10 | * -- solver_op_circle | ||
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. | ||
18 | * -- solve_doubles | ||
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 | ||
22 | * be white. | ||
23 | * QM: if you have 3 black cells of diagonal square in middle, fourth | ||
24 | * cell must be white. | ||
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 | ||
31 | * cell along wall. | ||
32 | * -- solve_corners (QC, TC, DC) | ||
33 | * IP: pair with one-offset-pair force whites by offset pair | ||
34 | * -- solve_offsetpair | ||
35 | * MC: any cells diag. adjacent to black cells that would split board | ||
36 | * into separate white regions must be white. | ||
37 | * -- solve_removesplits | ||
38 | * | ||
39 | * Still to do: | ||
40 | * | ||
41 | * TEP: 3 pairs of dominos parallel to side, can mark 4 white cells | ||
42 | * alongside. | ||
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? | ||
53 | * | ||
54 | */ | ||
55 | |||
56 | #include <stdio.h> | ||
57 | #include <stdlib.h> | ||
58 | #include <string.h> | ||
59 | #include "rbassert.h" | ||
60 | #include <ctype.h> | ||
61 | #include <math.h> | ||
62 | |||
63 | #include "puzzles.h" | ||
64 | #include "latin.h" | ||
65 | |||
66 | #ifdef STANDALONE_SOLVER | ||
67 | int verbose = 0; | ||
68 | #endif | ||
69 | |||
70 | #define PREFERRED_TILE_SIZE 32 | ||
71 | #define TILE_SIZE (ds->tilesize) | ||
72 | #define BORDER (TILE_SIZE / 2) | ||
73 | |||
74 | #define CRAD ((TILE_SIZE / 2) - 1) | ||
75 | #define TEXTSZ ((14*CRAD/10) - 1) /* 2 * sqrt(2) of CRAD */ | ||
76 | |||
77 | #define COORD(x) ( (x) * TILE_SIZE + BORDER ) | ||
78 | #define FROMCOORD(x) ( ((x) - BORDER + TILE_SIZE) / TILE_SIZE - 1 ) | ||
79 | |||
80 | #define INGRID(s,x,y) ((x) >= 0 && (x) < (s)->w && (y) >= 0 && (y) < (s)->h) | ||
81 | |||
82 | #define FLASH_TIME 0.7F | ||
83 | |||
84 | enum { | ||
85 | COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT, | ||
86 | COL_BLACK, COL_WHITE, COL_BLACKNUM, COL_GRID, | ||
87 | COL_CURSOR, COL_ERROR, | ||
88 | NCOLOURS | ||
89 | }; | ||
90 | |||
91 | struct game_params { | ||
92 | int w, h, diff; | ||
93 | }; | ||
94 | |||
95 | #define F_BLACK 0x1 | ||
96 | #define F_CIRCLE 0x2 | ||
97 | #define F_ERROR 0x4 | ||
98 | #define F_SCRATCH 0x8 | ||
99 | |||
100 | struct game_state { | ||
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 */ | ||
105 | }; | ||
106 | |||
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 }; | ||
110 | |||
111 | /* --- Game parameters and preset functions --- */ | ||
112 | |||
113 | #define DIFFLIST(A) \ | ||
114 | A(EASY,Easy,e) \ | ||
115 | A(TRICKY,Tricky,k) | ||
116 | |||
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 | ||
121 | |||
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) | ||
127 | |||
128 | static game_params *default_params(void) | ||
129 | { | ||
130 | game_params *ret = snew(game_params); | ||
131 | ret->w = ret->h = 5; | ||
132 | ret->diff = DIFF_EASY; | ||
133 | |||
134 | return ret; | ||
135 | } | ||
136 | |||
137 | static const struct game_params singles_presets[] = { | ||
138 | { 5, 5, DIFF_EASY }, | ||
139 | { 5, 5, DIFF_TRICKY }, | ||
140 | { 6, 6, DIFF_EASY }, | ||
141 | { 6, 6, DIFF_TRICKY }, | ||
142 | { 8, 8, DIFF_EASY }, | ||
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 } | ||
148 | }; | ||
149 | |||
150 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
151 | { | ||
152 | game_params *ret; | ||
153 | char buf[80]; | ||
154 | |||
155 | if (i < 0 || i >= lenof(singles_presets)) | ||
156 | return FALSE; | ||
157 | |||
158 | ret = default_params(); | ||
159 | *ret = singles_presets[i]; | ||
160 | *params = ret; | ||
161 | |||
162 | sprintf(buf, "%dx%d %s", ret->w, ret->h, singles_diffnames[ret->diff]); | ||
163 | *name = dupstr(buf); | ||
164 | |||
165 | return TRUE; | ||
166 | } | ||
167 | |||
168 | static void free_params(game_params *params) | ||
169 | { | ||
170 | sfree(params); | ||
171 | } | ||
172 | |||
173 | static game_params *dup_params(const game_params *params) | ||
174 | { | ||
175 | game_params *ret = snew(game_params); | ||
176 | *ret = *params; /* structure copy */ | ||
177 | return ret; | ||
178 | } | ||
179 | |||
180 | static void decode_params(game_params *ret, char const *string) | ||
181 | { | ||
182 | char const *p = string; | ||
183 | int i; | ||
184 | |||
185 | ret->w = ret->h = atoi(p); | ||
186 | while (*p && isdigit((unsigned char)*p)) p++; | ||
187 | if (*p == 'x') { | ||
188 | p++; | ||
189 | ret->h = atoi(p); | ||
190 | while (*p && isdigit((unsigned char)*p)) p++; | ||
191 | } | ||
192 | if (*p == 'd') { | ||
193 | ret->diff = DIFF_MAX; /* which is invalid */ | ||
194 | p++; | ||
195 | for (i = 0; i < DIFFCOUNT; i++) { | ||
196 | if (*p == singles_diffchars[i]) | ||
197 | ret->diff = i; | ||
198 | } | ||
199 | p++; | ||
200 | } | ||
201 | } | ||
202 | |||
203 | static char *encode_params(const game_params *params, int full) | ||
204 | { | ||
205 | char data[256]; | ||
206 | |||
207 | if (full) | ||
208 | sprintf(data, "%dx%dd%c", params->w, params->h, singles_diffchars[params->diff]); | ||
209 | else | ||
210 | sprintf(data, "%dx%d", params->w, params->h); | ||
211 | |||
212 | return dupstr(data); | ||
213 | } | ||
214 | |||
215 | static config_item *game_configure(const game_params *params) | ||
216 | { | ||
217 | config_item *ret; | ||
218 | char buf[80]; | ||
219 | |||
220 | ret = snewn(4, config_item); | ||
221 | |||
222 | ret[0].name = "Width"; | ||
223 | ret[0].type = C_STRING; | ||
224 | sprintf(buf, "%d", params->w); | ||
225 | ret[0].sval = dupstr(buf); | ||
226 | ret[0].ival = 0; | ||
227 | |||
228 | ret[1].name = "Height"; | ||
229 | ret[1].type = C_STRING; | ||
230 | sprintf(buf, "%d", params->h); | ||
231 | ret[1].sval = dupstr(buf); | ||
232 | ret[1].ival = 0; | ||
233 | |||
234 | ret[2].name = "Difficulty"; | ||
235 | ret[2].type = C_CHOICES; | ||
236 | ret[2].sval = DIFFCONFIG; | ||
237 | ret[2].ival = params->diff; | ||
238 | |||
239 | ret[3].name = NULL; | ||
240 | ret[3].type = C_END; | ||
241 | ret[3].sval = NULL; | ||
242 | ret[3].ival = 0; | ||
243 | |||
244 | return ret; | ||
245 | } | ||
246 | |||
247 | static game_params *custom_params(const config_item *cfg) | ||
248 | { | ||
249 | game_params *ret = snew(game_params); | ||
250 | |||
251 | ret->w = atoi(cfg[0].sval); | ||
252 | ret->h = atoi(cfg[1].sval); | ||
253 | ret->diff = cfg[2].ival; | ||
254 | |||
255 | return ret; | ||
256 | } | ||
257 | |||
258 | static char *validate_params(const game_params *params, int full) | ||
259 | { | ||
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"; | ||
264 | if (full) { | ||
265 | if (params->diff < 0 || params->diff >= DIFF_MAX) | ||
266 | return "Unknown difficulty rating"; | ||
267 | } | ||
268 | |||
269 | return NULL; | ||
270 | } | ||
271 | |||
272 | /* --- Game description string generation and unpicking --- */ | ||
273 | |||
274 | static game_state *blank_game(int w, int h) | ||
275 | { | ||
276 | game_state *state = snew(game_state); | ||
277 | |||
278 | memset(state, 0, sizeof(game_state)); | ||
279 | state->w = w; | ||
280 | state->h = h; | ||
281 | state->n = w*h; | ||
282 | state->o = max(w,h); | ||
283 | |||
284 | state->completed = state->used_solve = state->impossible = 0; | ||
285 | |||
286 | state->nums = snewn(state->n, int); | ||
287 | state->flags = snewn(state->n, unsigned int); | ||
288 | |||
289 | memset(state->nums, 0, state->n*sizeof(int)); | ||
290 | memset(state->flags, 0, state->n*sizeof(unsigned int)); | ||
291 | |||
292 | return state; | ||
293 | } | ||
294 | |||
295 | static game_state *dup_game(const game_state *state) | ||
296 | { | ||
297 | game_state *ret = blank_game(state->w, state->h); | ||
298 | |||
299 | ret->completed = state->completed; | ||
300 | ret->used_solve = state->used_solve; | ||
301 | ret->impossible = state->impossible; | ||
302 | |||
303 | memcpy(ret->nums, state->nums, state->n*sizeof(int)); | ||
304 | memcpy(ret->flags, state->flags, state->n*sizeof(unsigned int)); | ||
305 | |||
306 | return ret; | ||
307 | } | ||
308 | |||
309 | static void free_game(game_state *state) | ||
310 | { | ||
311 | sfree(state->nums); | ||
312 | sfree(state->flags); | ||
313 | sfree(state); | ||
314 | } | ||
315 | |||
316 | static char n2c(int num) { | ||
317 | if (num < 10) | ||
318 | return '0' + num; | ||
319 | else if (num < 10+26) | ||
320 | return 'a' + num - 10; | ||
321 | else | ||
322 | return 'A' + num - 10 - 26; | ||
323 | return '?'; | ||
324 | } | ||
325 | |||
326 | static int c2n(char c) { | ||
327 | if (isdigit((unsigned 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); | ||
333 | return -1; | ||
334 | } | ||
335 | |||
336 | static void unpick_desc(const game_params *params, const char *desc, | ||
337 | game_state **sout, char **mout) | ||
338 | { | ||
339 | game_state *state = blank_game(params->w, params->h); | ||
340 | char *msg = NULL; | ||
341 | int num = 0, i = 0; | ||
342 | |||
343 | if (strlen(desc) != state->n) { | ||
344 | msg = "Game description is wrong length"; | ||
345 | goto done; | ||
346 | } | ||
347 | for (i = 0; i < state->n; i++) { | ||
348 | num = c2n(desc[i]); | ||
349 | if (num <= 0 || num > state->o) { | ||
350 | msg = "Game description contains unexpected characters"; | ||
351 | goto done; | ||
352 | } | ||
353 | state->nums[i] = num; | ||
354 | } | ||
355 | done: | ||
356 | if (msg) { /* sth went wrong. */ | ||
357 | if (mout) *mout = msg; | ||
358 | free_game(state); | ||
359 | } else { | ||
360 | if (mout) *mout = NULL; | ||
361 | if (sout) *sout = state; | ||
362 | else free_game(state); | ||
363 | } | ||
364 | } | ||
365 | |||
366 | static char *generate_desc(game_state *state, int issolve) | ||
367 | { | ||
368 | char *ret = snewn(state->n+1+(issolve?1:0), char); | ||
369 | int i, p=0; | ||
370 | |||
371 | if (issolve) | ||
372 | ret[p++] = 'S'; | ||
373 | for (i = 0; i < state->n; i++) | ||
374 | ret[p++] = n2c(state->nums[i]); | ||
375 | ret[p] = '\0'; | ||
376 | return ret; | ||
377 | } | ||
378 | |||
379 | /* --- Useful game functions (completion, etc.) --- */ | ||
380 | |||
381 | static int game_can_format_as_text_now(const game_params *params) | ||
382 | { | ||
383 | return TRUE; | ||
384 | } | ||
385 | |||
386 | static char *game_text_format(const game_state *state) | ||
387 | { | ||
388 | int len, x, y, i; | ||
389 | char *ret, *p; | ||
390 | |||
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); | ||
395 | |||
396 | for (y = 0; y < state->h; y++) { | ||
397 | for (x = 0; x < state->w; x++) { | ||
398 | i = y*state->w + x; | ||
399 | if (x > 0) *p++ = ' '; | ||
400 | *p++ = (state->flags[i] & F_BLACK) ? '*' : n2c(state->nums[i]); | ||
401 | } | ||
402 | *p++ = '\n'; | ||
403 | for (x = 0; x < state->w; x++) { | ||
404 | i = y*state->w + x; | ||
405 | if (x > 0) *p++ = ' '; | ||
406 | *p++ = (state->flags[i] & F_CIRCLE) ? '~' : ' '; | ||
407 | } | ||
408 | *p++ = '\n'; | ||
409 | } | ||
410 | *p++ = '\0'; | ||
411 | assert(p - ret == len); | ||
412 | |||
413 | return ret; | ||
414 | } | ||
415 | |||
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)); | ||
419 | sfree(dbg); | ||
420 | } | ||
421 | |||
422 | static void connect_if_same(game_state *state, int *dsf, int i1, int i2) | ||
423 | { | ||
424 | int c1, c2; | ||
425 | |||
426 | if ((state->flags[i1] & F_BLACK) != (state->flags[i2] & F_BLACK)) | ||
427 | return; | ||
428 | |||
429 | c1 = dsf_canonify(dsf, i1); | ||
430 | c2 = dsf_canonify(dsf, i2); | ||
431 | dsf_merge(dsf, c1, c2); | ||
432 | } | ||
433 | |||
434 | static void connect_dsf(game_state *state, int *dsf) | ||
435 | { | ||
436 | int x, y, i; | ||
437 | |||
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++) { | ||
443 | i = y*state->w + x; | ||
444 | |||
445 | if (x < state->w-1) | ||
446 | connect_if_same(state, dsf, i, i+1); /* right */ | ||
447 | if (y < state->h-1) | ||
448 | connect_if_same(state, dsf, i, i+state->w); /* down */ | ||
449 | } | ||
450 | } | ||
451 | } | ||
452 | |||
453 | #define CC_MARK_ERRORS 1 | ||
454 | #define CC_MUST_FILL 2 | ||
455 | |||
456 | static int check_rowcol(game_state *state, int starti, int di, int sz, unsigned flags) | ||
457 | { | ||
458 | int nerr = 0, n, m, i, j; | ||
459 | |||
460 | /* if any circled numbers have identical non-circled numbers on | ||
461 | * same row/column, error (non-circled) | ||
462 | * if any circled numbers in same column are same number, highlight them. | ||
463 | * if any rows/columns have >1 of same number, not complete. */ | ||
464 | |||
465 | for (n = 0, i = starti; n < sz; n++, i += di) { | ||
466 | if (state->flags[i] & F_BLACK) continue; | ||
467 | for (m = n+1, j = i+di; m < sz; m++, j += di) { | ||
468 | if (state->flags[j] & F_BLACK) continue; | ||
469 | if (state->nums[i] != state->nums[j]) continue; | ||
470 | |||
471 | nerr++; /* ok, we have two numbers the same in a row. */ | ||
472 | if (!(flags & CC_MARK_ERRORS)) continue; | ||
473 | |||
474 | /* If we have two circles in the same row around | ||
475 | * two identical numbers, they are _both_ wrong. */ | ||
476 | if ((state->flags[i] & F_CIRCLE) && | ||
477 | (state->flags[j] & F_CIRCLE)) { | ||
478 | state->flags[i] |= F_ERROR; | ||
479 | state->flags[j] |= F_ERROR; | ||
480 | } | ||
481 | /* Otherwise, if we have a circle, any other identical | ||
482 | * numbers in that row are obviously wrong. We don't | ||
483 | * highlight this, however, since it makes the process | ||
484 | * of solving the puzzle too easy (you circle a number | ||
485 | * and it promptly tells you which numbers to blacken! */ | ||
486 | #if 0 | ||
487 | else if (state->flags[i] & F_CIRCLE) | ||
488 | state->flags[j] |= F_ERROR; | ||
489 | else if (state->flags[j] & F_CIRCLE) | ||
490 | state->flags[i] |= F_ERROR; | ||
491 | #endif | ||
492 | } | ||
493 | } | ||
494 | return nerr; | ||
495 | } | ||
496 | |||
497 | static int check_complete(game_state *state, unsigned flags) | ||
498 | { | ||
499 | int *dsf = snewn(state->n, int); | ||
500 | int x, y, i, error = 0, nwhite, w = state->w, h = state->h; | ||
501 | |||
502 | if (flags & CC_MARK_ERRORS) { | ||
503 | for (i = 0; i < state->n; i++) | ||
504 | state->flags[i] &= ~F_ERROR; | ||
505 | } | ||
506 | connect_dsf(state, dsf); | ||
507 | |||
508 | /* If we're the solver we need the grid all to be definitively | ||
509 | * black or definitively white (i.e. circled) otherwise the solver | ||
510 | * has found an ambiguous grid. */ | ||
511 | if (flags & CC_MUST_FILL) { | ||
512 | for (i = 0; i < state->n; i++) { | ||
513 | if (!(state->flags[i] & F_BLACK) && !(state->flags[i] & F_CIRCLE)) | ||
514 | error += 1; | ||
515 | } | ||
516 | } | ||
517 | |||
518 | /* Mark any black squares in groups of >1 as errors. | ||
519 | * Count number of white squares. */ | ||
520 | nwhite = 0; | ||
521 | for (i = 0; i < state->n; i++) { | ||
522 | if (state->flags[i] & F_BLACK) { | ||
523 | if (dsf_size(dsf, i) > 1) { | ||
524 | error += 1; | ||
525 | if (flags & CC_MARK_ERRORS) | ||
526 | state->flags[i] |= F_ERROR; | ||
527 | } | ||
528 | } else | ||
529 | nwhite += 1; | ||
530 | } | ||
531 | |||
532 | /* Check attributes of white squares, row- and column-wise. */ | ||
533 | for (x = 0; x < w; x++) /* check cols from (x,0) */ | ||
534 | error += check_rowcol(state, x, w, h, flags); | ||
535 | for (y = 0; y < h; y++) /* check rows from (0,y) */ | ||
536 | error += check_rowcol(state, y*w, 1, w, flags); | ||
537 | |||
538 | /* If there's more than one white region, pick the largest one to | ||
539 | * be the canonical one (arbitrarily tie-breaking towards lower | ||
540 | * array indices), and mark all the others as erroneous. */ | ||
541 | { | ||
542 | int largest = 0, canonical = -1; | ||
543 | for (i = 0; i < state->n; i++) | ||
544 | if (!(state->flags[i] & F_BLACK)) { | ||
545 | int size = dsf_size(dsf, i); | ||
546 | if (largest < size) { | ||
547 | largest = size; | ||
548 | canonical = i; | ||
549 | } | ||
550 | } | ||
551 | |||
552 | if (largest < nwhite) { | ||
553 | for (i = 0; i < state->n; i++) | ||
554 | if (!(state->flags[i] & F_BLACK) && | ||
555 | dsf_canonify(dsf, i) != canonical) { | ||
556 | error += 1; | ||
557 | if (flags & CC_MARK_ERRORS) | ||
558 | state->flags[i] |= F_ERROR; | ||
559 | } | ||
560 | } | ||
561 | } | ||
562 | |||
563 | sfree(dsf); | ||
564 | return (error > 0) ? 0 : 1; | ||
565 | } | ||
566 | |||
567 | static char *game_state_diff(const game_state *src, const game_state *dst, | ||
568 | int issolve) | ||
569 | { | ||
570 | char *ret = NULL, buf[80], c; | ||
571 | int retlen = 0, x, y, i, k; | ||
572 | unsigned int fmask = F_BLACK | F_CIRCLE; | ||
573 | |||
574 | assert(src->n == dst->n); | ||
575 | |||
576 | if (issolve) { | ||
577 | ret = sresize(ret, 3, char); | ||
578 | ret[0] = 'S'; ret[1] = ';'; ret[2] = '\0'; | ||
579 | retlen += 2; | ||
580 | } | ||
581 | |||
582 | for (x = 0; x < dst->w; x++) { | ||
583 | for (y = 0; y < dst->h; y++) { | ||
584 | i = y*dst->w + x; | ||
585 | if ((src->flags[i] & fmask) != (dst->flags[i] & fmask)) { | ||
586 | assert((dst->flags[i] & fmask) != fmask); | ||
587 | if (dst->flags[i] & F_BLACK) | ||
588 | c = 'B'; | ||
589 | else if (dst->flags[i] & F_CIRCLE) | ||
590 | c = 'C'; | ||
591 | else | ||
592 | c = 'E'; | ||
593 | k = sprintf(buf, "%c%d,%d;", (int)c, x, y); | ||
594 | ret = sresize(ret, retlen + k + 1, char); | ||
595 | strcpy(ret + retlen, buf); | ||
596 | retlen += k; | ||
597 | } | ||
598 | } | ||
599 | } | ||
600 | return ret; | ||
601 | } | ||
602 | |||
603 | /* --- Solver --- */ | ||
604 | |||
605 | enum { BLACK, CIRCLE }; | ||
606 | |||
607 | struct solver_op { | ||
608 | int x, y, op; /* op one of BLACK or CIRCLE. */ | ||
609 | const char *desc; /* must be non-malloced. */ | ||
610 | }; | ||
611 | |||
612 | struct solver_state { | ||
613 | struct solver_op *ops; | ||
614 | int n_ops, n_alloc; | ||
615 | int *scratch; | ||
616 | }; | ||
617 | |||
618 | static struct solver_state *solver_state_new(game_state *state) | ||
619 | { | ||
620 | struct solver_state *ss = snew(struct solver_state); | ||
621 | |||
622 | ss->ops = NULL; | ||
623 | ss->n_ops = ss->n_alloc = 0; | ||
624 | ss->scratch = snewn(state->n, int); | ||
625 | |||
626 | return ss; | ||
627 | } | ||
628 | |||
629 | static void solver_state_free(struct solver_state *ss) | ||
630 | { | ||
631 | sfree(ss->scratch); | ||
632 | if (ss->ops) sfree(ss->ops); | ||
633 | sfree(ss); | ||
634 | } | ||
635 | |||
636 | static void solver_op_add(struct solver_state *ss, int x, int y, int op, const char *desc) | ||
637 | { | ||
638 | struct solver_op *sop; | ||
639 | |||
640 | if (ss->n_alloc < ss->n_ops + 1) { | ||
641 | ss->n_alloc = (ss->n_alloc + 1) * 2; | ||
642 | ss->ops = sresize(ss->ops, ss->n_alloc, struct solver_op); | ||
643 | } | ||
644 | sop = &(ss->ops[ss->n_ops++]); | ||
645 | sop->x = x; sop->y = y; sop->op = op; sop->desc = desc; | ||
646 | debug(("added solver op %s ('%s') at (%d,%d)\n", | ||
647 | op == BLACK ? "BLACK" : "CIRCLE", desc, x, y)); | ||
648 | } | ||
649 | |||
650 | static void solver_op_circle(game_state *state, struct solver_state *ss, | ||
651 | int x, int y) | ||
652 | { | ||
653 | int i = y*state->w + x; | ||
654 | |||
655 | if (!INGRID(state, x, y)) return; | ||
656 | if (state->flags[i] & F_BLACK) { | ||
657 | debug(("... solver wants to add auto-circle on black (%d,%d)\n", x, y)); | ||
658 | state->impossible = 1; | ||
659 | return; | ||
660 | } | ||
661 | /* Only add circle op if it's not already circled. */ | ||
662 | if (!(state->flags[i] & F_CIRCLE)) { | ||
663 | solver_op_add(ss, x, y, CIRCLE, "SB - adjacent to black square"); | ||
664 | } | ||
665 | } | ||
666 | |||
667 | static void solver_op_blacken(game_state *state, struct solver_state *ss, | ||
668 | int x, int y, int num) | ||
669 | { | ||
670 | int i = y*state->w + x; | ||
671 | |||
672 | if (!INGRID(state, x, y)) return; | ||
673 | if (state->nums[i] != num) return; | ||
674 | if (state->flags[i] & F_CIRCLE) { | ||
675 | debug(("... solver wants to add auto-black on circled(%d,%d)\n", x, y)); | ||
676 | state->impossible = 1; | ||
677 | return; | ||
678 | } | ||
679 | /* Only add black op if it's not already black. */ | ||
680 | if (!(state->flags[i] & F_BLACK)) { | ||
681 | solver_op_add(ss, x, y, BLACK, "SC - number on same row/col as circled"); | ||
682 | } | ||
683 | } | ||
684 | |||
685 | static int solver_ops_do(game_state *state, struct solver_state *ss) | ||
686 | { | ||
687 | int next_op = 0, i, x, y, n_ops = 0; | ||
688 | struct solver_op op; | ||
689 | |||
690 | /* Care here: solver_op_* may call solver_op_add which may extend the | ||
691 | * ss->n_ops. */ | ||
692 | |||
693 | while (next_op < ss->n_ops) { | ||
694 | op = ss->ops[next_op++]; /* copy this away, it may get reallocated. */ | ||
695 | i = op.y*state->w + op.x; | ||
696 | |||
697 | if (op.op == BLACK) { | ||
698 | if (state->flags[i] & F_CIRCLE) { | ||
699 | debug(("Solver wants to blacken circled square (%d,%d)!\n", op.x, op.y)); | ||
700 | state->impossible = 1; | ||
701 | return n_ops; | ||
702 | } | ||
703 | if (!(state->flags[i] & F_BLACK)) { | ||
704 | debug(("... solver adding black at (%d,%d): %s\n", op.x, op.y, op.desc)); | ||
705 | #ifdef STANDALONE_SOLVER | ||
706 | if (verbose) | ||
707 | printf("Adding black at (%d,%d): %s\n", op.x, op.y, op.desc); | ||
708 | #endif | ||
709 | state->flags[i] |= F_BLACK; | ||
710 | /*debug_state("State after adding black", state);*/ | ||
711 | n_ops++; | ||
712 | solver_op_circle(state, ss, op.x-1, op.y); | ||
713 | solver_op_circle(state, ss, op.x+1, op.y); | ||
714 | solver_op_circle(state, ss, op.x, op.y-1); | ||
715 | solver_op_circle(state, ss, op.x, op.y+1); | ||
716 | } | ||
717 | } else { | ||
718 | if (state->flags[i] & F_BLACK) { | ||
719 | debug(("Solver wants to circle blackened square (%d,%d)!\n", op.x, op.y)); | ||
720 | state->impossible = 1; | ||
721 | return n_ops; | ||
722 | } | ||
723 | if (!(state->flags[i] & F_CIRCLE)) { | ||
724 | debug(("... solver adding circle at (%d,%d): %s\n", op.x, op.y, op.desc)); | ||
725 | #ifdef STANDALONE_SOLVER | ||
726 | if (verbose) | ||
727 | printf("Adding circle at (%d,%d): %s\n", op.x, op.y, op.desc); | ||
728 | #endif | ||
729 | state->flags[i] |= F_CIRCLE; | ||
730 | /*debug_state("State after adding circle", state);*/ | ||
731 | n_ops++; | ||
732 | for (x = 0; x < state->w; x++) { | ||
733 | if (x != op.x) | ||
734 | solver_op_blacken(state, ss, x, op.y, state->nums[i]); | ||
735 | } | ||
736 | for (y = 0; y < state->h; y++) { | ||
737 | if (y != op.y) | ||
738 | solver_op_blacken(state, ss, op.x, y, state->nums[i]); | ||
739 | } | ||
740 | } | ||
741 | } | ||
742 | } | ||
743 | ss->n_ops = 0; | ||
744 | return n_ops; | ||
745 | } | ||
746 | |||
747 | /* If the grid has two identical numbers with one cell between them, the inner | ||
748 | * cell _must_ be white (and thus circled); (at least) one of the two must be | ||
749 | * black (since they're in the same column or row) and thus the middle cell is | ||
750 | * next to a black cell. */ | ||
751 | static int solve_singlesep(game_state *state, struct solver_state *ss) | ||
752 | { | ||
753 | int x, y, i, ir, irr, id, idd, n_ops = ss->n_ops; | ||
754 | |||
755 | for (x = 0; x < state->w; x++) { | ||
756 | for (y = 0; y < state->h; y++) { | ||
757 | i = y*state->w + x; | ||
758 | |||
759 | /* Cell two to our right? */ | ||
760 | ir = i + 1; irr = ir + 1; | ||
761 | if (x < (state->w-2) && | ||
762 | state->nums[i] == state->nums[irr] && | ||
763 | !(state->flags[ir] & F_CIRCLE)) { | ||
764 | solver_op_add(ss, x+1, y, CIRCLE, "SP/ST - between identical nums"); | ||
765 | } | ||
766 | /* Cell two below us? */ | ||
767 | id = i + state->w; idd = id + state->w; | ||
768 | if (y < (state->h-2) && | ||
769 | state->nums[i] == state->nums[idd] && | ||
770 | !(state->flags[id] & F_CIRCLE)) { | ||
771 | solver_op_add(ss, x, y+1, CIRCLE, "SP/ST - between identical nums"); | ||
772 | } | ||
773 | } | ||
774 | } | ||
775 | return ss->n_ops - n_ops; | ||
776 | } | ||
777 | |||
778 | /* If we have two identical numbers next to each other (in a row or column), | ||
779 | * any other identical numbers in that column must be black. */ | ||
780 | static int solve_doubles(game_state *state, struct solver_state *ss) | ||
781 | { | ||
782 | int x, y, i, ii, n_ops = ss->n_ops, xy; | ||
783 | |||
784 | for (y = 0, i = 0; y < state->h; y++) { | ||
785 | for (x = 0; x < state->w; x++, i++) { | ||
786 | assert(i == y*state->w+x); | ||
787 | if (state->flags[i] & F_BLACK) continue; | ||
788 | |||
789 | ii = i+1; /* check cell to our right. */ | ||
790 | if (x < (state->w-1) && | ||
791 | !(state->flags[ii] & F_BLACK) && | ||
792 | state->nums[i] == state->nums[ii]) { | ||
793 | for (xy = 0; xy < state->w; xy++) { | ||
794 | if (xy == x || xy == (x+1)) continue; | ||
795 | if (state->nums[y*state->w + xy] == state->nums[i] && | ||
796 | !(state->flags[y*state->w + xy] & F_BLACK)) | ||
797 | solver_op_add(ss, xy, y, BLACK, "PI - same row as pair"); | ||
798 | } | ||
799 | } | ||
800 | |||
801 | ii = i+state->w; /* check cell below us */ | ||
802 | if (y < (state->h-1) && | ||
803 | !(state->flags[ii] & F_BLACK) && | ||
804 | state->nums[i] == state->nums[ii]) { | ||
805 | for (xy = 0; xy < state->h; xy++) { | ||
806 | if (xy == y || xy == (y+1)) continue; | ||
807 | if (state->nums[xy*state->w + x] == state->nums[i] && | ||
808 | !(state->flags[xy*state->w + x] & F_BLACK)) | ||
809 | solver_op_add(ss, x, xy, BLACK, "PI - same col as pair"); | ||
810 | } | ||
811 | } | ||
812 | } | ||
813 | } | ||
814 | return ss->n_ops - n_ops; | ||
815 | } | ||
816 | |||
817 | /* If a white square has all-but-one possible adjacent squares black, the | ||
818 | * one square left over must be white. */ | ||
819 | static int solve_allblackbutone(game_state *state, struct solver_state *ss) | ||
820 | { | ||
821 | int x, y, i, n_ops = ss->n_ops, xd, yd, id, ifree; | ||
822 | int dis[4], d; | ||
823 | |||
824 | dis[0] = -state->w; | ||
825 | dis[1] = 1; | ||
826 | dis[2] = state->w; | ||
827 | dis[3] = -1; | ||
828 | |||
829 | for (y = 0, i = 0; y < state->h; y++) { | ||
830 | for (x = 0; x < state->w; x++, i++) { | ||
831 | assert(i == y*state->w+x); | ||
832 | if (state->flags[i] & F_BLACK) continue; | ||
833 | |||
834 | ifree = -1; | ||
835 | for (d = 0; d < 4; d++) { | ||
836 | xd = x + dxs[d]; yd = y + dys[d]; id = i + dis[d]; | ||
837 | if (!INGRID(state, xd, yd)) continue; | ||
838 | |||
839 | if (state->flags[id] & F_CIRCLE) | ||
840 | goto skip; /* this cell already has a way out */ | ||
841 | if (!(state->flags[id] & F_BLACK)) { | ||
842 | if (ifree != -1) | ||
843 | goto skip; /* this cell has >1 white cell around it. */ | ||
844 | ifree = id; | ||
845 | } | ||
846 | } | ||
847 | if (ifree != -1) | ||
848 | solver_op_add(ss, ifree%state->w, ifree/state->w, CIRCLE, | ||
849 | "CC/CE/QM: white cell with single non-black around it"); | ||
850 | else { | ||
851 | debug(("White cell with no escape at (%d,%d)\n", x, y)); | ||
852 | state->impossible = 1; | ||
853 | return 0; | ||
854 | } | ||
855 | skip: ; | ||
856 | } | ||
857 | } | ||
858 | return ss->n_ops - n_ops; | ||
859 | } | ||
860 | |||
861 | /* If we have 4 numbers the same in a 2x2 corner, the far corner and the | ||
862 | * diagonally-adjacent square must both be black. | ||
863 | * If we have 3 numbers the same in a 2x2 corner, the apex of the L | ||
864 | * thus formed must be black. | ||
865 | * If we have 2 numbers the same in a 2x2 corner, the non-same cell | ||
866 | * one away from the corner must be white. */ | ||
867 | static void solve_corner(game_state *state, struct solver_state *ss, | ||
868 | int x, int y, int dx, int dy) | ||
869 | { | ||
870 | int is[4], ns[4], xx, yy, w = state->w; | ||
871 | |||
872 | for (yy = 0; yy < 2; yy++) { | ||
873 | for (xx = 0; xx < 2; xx++) { | ||
874 | is[yy*2+xx] = (y + dy*yy) * w + (x + dx*xx); | ||
875 | ns[yy*2+xx] = state->nums[is[yy*2+xx]]; | ||
876 | } | ||
877 | } /* order is now (corner, side 1, side 2, inner) */ | ||
878 | |||
879 | if (ns[0] == ns[1] && ns[0] == ns[2] && ns[0] == ns[3]) { | ||
880 | solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "QC: corner with 4 matching"); | ||
881 | solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "QC: corner with 4 matching"); | ||
882 | } else if (ns[0] == ns[1] && ns[0] == ns[2]) { | ||
883 | /* corner and 2 sides: apex is corner. */ | ||
884 | solver_op_add(ss, is[0]%w, is[0]/w, BLACK, "TC: corner apex from 3 matching"); | ||
885 | } else if (ns[1] == ns[2] && ns[1] == ns[3]) { | ||
886 | /* side, side, fourth: apex is fourth. */ | ||
887 | solver_op_add(ss, is[3]%w, is[3]/w, BLACK, "TC: inside apex from 3 matching"); | ||
888 | } else if (ns[0] == ns[1] || ns[1] == ns[3]) { | ||
889 | /* either way here we match the non-identical side. */ | ||
890 | solver_op_add(ss, is[2]%w, is[2]/w, CIRCLE, "DC: corner with 2 matching"); | ||
891 | } else if (ns[0] == ns[2] || ns[2] == ns[3]) { | ||
892 | /* ditto */ | ||
893 | solver_op_add(ss, is[1]%w, is[1]/w, CIRCLE, "DC: corner with 2 matching"); | ||
894 | } | ||
895 | } | ||
896 | |||
897 | static int solve_corners(game_state *state, struct solver_state *ss) | ||
898 | { | ||
899 | int n_ops = ss->n_ops; | ||
900 | |||
901 | solve_corner(state, ss, 0, 0, 1, 1); | ||
902 | solve_corner(state, ss, state->w-1, 0, -1, 1); | ||
903 | solve_corner(state, ss, state->w-1, state->h-1, -1, -1); | ||
904 | solve_corner(state, ss, 0, state->h-1, 1, -1); | ||
905 | |||
906 | return ss->n_ops - n_ops; | ||
907 | } | ||
908 | |||
909 | /* If you have the following situation: | ||
910 | * ... | ||
911 | * ...x A x x y A x... | ||
912 | * ...x B x x B y x... | ||
913 | * ... | ||
914 | * then both squares marked 'y' must be white. One of the left-most A or B must | ||
915 | * be white (since two side-by-side black cells are disallowed), which means | ||
916 | * that the corresponding right-most A or B must be black (since you can't | ||
917 | * have two of the same number on one line); thus, the adjacent squares | ||
918 | * to that right-most A or B must be white, which include the two marked 'y' | ||
919 | * in either case. | ||
920 | * Obviously this works in any row or column. It also works if A == B. | ||
921 | * It doesn't work for the degenerate case: | ||
922 | * ...x A A x x | ||
923 | * ...x B y x x | ||
924 | * where the square marked 'y' isn't necessarily white (consider the left-most A | ||
925 | * is black). | ||
926 | * | ||
927 | * */ | ||
928 | static void solve_offsetpair_pair(game_state *state, struct solver_state *ss, | ||
929 | int x1, int y1, int x2, int y2) | ||
930 | { | ||
931 | int ox, oy, w = state->w, ax, ay, an, d, dx[2], dy[2], dn, xd, yd; | ||
932 | |||
933 | if (x1 == x2) { /* same column */ | ||
934 | ox = 1; oy = 0; | ||
935 | } else { | ||
936 | assert(y1 == y2); | ||
937 | ox = 0; oy = 1; | ||
938 | } | ||
939 | |||
940 | /* We try adjacent to (x1,y1) and the two diag. adjacent to (x2, y2). | ||
941 | * We expect to be called twice, once each way around. */ | ||
942 | ax = x1+ox; ay = y1+oy; | ||
943 | assert(INGRID(state, ax, ay)); | ||
944 | an = state->nums[ay*w + ax]; | ||
945 | |||
946 | dx[0] = x2 + ox + oy; dx[1] = x2 + ox - oy; | ||
947 | dy[0] = y2 + oy + ox; dy[1] = y2 + oy - ox; | ||
948 | |||
949 | for (d = 0; d < 2; d++) { | ||
950 | if (INGRID(state, dx[d], dy[d]) && (dx[d] != ax || dy[d] != ay)) { | ||
951 | /* The 'dx != ax || dy != ay' removes the degenerate case, | ||
952 | * mentioned above. */ | ||
953 | dn = state->nums[dy[d]*w + dx[d]]; | ||
954 | if (an == dn) { | ||
955 | /* We have a match; so (WLOG) the 'A' marked above are at | ||
956 | * (x1,y1) and (x2,y2), and the 'B' are at (ax,ay) and (dx,dy). */ | ||
957 | debug(("Found offset-pair: %d at (%d,%d) and (%d,%d)\n", | ||
958 | state->nums[y1*w + x1], x1, y1, x2, y2)); | ||
959 | debug((" and: %d at (%d,%d) and (%d,%d)\n", | ||
960 | an, ax, ay, dx[d], dy[d])); | ||
961 | |||
962 | xd = dx[d] - x2; yd = dy[d] - y2; | ||
963 | solver_op_add(ss, x2 + xd, y2, CIRCLE, "IP: next to offset-pair"); | ||
964 | solver_op_add(ss, x2, y2 + yd, CIRCLE, "IP: next to offset-pair"); | ||
965 | } | ||
966 | } | ||
967 | } | ||
968 | } | ||
969 | |||
970 | static int solve_offsetpair(game_state *state, struct solver_state *ss) | ||
971 | { | ||
972 | int n_ops = ss->n_ops, x, xx, y, yy, n1, n2; | ||
973 | |||
974 | for (x = 0; x < state->w-1; x++) { | ||
975 | for (y = 0; y < state->h; y++) { | ||
976 | n1 = state->nums[y*state->w + x]; | ||
977 | for (yy = y+1; yy < state->h; yy++) { | ||
978 | n2 = state->nums[yy*state->w + x]; | ||
979 | if (n1 == n2) { | ||
980 | solve_offsetpair_pair(state, ss, x, y, x, yy); | ||
981 | solve_offsetpair_pair(state, ss, x, yy, x, y); | ||
982 | } | ||
983 | } | ||
984 | } | ||
985 | } | ||
986 | for (y = 0; y < state->h-1; y++) { | ||
987 | for (x = 0; x < state->w; x++) { | ||
988 | n1 = state->nums[y*state->w + x]; | ||
989 | for (xx = x+1; xx < state->w; xx++) { | ||
990 | n2 = state->nums[y*state->w + xx]; | ||
991 | if (n1 == n2) { | ||
992 | solve_offsetpair_pair(state, ss, x, y, xx, y); | ||
993 | solve_offsetpair_pair(state, ss, xx, y, x, y); | ||
994 | } | ||
995 | } | ||
996 | } | ||
997 | } | ||
998 | return ss->n_ops - n_ops; | ||
999 | } | ||
1000 | |||
1001 | static int solve_hassinglewhiteregion(game_state *state, struct solver_state *ss) | ||
1002 | { | ||
1003 | int i, j, nwhite = 0, lwhite = -1, szwhite, start, end, next, a, d, x, y; | ||
1004 | |||
1005 | for (i = 0; i < state->n; i++) { | ||
1006 | if (!(state->flags[i] & F_BLACK)) { | ||
1007 | nwhite++; | ||
1008 | lwhite = i; | ||
1009 | } | ||
1010 | state->flags[i] &= ~F_SCRATCH; | ||
1011 | } | ||
1012 | if (lwhite == -1) { | ||
1013 | debug(("solve_hassinglewhite: no white squares found!\n")); | ||
1014 | state->impossible = 1; | ||
1015 | return 0; | ||
1016 | } | ||
1017 | /* We don't use connect_dsf here; it's too slow, and there's a quicker | ||
1018 | * algorithm if all we want is the size of one region. */ | ||
1019 | /* Having written this, this algorithm is only about 5% faster than | ||
1020 | * using a dsf. */ | ||
1021 | memset(ss->scratch, -1, state->n * sizeof(int)); | ||
1022 | ss->scratch[0] = lwhite; | ||
1023 | state->flags[lwhite] |= F_SCRATCH; | ||
1024 | start = 0; end = next = 1; | ||
1025 | while (start < end) { | ||
1026 | for (a = start; a < end; a++) { | ||
1027 | i = ss->scratch[a]; assert(i != -1); | ||
1028 | for (d = 0; d < 4; d++) { | ||
1029 | x = (i % state->w) + dxs[d]; | ||
1030 | y = (i / state->w) + dys[d]; | ||
1031 | j = y*state->w + x; | ||
1032 | if (!INGRID(state, x, y)) continue; | ||
1033 | if (state->flags[j] & (F_BLACK | F_SCRATCH)) continue; | ||
1034 | ss->scratch[next++] = j; | ||
1035 | state->flags[j] |= F_SCRATCH; | ||
1036 | } | ||
1037 | } | ||
1038 | start = end; end = next; | ||
1039 | } | ||
1040 | szwhite = next; | ||
1041 | return (szwhite == nwhite) ? 1 : 0; | ||
1042 | } | ||
1043 | |||
1044 | static void solve_removesplits_check(game_state *state, struct solver_state *ss, | ||
1045 | int x, int y) | ||
1046 | { | ||
1047 | int i = y*state->w + x, issingle; | ||
1048 | |||
1049 | if (!INGRID(state, x, y)) return; | ||
1050 | if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) | ||
1051 | return; | ||
1052 | |||
1053 | /* If putting a black square at (x,y) would make the white region | ||
1054 | * non-contiguous, it must be circled. */ | ||
1055 | state->flags[i] |= F_BLACK; | ||
1056 | issingle = solve_hassinglewhiteregion(state, ss); | ||
1057 | state->flags[i] &= ~F_BLACK; | ||
1058 | |||
1059 | if (!issingle) | ||
1060 | solver_op_add(ss, x, y, CIRCLE, "MC: black square here would split white region"); | ||
1061 | } | ||
1062 | |||
1063 | /* For all black squares, search in squares diagonally adjacent to see if | ||
1064 | * we can rule out putting a black square there (because it would make the | ||
1065 | * white region non-contiguous). */ | ||
1066 | /* This function is likely to be somewhat slow. */ | ||
1067 | static int solve_removesplits(game_state *state, struct solver_state *ss) | ||
1068 | { | ||
1069 | int i, x, y, n_ops = ss->n_ops; | ||
1070 | |||
1071 | if (!solve_hassinglewhiteregion(state, ss)) { | ||
1072 | debug(("solve_removesplits: white region is not contiguous at start!\n")); | ||
1073 | state->impossible = 1; | ||
1074 | return 0; | ||
1075 | } | ||
1076 | |||
1077 | for (i = 0; i < state->n; i++) { | ||
1078 | if (!(state->flags[i] & F_BLACK)) continue; | ||
1079 | |||
1080 | x = i%state->w; y = i/state->w; | ||
1081 | solve_removesplits_check(state, ss, x-1, y-1); | ||
1082 | solve_removesplits_check(state, ss, x+1, y-1); | ||
1083 | solve_removesplits_check(state, ss, x+1, y+1); | ||
1084 | solve_removesplits_check(state, ss, x-1, y+1); | ||
1085 | } | ||
1086 | return ss->n_ops - n_ops; | ||
1087 | } | ||
1088 | |||
1089 | /* | ||
1090 | * This function performs a solver step that isn't implicit in the rules | ||
1091 | * of the game and is thus treated somewhat differently. | ||
1092 | * | ||
1093 | * It marks cells whose number does not exist elsewhere in its row/column | ||
1094 | * with circles. As it happens the game generator here does mean that this | ||
1095 | * is always correct, but it's a solving method that people should not have | ||
1096 | * to rely upon (except in the hidden 'sneaky' difficulty setting) and so | ||
1097 | * all grids at 'tricky' and above are checked to make sure that the grid | ||
1098 | * is no easier if this solving step is performed beforehand. | ||
1099 | * | ||
1100 | * Calling with ss=NULL just returns the number of sneaky deductions that | ||
1101 | * would have been made. | ||
1102 | */ | ||
1103 | static int solve_sneaky(game_state *state, struct solver_state *ss) | ||
1104 | { | ||
1105 | int i, ii, x, xx, y, yy, nunique = 0; | ||
1106 | |||
1107 | /* Clear SCRATCH flags. */ | ||
1108 | for (i = 0; i < state->n; i++) state->flags[i] &= ~F_SCRATCH; | ||
1109 | |||
1110 | for (x = 0; x < state->w; x++) { | ||
1111 | for (y = 0; y < state->h; y++) { | ||
1112 | i = y*state->w + x; | ||
1113 | |||
1114 | /* Check for duplicate numbers on our row, mark (both) if so */ | ||
1115 | for (xx = x; xx < state->w; xx++) { | ||
1116 | ii = y*state->w + xx; | ||
1117 | if (i == ii) continue; | ||
1118 | |||
1119 | if (state->nums[i] == state->nums[ii]) { | ||
1120 | state->flags[i] |= F_SCRATCH; | ||
1121 | state->flags[ii] |= F_SCRATCH; | ||
1122 | } | ||
1123 | } | ||
1124 | |||
1125 | /* Check for duplicate numbers on our col, mark (both) if so */ | ||
1126 | for (yy = y; yy < state->h; yy++) { | ||
1127 | ii = yy*state->w + x; | ||
1128 | if (i == ii) continue; | ||
1129 | |||
1130 | if (state->nums[i] == state->nums[ii]) { | ||
1131 | state->flags[i] |= F_SCRATCH; | ||
1132 | state->flags[ii] |= F_SCRATCH; | ||
1133 | } | ||
1134 | } | ||
1135 | } | ||
1136 | } | ||
1137 | |||
1138 | /* Any cell with no marking has no duplicates on its row or column: | ||
1139 | * set its CIRCLE. */ | ||
1140 | for (i = 0; i < state->n; i++) { | ||
1141 | if (!(state->flags[i] & F_SCRATCH)) { | ||
1142 | if (ss) solver_op_add(ss, i%state->w, i/state->w, CIRCLE, | ||
1143 | "SNEAKY: only one of its number in row and col"); | ||
1144 | nunique += 1; | ||
1145 | } else | ||
1146 | state->flags[i] &= ~F_SCRATCH; | ||
1147 | } | ||
1148 | return nunique; | ||
1149 | } | ||
1150 | |||
1151 | static int solve_specific(game_state *state, int diff, int sneaky) | ||
1152 | { | ||
1153 | struct solver_state *ss = solver_state_new(state); | ||
1154 | |||
1155 | if (sneaky) solve_sneaky(state, ss); | ||
1156 | |||
1157 | /* Some solver operations we only have to perform once -- | ||
1158 | * they're only based on the numbers available, and not black | ||
1159 | * squares or circles which may be added later. */ | ||
1160 | |||
1161 | solve_singlesep(state, ss); /* never sets impossible */ | ||
1162 | solve_doubles(state, ss); /* ditto */ | ||
1163 | solve_corners(state, ss); /* ditto */ | ||
1164 | |||
1165 | if (diff >= DIFF_TRICKY) | ||
1166 | solve_offsetpair(state, ss); /* ditto */ | ||
1167 | |||
1168 | while (1) { | ||
1169 | if (ss->n_ops > 0) solver_ops_do(state, ss); | ||
1170 | if (state->impossible) break; | ||
1171 | |||
1172 | if (solve_allblackbutone(state, ss) > 0) continue; | ||
1173 | if (state->impossible) break; | ||
1174 | |||
1175 | if (diff >= DIFF_TRICKY) { | ||
1176 | if (solve_removesplits(state, ss) > 0) continue; | ||
1177 | if (state->impossible) break; | ||
1178 | } | ||
1179 | |||
1180 | break; | ||
1181 | } | ||
1182 | |||
1183 | solver_state_free(ss); | ||
1184 | return state->impossible ? -1 : check_complete(state, CC_MUST_FILL); | ||
1185 | } | ||
1186 | |||
1187 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1188 | const char *aux, char **error) | ||
1189 | { | ||
1190 | game_state *solved = dup_game(currstate); | ||
1191 | char *move = NULL; | ||
1192 | |||
1193 | if (solve_specific(solved, DIFF_ANY, 0) > 0) goto solved; | ||
1194 | free_game(solved); | ||
1195 | |||
1196 | solved = dup_game(state); | ||
1197 | if (solve_specific(solved, DIFF_ANY, 0) > 0) goto solved; | ||
1198 | free_game(solved); | ||
1199 | |||
1200 | *error = "Unable to solve puzzle."; | ||
1201 | return NULL; | ||
1202 | |||
1203 | solved: | ||
1204 | move = game_state_diff(currstate, solved, 1); | ||
1205 | free_game(solved); | ||
1206 | return move; | ||
1207 | } | ||
1208 | |||
1209 | /* --- Game generation --- */ | ||
1210 | |||
1211 | /* A correctly completed Hitori board is essentially a latin square | ||
1212 | * (no duplicated numbers in any row or column) with black squares | ||
1213 | * added such that no black square touches another, and the white | ||
1214 | * squares make a contiguous region. | ||
1215 | * | ||
1216 | * So we can generate it by: | ||
1217 | * constructing a latin square | ||
1218 | * adding black squares at random (minding the constraints) | ||
1219 | * altering the numbers under the new black squares such that | ||
1220 | the solver gets a headstart working out where they are. | ||
1221 | */ | ||
1222 | |||
1223 | static int new_game_is_good(const game_params *params, | ||
1224 | game_state *state, game_state *tosolve) | ||
1225 | { | ||
1226 | int sret, sret_easy = 0; | ||
1227 | |||
1228 | memcpy(tosolve->nums, state->nums, state->n * sizeof(int)); | ||
1229 | memset(tosolve->flags, 0, state->n * sizeof(unsigned int)); | ||
1230 | tosolve->completed = tosolve->impossible = 0; | ||
1231 | |||
1232 | /* | ||
1233 | * We try and solve it twice, once at our requested difficulty level | ||
1234 | * (ensuring it's soluble at all) and once at the level below (if | ||
1235 | * it exists), which we hope to fail: if you can also solve it at | ||
1236 | * the level below then it's too easy and we have to try again. | ||
1237 | * | ||
1238 | * With this puzzle in particular there's an extra finesse, which is | ||
1239 | * that we check that the generated puzzle isn't too easy _with | ||
1240 | * an extra solver step first_, which is the 'sneaky' mode of deductions | ||
1241 | * (asserting that any number which fulfils the latin-square rules | ||
1242 | * on its row/column must be white). This is an artefact of the | ||
1243 | * generation process and not implicit in the rules, so we don't want | ||
1244 | * people to be able to use it to make the puzzle easier. | ||
1245 | */ | ||
1246 | |||
1247 | assert(params->diff < DIFF_MAX); | ||
1248 | sret = solve_specific(tosolve, params->diff, 0); | ||
1249 | if (params->diff > DIFF_EASY) { | ||
1250 | memset(tosolve->flags, 0, state->n * sizeof(unsigned int)); | ||
1251 | tosolve->completed = tosolve->impossible = 0; | ||
1252 | |||
1253 | /* this is the only time the 'sneaky' flag is set to 1. */ | ||
1254 | sret_easy = solve_specific(tosolve, params->diff-1, 1); | ||
1255 | } | ||
1256 | |||
1257 | if (sret <= 0 || sret_easy > 0) { | ||
1258 | debug(("Generated puzzle %s at chosen difficulty %s\n", | ||
1259 | sret <= 0 ? "insoluble" : "too easy", | ||
1260 | singles_diffnames[params->diff])); | ||
1261 | return 0; | ||
1262 | } | ||
1263 | return 1; | ||
1264 | } | ||
1265 | |||
1266 | #define MAXTRIES 20 | ||
1267 | |||
1268 | static int best_black_col(game_state *state, random_state *rs, int *scratch, | ||
1269 | int i, int *rownums, int *colnums) | ||
1270 | { | ||
1271 | int w = state->w, x = i%w, y = i/w, j, o = state->o; | ||
1272 | |||
1273 | /* Randomise the list of numbers to try. */ | ||
1274 | for (i = 0; i < o; i++) scratch[i] = i; | ||
1275 | shuffle(scratch, o, sizeof(int), rs); | ||
1276 | |||
1277 | /* Try each number in turn, first giving preference to removing | ||
1278 | * latin-square characteristics (i.e. those numbers which only | ||
1279 | * occur once in a row/column). The '&&' here, although intuitively | ||
1280 | * wrong, results in a smaller number of 'sneaky' deductions on | ||
1281 | * solvable boards. */ | ||
1282 | for (i = 0; i < o; i++) { | ||
1283 | j = scratch[i] + 1; | ||
1284 | if (rownums[y*o + j-1] == 1 && colnums[x*o + j-1] == 1) | ||
1285 | goto found; | ||
1286 | } | ||
1287 | |||
1288 | /* Then try each number in turn returning the first one that's | ||
1289 | * not actually unique in its row/column (see comment below) */ | ||
1290 | for (i = 0; i < o; i++) { | ||
1291 | j = scratch[i] + 1; | ||
1292 | if (rownums[y*o + j-1] != 0 || colnums[x*o + j-1] != 0) | ||
1293 | goto found; | ||
1294 | } | ||
1295 | assert(!"unable to place number under black cell."); | ||
1296 | return 0; | ||
1297 | |||
1298 | found: | ||
1299 | /* Update column and row counts assuming this number will be placed. */ | ||
1300 | rownums[y*o + j-1] += 1; | ||
1301 | colnums[x*o + j-1] += 1; | ||
1302 | return j; | ||
1303 | } | ||
1304 | |||
1305 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1306 | char **aux, int interactive) | ||
1307 | { | ||
1308 | game_state *state = blank_game(params->w, params->h); | ||
1309 | game_state *tosolve = blank_game(params->w, params->h); | ||
1310 | int i, j, *scratch, *rownums, *colnums, x, y, ntries; | ||
1311 | int w = state->w, h = state->h, o = state->o; | ||
1312 | char *ret; | ||
1313 | digit *latin; | ||
1314 | struct solver_state *ss = solver_state_new(state); | ||
1315 | |||
1316 | scratch = snewn(state->n, int); | ||
1317 | rownums = snewn(h*o, int); | ||
1318 | colnums = snewn(w*o, int); | ||
1319 | |||
1320 | generate: | ||
1321 | ss->n_ops = 0; | ||
1322 | debug(("Starting game generation, size %dx%d\n", w, h)); | ||
1323 | |||
1324 | memset(state->flags, 0, state->n*sizeof(unsigned int)); | ||
1325 | |||
1326 | /* First, generate the latin rectangle. | ||
1327 | * The order of this, o, is max(w,h). */ | ||
1328 | latin = latin_generate_rect(w, h, rs); | ||
1329 | for (i = 0; i < state->n; i++) | ||
1330 | state->nums[i] = (int)latin[i]; | ||
1331 | sfree(latin); | ||
1332 | debug_state("State after latin square", state); | ||
1333 | |||
1334 | /* Add black squares at random, using bits of solver as we go (to lay | ||
1335 | * white squares), until we can lay no more blacks. */ | ||
1336 | for (i = 0; i < state->n; i++) | ||
1337 | scratch[i] = i; | ||
1338 | shuffle(scratch, state->n, sizeof(int), rs); | ||
1339 | for (j = 0; j < state->n; j++) { | ||
1340 | i = scratch[j]; | ||
1341 | if ((state->flags[i] & F_CIRCLE) || (state->flags[i] & F_BLACK)) { | ||
1342 | debug(("generator skipping (%d,%d): %s\n", i%w, i/w, | ||
1343 | (state->flags[i] & F_CIRCLE) ? "CIRCLE" : "BLACK")); | ||
1344 | continue; /* solver knows this must be one or the other already. */ | ||
1345 | } | ||
1346 | |||
1347 | /* Add a random black cell... */ | ||
1348 | solver_op_add(ss, i%w, i/w, BLACK, "Generator: adding random black cell"); | ||
1349 | solver_ops_do(state, ss); | ||
1350 | |||
1351 | /* ... and do as well as we know how to lay down whites that are now forced. */ | ||
1352 | solve_allblackbutone(state, ss); | ||
1353 | solver_ops_do(state, ss); | ||
1354 | |||
1355 | solve_removesplits(state, ss); | ||
1356 | solver_ops_do(state, ss); | ||
1357 | |||
1358 | if (state->impossible) { | ||
1359 | debug(("generator made impossible, restarting...\n")); | ||
1360 | goto generate; | ||
1361 | } | ||
1362 | } | ||
1363 | debug_state("State after adding blacks", state); | ||
1364 | |||
1365 | /* Now we know which squares are white and which are black, we lay numbers | ||
1366 | * under black squares at random, except that the number must appear in | ||
1367 | * white cells at least once more in the same column or row as that [black] | ||
1368 | * square. That's necessary to avoid multiple solutions, where blackening | ||
1369 | * squares in the finished puzzle becomes optional. We use two arrays: | ||
1370 | * | ||
1371 | * rownums[ROW * o + NUM-1] is the no. of white cells containing NUM in y=ROW | ||
1372 | * colnums[COL * o + NUM-1] is the no. of white cells containing NUM in x=COL | ||
1373 | */ | ||
1374 | |||
1375 | memset(rownums, 0, h*o * sizeof(int)); | ||
1376 | memset(colnums, 0, w*o * sizeof(int)); | ||
1377 | for (i = 0; i < state->n; i++) { | ||
1378 | if (state->flags[i] & F_BLACK) continue; | ||
1379 | j = state->nums[i]; | ||
1380 | x = i%w; y = i/w; | ||
1381 | rownums[y * o + j-1] += 1; | ||
1382 | colnums[x * o + j-1] += 1; | ||
1383 | } | ||
1384 | |||
1385 | ntries = 0; | ||
1386 | randomise: | ||
1387 | for (i = 0; i < state->n; i++) { | ||
1388 | if (!(state->flags[i] & F_BLACK)) continue; | ||
1389 | state->nums[i] = best_black_col(state, rs, scratch, i, rownums, colnums); | ||
1390 | } | ||
1391 | debug_state("State after adding numbers", state); | ||
1392 | |||
1393 | /* DIFF_ANY just returns whatever we first generated, for testing purposes. */ | ||
1394 | if (params->diff != DIFF_ANY && | ||
1395 | !new_game_is_good(params, state, tosolve)) { | ||
1396 | ntries++; | ||
1397 | if (ntries > MAXTRIES) { | ||
1398 | debug(("Ran out of randomisation attempts, re-generating.\n")); | ||
1399 | goto generate; | ||
1400 | } | ||
1401 | debug(("Re-randomising numbers under black squares.\n")); | ||
1402 | goto randomise; | ||
1403 | } | ||
1404 | |||
1405 | ret = generate_desc(state, 0); | ||
1406 | |||
1407 | free_game(tosolve); | ||
1408 | free_game(state); | ||
1409 | solver_state_free(ss); | ||
1410 | sfree(scratch); | ||
1411 | sfree(rownums); | ||
1412 | sfree(colnums); | ||
1413 | |||
1414 | return ret; | ||
1415 | } | ||
1416 | |||
1417 | static char *validate_desc(const game_params *params, const char *desc) | ||
1418 | { | ||
1419 | char *ret = NULL; | ||
1420 | |||
1421 | unpick_desc(params, desc, NULL, &ret); | ||
1422 | return ret; | ||
1423 | } | ||
1424 | |||
1425 | static game_state *new_game(midend *me, const game_params *params, | ||
1426 | const char *desc) | ||
1427 | { | ||
1428 | game_state *state = NULL; | ||
1429 | |||
1430 | unpick_desc(params, desc, &state, NULL); | ||
1431 | if (!state) assert(!"new_game failed to unpick"); | ||
1432 | return state; | ||
1433 | } | ||
1434 | |||
1435 | /* --- Game UI and move routines --- */ | ||
1436 | |||
1437 | struct game_ui { | ||
1438 | int cx, cy, cshow; | ||
1439 | int show_black_nums; | ||
1440 | }; | ||
1441 | |||
1442 | static game_ui *new_ui(const game_state *state) | ||
1443 | { | ||
1444 | game_ui *ui = snew(game_ui); | ||
1445 | |||
1446 | ui->cx = ui->cy = ui->cshow = 0; | ||
1447 | ui->show_black_nums = 0; | ||
1448 | |||
1449 | return ui; | ||
1450 | } | ||
1451 | |||
1452 | static void free_ui(game_ui *ui) | ||
1453 | { | ||
1454 | sfree(ui); | ||
1455 | } | ||
1456 | |||
1457 | static char *encode_ui(const game_ui *ui) | ||
1458 | { | ||
1459 | return NULL; | ||
1460 | } | ||
1461 | |||
1462 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1463 | { | ||
1464 | } | ||
1465 | |||
1466 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1467 | const game_state *newstate) | ||
1468 | { | ||
1469 | if (!oldstate->completed && newstate->completed) | ||
1470 | ui->cshow = 0; | ||
1471 | } | ||
1472 | |||
1473 | #define DS_BLACK 0x1 | ||
1474 | #define DS_CIRCLE 0x2 | ||
1475 | #define DS_CURSOR 0x4 | ||
1476 | #define DS_BLACK_NUM 0x8 | ||
1477 | #define DS_ERROR 0x10 | ||
1478 | #define DS_FLASH 0x20 | ||
1479 | #define DS_IMPOSSIBLE 0x40 | ||
1480 | |||
1481 | struct game_drawstate { | ||
1482 | int tilesize, started, solved; | ||
1483 | int w, h, n; | ||
1484 | |||
1485 | unsigned int *flags; | ||
1486 | }; | ||
1487 | |||
1488 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1489 | const game_drawstate *ds, | ||
1490 | int mx, int my, int button) | ||
1491 | { | ||
1492 | char buf[80], c; | ||
1493 | int i, x = FROMCOORD(mx), y = FROMCOORD(my); | ||
1494 | enum { NONE, TOGGLE_BLACK, TOGGLE_CIRCLE, UI } action = NONE; | ||
1495 | |||
1496 | if (IS_CURSOR_MOVE(button)) { | ||
1497 | move_cursor(button, &ui->cx, &ui->cy, state->w, state->h, 1); | ||
1498 | ui->cshow = 1; | ||
1499 | action = UI; | ||
1500 | } else if (IS_CURSOR_SELECT(button)) { | ||
1501 | x = ui->cx; y = ui->cy; | ||
1502 | if (!ui->cshow) { | ||
1503 | action = UI; | ||
1504 | ui->cshow = 1; | ||
1505 | } | ||
1506 | if (button == CURSOR_SELECT) { | ||
1507 | action = TOGGLE_BLACK; | ||
1508 | } else if (button == CURSOR_SELECT2) { | ||
1509 | action = TOGGLE_CIRCLE; | ||
1510 | } | ||
1511 | } else if (IS_MOUSE_DOWN(button)) { | ||
1512 | if (ui->cshow) { | ||
1513 | ui->cshow = 0; | ||
1514 | action = UI; | ||
1515 | } | ||
1516 | if (!INGRID(state, x, y)) { | ||
1517 | ui->show_black_nums = 1 - ui->show_black_nums; | ||
1518 | action = UI; /* this wants to be a per-game option. */ | ||
1519 | } else if (button == LEFT_BUTTON) { | ||
1520 | action = TOGGLE_BLACK; | ||
1521 | } else if (button == RIGHT_BUTTON) { | ||
1522 | action = TOGGLE_CIRCLE; | ||
1523 | } | ||
1524 | } | ||
1525 | if (action == UI) return ""; | ||
1526 | |||
1527 | if (action == TOGGLE_BLACK || action == TOGGLE_CIRCLE) { | ||
1528 | i = y * state->w + x; | ||
1529 | if (state->flags[i] & (F_BLACK | F_CIRCLE)) | ||
1530 | c = 'E'; | ||
1531 | else | ||
1532 | c = (action == TOGGLE_BLACK) ? 'B' : 'C'; | ||
1533 | sprintf(buf, "%c%d,%d", (int)c, x, y); | ||
1534 | return dupstr(buf); | ||
1535 | } | ||
1536 | |||
1537 | return NULL; | ||
1538 | } | ||
1539 | |||
1540 | static game_state *execute_move(const game_state *state, const char *move) | ||
1541 | { | ||
1542 | game_state *ret = dup_game(state); | ||
1543 | int x, y, i, n; | ||
1544 | |||
1545 | debug(("move: %s\n", move)); | ||
1546 | |||
1547 | while (*move) { | ||
1548 | char c = *move; | ||
1549 | if (c == 'B' || c == 'C' || c == 'E') { | ||
1550 | move++; | ||
1551 | if (sscanf(move, "%d,%d%n", &x, &y, &n) != 2 || | ||
1552 | !INGRID(state, x, y)) | ||
1553 | goto badmove; | ||
1554 | |||
1555 | i = y*ret->w + x; | ||
1556 | ret->flags[i] &= ~(F_CIRCLE | F_BLACK); /* empty first, always. */ | ||
1557 | if (c == 'B') | ||
1558 | ret->flags[i] |= F_BLACK; | ||
1559 | else if (c == 'C') | ||
1560 | ret->flags[i] |= F_CIRCLE; | ||
1561 | move += n; | ||
1562 | } else if (c == 'S') { | ||
1563 | move++; | ||
1564 | ret->used_solve = 1; | ||
1565 | } else | ||
1566 | goto badmove; | ||
1567 | |||
1568 | if (*move == ';') | ||
1569 | move++; | ||
1570 | else if (*move) | ||
1571 | goto badmove; | ||
1572 | } | ||
1573 | if (check_complete(ret, CC_MARK_ERRORS)) ret->completed = 1; | ||
1574 | return ret; | ||
1575 | |||
1576 | badmove: | ||
1577 | free_game(ret); | ||
1578 | return NULL; | ||
1579 | } | ||
1580 | |||
1581 | /* ---------------------------------------------------------------------- | ||
1582 | * Drawing routines. | ||
1583 | */ | ||
1584 | |||
1585 | static void game_compute_size(const game_params *params, int tilesize, | ||
1586 | int *x, int *y) | ||
1587 | { | ||
1588 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1589 | struct { int tilesize; } ads, *ds = &ads; | ||
1590 | ads.tilesize = tilesize; | ||
1591 | |||
1592 | *x = TILE_SIZE * params->w + 2 * BORDER; | ||
1593 | *y = TILE_SIZE * params->h + 2 * BORDER; | ||
1594 | } | ||
1595 | |||
1596 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1597 | const game_params *params, int tilesize) | ||
1598 | { | ||
1599 | ds->tilesize = tilesize; | ||
1600 | } | ||
1601 | |||
1602 | static float *game_colours(frontend *fe, int *ncolours) | ||
1603 | { | ||
1604 | float *ret = snewn(3 * NCOLOURS, float); | ||
1605 | int i; | ||
1606 | |||
1607 | game_mkhighlight(fe, ret, COL_BACKGROUND, COL_HIGHLIGHT, COL_LOWLIGHT); | ||
1608 | for (i = 0; i < 3; i++) { | ||
1609 | ret[COL_BLACK * 3 + i] = 0.0F; | ||
1610 | ret[COL_BLACKNUM * 3 + i] = 0.4F; | ||
1611 | ret[COL_WHITE * 3 + i] = 1.0F; | ||
1612 | ret[COL_GRID * 3 + i] = ret[COL_LOWLIGHT * 3 + i]; | ||
1613 | } | ||
1614 | ret[COL_CURSOR * 3 + 0] = 0.2F; | ||
1615 | ret[COL_CURSOR * 3 + 1] = 0.8F; | ||
1616 | ret[COL_CURSOR * 3 + 2] = 0.0F; | ||
1617 | |||
1618 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1619 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1620 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1621 | |||
1622 | *ncolours = NCOLOURS; | ||
1623 | return ret; | ||
1624 | } | ||
1625 | |||
1626 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1627 | { | ||
1628 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1629 | |||
1630 | ds->tilesize = ds->started = ds->solved = 0; | ||
1631 | ds->w = state->w; | ||
1632 | ds->h = state->h; | ||
1633 | ds->n = state->n; | ||
1634 | |||
1635 | ds->flags = snewn(state->n, unsigned int); | ||
1636 | |||
1637 | memset(ds->flags, 0, state->n*sizeof(unsigned int)); | ||
1638 | |||
1639 | return ds; | ||
1640 | } | ||
1641 | |||
1642 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1643 | { | ||
1644 | sfree(ds->flags); | ||
1645 | sfree(ds); | ||
1646 | } | ||
1647 | |||
1648 | static void tile_redraw(drawing *dr, game_drawstate *ds, int x, int y, | ||
1649 | int num, unsigned int f) | ||
1650 | { | ||
1651 | int tcol, bg, dnum, cx, cy, tsz; | ||
1652 | char buf[32]; | ||
1653 | |||
1654 | if (f & DS_BLACK) { | ||
1655 | bg = (f & DS_ERROR) ? COL_ERROR : COL_BLACK; | ||
1656 | tcol = COL_BLACKNUM; | ||
1657 | dnum = (f & DS_BLACK_NUM) ? 1 : 0; | ||
1658 | } else { | ||
1659 | bg = (f & DS_FLASH) ? COL_LOWLIGHT : COL_BACKGROUND; | ||
1660 | tcol = (f & DS_ERROR) ? COL_ERROR : COL_BLACK; | ||
1661 | dnum = 1; | ||
1662 | } | ||
1663 | |||
1664 | cx = x + TILE_SIZE/2; cy = y + TILE_SIZE/2; | ||
1665 | |||
1666 | draw_rect(dr, x, y, TILE_SIZE, TILE_SIZE, bg); | ||
1667 | draw_rect_outline(dr, x, y, TILE_SIZE, TILE_SIZE, | ||
1668 | (f & DS_IMPOSSIBLE) ? COL_ERROR : COL_GRID); | ||
1669 | |||
1670 | if (f & DS_CIRCLE) { | ||
1671 | draw_circle(dr, cx, cy, CRAD, tcol, tcol); | ||
1672 | draw_circle(dr, cx, cy, CRAD-1, bg, tcol); | ||
1673 | } | ||
1674 | |||
1675 | if (dnum) { | ||
1676 | sprintf(buf, "%d", num); | ||
1677 | if (strlen(buf) == 1) | ||
1678 | tsz = TEXTSZ; | ||
1679 | else | ||
1680 | tsz = (CRAD*2 - 1) / strlen(buf); | ||
1681 | draw_text(dr, cx, cy, FONT_VARIABLE, tsz, | ||
1682 | ALIGN_VCENTRE | ALIGN_HCENTRE, tcol, buf); | ||
1683 | } | ||
1684 | |||
1685 | if (f & DS_CURSOR) | ||
1686 | draw_rect_corners(dr, cx, cy, TEXTSZ/2, COL_CURSOR); | ||
1687 | |||
1688 | draw_update(dr, x, y, TILE_SIZE, TILE_SIZE); | ||
1689 | } | ||
1690 | |||
1691 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1692 | const game_state *oldstate, const game_state *state, | ||
1693 | int dir, const game_ui *ui, | ||
1694 | float animtime, float flashtime) | ||
1695 | { | ||
1696 | int x, y, i, flash; | ||
1697 | unsigned int f; | ||
1698 | |||
1699 | flash = (int)(flashtime * 5 / FLASH_TIME) % 2; | ||
1700 | |||
1701 | if (!ds->started) { | ||
1702 | int wsz = TILE_SIZE * state->w + 2 * BORDER; | ||
1703 | int hsz = TILE_SIZE * state->h + 2 * BORDER; | ||
1704 | draw_rect(dr, 0, 0, wsz, hsz, COL_BACKGROUND); | ||
1705 | draw_rect_outline(dr, COORD(0)-1, COORD(0)-1, | ||
1706 | TILE_SIZE * state->w + 2, TILE_SIZE * state->h + 2, | ||
1707 | COL_GRID); | ||
1708 | draw_update(dr, 0, 0, wsz, hsz); | ||
1709 | } | ||
1710 | for (x = 0; x < state->w; x++) { | ||
1711 | for (y = 0; y < state->h; y++) { | ||
1712 | i = y*state->w + x; | ||
1713 | f = 0; | ||
1714 | |||
1715 | if (flash) f |= DS_FLASH; | ||
1716 | if (state->impossible) f |= DS_IMPOSSIBLE; | ||
1717 | |||
1718 | if (ui->cshow && x == ui->cx && y == ui->cy) | ||
1719 | f |= DS_CURSOR; | ||
1720 | if (state->flags[i] & F_BLACK) { | ||
1721 | f |= DS_BLACK; | ||
1722 | if (ui->show_black_nums) f |= DS_BLACK_NUM; | ||
1723 | } | ||
1724 | if (state->flags[i] & F_CIRCLE) | ||
1725 | f |= DS_CIRCLE; | ||
1726 | if (state->flags[i] & F_ERROR) | ||
1727 | f |= DS_ERROR; | ||
1728 | |||
1729 | if (!ds->started || ds->flags[i] != f) { | ||
1730 | tile_redraw(dr, ds, COORD(x), COORD(y), | ||
1731 | state->nums[i], f); | ||
1732 | ds->flags[i] = f; | ||
1733 | } | ||
1734 | } | ||
1735 | } | ||
1736 | ds->started = 1; | ||
1737 | } | ||
1738 | |||
1739 | static float game_anim_length(const game_state *oldstate, | ||
1740 | const game_state *newstate, int dir, game_ui *ui) | ||
1741 | { | ||
1742 | return 0.0F; | ||
1743 | } | ||
1744 | |||
1745 | static float game_flash_length(const game_state *oldstate, | ||
1746 | const game_state *newstate, int dir, game_ui *ui) | ||
1747 | { | ||
1748 | if (!oldstate->completed && | ||
1749 | newstate->completed && !newstate->used_solve) | ||
1750 | return FLASH_TIME; | ||
1751 | return 0.0F; | ||
1752 | } | ||
1753 | |||
1754 | static int game_status(const game_state *state) | ||
1755 | { | ||
1756 | return state->completed ? +1 : 0; | ||
1757 | } | ||
1758 | |||
1759 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1760 | { | ||
1761 | return TRUE; | ||
1762 | } | ||
1763 | |||
1764 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1765 | { | ||
1766 | int pw, ph; | ||
1767 | |||
1768 | /* 8mm squares by default. */ | ||
1769 | game_compute_size(params, 800, &pw, &ph); | ||
1770 | *x = pw / 100.0F; | ||
1771 | *y = ph / 100.0F; | ||
1772 | } | ||
1773 | |||
1774 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1775 | { | ||
1776 | int ink = print_mono_colour(dr, 0); | ||
1777 | int paper = print_mono_colour(dr, 1); | ||
1778 | int x, y, ox, oy, i; | ||
1779 | char buf[32]; | ||
1780 | |||
1781 | /* Ick: fake up `ds->tilesize' for macro expansion purposes */ | ||
1782 | game_drawstate ads, *ds = &ads; | ||
1783 | game_set_size(dr, ds, NULL, tilesize); | ||
1784 | |||
1785 | print_line_width(dr, 2 * TILE_SIZE / 40); | ||
1786 | |||
1787 | for (x = 0; x < state->w; x++) { | ||
1788 | for (y = 0; y < state->h; y++) { | ||
1789 | ox = COORD(x); oy = COORD(y); | ||
1790 | i = y*state->w+x; | ||
1791 | |||
1792 | if (state->flags[i] & F_BLACK) { | ||
1793 | draw_rect(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink); | ||
1794 | } else { | ||
1795 | draw_rect_outline(dr, ox, oy, TILE_SIZE, TILE_SIZE, ink); | ||
1796 | |||
1797 | if (state->flags[i] & DS_CIRCLE) | ||
1798 | draw_circle(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, CRAD, | ||
1799 | paper, ink); | ||
1800 | |||
1801 | sprintf(buf, "%d", state->nums[i]); | ||
1802 | draw_text(dr, ox+TILE_SIZE/2, oy+TILE_SIZE/2, FONT_VARIABLE, | ||
1803 | TEXTSZ/strlen(buf), ALIGN_VCENTRE | ALIGN_HCENTRE, | ||
1804 | ink, buf); | ||
1805 | } | ||
1806 | } | ||
1807 | } | ||
1808 | } | ||
1809 | |||
1810 | #ifdef COMBINED | ||
1811 | #define thegame singles | ||
1812 | #endif | ||
1813 | |||
1814 | const struct game thegame = { | ||
1815 | "Singles", "games.singles", "singles", | ||
1816 | default_params, | ||
1817 | game_fetch_preset, | ||
1818 | decode_params, | ||
1819 | encode_params, | ||
1820 | free_params, | ||
1821 | dup_params, | ||
1822 | TRUE, game_configure, custom_params, | ||
1823 | validate_params, | ||
1824 | new_game_desc, | ||
1825 | validate_desc, | ||
1826 | new_game, | ||
1827 | dup_game, | ||
1828 | free_game, | ||
1829 | TRUE, solve_game, | ||
1830 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1831 | new_ui, | ||
1832 | free_ui, | ||
1833 | encode_ui, | ||
1834 | decode_ui, | ||
1835 | game_changed_state, | ||
1836 | interpret_move, | ||
1837 | execute_move, | ||
1838 | PREFERRED_TILE_SIZE, game_compute_size, game_set_size, | ||
1839 | game_colours, | ||
1840 | game_new_drawstate, | ||
1841 | game_free_drawstate, | ||
1842 | game_redraw, | ||
1843 | game_anim_length, | ||
1844 | game_flash_length, | ||
1845 | game_status, | ||
1846 | TRUE, FALSE, game_print_size, game_print, | ||
1847 | FALSE, /* wants_statusbar */ | ||
1848 | FALSE, game_timing_state, | ||
1849 | REQUIRE_RBUTTON, /* flags */ | ||
1850 | }; | ||
1851 | |||
1852 | #ifdef STANDALONE_SOLVER | ||
1853 | |||
1854 | #include <time.h> | ||
1855 | #include <stdarg.h> | ||
1856 | |||
1857 | static void start_soak(game_params *p, random_state *rs) | ||
1858 | { | ||
1859 | time_t tt_start, tt_now, tt_last; | ||
1860 | char *desc, *aux; | ||
1861 | game_state *s; | ||
1862 | int i, n = 0, ndiff[DIFF_MAX], diff, sret, nblack = 0, nsneaky = 0; | ||
1863 | |||
1864 | tt_start = tt_now = time(NULL); | ||
1865 | |||
1866 | printf("Soak-testing a %dx%d grid.\n", p->w, p->h); | ||
1867 | p->diff = DIFF_ANY; | ||
1868 | |||
1869 | memset(ndiff, 0, DIFF_MAX * sizeof(int)); | ||
1870 | |||
1871 | while (1) { | ||
1872 | n++; | ||
1873 | desc = new_game_desc(p, rs, &aux, 0); | ||
1874 | s = new_game(NULL, p, desc); | ||
1875 | nsneaky += solve_sneaky(s, NULL); | ||
1876 | |||
1877 | for (diff = 0; diff < DIFF_MAX; diff++) { | ||
1878 | memset(s->flags, 0, s->n * sizeof(unsigned int)); | ||
1879 | s->completed = s->impossible = 0; | ||
1880 | sret = solve_specific(s, diff, 0); | ||
1881 | if (sret > 0) { | ||
1882 | ndiff[diff]++; | ||
1883 | break; | ||
1884 | } else if (sret < 0) | ||
1885 | fprintf(stderr, "Impossible! %s\n", desc); | ||
1886 | } | ||
1887 | for (i = 0; i < s->n; i++) { | ||
1888 | if (s->flags[i] & F_BLACK) nblack++; | ||
1889 | } | ||
1890 | free_game(s); | ||
1891 | sfree(desc); | ||
1892 | |||
1893 | tt_last = time(NULL); | ||
1894 | if (tt_last > tt_now) { | ||
1895 | tt_now = tt_last; | ||
1896 | printf("%d total, %3.1f/s, bl/sn %3.1f%%/%3.1f%%: ", | ||
1897 | n, (double)n / ((double)tt_now - tt_start), | ||
1898 | ((double)nblack * 100.0) / (double)(n * p->w * p->h), | ||
1899 | ((double)nsneaky * 100.0) / (double)(n * p->w * p->h)); | ||
1900 | for (diff = 0; diff < DIFF_MAX; diff++) { | ||
1901 | if (diff > 0) printf(", "); | ||
1902 | printf("%d (%3.1f%%) %s", | ||
1903 | ndiff[diff], (double)ndiff[diff] * 100.0 / (double)n, | ||
1904 | singles_diffnames[diff]); | ||
1905 | } | ||
1906 | printf("\n"); | ||
1907 | } | ||
1908 | } | ||
1909 | } | ||
1910 | |||
1911 | int main(int argc, char **argv) | ||
1912 | { | ||
1913 | char *id = NULL, *desc, *desc_gen = NULL, *tgame, *err, *aux; | ||
1914 | game_state *s = NULL; | ||
1915 | game_params *p = NULL; | ||
1916 | int soln, soak = 0, ret = 1; | ||
1917 | time_t seed = time(NULL); | ||
1918 | random_state *rs = NULL; | ||
1919 | |||
1920 | setvbuf(stdout, NULL, _IONBF, 0); | ||
1921 | |||
1922 | while (--argc > 0) { | ||
1923 | char *p = *++argv; | ||
1924 | if (!strcmp(p, "-v")) { | ||
1925 | verbose = 1; | ||
1926 | } else if (!strcmp(p, "--soak")) { | ||
1927 | soak = 1; | ||
1928 | } else if (!strcmp(p, "--seed")) { | ||
1929 | if (argc == 0) { | ||
1930 | fprintf(stderr, "%s: --seed needs an argument", argv[0]); | ||
1931 | goto done; | ||
1932 | } | ||
1933 | seed = (time_t)atoi(*++argv); | ||
1934 | argc--; | ||
1935 | } else if (*p == '-') { | ||
1936 | fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0], p); | ||
1937 | return 1; | ||
1938 | } else { | ||
1939 | id = p; | ||
1940 | } | ||
1941 | } | ||
1942 | |||
1943 | rs = random_new((void*)&seed, sizeof(time_t)); | ||
1944 | |||
1945 | if (!id) { | ||
1946 | fprintf(stderr, "usage: %s [-v] [--soak] <params> | <game_id>\n", argv[0]); | ||
1947 | goto done; | ||
1948 | } | ||
1949 | desc = strchr(id, ':'); | ||
1950 | if (desc) *desc++ = '\0'; | ||
1951 | |||
1952 | p = default_params(); | ||
1953 | decode_params(p, id); | ||
1954 | err = validate_params(p, 1); | ||
1955 | if (err) { | ||
1956 | fprintf(stderr, "%s: %s", argv[0], err); | ||
1957 | goto done; | ||
1958 | } | ||
1959 | |||
1960 | if (soak) { | ||
1961 | if (desc) { | ||
1962 | fprintf(stderr, "%s: --soak only needs params, not game desc.\n", argv[0]); | ||
1963 | goto done; | ||
1964 | } | ||
1965 | start_soak(p, rs); | ||
1966 | } else { | ||
1967 | if (!desc) desc = desc_gen = new_game_desc(p, rs, &aux, 0); | ||
1968 | |||
1969 | err = validate_desc(p, desc); | ||
1970 | if (err) { | ||
1971 | fprintf(stderr, "%s: %s\n", argv[0], err); | ||
1972 | free_params(p); | ||
1973 | goto done; | ||
1974 | } | ||
1975 | s = new_game(NULL, p, desc); | ||
1976 | |||
1977 | if (verbose) { | ||
1978 | tgame = game_text_format(s); | ||
1979 | fputs(tgame, stdout); | ||
1980 | sfree(tgame); | ||
1981 | } | ||
1982 | |||
1983 | soln = solve_specific(s, DIFF_ANY, 0); | ||
1984 | tgame = game_text_format(s); | ||
1985 | fputs(tgame, stdout); | ||
1986 | sfree(tgame); | ||
1987 | printf("Game was %s.\n\n", | ||
1988 | soln < 0 ? "impossible" : soln > 0 ? "solved" : "not solved"); | ||
1989 | } | ||
1990 | ret = 0; | ||
1991 | |||
1992 | done: | ||
1993 | if (desc_gen) sfree(desc_gen); | ||
1994 | if (p) free_params(p); | ||
1995 | if (s) free_game(s); | ||
1996 | if (rs) random_free(rs); | ||
1997 | |||
1998 | return ret; | ||
1999 | } | ||
2000 | |||
2001 | #endif | ||
2002 | |||
2003 | |||
2004 | /* vim: set shiftwidth=4 tabstop=8: */ | ||