diff options
Diffstat (limited to 'apps/plugins/puzzles/unruly.c')
-rw-r--r-- | apps/plugins/puzzles/unruly.c | 2071 |
1 files changed, 2071 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/unruly.c b/apps/plugins/puzzles/unruly.c new file mode 100644 index 0000000000..aea4cdf789 --- /dev/null +++ b/apps/plugins/puzzles/unruly.c | |||
@@ -0,0 +1,2071 @@ | |||
1 | /* | ||
2 | * unruly.c: Implementation for Binary Puzzles. | ||
3 | * (C) 2012 Lennard Sprong | ||
4 | * Created for Simon Tatham's Portable Puzzle Collection | ||
5 | * See LICENCE for licence details | ||
6 | * | ||
7 | * Objective of the game: Fill the grid with zeros and ones, with the | ||
8 | * following rules: | ||
9 | * - There can't be a run of three or more equal numbers. | ||
10 | * - Each row and column contains an equal amount of zeros and ones. | ||
11 | * | ||
12 | * This puzzle type is known under several names, including | ||
13 | * Tohu-Wa-Vohu, One and Two and Binairo. | ||
14 | * | ||
15 | * Some variants include an extra constraint, stating that no two rows or two | ||
16 | * columns may contain the same exact sequence of zeros and ones. | ||
17 | * This rule is rarely used, so it is not enabled in the default presets | ||
18 | * (but it can be selected via the Custom configurer). | ||
19 | * | ||
20 | * More information: | ||
21 | * http://www.janko.at/Raetsel/Tohu-Wa-Vohu/index.htm | ||
22 | */ | ||
23 | |||
24 | /* | ||
25 | * Possible future improvements: | ||
26 | * | ||
27 | * More solver cleverness | ||
28 | * | ||
29 | * - a counting-based deduction in which you find groups of squares | ||
30 | * which must each contain at least one of a given colour, plus | ||
31 | * other squares which are already known to be that colour, and see | ||
32 | * if you have any squares left over when you've worked out where | ||
33 | * they all have to be. This is a generalisation of the current | ||
34 | * check_near_complete: where that only covers rows with three | ||
35 | * unfilled squares, this would handle more, such as | ||
36 | * 0 . . 1 0 1 . . 0 . | ||
37 | * in which each of the two-square gaps must contain a 0, and there | ||
38 | * are three 0s placed, and that means the rightmost square can't | ||
39 | * be a 0. | ||
40 | * | ||
41 | * - an 'Unreasonable' difficulty level, supporting recursion and | ||
42 | * backtracking. | ||
43 | */ | ||
44 | |||
45 | #include <stdio.h> | ||
46 | #include <stdlib.h> | ||
47 | #include <string.h> | ||
48 | #include "rbassert.h" | ||
49 | #include <ctype.h> | ||
50 | #include <math.h> | ||
51 | |||
52 | #include "puzzles.h" | ||
53 | |||
54 | #ifdef STANDALONE_SOLVER | ||
55 | int solver_verbose = FALSE; | ||
56 | #endif | ||
57 | |||
58 | enum { | ||
59 | COL_BACKGROUND, | ||
60 | COL_GRID, | ||
61 | COL_EMPTY, | ||
62 | /* | ||
63 | * When editing this enum, maintain the invariants | ||
64 | * COL_n_HIGHLIGHT = COL_n + 1 | ||
65 | * COL_n_LOWLIGHT = COL_n + 2 | ||
66 | */ | ||
67 | COL_0, | ||
68 | COL_0_HIGHLIGHT, | ||
69 | COL_0_LOWLIGHT, | ||
70 | COL_1, | ||
71 | COL_1_HIGHLIGHT, | ||
72 | COL_1_LOWLIGHT, | ||
73 | COL_CURSOR, | ||
74 | COL_ERROR, | ||
75 | NCOLOURS | ||
76 | }; | ||
77 | |||
78 | struct game_params { | ||
79 | int w2, h2; /* full grid width and height respectively */ | ||
80 | int unique; /* should row and column patterns be unique? */ | ||
81 | int diff; | ||
82 | }; | ||
83 | #define DIFFLIST(A) \ | ||
84 | A(EASY,Easy, e) \ | ||
85 | A(NORMAL,Normal, n) \ | ||
86 | |||
87 | #define ENUM(upper,title,lower) DIFF_ ## upper, | ||
88 | #define TITLE(upper,title,lower) #title, | ||
89 | #define ENCODE(upper,title,lower) #lower | ||
90 | #define CONFIG(upper,title,lower) ":" #title | ||
91 | enum { DIFFLIST(ENUM) DIFFCOUNT }; | ||
92 | static char const *const unruly_diffnames[] = { DIFFLIST(TITLE) }; | ||
93 | |||
94 | static char const unruly_diffchars[] = DIFFLIST(ENCODE); | ||
95 | #define DIFFCONFIG DIFFLIST(CONFIG) | ||
96 | |||
97 | const static struct game_params unruly_presets[] = { | ||
98 | { 8, 8, FALSE, DIFF_EASY}, | ||
99 | { 8, 8, FALSE, DIFF_NORMAL}, | ||
100 | {10, 10, FALSE, DIFF_EASY}, | ||
101 | {10, 10, FALSE, DIFF_NORMAL}, | ||
102 | {14, 14, FALSE, DIFF_EASY}, | ||
103 | {14, 14, FALSE, DIFF_NORMAL} | ||
104 | }; | ||
105 | |||
106 | #define DEFAULT_PRESET 0 | ||
107 | |||
108 | enum { | ||
109 | EMPTY, | ||
110 | N_ONE, | ||
111 | N_ZERO, | ||
112 | BOGUS | ||
113 | }; | ||
114 | |||
115 | #define FE_HOR_ROW_LEFT 0x0001 | ||
116 | #define FE_HOR_ROW_MID 0x0003 | ||
117 | #define FE_HOR_ROW_RIGHT 0x0002 | ||
118 | |||
119 | #define FE_VER_ROW_TOP 0x0004 | ||
120 | #define FE_VER_ROW_MID 0x000C | ||
121 | #define FE_VER_ROW_BOTTOM 0x0008 | ||
122 | |||
123 | #define FE_COUNT 0x0010 | ||
124 | |||
125 | #define FE_ROW_MATCH 0x0020 | ||
126 | #define FE_COL_MATCH 0x0040 | ||
127 | |||
128 | #define FF_ONE 0x0080 | ||
129 | #define FF_ZERO 0x0100 | ||
130 | #define FF_CURSOR 0x0200 | ||
131 | |||
132 | #define FF_FLASH1 0x0400 | ||
133 | #define FF_FLASH2 0x0800 | ||
134 | #define FF_IMMUTABLE 0x1000 | ||
135 | |||
136 | struct game_state { | ||
137 | int w2, h2; | ||
138 | int unique; | ||
139 | char *grid; | ||
140 | unsigned char *immutable; | ||
141 | |||
142 | int completed, cheated; | ||
143 | }; | ||
144 | |||
145 | static game_params *default_params(void) | ||
146 | { | ||
147 | game_params *ret = snew(game_params); | ||
148 | |||
149 | *ret = unruly_presets[DEFAULT_PRESET]; /* structure copy */ | ||
150 | |||
151 | return ret; | ||
152 | } | ||
153 | |||
154 | static int game_fetch_preset(int i, char **name, game_params **params) | ||
155 | { | ||
156 | game_params *ret; | ||
157 | char buf[80]; | ||
158 | |||
159 | if (i < 0 || i >= lenof(unruly_presets)) | ||
160 | return FALSE; | ||
161 | |||
162 | ret = snew(game_params); | ||
163 | *ret = unruly_presets[i]; /* structure copy */ | ||
164 | |||
165 | sprintf(buf, "%dx%d %s", ret->w2, ret->h2, unruly_diffnames[ret->diff]); | ||
166 | |||
167 | *name = dupstr(buf); | ||
168 | *params = ret; | ||
169 | return TRUE; | ||
170 | } | ||
171 | |||
172 | static void free_params(game_params *params) | ||
173 | { | ||
174 | sfree(params); | ||
175 | } | ||
176 | |||
177 | static game_params *dup_params(const game_params *params) | ||
178 | { | ||
179 | game_params *ret = snew(game_params); | ||
180 | *ret = *params; /* structure copy */ | ||
181 | return ret; | ||
182 | } | ||
183 | |||
184 | static void decode_params(game_params *params, char const *string) | ||
185 | { | ||
186 | char const *p = string; | ||
187 | |||
188 | params->unique = FALSE; | ||
189 | |||
190 | params->w2 = atoi(p); | ||
191 | while (*p && isdigit((unsigned char)*p)) p++; | ||
192 | if (*p == 'x') { | ||
193 | p++; | ||
194 | params->h2 = atoi(p); | ||
195 | while (*p && isdigit((unsigned char)*p)) p++; | ||
196 | } else { | ||
197 | params->h2 = params->w2; | ||
198 | } | ||
199 | |||
200 | if (*p == 'u') { | ||
201 | p++; | ||
202 | params->unique = TRUE; | ||
203 | } | ||
204 | |||
205 | if (*p == 'd') { | ||
206 | int i; | ||
207 | p++; | ||
208 | params->diff = DIFFCOUNT + 1; /* ...which is invalid */ | ||
209 | if (*p) { | ||
210 | for (i = 0; i < DIFFCOUNT; i++) { | ||
211 | if (*p == unruly_diffchars[i]) | ||
212 | params->diff = i; | ||
213 | } | ||
214 | p++; | ||
215 | } | ||
216 | } | ||
217 | } | ||
218 | |||
219 | static char *encode_params(const game_params *params, int full) | ||
220 | { | ||
221 | char buf[80]; | ||
222 | |||
223 | sprintf(buf, "%dx%d", params->w2, params->h2); | ||
224 | if (params->unique) | ||
225 | strcat(buf, "u"); | ||
226 | if (full) | ||
227 | sprintf(buf + strlen(buf), "d%c", unruly_diffchars[params->diff]); | ||
228 | |||
229 | return dupstr(buf); | ||
230 | } | ||
231 | |||
232 | static config_item *game_configure(const game_params *params) | ||
233 | { | ||
234 | config_item *ret; | ||
235 | char buf[80]; | ||
236 | |||
237 | ret = snewn(5, config_item); | ||
238 | |||
239 | ret[0].name = "Width"; | ||
240 | ret[0].type = C_STRING; | ||
241 | sprintf(buf, "%d", params->w2); | ||
242 | ret[0].sval = dupstr(buf); | ||
243 | ret[0].ival = 0; | ||
244 | |||
245 | ret[1].name = "Height"; | ||
246 | ret[1].type = C_STRING; | ||
247 | sprintf(buf, "%d", params->h2); | ||
248 | ret[1].sval = dupstr(buf); | ||
249 | ret[1].ival = 0; | ||
250 | |||
251 | ret[2].name = "Unique rows and columns"; | ||
252 | ret[2].type = C_BOOLEAN; | ||
253 | ret[2].ival = params->unique; | ||
254 | |||
255 | ret[3].name = "Difficulty"; | ||
256 | ret[3].type = C_CHOICES; | ||
257 | ret[3].sval = DIFFCONFIG; | ||
258 | ret[3].ival = params->diff; | ||
259 | |||
260 | ret[4].name = NULL; | ||
261 | ret[4].type = C_END; | ||
262 | ret[4].sval = NULL; | ||
263 | ret[4].ival = 0; | ||
264 | |||
265 | return ret; | ||
266 | } | ||
267 | |||
268 | static game_params *custom_params(const config_item *cfg) | ||
269 | { | ||
270 | game_params *ret = snew(game_params); | ||
271 | |||
272 | ret->w2 = atoi(cfg[0].sval); | ||
273 | ret->h2 = atoi(cfg[1].sval); | ||
274 | ret->unique = cfg[2].ival; | ||
275 | ret->diff = cfg[3].ival; | ||
276 | |||
277 | return ret; | ||
278 | } | ||
279 | |||
280 | static char *validate_params(const game_params *params, int full) | ||
281 | { | ||
282 | if ((params->w2 & 1) || (params->h2 & 1)) | ||
283 | return "Width and height must both be even"; | ||
284 | if (params->w2 < 6 || params->h2 < 6) | ||
285 | return "Width and height must be at least 6"; | ||
286 | if (params->unique) { | ||
287 | static const long A177790[] = { | ||
288 | /* | ||
289 | * The nth element of this array gives the number of | ||
290 | * distinct possible Unruly rows of length 2n (that is, | ||
291 | * containing exactly n 1s and n 0s and not containing | ||
292 | * three consecutive elements the same) for as long as | ||
293 | * those numbers fit in a 32-bit signed int. | ||
294 | * | ||
295 | * So in unique-rows mode, if the puzzle width is 2n, then | ||
296 | * the height must be at most (this array)[n], and vice | ||
297 | * versa. | ||
298 | * | ||
299 | * This is sequence A177790 in the Online Encyclopedia of | ||
300 | * Integer Sequences: http://oeis.org/A177790 | ||
301 | */ | ||
302 | 1L, 2L, 6L, 14L, 34L, 84L, 208L, 518L, 1296L, 3254L, | ||
303 | 8196L, 20700L, 52404L, 132942L, 337878L, 860142L, | ||
304 | 2192902L, 5598144L, 14308378L, 36610970L, 93770358L, | ||
305 | 240390602L, 616787116L, 1583765724L | ||
306 | }; | ||
307 | if (params->w2 < 2*lenof(A177790) && | ||
308 | params->h2 > A177790[params->w2/2]) { | ||
309 | return "Puzzle is too tall for unique-rows mode"; | ||
310 | } | ||
311 | if (params->h2 < 2*lenof(A177790) && | ||
312 | params->w2 > A177790[params->h2/2]) { | ||
313 | return "Puzzle is too long for unique-rows mode"; | ||
314 | } | ||
315 | } | ||
316 | if (params->diff >= DIFFCOUNT) | ||
317 | return "Unknown difficulty rating"; | ||
318 | |||
319 | return NULL; | ||
320 | } | ||
321 | |||
322 | static char *validate_desc(const game_params *params, const char *desc) | ||
323 | { | ||
324 | int w2 = params->w2, h2 = params->h2; | ||
325 | int s = w2 * h2; | ||
326 | |||
327 | const char *p = desc; | ||
328 | int pos = 0; | ||
329 | |||
330 | while (*p) { | ||
331 | if (*p >= 'a' && *p < 'z') | ||
332 | pos += 1 + (*p - 'a'); | ||
333 | else if (*p >= 'A' && *p < 'Z') | ||
334 | pos += 1 + (*p - 'A'); | ||
335 | else if (*p == 'Z' || *p == 'z') | ||
336 | pos += 25; | ||
337 | else | ||
338 | return "Description contains invalid characters"; | ||
339 | |||
340 | ++p; | ||
341 | } | ||
342 | |||
343 | if (pos < s+1) | ||
344 | return "Description too short"; | ||
345 | if (pos > s+1) | ||
346 | return "Description too long"; | ||
347 | |||
348 | return NULL; | ||
349 | } | ||
350 | |||
351 | static game_state *blank_state(int w2, int h2, int unique) | ||
352 | { | ||
353 | game_state *state = snew(game_state); | ||
354 | int s = w2 * h2; | ||
355 | |||
356 | state->w2 = w2; | ||
357 | state->h2 = h2; | ||
358 | state->unique = unique; | ||
359 | state->grid = snewn(s, char); | ||
360 | state->immutable = snewn(s, unsigned char); | ||
361 | |||
362 | memset(state->grid, EMPTY, s); | ||
363 | memset(state->immutable, FALSE, s); | ||
364 | |||
365 | state->completed = state->cheated = FALSE; | ||
366 | |||
367 | return state; | ||
368 | } | ||
369 | |||
370 | static game_state *new_game(midend *me, const game_params *params, | ||
371 | const char *desc) | ||
372 | { | ||
373 | int w2 = params->w2, h2 = params->h2; | ||
374 | int s = w2 * h2; | ||
375 | |||
376 | game_state *state = blank_state(w2, h2, params->unique); | ||
377 | |||
378 | const char *p = desc; | ||
379 | int pos = 0; | ||
380 | |||
381 | while (*p) { | ||
382 | if (*p >= 'a' && *p < 'z') { | ||
383 | pos += (*p - 'a'); | ||
384 | if (pos < s) { | ||
385 | state->grid[pos] = N_ZERO; | ||
386 | state->immutable[pos] = TRUE; | ||
387 | } | ||
388 | pos++; | ||
389 | } else if (*p >= 'A' && *p < 'Z') { | ||
390 | pos += (*p - 'A'); | ||
391 | if (pos < s) { | ||
392 | state->grid[pos] = N_ONE; | ||
393 | state->immutable[pos] = TRUE; | ||
394 | } | ||
395 | pos++; | ||
396 | } else if (*p == 'Z' || *p == 'z') { | ||
397 | pos += 25; | ||
398 | } else | ||
399 | assert(!"Description contains invalid characters"); | ||
400 | |||
401 | ++p; | ||
402 | } | ||
403 | assert(pos == s+1); | ||
404 | |||
405 | return state; | ||
406 | } | ||
407 | |||
408 | static game_state *dup_game(const game_state *state) | ||
409 | { | ||
410 | int w2 = state->w2, h2 = state->h2; | ||
411 | int s = w2 * h2; | ||
412 | |||
413 | game_state *ret = blank_state(w2, h2, state->unique); | ||
414 | |||
415 | memcpy(ret->grid, state->grid, s); | ||
416 | memcpy(ret->immutable, state->immutable, s); | ||
417 | |||
418 | ret->completed = state->completed; | ||
419 | ret->cheated = state->cheated; | ||
420 | |||
421 | return ret; | ||
422 | } | ||
423 | |||
424 | static void free_game(game_state *state) | ||
425 | { | ||
426 | sfree(state->grid); | ||
427 | sfree(state->immutable); | ||
428 | |||
429 | sfree(state); | ||
430 | } | ||
431 | |||
432 | static int game_can_format_as_text_now(const game_params *params) | ||
433 | { | ||
434 | return TRUE; | ||
435 | } | ||
436 | |||
437 | static char *game_text_format(const game_state *state) | ||
438 | { | ||
439 | int w2 = state->w2, h2 = state->h2; | ||
440 | int lr = w2*2 + 1; | ||
441 | |||
442 | char *ret = snewn(lr * h2 + 1, char); | ||
443 | char *p = ret; | ||
444 | |||
445 | int x, y; | ||
446 | for (y = 0; y < h2; y++) { | ||
447 | for (x = 0; x < w2; x++) { | ||
448 | /* Place number */ | ||
449 | char c = state->grid[y * w2 + x]; | ||
450 | *p++ = (c == N_ONE ? '1' : c == N_ZERO ? '0' : '.'); | ||
451 | *p++ = ' '; | ||
452 | } | ||
453 | /* End line */ | ||
454 | *p++ = '\n'; | ||
455 | } | ||
456 | /* End with NUL */ | ||
457 | *p++ = '\0'; | ||
458 | |||
459 | return ret; | ||
460 | } | ||
461 | |||
462 | /* ****** * | ||
463 | * Solver * | ||
464 | * ****** */ | ||
465 | |||
466 | struct unruly_scratch { | ||
467 | int *ones_rows; | ||
468 | int *ones_cols; | ||
469 | int *zeros_rows; | ||
470 | int *zeros_cols; | ||
471 | }; | ||
472 | |||
473 | static void unruly_solver_update_remaining(const game_state *state, | ||
474 | struct unruly_scratch *scratch) | ||
475 | { | ||
476 | int w2 = state->w2, h2 = state->h2; | ||
477 | int x, y; | ||
478 | |||
479 | /* Reset all scratch data */ | ||
480 | memset(scratch->ones_rows, 0, h2 * sizeof(int)); | ||
481 | memset(scratch->ones_cols, 0, w2 * sizeof(int)); | ||
482 | memset(scratch->zeros_rows, 0, h2 * sizeof(int)); | ||
483 | memset(scratch->zeros_cols, 0, w2 * sizeof(int)); | ||
484 | |||
485 | for (x = 0; x < w2; x++) | ||
486 | for (y = 0; y < h2; y++) { | ||
487 | if (state->grid[y * w2 + x] == N_ONE) { | ||
488 | scratch->ones_rows[y]++; | ||
489 | scratch->ones_cols[x]++; | ||
490 | } else if (state->grid[y * w2 + x] == N_ZERO) { | ||
491 | scratch->zeros_rows[y]++; | ||
492 | scratch->zeros_cols[x]++; | ||
493 | } | ||
494 | } | ||
495 | } | ||
496 | |||
497 | static struct unruly_scratch *unruly_new_scratch(const game_state *state) | ||
498 | { | ||
499 | int w2 = state->w2, h2 = state->h2; | ||
500 | |||
501 | struct unruly_scratch *ret = snew(struct unruly_scratch); | ||
502 | |||
503 | ret->ones_rows = snewn(h2, int); | ||
504 | ret->ones_cols = snewn(w2, int); | ||
505 | ret->zeros_rows = snewn(h2, int); | ||
506 | ret->zeros_cols = snewn(w2, int); | ||
507 | |||
508 | unruly_solver_update_remaining(state, ret); | ||
509 | |||
510 | return ret; | ||
511 | } | ||
512 | |||
513 | static void unruly_free_scratch(struct unruly_scratch *scratch) | ||
514 | { | ||
515 | sfree(scratch->ones_rows); | ||
516 | sfree(scratch->ones_cols); | ||
517 | sfree(scratch->zeros_rows); | ||
518 | sfree(scratch->zeros_cols); | ||
519 | |||
520 | sfree(scratch); | ||
521 | } | ||
522 | |||
523 | static int unruly_solver_check_threes(game_state *state, int *rowcount, | ||
524 | int *colcount, int horizontal, | ||
525 | char check, char block) | ||
526 | { | ||
527 | int w2 = state->w2, h2 = state->h2; | ||
528 | |||
529 | int dx = horizontal ? 1 : 0, dy = 1 - dx; | ||
530 | int sx = dx, sy = dy; | ||
531 | int ex = w2 - dx, ey = h2 - dy; | ||
532 | |||
533 | int x, y; | ||
534 | int ret = 0; | ||
535 | |||
536 | /* Check for any three squares which almost form three in a row */ | ||
537 | for (y = sy; y < ey; y++) { | ||
538 | for (x = sx; x < ex; x++) { | ||
539 | int i1 = (y-dy) * w2 + (x-dx); | ||
540 | int i2 = y * w2 + x; | ||
541 | int i3 = (y+dy) * w2 + (x+dx); | ||
542 | |||
543 | if (state->grid[i1] == check && state->grid[i2] == check | ||
544 | && state->grid[i3] == EMPTY) { | ||
545 | ret++; | ||
546 | #ifdef STANDALONE_SOLVER | ||
547 | if (solver_verbose) { | ||
548 | printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n", | ||
549 | i1 % w2, i1 / w2, i2 % w2, i2 / w2, | ||
550 | (block == N_ONE ? '1' : '0'), i3 % w2, | ||
551 | i3 / w2); | ||
552 | } | ||
553 | #endif | ||
554 | state->grid[i3] = block; | ||
555 | rowcount[i3 / w2]++; | ||
556 | colcount[i3 % w2]++; | ||
557 | } | ||
558 | if (state->grid[i1] == check && state->grid[i2] == EMPTY | ||
559 | && state->grid[i3] == check) { | ||
560 | ret++; | ||
561 | #ifdef STANDALONE_SOLVER | ||
562 | if (solver_verbose) { | ||
563 | printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n", | ||
564 | i1 % w2, i1 / w2, i3 % w2, i3 / w2, | ||
565 | (block == N_ONE ? '1' : '0'), i2 % w2, | ||
566 | i2 / w2); | ||
567 | } | ||
568 | #endif | ||
569 | state->grid[i2] = block; | ||
570 | rowcount[i2 / w2]++; | ||
571 | colcount[i2 % w2]++; | ||
572 | } | ||
573 | if (state->grid[i1] == EMPTY && state->grid[i2] == check | ||
574 | && state->grid[i3] == check) { | ||
575 | ret++; | ||
576 | #ifdef STANDALONE_SOLVER | ||
577 | if (solver_verbose) { | ||
578 | printf("Solver: %i,%i and %i,%i confirm %c at %i,%i\n", | ||
579 | i2 % w2, i2 / w2, i3 % w2, i3 / w2, | ||
580 | (block == N_ONE ? '1' : '0'), i1 % w2, | ||
581 | i1 / w2); | ||
582 | } | ||
583 | #endif | ||
584 | state->grid[i1] = block; | ||
585 | rowcount[i1 / w2]++; | ||
586 | colcount[i1 % w2]++; | ||
587 | } | ||
588 | } | ||
589 | } | ||
590 | |||
591 | return ret; | ||
592 | } | ||
593 | |||
594 | static int unruly_solver_check_all_threes(game_state *state, | ||
595 | struct unruly_scratch *scratch) | ||
596 | { | ||
597 | int ret = 0; | ||
598 | |||
599 | ret += | ||
600 | unruly_solver_check_threes(state, scratch->zeros_rows, | ||
601 | scratch->zeros_cols, TRUE, N_ONE, N_ZERO); | ||
602 | ret += | ||
603 | unruly_solver_check_threes(state, scratch->ones_rows, | ||
604 | scratch->ones_cols, TRUE, N_ZERO, N_ONE); | ||
605 | ret += | ||
606 | unruly_solver_check_threes(state, scratch->zeros_rows, | ||
607 | scratch->zeros_cols, FALSE, N_ONE, | ||
608 | N_ZERO); | ||
609 | ret += | ||
610 | unruly_solver_check_threes(state, scratch->ones_rows, | ||
611 | scratch->ones_cols, FALSE, N_ZERO, N_ONE); | ||
612 | |||
613 | return ret; | ||
614 | } | ||
615 | |||
616 | static int unruly_solver_check_uniques(game_state *state, int *rowcount, | ||
617 | int horizontal, char check, char block, | ||
618 | struct unruly_scratch *scratch) | ||
619 | { | ||
620 | int w2 = state->w2, h2 = state->h2; | ||
621 | |||
622 | int rmult = (horizontal ? w2 : 1); | ||
623 | int cmult = (horizontal ? 1 : w2); | ||
624 | int nr = (horizontal ? h2 : w2); | ||
625 | int nc = (horizontal ? w2 : h2); | ||
626 | int max = nc / 2; | ||
627 | |||
628 | int r, r2, c; | ||
629 | int ret = 0; | ||
630 | |||
631 | /* | ||
632 | * Find each row that has max entries of type 'check', and see if | ||
633 | * all those entries match those in any row with max-1 entries. If | ||
634 | * so, set the last non-matching entry of the latter row to ensure | ||
635 | * that it's different. | ||
636 | */ | ||
637 | for (r = 0; r < nr; r++) { | ||
638 | if (rowcount[r] != max) | ||
639 | continue; | ||
640 | for (r2 = 0; r2 < nr; r2++) { | ||
641 | int nmatch = 0, nonmatch = -1; | ||
642 | if (rowcount[r2] != max-1) | ||
643 | continue; | ||
644 | for (c = 0; c < nc; c++) { | ||
645 | if (state->grid[r*rmult + c*cmult] == check) { | ||
646 | if (state->grid[r2*rmult + c*cmult] == check) | ||
647 | nmatch++; | ||
648 | else | ||
649 | nonmatch = c; | ||
650 | } | ||
651 | } | ||
652 | if (nmatch == max-1) { | ||
653 | int i1 = r2 * rmult + nonmatch * cmult; | ||
654 | assert(nonmatch != -1); | ||
655 | if (state->grid[i1] == block) | ||
656 | continue; | ||
657 | assert(state->grid[i1] == EMPTY); | ||
658 | #ifdef STANDALONE_SOLVER | ||
659 | if (solver_verbose) { | ||
660 | printf("Solver: matching %s %i, %i gives %c at %i,%i\n", | ||
661 | horizontal ? "rows" : "cols", | ||
662 | r, r2, (block == N_ONE ? '1' : '0'), i1 % w2, | ||
663 | i1 / w2); | ||
664 | } | ||
665 | #endif | ||
666 | state->grid[i1] = block; | ||
667 | if (block == N_ONE) { | ||
668 | scratch->ones_rows[i1 / w2]++; | ||
669 | scratch->ones_cols[i1 % w2]++; | ||
670 | } else { | ||
671 | scratch->zeros_rows[i1 / w2]++; | ||
672 | scratch->zeros_cols[i1 % w2]++; | ||
673 | } | ||
674 | ret++; | ||
675 | } | ||
676 | } | ||
677 | } | ||
678 | return ret; | ||
679 | } | ||
680 | |||
681 | static int unruly_solver_check_all_uniques(game_state *state, | ||
682 | struct unruly_scratch *scratch) | ||
683 | { | ||
684 | int ret = 0; | ||
685 | |||
686 | ret += unruly_solver_check_uniques(state, scratch->ones_rows, | ||
687 | TRUE, N_ONE, N_ZERO, scratch); | ||
688 | ret += unruly_solver_check_uniques(state, scratch->zeros_rows, | ||
689 | TRUE, N_ZERO, N_ONE, scratch); | ||
690 | ret += unruly_solver_check_uniques(state, scratch->ones_cols, | ||
691 | FALSE, N_ONE, N_ZERO, scratch); | ||
692 | ret += unruly_solver_check_uniques(state, scratch->zeros_cols, | ||
693 | FALSE, N_ZERO, N_ONE, scratch); | ||
694 | |||
695 | return ret; | ||
696 | } | ||
697 | |||
698 | static int unruly_solver_fill_row(game_state *state, int i, int horizontal, | ||
699 | int *rowcount, int *colcount, char fill) | ||
700 | { | ||
701 | int ret = 0; | ||
702 | int w2 = state->w2, h2 = state->h2; | ||
703 | int j; | ||
704 | |||
705 | #ifdef STANDALONE_SOLVER | ||
706 | if (solver_verbose) { | ||
707 | printf("Solver: Filling %s %i with %c:", | ||
708 | (horizontal ? "Row" : "Col"), i, | ||
709 | (fill == N_ZERO ? '0' : '1')); | ||
710 | } | ||
711 | #endif | ||
712 | /* Place a number in every empty square in a row/column */ | ||
713 | for (j = 0; j < (horizontal ? w2 : h2); j++) { | ||
714 | int p = (horizontal ? i * w2 + j : j * w2 + i); | ||
715 | |||
716 | if (state->grid[p] == EMPTY) { | ||
717 | #ifdef STANDALONE_SOLVER | ||
718 | if (solver_verbose) { | ||
719 | printf(" (%i,%i)", (horizontal ? j : i), | ||
720 | (horizontal ? i : j)); | ||
721 | } | ||
722 | #endif | ||
723 | ret++; | ||
724 | state->grid[p] = fill; | ||
725 | rowcount[(horizontal ? i : j)]++; | ||
726 | colcount[(horizontal ? j : i)]++; | ||
727 | } | ||
728 | } | ||
729 | |||
730 | #ifdef STANDALONE_SOLVER | ||
731 | if (solver_verbose) { | ||
732 | printf("\n"); | ||
733 | } | ||
734 | #endif | ||
735 | |||
736 | return ret; | ||
737 | } | ||
738 | |||
739 | static int unruly_solver_check_complete_nums(game_state *state, | ||
740 | int *complete, int horizontal, | ||
741 | int *rowcount, int *colcount, | ||
742 | char fill) | ||
743 | { | ||
744 | int w2 = state->w2, h2 = state->h2; | ||
745 | int count = (horizontal ? h2 : w2); /* number of rows to check */ | ||
746 | int target = (horizontal ? w2 : h2) / 2; /* target number of 0s/1s */ | ||
747 | int *other = (horizontal ? rowcount : colcount); | ||
748 | |||
749 | int ret = 0; | ||
750 | |||
751 | int i; | ||
752 | /* Check for completed rows/cols for one number, then fill in the rest */ | ||
753 | for (i = 0; i < count; i++) { | ||
754 | if (complete[i] == target && other[i] < target) { | ||
755 | #ifdef STANDALONE_SOLVER | ||
756 | if (solver_verbose) { | ||
757 | printf("Solver: Row %i satisfied for %c\n", i, | ||
758 | (fill != N_ZERO ? '0' : '1')); | ||
759 | } | ||
760 | #endif | ||
761 | ret += unruly_solver_fill_row(state, i, horizontal, rowcount, | ||
762 | colcount, fill); | ||
763 | } | ||
764 | } | ||
765 | |||
766 | return ret; | ||
767 | } | ||
768 | |||
769 | static int unruly_solver_check_all_complete_nums(game_state *state, | ||
770 | struct unruly_scratch *scratch) | ||
771 | { | ||
772 | int ret = 0; | ||
773 | |||
774 | ret += | ||
775 | unruly_solver_check_complete_nums(state, scratch->ones_rows, TRUE, | ||
776 | scratch->zeros_rows, | ||
777 | scratch->zeros_cols, N_ZERO); | ||
778 | ret += | ||
779 | unruly_solver_check_complete_nums(state, scratch->ones_cols, FALSE, | ||
780 | scratch->zeros_rows, | ||
781 | scratch->zeros_cols, N_ZERO); | ||
782 | ret += | ||
783 | unruly_solver_check_complete_nums(state, scratch->zeros_rows, TRUE, | ||
784 | scratch->ones_rows, | ||
785 | scratch->ones_cols, N_ONE); | ||
786 | ret += | ||
787 | unruly_solver_check_complete_nums(state, scratch->zeros_cols, FALSE, | ||
788 | scratch->ones_rows, | ||
789 | scratch->ones_cols, N_ONE); | ||
790 | |||
791 | return ret; | ||
792 | } | ||
793 | |||
794 | static int unruly_solver_check_near_complete(game_state *state, | ||
795 | int *complete, int horizontal, | ||
796 | int *rowcount, int *colcount, | ||
797 | char fill) | ||
798 | { | ||
799 | int w2 = state->w2, h2 = state->h2; | ||
800 | int w = w2/2, h = h2/2; | ||
801 | |||
802 | int dx = horizontal ? 1 : 0, dy = 1 - dx; | ||
803 | |||
804 | int sx = dx, sy = dy; | ||
805 | int ex = w2 - dx, ey = h2 - dy; | ||
806 | |||
807 | int x, y; | ||
808 | int ret = 0; | ||
809 | |||
810 | /* | ||
811 | * This function checks for a row with one Y remaining, then looks | ||
812 | * for positions that could cause the remaining squares in the row | ||
813 | * to make 3 X's in a row. Example: | ||
814 | * | ||
815 | * Consider the following row: | ||
816 | * 1 1 0 . . . | ||
817 | * If the last 1 was placed in the last square, the remaining | ||
818 | * squares would be 0: | ||
819 | * 1 1 0 0 0 1 | ||
820 | * This violates the 3 in a row rule. We now know that the last 1 | ||
821 | * shouldn't be in the last cell. | ||
822 | * 1 1 0 . . 0 | ||
823 | */ | ||
824 | |||
825 | /* Check for any two blank and one filled square */ | ||
826 | for (y = sy; y < ey; y++) { | ||
827 | /* One type must have 1 remaining, the other at least 2 */ | ||
828 | if (horizontal && (complete[y] < w - 1 || rowcount[y] > w - 2)) | ||
829 | continue; | ||
830 | |||
831 | for (x = sx; x < ex; x++) { | ||
832 | int i, i1, i2, i3; | ||
833 | if (!horizontal | ||
834 | && (complete[x] < h - 1 || colcount[x] > h - 2)) | ||
835 | continue; | ||
836 | |||
837 | i = (horizontal ? y : x); | ||
838 | i1 = (y-dy) * w2 + (x-dx); | ||
839 | i2 = y * w2 + x; | ||
840 | i3 = (y+dy) * w2 + (x+dx); | ||
841 | |||
842 | if (state->grid[i1] == fill && state->grid[i2] == EMPTY | ||
843 | && state->grid[i3] == EMPTY) { | ||
844 | /* | ||
845 | * Temporarily fill the empty spaces with something else. | ||
846 | * This avoids raising the counts for the row and column | ||
847 | */ | ||
848 | state->grid[i2] = BOGUS; | ||
849 | state->grid[i3] = BOGUS; | ||
850 | |||
851 | #ifdef STANDALONE_SOLVER | ||
852 | if (solver_verbose) { | ||
853 | printf("Solver: Row %i nearly satisfied for %c\n", i, | ||
854 | (fill != N_ZERO ? '0' : '1')); | ||
855 | } | ||
856 | #endif | ||
857 | ret += | ||
858 | unruly_solver_fill_row(state, i, horizontal, rowcount, | ||
859 | colcount, fill); | ||
860 | |||
861 | state->grid[i2] = EMPTY; | ||
862 | state->grid[i3] = EMPTY; | ||
863 | } | ||
864 | |||
865 | else if (state->grid[i1] == EMPTY && state->grid[i2] == fill | ||
866 | && state->grid[i3] == EMPTY) { | ||
867 | state->grid[i1] = BOGUS; | ||
868 | state->grid[i3] = BOGUS; | ||
869 | |||
870 | #ifdef STANDALONE_SOLVER | ||
871 | if (solver_verbose) { | ||
872 | printf("Solver: Row %i nearly satisfied for %c\n", i, | ||
873 | (fill != N_ZERO ? '0' : '1')); | ||
874 | } | ||
875 | #endif | ||
876 | ret += | ||
877 | unruly_solver_fill_row(state, i, horizontal, rowcount, | ||
878 | colcount, fill); | ||
879 | |||
880 | state->grid[i1] = EMPTY; | ||
881 | state->grid[i3] = EMPTY; | ||
882 | } | ||
883 | |||
884 | else if (state->grid[i1] == EMPTY && state->grid[i2] == EMPTY | ||
885 | && state->grid[i3] == fill) { | ||
886 | state->grid[i1] = BOGUS; | ||
887 | state->grid[i2] = BOGUS; | ||
888 | |||
889 | #ifdef STANDALONE_SOLVER | ||
890 | if (solver_verbose) { | ||
891 | printf("Solver: Row %i nearly satisfied for %c\n", i, | ||
892 | (fill != N_ZERO ? '0' : '1')); | ||
893 | } | ||
894 | #endif | ||
895 | ret += | ||
896 | unruly_solver_fill_row(state, i, horizontal, rowcount, | ||
897 | colcount, fill); | ||
898 | |||
899 | state->grid[i1] = EMPTY; | ||
900 | state->grid[i2] = EMPTY; | ||
901 | } | ||
902 | |||
903 | else if (state->grid[i1] == EMPTY && state->grid[i2] == EMPTY | ||
904 | && state->grid[i3] == EMPTY) { | ||
905 | state->grid[i1] = BOGUS; | ||
906 | state->grid[i2] = BOGUS; | ||
907 | state->grid[i3] = BOGUS; | ||
908 | |||
909 | #ifdef STANDALONE_SOLVER | ||
910 | if (solver_verbose) { | ||
911 | printf("Solver: Row %i nearly satisfied for %c\n", i, | ||
912 | (fill != N_ZERO ? '0' : '1')); | ||
913 | } | ||
914 | #endif | ||
915 | ret += | ||
916 | unruly_solver_fill_row(state, i, horizontal, rowcount, | ||
917 | colcount, fill); | ||
918 | |||
919 | state->grid[i1] = EMPTY; | ||
920 | state->grid[i2] = EMPTY; | ||
921 | state->grid[i3] = EMPTY; | ||
922 | } | ||
923 | } | ||
924 | } | ||
925 | |||
926 | return ret; | ||
927 | } | ||
928 | |||
929 | static int unruly_solver_check_all_near_complete(game_state *state, | ||
930 | struct unruly_scratch *scratch) | ||
931 | { | ||
932 | int ret = 0; | ||
933 | |||
934 | ret += | ||
935 | unruly_solver_check_near_complete(state, scratch->ones_rows, TRUE, | ||
936 | scratch->zeros_rows, | ||
937 | scratch->zeros_cols, N_ZERO); | ||
938 | ret += | ||
939 | unruly_solver_check_near_complete(state, scratch->ones_cols, FALSE, | ||
940 | scratch->zeros_rows, | ||
941 | scratch->zeros_cols, N_ZERO); | ||
942 | ret += | ||
943 | unruly_solver_check_near_complete(state, scratch->zeros_rows, TRUE, | ||
944 | scratch->ones_rows, | ||
945 | scratch->ones_cols, N_ONE); | ||
946 | ret += | ||
947 | unruly_solver_check_near_complete(state, scratch->zeros_cols, FALSE, | ||
948 | scratch->ones_rows, | ||
949 | scratch->ones_cols, N_ONE); | ||
950 | |||
951 | return ret; | ||
952 | } | ||
953 | |||
954 | static int unruly_validate_rows(const game_state *state, int horizontal, | ||
955 | char check, int *errors) | ||
956 | { | ||
957 | int w2 = state->w2, h2 = state->h2; | ||
958 | |||
959 | int dx = horizontal ? 1 : 0, dy = 1 - dx; | ||
960 | |||
961 | int sx = dx, sy = dy; | ||
962 | int ex = w2 - dx, ey = h2 - dy; | ||
963 | |||
964 | int x, y; | ||
965 | int ret = 0; | ||
966 | |||
967 | int err1 = (horizontal ? FE_HOR_ROW_LEFT : FE_VER_ROW_TOP); | ||
968 | int err2 = (horizontal ? FE_HOR_ROW_MID : FE_VER_ROW_MID); | ||
969 | int err3 = (horizontal ? FE_HOR_ROW_RIGHT : FE_VER_ROW_BOTTOM); | ||
970 | |||
971 | /* Check for any three in a row, and mark errors accordingly (if | ||
972 | * required) */ | ||
973 | for (y = sy; y < ey; y++) { | ||
974 | for (x = sx; x < ex; x++) { | ||
975 | int i1 = (y-dy) * w2 + (x-dx); | ||
976 | int i2 = y * w2 + x; | ||
977 | int i3 = (y+dy) * w2 + (x+dx); | ||
978 | |||
979 | if (state->grid[i1] == check && state->grid[i2] == check | ||
980 | && state->grid[i3] == check) { | ||
981 | ret++; | ||
982 | if (errors) { | ||
983 | errors[i1] |= err1; | ||
984 | errors[i2] |= err2; | ||
985 | errors[i3] |= err3; | ||
986 | } | ||
987 | } | ||
988 | } | ||
989 | } | ||
990 | |||
991 | return ret; | ||
992 | } | ||
993 | |||
994 | static int unruly_validate_unique(const game_state *state, int horizontal, | ||
995 | int *errors) | ||
996 | { | ||
997 | int w2 = state->w2, h2 = state->h2; | ||
998 | |||
999 | int rmult = (horizontal ? w2 : 1); | ||
1000 | int cmult = (horizontal ? 1 : w2); | ||
1001 | int nr = (horizontal ? h2 : w2); | ||
1002 | int nc = (horizontal ? w2 : h2); | ||
1003 | int err = (horizontal ? FE_ROW_MATCH : FE_COL_MATCH); | ||
1004 | |||
1005 | int r, r2, c; | ||
1006 | int ret = 0; | ||
1007 | |||
1008 | /* Check for any two full rows matching exactly, and mark errors | ||
1009 | * accordingly (if required) */ | ||
1010 | for (r = 0; r < nr; r++) { | ||
1011 | int nfull = 0; | ||
1012 | for (c = 0; c < nc; c++) | ||
1013 | if (state->grid[r*rmult + c*cmult] != EMPTY) | ||
1014 | nfull++; | ||
1015 | if (nfull != nc) | ||
1016 | continue; | ||
1017 | for (r2 = r+1; r2 < nr; r2++) { | ||
1018 | int match = TRUE; | ||
1019 | for (c = 0; c < nc; c++) | ||
1020 | if (state->grid[r*rmult + c*cmult] != | ||
1021 | state->grid[r2*rmult + c*cmult]) | ||
1022 | match = FALSE; | ||
1023 | if (match) { | ||
1024 | if (errors) { | ||
1025 | for (c = 0; c < nc; c++) { | ||
1026 | errors[r*rmult + c*cmult] |= err; | ||
1027 | errors[r2*rmult + c*cmult] |= err; | ||
1028 | } | ||
1029 | } | ||
1030 | ret++; | ||
1031 | } | ||
1032 | } | ||
1033 | } | ||
1034 | |||
1035 | return ret; | ||
1036 | } | ||
1037 | |||
1038 | static int unruly_validate_all_rows(const game_state *state, int *errors) | ||
1039 | { | ||
1040 | int errcount = 0; | ||
1041 | |||
1042 | errcount += unruly_validate_rows(state, TRUE, N_ONE, errors); | ||
1043 | errcount += unruly_validate_rows(state, FALSE, N_ONE, errors); | ||
1044 | errcount += unruly_validate_rows(state, TRUE, N_ZERO, errors); | ||
1045 | errcount += unruly_validate_rows(state, FALSE, N_ZERO, errors); | ||
1046 | |||
1047 | if (state->unique) { | ||
1048 | errcount += unruly_validate_unique(state, TRUE, errors); | ||
1049 | errcount += unruly_validate_unique(state, FALSE, errors); | ||
1050 | } | ||
1051 | |||
1052 | if (errcount) | ||
1053 | return -1; | ||
1054 | return 0; | ||
1055 | } | ||
1056 | |||
1057 | static int unruly_validate_counts(const game_state *state, | ||
1058 | struct unruly_scratch *scratch, int *errors) | ||
1059 | { | ||
1060 | int w2 = state->w2, h2 = state->h2; | ||
1061 | int w = w2/2, h = h2/2; | ||
1062 | char below = FALSE; | ||
1063 | char above = FALSE; | ||
1064 | int i; | ||
1065 | |||
1066 | /* See if all rows/columns are satisfied. If one is exceeded, | ||
1067 | * mark it as an error (if required) | ||
1068 | */ | ||
1069 | |||
1070 | char hasscratch = TRUE; | ||
1071 | if (!scratch) { | ||
1072 | scratch = unruly_new_scratch(state); | ||
1073 | hasscratch = FALSE; | ||
1074 | } | ||
1075 | |||
1076 | for (i = 0; i < w2; i++) { | ||
1077 | if (scratch->ones_cols[i] < h) | ||
1078 | below = TRUE; | ||
1079 | if (scratch->zeros_cols[i] < h) | ||
1080 | below = TRUE; | ||
1081 | |||
1082 | if (scratch->ones_cols[i] > h) { | ||
1083 | above = TRUE; | ||
1084 | if (errors) | ||
1085 | errors[2*h2 + i] = TRUE; | ||
1086 | } else if (errors) | ||
1087 | errors[2*h2 + i] = FALSE; | ||
1088 | |||
1089 | if (scratch->zeros_cols[i] > h) { | ||
1090 | above = TRUE; | ||
1091 | if (errors) | ||
1092 | errors[2*h2 + w2 + i] = TRUE; | ||
1093 | } else if (errors) | ||
1094 | errors[2*h2 + w2 + i] = FALSE; | ||
1095 | } | ||
1096 | for (i = 0; i < h2; i++) { | ||
1097 | if (scratch->ones_rows[i] < w) | ||
1098 | below = TRUE; | ||
1099 | if (scratch->zeros_rows[i] < w) | ||
1100 | below = TRUE; | ||
1101 | |||
1102 | if (scratch->ones_rows[i] > w) { | ||
1103 | above = TRUE; | ||
1104 | if (errors) | ||
1105 | errors[i] = TRUE; | ||
1106 | } else if (errors) | ||
1107 | errors[i] = FALSE; | ||
1108 | |||
1109 | if (scratch->zeros_rows[i] > w) { | ||
1110 | above = TRUE; | ||
1111 | if (errors) | ||
1112 | errors[h2 + i] = TRUE; | ||
1113 | } else if (errors) | ||
1114 | errors[h2 + i] = FALSE; | ||
1115 | } | ||
1116 | |||
1117 | if (!hasscratch) | ||
1118 | unruly_free_scratch(scratch); | ||
1119 | |||
1120 | return (above ? -1 : below ? 1 : 0); | ||
1121 | } | ||
1122 | |||
1123 | static int unruly_solve_game(game_state *state, | ||
1124 | struct unruly_scratch *scratch, int diff) | ||
1125 | { | ||
1126 | int done, maxdiff = -1; | ||
1127 | |||
1128 | while (TRUE) { | ||
1129 | done = 0; | ||
1130 | |||
1131 | /* Check for impending 3's */ | ||
1132 | done += unruly_solver_check_all_threes(state, scratch); | ||
1133 | |||
1134 | /* Keep using the simpler techniques while they produce results */ | ||
1135 | if (done) { | ||
1136 | if (maxdiff < DIFF_EASY) | ||
1137 | maxdiff = DIFF_EASY; | ||
1138 | continue; | ||
1139 | } | ||
1140 | |||
1141 | /* Check for completed rows */ | ||
1142 | done += unruly_solver_check_all_complete_nums(state, scratch); | ||
1143 | |||
1144 | if (done) { | ||
1145 | if (maxdiff < DIFF_EASY) | ||
1146 | maxdiff = DIFF_EASY; | ||
1147 | continue; | ||
1148 | } | ||
1149 | |||
1150 | /* Check for impending failures of row/column uniqueness, if | ||
1151 | * it's enabled in this game mode */ | ||
1152 | if (state->unique) { | ||
1153 | done += unruly_solver_check_all_uniques(state, scratch); | ||
1154 | |||
1155 | if (done) { | ||
1156 | if (maxdiff < DIFF_EASY) | ||
1157 | maxdiff = DIFF_EASY; | ||
1158 | continue; | ||
1159 | } | ||
1160 | } | ||
1161 | |||
1162 | /* Normal techniques */ | ||
1163 | if (diff < DIFF_NORMAL) | ||
1164 | break; | ||
1165 | |||
1166 | /* Check for nearly completed rows */ | ||
1167 | done += unruly_solver_check_all_near_complete(state, scratch); | ||
1168 | |||
1169 | if (done) { | ||
1170 | if (maxdiff < DIFF_NORMAL) | ||
1171 | maxdiff = DIFF_NORMAL; | ||
1172 | continue; | ||
1173 | } | ||
1174 | |||
1175 | break; | ||
1176 | } | ||
1177 | return maxdiff; | ||
1178 | } | ||
1179 | |||
1180 | static char *solve_game(const game_state *state, const game_state *currstate, | ||
1181 | const char *aux, char **error) | ||
1182 | { | ||
1183 | game_state *solved = dup_game(state); | ||
1184 | struct unruly_scratch *scratch = unruly_new_scratch(solved); | ||
1185 | char *ret = NULL; | ||
1186 | int result; | ||
1187 | |||
1188 | unruly_solve_game(solved, scratch, DIFFCOUNT); | ||
1189 | |||
1190 | result = unruly_validate_counts(solved, scratch, NULL); | ||
1191 | if (unruly_validate_all_rows(solved, NULL) == -1) | ||
1192 | result = -1; | ||
1193 | |||
1194 | if (result == 0) { | ||
1195 | int w2 = solved->w2, h2 = solved->h2; | ||
1196 | int s = w2 * h2; | ||
1197 | char *p; | ||
1198 | int i; | ||
1199 | |||
1200 | ret = snewn(s + 2, char); | ||
1201 | p = ret; | ||
1202 | *p++ = 'S'; | ||
1203 | |||
1204 | for (i = 0; i < s; i++) | ||
1205 | *p++ = (solved->grid[i] == N_ONE ? '1' : '0'); | ||
1206 | |||
1207 | *p++ = '\0'; | ||
1208 | } else if (result == 1) | ||
1209 | *error = "No solution found."; | ||
1210 | else if (result == -1) | ||
1211 | *error = "Puzzle is invalid."; | ||
1212 | |||
1213 | free_game(solved); | ||
1214 | unruly_free_scratch(scratch); | ||
1215 | return ret; | ||
1216 | } | ||
1217 | |||
1218 | /* ********* * | ||
1219 | * Generator * | ||
1220 | * ********* */ | ||
1221 | |||
1222 | static int unruly_fill_game(game_state *state, struct unruly_scratch *scratch, | ||
1223 | random_state *rs) | ||
1224 | { | ||
1225 | |||
1226 | int w2 = state->w2, h2 = state->h2; | ||
1227 | int s = w2 * h2; | ||
1228 | int i, j; | ||
1229 | int *spaces; | ||
1230 | |||
1231 | #ifdef STANDALONE_SOLVER | ||
1232 | if (solver_verbose) { | ||
1233 | printf("Generator: Attempt to fill grid\n"); | ||
1234 | } | ||
1235 | #endif | ||
1236 | |||
1237 | /* Generate random array of spaces */ | ||
1238 | spaces = snewn(s, int); | ||
1239 | for (i = 0; i < s; i++) | ||
1240 | spaces[i] = i; | ||
1241 | shuffle(spaces, s, sizeof(*spaces), rs); | ||
1242 | |||
1243 | /* | ||
1244 | * Construct a valid filled grid by repeatedly picking an unfilled | ||
1245 | * space and fill it, then calling the solver to fill in any | ||
1246 | * spaces forced by the change. | ||
1247 | */ | ||
1248 | for (j = 0; j < s; j++) { | ||
1249 | i = spaces[j]; | ||
1250 | |||
1251 | if (state->grid[i] != EMPTY) | ||
1252 | continue; | ||
1253 | |||
1254 | if (random_upto(rs, 2)) { | ||
1255 | state->grid[i] = N_ONE; | ||
1256 | scratch->ones_rows[i / w2]++; | ||
1257 | scratch->ones_cols[i % w2]++; | ||
1258 | } else { | ||
1259 | state->grid[i] = N_ZERO; | ||
1260 | scratch->zeros_rows[i / w2]++; | ||
1261 | scratch->zeros_cols[i % w2]++; | ||
1262 | } | ||
1263 | |||
1264 | unruly_solve_game(state, scratch, DIFFCOUNT); | ||
1265 | } | ||
1266 | sfree(spaces); | ||
1267 | |||
1268 | if (unruly_validate_all_rows(state, NULL) != 0 | ||
1269 | || unruly_validate_counts(state, scratch, NULL) != 0) | ||
1270 | return FALSE; | ||
1271 | |||
1272 | return TRUE; | ||
1273 | } | ||
1274 | |||
1275 | static char *new_game_desc(const game_params *params, random_state *rs, | ||
1276 | char **aux, int interactive) | ||
1277 | { | ||
1278 | #ifdef STANDALONE_SOLVER | ||
1279 | char *debug; | ||
1280 | int temp_verbose = FALSE; | ||
1281 | #endif | ||
1282 | |||
1283 | int w2 = params->w2, h2 = params->h2; | ||
1284 | int s = w2 * h2; | ||
1285 | int *spaces; | ||
1286 | int i, j, run; | ||
1287 | char *ret, *p; | ||
1288 | |||
1289 | game_state *state; | ||
1290 | struct unruly_scratch *scratch; | ||
1291 | |||
1292 | int attempts = 0; | ||
1293 | |||
1294 | while (1) { | ||
1295 | |||
1296 | while (TRUE) { | ||
1297 | attempts++; | ||
1298 | state = blank_state(w2, h2, params->unique); | ||
1299 | scratch = unruly_new_scratch(state); | ||
1300 | if (unruly_fill_game(state, scratch, rs)) | ||
1301 | break; | ||
1302 | free_game(state); | ||
1303 | unruly_free_scratch(scratch); | ||
1304 | } | ||
1305 | |||
1306 | #ifdef STANDALONE_SOLVER | ||
1307 | if (solver_verbose) { | ||
1308 | printf("Puzzle generated in %i attempts\n", attempts); | ||
1309 | debug = game_text_format(state); | ||
1310 | fputs(debug, stdout); | ||
1311 | sfree(debug); | ||
1312 | |||
1313 | temp_verbose = solver_verbose; | ||
1314 | solver_verbose = FALSE; | ||
1315 | } | ||
1316 | #endif | ||
1317 | |||
1318 | unruly_free_scratch(scratch); | ||
1319 | |||
1320 | /* Generate random array of spaces */ | ||
1321 | spaces = snewn(s, int); | ||
1322 | for (i = 0; i < s; i++) | ||
1323 | spaces[i] = i; | ||
1324 | shuffle(spaces, s, sizeof(*spaces), rs); | ||
1325 | |||
1326 | /* | ||
1327 | * Winnow the clues by starting from our filled grid, repeatedly | ||
1328 | * picking a filled space and emptying it, as long as the solver | ||
1329 | * reports that the puzzle can still be solved after doing so. | ||
1330 | */ | ||
1331 | for (j = 0; j < s; j++) { | ||
1332 | char c; | ||
1333 | game_state *solver; | ||
1334 | |||
1335 | i = spaces[j]; | ||
1336 | |||
1337 | c = state->grid[i]; | ||
1338 | state->grid[i] = EMPTY; | ||
1339 | |||
1340 | solver = dup_game(state); | ||
1341 | scratch = unruly_new_scratch(state); | ||
1342 | |||
1343 | unruly_solve_game(solver, scratch, params->diff); | ||
1344 | |||
1345 | if (unruly_validate_counts(solver, scratch, NULL) != 0) | ||
1346 | state->grid[i] = c; | ||
1347 | |||
1348 | free_game(solver); | ||
1349 | unruly_free_scratch(scratch); | ||
1350 | } | ||
1351 | sfree(spaces); | ||
1352 | |||
1353 | #ifdef STANDALONE_SOLVER | ||
1354 | if (temp_verbose) { | ||
1355 | solver_verbose = TRUE; | ||
1356 | |||
1357 | printf("Final puzzle:\n"); | ||
1358 | debug = game_text_format(state); | ||
1359 | fputs(debug, stdout); | ||
1360 | sfree(debug); | ||
1361 | } | ||
1362 | #endif | ||
1363 | |||
1364 | /* | ||
1365 | * See if the game has accidentally come out too easy. | ||
1366 | */ | ||
1367 | if (params->diff > 0) { | ||
1368 | int ok; | ||
1369 | game_state *solver; | ||
1370 | |||
1371 | solver = dup_game(state); | ||
1372 | scratch = unruly_new_scratch(state); | ||
1373 | |||
1374 | unruly_solve_game(solver, scratch, params->diff - 1); | ||
1375 | |||
1376 | ok = unruly_validate_counts(solver, scratch, NULL); | ||
1377 | |||
1378 | free_game(solver); | ||
1379 | unruly_free_scratch(scratch); | ||
1380 | |||
1381 | if (ok) | ||
1382 | break; | ||
1383 | } else { | ||
1384 | /* | ||
1385 | * Puzzles of the easiest difficulty can't be too easy. | ||
1386 | */ | ||
1387 | break; | ||
1388 | } | ||
1389 | } | ||
1390 | |||
1391 | /* Encode description */ | ||
1392 | ret = snewn(s + 1, char); | ||
1393 | p = ret; | ||
1394 | run = 0; | ||
1395 | for (i = 0; i < s+1; i++) { | ||
1396 | if (i == s || state->grid[i] == N_ZERO) { | ||
1397 | while (run > 24) { | ||
1398 | *p++ = 'z'; | ||
1399 | run -= 25; | ||
1400 | } | ||
1401 | *p++ = 'a' + run; | ||
1402 | run = 0; | ||
1403 | } else if (state->grid[i] == N_ONE) { | ||
1404 | while (run > 24) { | ||
1405 | *p++ = 'Z'; | ||
1406 | run -= 25; | ||
1407 | } | ||
1408 | *p++ = 'A' + run; | ||
1409 | run = 0; | ||
1410 | } else { | ||
1411 | run++; | ||
1412 | } | ||
1413 | } | ||
1414 | *p = '\0'; | ||
1415 | |||
1416 | free_game(state); | ||
1417 | |||
1418 | return ret; | ||
1419 | } | ||
1420 | |||
1421 | /* ************** * | ||
1422 | * User Interface * | ||
1423 | * ************** */ | ||
1424 | |||
1425 | struct game_ui { | ||
1426 | int cx, cy; | ||
1427 | char cursor; | ||
1428 | }; | ||
1429 | |||
1430 | static game_ui *new_ui(const game_state *state) | ||
1431 | { | ||
1432 | game_ui *ret = snew(game_ui); | ||
1433 | |||
1434 | ret->cx = ret->cy = 0; | ||
1435 | ret->cursor = FALSE; | ||
1436 | |||
1437 | return ret; | ||
1438 | } | ||
1439 | |||
1440 | static void free_ui(game_ui *ui) | ||
1441 | { | ||
1442 | sfree(ui); | ||
1443 | } | ||
1444 | |||
1445 | static char *encode_ui(const game_ui *ui) | ||
1446 | { | ||
1447 | return NULL; | ||
1448 | } | ||
1449 | |||
1450 | static void decode_ui(game_ui *ui, const char *encoding) | ||
1451 | { | ||
1452 | } | ||
1453 | |||
1454 | static void game_changed_state(game_ui *ui, const game_state *oldstate, | ||
1455 | const game_state *newstate) | ||
1456 | { | ||
1457 | } | ||
1458 | |||
1459 | struct game_drawstate { | ||
1460 | int tilesize; | ||
1461 | int w2, h2; | ||
1462 | int started; | ||
1463 | |||
1464 | int *gridfs; | ||
1465 | int *rowfs; | ||
1466 | |||
1467 | int *grid; | ||
1468 | }; | ||
1469 | |||
1470 | static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state) | ||
1471 | { | ||
1472 | struct game_drawstate *ds = snew(struct game_drawstate); | ||
1473 | |||
1474 | int w2 = state->w2, h2 = state->h2; | ||
1475 | int s = w2 * h2; | ||
1476 | int i; | ||
1477 | |||
1478 | ds->tilesize = 0; | ||
1479 | ds->w2 = w2; | ||
1480 | ds->h2 = h2; | ||
1481 | ds->started = FALSE; | ||
1482 | |||
1483 | ds->gridfs = snewn(s, int); | ||
1484 | ds->rowfs = snewn(2 * (w2 + h2), int); | ||
1485 | |||
1486 | ds->grid = snewn(s, int); | ||
1487 | for (i = 0; i < s; i++) | ||
1488 | ds->grid[i] = -1; | ||
1489 | |||
1490 | return ds; | ||
1491 | } | ||
1492 | |||
1493 | static void game_free_drawstate(drawing *dr, game_drawstate *ds) | ||
1494 | { | ||
1495 | sfree(ds->gridfs); | ||
1496 | sfree(ds->rowfs); | ||
1497 | sfree(ds->grid); | ||
1498 | sfree(ds); | ||
1499 | } | ||
1500 | |||
1501 | #define COORD(x) ( (x) * ds->tilesize + ds->tilesize/2 ) | ||
1502 | #define FROMCOORD(x) ( ((x)-(ds->tilesize/2)) / ds->tilesize ) | ||
1503 | |||
1504 | static char *interpret_move(const game_state *state, game_ui *ui, | ||
1505 | const game_drawstate *ds, | ||
1506 | int ox, int oy, int button) | ||
1507 | { | ||
1508 | int hx = ui->cx; | ||
1509 | int hy = ui->cy; | ||
1510 | |||
1511 | int gx = FROMCOORD(ox); | ||
1512 | int gy = FROMCOORD(oy); | ||
1513 | |||
1514 | int w2 = state->w2, h2 = state->h2; | ||
1515 | |||
1516 | button &= ~MOD_MASK; | ||
1517 | |||
1518 | /* Mouse click */ | ||
1519 | if (button == LEFT_BUTTON || button == RIGHT_BUTTON || | ||
1520 | button == MIDDLE_BUTTON) { | ||
1521 | if (ox >= (ds->tilesize / 2) && gx < w2 | ||
1522 | && oy >= (ds->tilesize / 2) && gy < h2) { | ||
1523 | hx = gx; | ||
1524 | hy = gy; | ||
1525 | ui->cursor = FALSE; | ||
1526 | } else | ||
1527 | return NULL; | ||
1528 | } | ||
1529 | |||
1530 | /* Keyboard move */ | ||
1531 | if (IS_CURSOR_MOVE(button)) { | ||
1532 | move_cursor(button, &ui->cx, &ui->cy, w2, h2, 0); | ||
1533 | ui->cursor = TRUE; | ||
1534 | return ""; | ||
1535 | } | ||
1536 | |||
1537 | /* Place one */ | ||
1538 | if ((ui->cursor && (button == CURSOR_SELECT || button == CURSOR_SELECT2 | ||
1539 | || button == '\b' || button == '0' || button == '1' | ||
1540 | || button == '2')) || | ||
1541 | button == LEFT_BUTTON || button == RIGHT_BUTTON || | ||
1542 | button == MIDDLE_BUTTON) { | ||
1543 | char buf[80]; | ||
1544 | char c, i; | ||
1545 | |||
1546 | if (state->immutable[hy * w2 + hx]) | ||
1547 | return NULL; | ||
1548 | |||
1549 | c = '-'; | ||
1550 | i = state->grid[hy * w2 + hx]; | ||
1551 | |||
1552 | if (button == '0' || button == '2') | ||
1553 | c = '0'; | ||
1554 | else if (button == '1') | ||
1555 | c = '1'; | ||
1556 | else if (button == MIDDLE_BUTTON) | ||
1557 | c = '-'; | ||
1558 | |||
1559 | /* Cycle through options */ | ||
1560 | else if (button == CURSOR_SELECT2 || button == RIGHT_BUTTON) | ||
1561 | c = (i == EMPTY ? '0' : i == N_ZERO ? '1' : '-'); | ||
1562 | else if (button == CURSOR_SELECT || button == LEFT_BUTTON) | ||
1563 | c = (i == EMPTY ? '1' : i == N_ONE ? '0' : '-'); | ||
1564 | |||
1565 | if (state->grid[hy * w2 + hx] == | ||
1566 | (c == '0' ? N_ZERO : c == '1' ? N_ONE : EMPTY)) | ||
1567 | return NULL; /* don't put no-ops on the undo chain */ | ||
1568 | |||
1569 | sprintf(buf, "P%c,%d,%d", c, hx, hy); | ||
1570 | |||
1571 | return dupstr(buf); | ||
1572 | } | ||
1573 | return NULL; | ||
1574 | } | ||
1575 | |||
1576 | static game_state *execute_move(const game_state *state, const char *move) | ||
1577 | { | ||
1578 | int w2 = state->w2, h2 = state->h2; | ||
1579 | int s = w2 * h2; | ||
1580 | int x, y, i; | ||
1581 | char c; | ||
1582 | |||
1583 | game_state *ret; | ||
1584 | |||
1585 | if (move[0] == 'S') { | ||
1586 | const char *p; | ||
1587 | |||
1588 | ret = dup_game(state); | ||
1589 | p = move + 1; | ||
1590 | |||
1591 | for (i = 0; i < s; i++) { | ||
1592 | |||
1593 | if (!*p || !(*p == '1' || *p == '0')) { | ||
1594 | free_game(ret); | ||
1595 | return NULL; | ||
1596 | } | ||
1597 | |||
1598 | ret->grid[i] = (*p == '1' ? N_ONE : N_ZERO); | ||
1599 | p++; | ||
1600 | } | ||
1601 | |||
1602 | ret->completed = ret->cheated = TRUE; | ||
1603 | return ret; | ||
1604 | } else if (move[0] == 'P' | ||
1605 | && sscanf(move + 1, "%c,%d,%d", &c, &x, &y) == 3 && x >= 0 | ||
1606 | && x < w2 && y >= 0 && y < h2 && (c == '-' || c == '0' | ||
1607 | || c == '1')) { | ||
1608 | ret = dup_game(state); | ||
1609 | i = y * w2 + x; | ||
1610 | |||
1611 | if (state->immutable[i]) { | ||
1612 | free_game(ret); | ||
1613 | return NULL; | ||
1614 | } | ||
1615 | |||
1616 | ret->grid[i] = (c == '1' ? N_ONE : c == '0' ? N_ZERO : EMPTY); | ||
1617 | |||
1618 | if (!ret->completed && unruly_validate_counts(ret, NULL, NULL) == 0 | ||
1619 | && (unruly_validate_all_rows(ret, NULL) == 0)) | ||
1620 | ret->completed = TRUE; | ||
1621 | |||
1622 | return ret; | ||
1623 | } | ||
1624 | |||
1625 | return NULL; | ||
1626 | } | ||
1627 | |||
1628 | /* ---------------------------------------------------------------------- | ||
1629 | * Drawing routines. | ||
1630 | */ | ||
1631 | |||
1632 | static void game_compute_size(const game_params *params, int tilesize, | ||
1633 | int *x, int *y) | ||
1634 | { | ||
1635 | *x = tilesize * (params->w2 + 1); | ||
1636 | *y = tilesize * (params->h2 + 1); | ||
1637 | } | ||
1638 | |||
1639 | static void game_set_size(drawing *dr, game_drawstate *ds, | ||
1640 | const game_params *params, int tilesize) | ||
1641 | { | ||
1642 | ds->tilesize = tilesize; | ||
1643 | } | ||
1644 | |||
1645 | static float *game_colours(frontend *fe, int *ncolours) | ||
1646 | { | ||
1647 | float *ret = snewn(3 * NCOLOURS, float); | ||
1648 | int i; | ||
1649 | |||
1650 | frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]); | ||
1651 | |||
1652 | for (i = 0; i < 3; i++) { | ||
1653 | ret[COL_1 * 3 + i] = 0.2F; | ||
1654 | ret[COL_1_HIGHLIGHT * 3 + i] = 0.4F; | ||
1655 | ret[COL_1_LOWLIGHT * 3 + i] = 0.0F; | ||
1656 | ret[COL_0 * 3 + i] = 0.95F; | ||
1657 | ret[COL_0_HIGHLIGHT * 3 + i] = 1.0F; | ||
1658 | ret[COL_0_LOWLIGHT * 3 + i] = 0.9F; | ||
1659 | ret[COL_EMPTY * 3 + i] = 0.5F; | ||
1660 | ret[COL_GRID * 3 + i] = 0.3F; | ||
1661 | } | ||
1662 | game_mkhighlight_specific(fe, ret, COL_0, COL_0_HIGHLIGHT, COL_0_LOWLIGHT); | ||
1663 | game_mkhighlight_specific(fe, ret, COL_1, COL_1_HIGHLIGHT, COL_1_LOWLIGHT); | ||
1664 | |||
1665 | ret[COL_ERROR * 3 + 0] = 1.0F; | ||
1666 | ret[COL_ERROR * 3 + 1] = 0.0F; | ||
1667 | ret[COL_ERROR * 3 + 2] = 0.0F; | ||
1668 | |||
1669 | ret[COL_CURSOR * 3 + 0] = 0.0F; | ||
1670 | ret[COL_CURSOR * 3 + 1] = 0.7F; | ||
1671 | ret[COL_CURSOR * 3 + 2] = 0.0F; | ||
1672 | |||
1673 | *ncolours = NCOLOURS; | ||
1674 | return ret; | ||
1675 | } | ||
1676 | |||
1677 | static void unruly_draw_err_rectangle(drawing *dr, int x, int y, int w, int h, | ||
1678 | int tilesize) | ||
1679 | { | ||
1680 | double thick = tilesize / 10; | ||
1681 | double margin = tilesize / 20; | ||
1682 | |||
1683 | draw_rect(dr, x+margin, y+margin, w-2*margin, thick, COL_ERROR); | ||
1684 | draw_rect(dr, x+margin, y+margin, thick, h-2*margin, COL_ERROR); | ||
1685 | draw_rect(dr, x+margin, y+h-margin-thick, w-2*margin, thick, COL_ERROR); | ||
1686 | draw_rect(dr, x+w-margin-thick, y+margin, thick, h-2*margin, COL_ERROR); | ||
1687 | } | ||
1688 | |||
1689 | static void unruly_draw_tile(drawing *dr, int x, int y, int tilesize, int tile) | ||
1690 | { | ||
1691 | clip(dr, x, y, tilesize, tilesize); | ||
1692 | |||
1693 | /* Draw the grid edge first, so the tile can overwrite it */ | ||
1694 | draw_rect(dr, x, y, tilesize, tilesize, COL_GRID); | ||
1695 | |||
1696 | /* Background of the tile */ | ||
1697 | { | ||
1698 | int val = (tile & FF_ZERO ? 0 : tile & FF_ONE ? 2 : 1); | ||
1699 | val = (val == 0 ? COL_0 : val == 2 ? COL_1 : COL_EMPTY); | ||
1700 | |||
1701 | if ((tile & (FF_FLASH1 | FF_FLASH2)) && | ||
1702 | (val == COL_0 || val == COL_1)) { | ||
1703 | val += (tile & FF_FLASH1 ? 1 : 2); | ||
1704 | } | ||
1705 | |||
1706 | draw_rect(dr, x, y, tilesize-1, tilesize-1, val); | ||
1707 | |||
1708 | if ((val == COL_0 || val == COL_1) && (tile & FF_IMMUTABLE)) { | ||
1709 | draw_rect(dr, x + tilesize/6, y + tilesize/6, | ||
1710 | tilesize - 2*(tilesize/6) - 2, 1, val + 2); | ||
1711 | draw_rect(dr, x + tilesize/6, y + tilesize/6, | ||
1712 | 1, tilesize - 2*(tilesize/6) - 2, val + 2); | ||
1713 | draw_rect(dr, x + tilesize/6 + 1, y + tilesize - tilesize/6 - 2, | ||
1714 | tilesize - 2*(tilesize/6) - 2, 1, val + 1); | ||
1715 | draw_rect(dr, x + tilesize - tilesize/6 - 2, y + tilesize/6 + 1, | ||
1716 | 1, tilesize - 2*(tilesize/6) - 2, val + 1); | ||
1717 | } | ||
1718 | } | ||
1719 | |||
1720 | /* 3-in-a-row errors */ | ||
1721 | if (tile & (FE_HOR_ROW_LEFT | FE_HOR_ROW_RIGHT)) { | ||
1722 | int left = x, right = x + tilesize - 1; | ||
1723 | if ((tile & FE_HOR_ROW_LEFT)) | ||
1724 | right += tilesize/2; | ||
1725 | if ((tile & FE_HOR_ROW_RIGHT)) | ||
1726 | left -= tilesize/2; | ||
1727 | unruly_draw_err_rectangle(dr, left, y, right-left, tilesize-1, tilesize); | ||
1728 | } | ||
1729 | if (tile & (FE_VER_ROW_TOP | FE_VER_ROW_BOTTOM)) { | ||
1730 | int top = y, bottom = y + tilesize - 1; | ||
1731 | if ((tile & FE_VER_ROW_TOP)) | ||
1732 | bottom += tilesize/2; | ||
1733 | if ((tile & FE_VER_ROW_BOTTOM)) | ||
1734 | top -= tilesize/2; | ||
1735 | unruly_draw_err_rectangle(dr, x, top, tilesize-1, bottom-top, tilesize); | ||
1736 | } | ||
1737 | |||
1738 | /* Count errors */ | ||
1739 | if (tile & FE_COUNT) { | ||
1740 | draw_text(dr, x + tilesize/2, y + tilesize/2, FONT_VARIABLE, | ||
1741 | tilesize/2, ALIGN_HCENTRE | ALIGN_VCENTRE, COL_ERROR, "!"); | ||
1742 | } | ||
1743 | |||
1744 | /* Row-match errors */ | ||
1745 | if (tile & FE_ROW_MATCH) { | ||
1746 | draw_rect(dr, x, y+tilesize/2-tilesize/12, | ||
1747 | tilesize, 2*(tilesize/12), COL_ERROR); | ||
1748 | } | ||
1749 | if (tile & FE_COL_MATCH) { | ||
1750 | draw_rect(dr, x+tilesize/2-tilesize/12, y, | ||
1751 | 2*(tilesize/12), tilesize, COL_ERROR); | ||
1752 | } | ||
1753 | |||
1754 | /* Cursor rectangle */ | ||
1755 | if (tile & FF_CURSOR) { | ||
1756 | draw_rect(dr, x, y, tilesize/12, tilesize-1, COL_CURSOR); | ||
1757 | draw_rect(dr, x, y, tilesize-1, tilesize/12, COL_CURSOR); | ||
1758 | draw_rect(dr, x+tilesize-1-tilesize/12, y, tilesize/12, tilesize-1, | ||
1759 | COL_CURSOR); | ||
1760 | draw_rect(dr, x, y+tilesize-1-tilesize/12, tilesize-1, tilesize/12, | ||
1761 | COL_CURSOR); | ||
1762 | } | ||
1763 | |||
1764 | unclip(dr); | ||
1765 | draw_update(dr, x, y, tilesize, tilesize); | ||
1766 | } | ||
1767 | |||
1768 | #define TILE_SIZE (ds->tilesize) | ||
1769 | #define DEFAULT_TILE_SIZE 32 | ||
1770 | #define FLASH_FRAME 0.12F | ||
1771 | #define FLASH_TIME (FLASH_FRAME * 3) | ||
1772 | |||
1773 | static void game_redraw(drawing *dr, game_drawstate *ds, | ||
1774 | const game_state *oldstate, const game_state *state, | ||
1775 | int dir, const game_ui *ui, | ||
1776 | float animtime, float flashtime) | ||
1777 | { | ||
1778 | int w2 = state->w2, h2 = state->h2; | ||
1779 | int s = w2 * h2; | ||
1780 | int flash; | ||
1781 | int x, y, i; | ||
1782 | |||
1783 | if (!ds->started) { | ||
1784 | /* Main window background */ | ||
1785 | draw_rect(dr, 0, 0, TILE_SIZE * (w2+1), TILE_SIZE * (h2+1), | ||
1786 | COL_BACKGROUND); | ||
1787 | /* Outer edge of grid */ | ||
1788 | draw_rect(dr, COORD(0)-TILE_SIZE/10, COORD(0)-TILE_SIZE/10, | ||
1789 | TILE_SIZE*w2 + 2*(TILE_SIZE/10) - 1, | ||
1790 | TILE_SIZE*h2 + 2*(TILE_SIZE/10) - 1, COL_GRID); | ||
1791 | |||
1792 | draw_update(dr, 0, 0, TILE_SIZE * (w2+1), TILE_SIZE * (h2+1)); | ||
1793 | ds->started = TRUE; | ||
1794 | } | ||
1795 | |||
1796 | flash = 0; | ||
1797 | if (flashtime > 0) | ||
1798 | flash = (int)(flashtime / FLASH_FRAME) == 1 ? FF_FLASH2 : FF_FLASH1; | ||
1799 | |||
1800 | for (i = 0; i < s; i++) | ||
1801 | ds->gridfs[i] = 0; | ||
1802 | unruly_validate_all_rows(state, ds->gridfs); | ||
1803 | for (i = 0; i < 2 * (h2 + w2); i++) | ||
1804 | ds->rowfs[i] = 0; | ||
1805 | unruly_validate_counts(state, NULL, ds->rowfs); | ||
1806 | |||
1807 | for (y = 0; y < h2; y++) { | ||
1808 | for (x = 0; x < w2; x++) { | ||
1809 | int tile; | ||
1810 | |||
1811 | i = y * w2 + x; | ||
1812 | |||
1813 | tile = ds->gridfs[i]; | ||
1814 | |||
1815 | if (state->grid[i] == N_ONE) { | ||
1816 | tile |= FF_ONE; | ||
1817 | if (ds->rowfs[y] || ds->rowfs[2*h2 + x]) | ||
1818 | tile |= FE_COUNT; | ||
1819 | } else if (state->grid[i] == N_ZERO) { | ||
1820 | tile |= FF_ZERO; | ||
1821 | if (ds->rowfs[h2 + y] || ds->rowfs[2*h2 + w2 + x]) | ||
1822 | tile |= FE_COUNT; | ||
1823 | } | ||
1824 | |||
1825 | tile |= flash; | ||
1826 | |||
1827 | if (state->immutable[i]) | ||
1828 | tile |= FF_IMMUTABLE; | ||
1829 | |||
1830 | if (ui->cursor && ui->cx == x && ui->cy == y) | ||
1831 | tile |= FF_CURSOR; | ||
1832 | |||
1833 | if (ds->grid[i] != tile) { | ||
1834 | ds->grid[i] = tile; | ||
1835 | unruly_draw_tile(dr, COORD(x), COORD(y), TILE_SIZE, tile); | ||
1836 | } | ||
1837 | } | ||
1838 | } | ||
1839 | } | ||
1840 | |||
1841 | static float game_anim_length(const game_state *oldstate, | ||
1842 | const game_state *newstate, int dir, game_ui *ui) | ||
1843 | { | ||
1844 | return 0.0F; | ||
1845 | } | ||
1846 | |||
1847 | static float game_flash_length(const game_state *oldstate, | ||
1848 | const game_state *newstate, int dir, game_ui *ui) | ||
1849 | { | ||
1850 | if (!oldstate->completed && newstate->completed && | ||
1851 | !oldstate->cheated && !newstate->cheated) | ||
1852 | return FLASH_TIME; | ||
1853 | return 0.0F; | ||
1854 | } | ||
1855 | |||
1856 | static int game_status(const game_state *state) | ||
1857 | { | ||
1858 | return state->completed ? +1 : 0; | ||
1859 | } | ||
1860 | |||
1861 | static int game_timing_state(const game_state *state, game_ui *ui) | ||
1862 | { | ||
1863 | return TRUE; | ||
1864 | } | ||
1865 | |||
1866 | static void game_print_size(const game_params *params, float *x, float *y) | ||
1867 | { | ||
1868 | int pw, ph; | ||
1869 | |||
1870 | /* Using 7mm squares */ | ||
1871 | game_compute_size(params, 700, &pw, &ph); | ||
1872 | *x = pw / 100.0F; | ||
1873 | *y = ph / 100.0F; | ||
1874 | } | ||
1875 | |||
1876 | static void game_print(drawing *dr, const game_state *state, int tilesize) | ||
1877 | { | ||
1878 | int w2 = state->w2, h2 = state->h2; | ||
1879 | int x, y; | ||
1880 | |||
1881 | int ink = print_mono_colour(dr, 0); | ||
1882 | |||
1883 | for (y = 0; y < h2; y++) | ||
1884 | for (x = 0; x < w2; x++) { | ||
1885 | int tx = x * tilesize + (tilesize / 2); | ||
1886 | int ty = y * tilesize + (tilesize / 2); | ||
1887 | |||
1888 | /* Draw the border */ | ||
1889 | int coords[8]; | ||
1890 | coords[0] = tx; | ||
1891 | coords[1] = ty - 1; | ||
1892 | coords[2] = tx + tilesize; | ||
1893 | coords[3] = ty - 1; | ||
1894 | coords[4] = tx + tilesize; | ||
1895 | coords[5] = ty + tilesize - 1; | ||
1896 | coords[6] = tx; | ||
1897 | coords[7] = ty + tilesize - 1; | ||
1898 | draw_polygon(dr, coords, 4, -1, ink); | ||
1899 | |||
1900 | if (state->grid[y * w2 + x] == N_ONE) | ||
1901 | draw_rect(dr, tx, ty, tilesize, tilesize, ink); | ||
1902 | else if (state->grid[y * w2 + x] == N_ZERO) | ||
1903 | draw_circle(dr, tx + tilesize/2, ty + tilesize/2, | ||
1904 | tilesize/12, ink, ink); | ||
1905 | } | ||
1906 | } | ||
1907 | |||
1908 | #ifdef COMBINED | ||
1909 | #define thegame unruly | ||
1910 | #endif | ||
1911 | |||
1912 | const struct game thegame = { | ||
1913 | "Unruly", "games.unruly", "unruly", | ||
1914 | default_params, | ||
1915 | game_fetch_preset, | ||
1916 | decode_params, | ||
1917 | encode_params, | ||
1918 | free_params, | ||
1919 | dup_params, | ||
1920 | TRUE, game_configure, custom_params, | ||
1921 | validate_params, | ||
1922 | new_game_desc, | ||
1923 | validate_desc, | ||
1924 | new_game, | ||
1925 | dup_game, | ||
1926 | free_game, | ||
1927 | TRUE, solve_game, | ||
1928 | TRUE, game_can_format_as_text_now, game_text_format, | ||
1929 | new_ui, | ||
1930 | free_ui, | ||
1931 | encode_ui, | ||
1932 | decode_ui, | ||
1933 | game_changed_state, | ||
1934 | interpret_move, | ||
1935 | execute_move, | ||
1936 | DEFAULT_TILE_SIZE, game_compute_size, game_set_size, | ||
1937 | game_colours, | ||
1938 | game_new_drawstate, | ||
1939 | game_free_drawstate, | ||
1940 | game_redraw, | ||
1941 | game_anim_length, | ||
1942 | game_flash_length, | ||
1943 | game_status, | ||
1944 | TRUE, FALSE, game_print_size, game_print, | ||
1945 | FALSE, /* wants_statusbar */ | ||
1946 | FALSE, game_timing_state, | ||
1947 | 0, /* flags */ | ||
1948 | }; | ||
1949 | |||
1950 | /* ***************** * | ||
1951 | * Standalone solver * | ||
1952 | * ***************** */ | ||
1953 | |||
1954 | #ifdef STANDALONE_SOLVER | ||
1955 | #include <time.h> | ||
1956 | #include <stdarg.h> | ||
1957 | |||
1958 | /* Most of the standalone solver code was copied from unequal.c and singles.c */ | ||
1959 | |||
1960 | const char *quis; | ||
1961 | |||
1962 | static void usage_exit(const char *msg) | ||
1963 | { | ||
1964 | if (msg) | ||
1965 | fprintf(stderr, "%s: %s\n", quis, msg); | ||
1966 | fprintf(stderr, | ||
1967 | "Usage: %s [-v] [--seed SEED] <params> | [game_id [game_id ...]]\n", | ||
1968 | quis); | ||
1969 | exit(1); | ||
1970 | } | ||
1971 | |||
1972 | int main(int argc, char *argv[]) | ||
1973 | { | ||
1974 | random_state *rs; | ||
1975 | time_t seed = time(NULL); | ||
1976 | |||
1977 | game_params *params = NULL; | ||
1978 | |||
1979 | char *id = NULL, *desc = NULL, *err; | ||
1980 | |||
1981 | quis = argv[0]; | ||
1982 | |||
1983 | while (--argc > 0) { | ||
1984 | char *p = *++argv; | ||
1985 | if (!strcmp(p, "--seed")) { | ||
1986 | if (argc == 0) | ||
1987 | usage_exit("--seed needs an argument"); | ||
1988 | seed = (time_t) atoi(*++argv); | ||
1989 | argc--; | ||
1990 | } else if (!strcmp(p, "-v")) | ||
1991 | solver_verbose = TRUE; | ||
1992 | else if (*p == '-') | ||
1993 | usage_exit("unrecognised option"); | ||
1994 | else | ||
1995 | id = p; | ||
1996 | } | ||
1997 | |||
1998 | if (id) { | ||
1999 | desc = strchr(id, ':'); | ||
2000 | if (desc) | ||
2001 | *desc++ = '\0'; | ||
2002 | |||
2003 | params = default_params(); | ||
2004 | decode_params(params, id); | ||
2005 | err = validate_params(params, TRUE); | ||
2006 | if (err) { | ||
2007 | fprintf(stderr, "Parameters are invalid\n"); | ||
2008 | fprintf(stderr, "%s: %s", argv[0], err); | ||
2009 | exit(1); | ||
2010 | } | ||
2011 | } | ||
2012 | |||
2013 | if (!desc) { | ||
2014 | char *desc_gen, *aux; | ||
2015 | rs = random_new((void *) &seed, sizeof(time_t)); | ||
2016 | if (!params) | ||
2017 | params = default_params(); | ||
2018 | printf("Generating puzzle with parameters %s\n", | ||
2019 | encode_params(params, TRUE)); | ||
2020 | desc_gen = new_game_desc(params, rs, &aux, FALSE); | ||
2021 | |||
2022 | if (!solver_verbose) { | ||
2023 | char *fmt = game_text_format(new_game(NULL, params, desc_gen)); | ||
2024 | fputs(fmt, stdout); | ||
2025 | sfree(fmt); | ||
2026 | } | ||
2027 | |||
2028 | printf("Game ID: %s\n", desc_gen); | ||
2029 | } else { | ||
2030 | game_state *input; | ||
2031 | struct unruly_scratch *scratch; | ||
2032 | int maxdiff, errcode; | ||
2033 | |||
2034 | err = validate_desc(params, desc); | ||
2035 | if (err) { | ||
2036 | fprintf(stderr, "Description is invalid\n"); | ||
2037 | fprintf(stderr, "%s", err); | ||
2038 | exit(1); | ||
2039 | } | ||
2040 | |||
2041 | input = new_game(NULL, params, desc); | ||
2042 | scratch = unruly_new_scratch(input); | ||
2043 | |||
2044 | maxdiff = unruly_solve_game(input, scratch, DIFFCOUNT); | ||
2045 | |||
2046 | errcode = unruly_validate_counts(input, scratch, NULL); | ||
2047 | if (unruly_validate_all_rows(input, NULL) == -1) | ||
2048 | errcode = -1; | ||
2049 | |||
2050 | if (errcode != -1) { | ||
2051 | char *fmt = game_text_format(input); | ||
2052 | fputs(fmt, stdout); | ||
2053 | sfree(fmt); | ||
2054 | if (maxdiff < 0) | ||
2055 | printf("Difficulty: already solved!\n"); | ||
2056 | else | ||
2057 | printf("Difficulty: %s\n", unruly_diffnames[maxdiff]); | ||
2058 | } | ||
2059 | |||
2060 | if (errcode == 1) | ||
2061 | printf("No solution found.\n"); | ||
2062 | else if (errcode == -1) | ||
2063 | printf("Puzzle is invalid.\n"); | ||
2064 | |||
2065 | free_game(input); | ||
2066 | unruly_free_scratch(scratch); | ||
2067 | } | ||
2068 | |||
2069 | return 0; | ||
2070 | } | ||
2071 | #endif | ||