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