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