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 * filling.c: An implementation of the Nikoli game fillomino.
3 * Copyright (C) 2007 Jonas Kölker. See LICENSE for the license.
4 */
5
6/* TODO:
7 *
8 * - use a typedef instead of int for numbers on the board
9 * + replace int with something else (signed short?)
10 * - the type should be signed (for -board[i] and -SENTINEL)
11 * - the type should be somewhat big: board[i] = i
12 * - Using shorts gives us 181x181 puzzles as upper bound.
13 *
14 * - in board generation, after having merged regions such that no
15 * more merges are necessary, try splitting (big) regions.
16 * + it seems that smaller regions make for better puzzles; see
17 * for instance the 7x7 puzzle in this file (grep for 7x7:).
18 *
19 * - symmetric hints (solo-style)
20 * + right now that means including _many_ hints, and the puzzles
21 * won't look any nicer. Not worth it (at the moment).
22 *
23 * - make the solver do recursion/backtracking.
24 * + This is for user-submitted puzzles, not for puzzle
25 * generation (on the other hand, never say never).
26 *
27 * - prove that only w=h=2 needs a special case
28 *
29 * - solo-like pencil marks?
30 *
31 * - a user says that the difficulty is unevenly distributed.
32 * + partition into levels? Will they be non-crap?
33 *
34 * - Allow square contents > 9?
35 * + I could use letters for digits (solo does this), but
36 * letters don't have numeric significance (normal people hate
37 * base36), which is relevant here (much more than in solo).
38 * + [click, 1, 0, enter] => [10 in clicked square]?
39 * + How much information is needed to solve? Does one need to
40 * know the algorithm by which the largest number is set?
41 *
42 * - eliminate puzzle instances with done chunks (1's in particular)?
43 * + that's what the qsort call is all about.
44 * + the 1's don't bother me that much.
45 * + but this takes a LONG time (not always possible)?
46 * - this may be affected by solver (lack of) quality.
47 * - weed them out by construction instead of post-cons check
48 * + but that interleaves make_board and new_game_desc: you
49 * have to alternate between changing the board and
50 * changing the hint set (instead of just creating the
51 * board once, then changing the hint set once -> done).
52 *
53 * - use binary search when discovering the minimal sovable point
54 * + profile to show a need (but when the solver gets slower...)
55 * + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100)
56 * + but the hints are independent, not linear, so... what?
57 */
58
59#include <assert.h>
60#include <ctype.h>
61#ifdef NO_TGMATH_H
62# include <math.h>
63#else
64# include <tgmath.h>
65#endif
66#include <stdarg.h>
67#include <stdio.h>
68#include <stdlib.h>
69#include <string.h>
70
71#include "puzzles.h"
72
73static bool verbose;
74
75#ifdef STANDALONE_SOLVER
76#define printv if (!verbose); else printf
77#else
78#define printv(...)
79#endif
80
81/*****************************************************************************
82 * GAME CONFIGURATION AND PARAMETERS *
83 *****************************************************************************/
84
85struct game_params {
86 int w, h;
87};
88
89struct shared_state {
90 struct game_params params;
91 int *clues;
92 int refcnt;
93};
94
95struct game_state {
96 int *board;
97 struct shared_state *shared;
98 bool completed, cheated;
99};
100
101static const struct game_params filling_defaults[3] = {
102 {9, 7}, {13, 9}, {17, 13}
103};
104
105static game_params *default_params(void)
106{
107 game_params *ret = snew(game_params);
108
109 *ret = filling_defaults[1]; /* struct copy */
110
111 return ret;
112}
113
114static bool game_fetch_preset(int i, char **name, game_params **params)
115{
116 char buf[64];
117
118 if (i < 0 || i >= lenof(filling_defaults)) return false;
119 *params = snew(game_params);
120 **params = filling_defaults[i]; /* struct copy */
121 sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h);
122 *name = dupstr(buf);
123
124 return true;
125}
126
127static void free_params(game_params *params)
128{
129 sfree(params);
130}
131
132static game_params *dup_params(const game_params *params)
133{
134 game_params *ret = snew(game_params);
135 *ret = *params; /* struct copy */
136 return ret;
137}
138
139static void decode_params(game_params *ret, char const *string)
140{
141 ret->w = ret->h = atoi(string);
142 while (*string && isdigit((unsigned char) *string)) ++string;
143 if (*string == 'x') ret->h = atoi(++string);
144}
145
146static char *encode_params(const game_params *params, bool full)
147{
148 char buf[64];
149 sprintf(buf, "%dx%d", params->w, params->h);
150 return dupstr(buf);
151}
152
153static config_item *game_configure(const game_params *params)
154{
155 config_item *ret;
156 char buf[64];
157
158 ret = snewn(3, config_item);
159
160 ret[0].name = "Width";
161 ret[0].type = C_STRING;
162 sprintf(buf, "%d", params->w);
163 ret[0].u.string.sval = dupstr(buf);
164
165 ret[1].name = "Height";
166 ret[1].type = C_STRING;
167 sprintf(buf, "%d", params->h);
168 ret[1].u.string.sval = dupstr(buf);
169
170 ret[2].name = NULL;
171 ret[2].type = C_END;
172
173 return ret;
174}
175
176static game_params *custom_params(const config_item *cfg)
177{
178 game_params *ret = snew(game_params);
179
180 ret->w = atoi(cfg[0].u.string.sval);
181 ret->h = atoi(cfg[1].u.string.sval);
182
183 return ret;
184}
185
186static const char *validate_params(const game_params *params, bool full)
187{
188 if (params->w < 1) return "Width must be at least one";
189 if (params->h < 1) return "Height must be at least one";
190 if (params->w > INT_MAX / params->h)
191 return "Width times height must not be unreasonably large";
192
193 return NULL;
194}
195
196/*****************************************************************************
197 * STRINGIFICATION OF GAME STATE *
198 *****************************************************************************/
199
200#define EMPTY 0
201
202/* Example of plaintext rendering:
203 * +---+---+---+---+---+---+---+
204 * | 6 | | | 2 | | | 2 |
205 * +---+---+---+---+---+---+---+
206 * | | 3 | | 6 | | 3 | |
207 * +---+---+---+---+---+---+---+
208 * | 3 | | | | | | 1 |
209 * +---+---+---+---+---+---+---+
210 * | | 2 | 3 | | 4 | 2 | |
211 * +---+---+---+---+---+---+---+
212 * | 2 | | | | | | 3 |
213 * +---+---+---+---+---+---+---+
214 * | | 5 | | 1 | | 4 | |
215 * +---+---+---+---+---+---+---+
216 * | 4 | | | 3 | | | 3 |
217 * +---+---+---+---+---+---+---+
218 *
219 * This puzzle instance is taken from the nikoli website
220 * Encoded (unsolved and solved), the strings are these:
221 * 7x7:6002002030603030000010230420200000305010404003003
222 * 7x7:6662232336663232331311235422255544325413434443313
223 */
224static char *board_to_string(int *board, int w, int h) {
225 const int sz = w * h;
226 const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
227 const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
228 const int chlen = chw * chh;
229 char *repr = snewn(chlen + 1, char);
230 int i;
231
232 assert(board);
233
234 /* build the first line ("^(\+---){n}\+$") */
235 for (i = 0; i < w; ++i) {
236 repr[4*i + 0] = '+';
237 repr[4*i + 1] = '-';
238 repr[4*i + 2] = '-';
239 repr[4*i + 3] = '-';
240 }
241 repr[4*i + 0] = '+';
242 repr[4*i + 1] = '\n';
243
244 /* ... and copy it onto the odd-numbered lines */
245 for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
246
247 /* build the second line ("^(\|\t){n}\|$") */
248 for (i = 0; i < w; ++i) {
249 repr[chw + 4*i + 0] = '|';
250 repr[chw + 4*i + 1] = ' ';
251 repr[chw + 4*i + 2] = ' ';
252 repr[chw + 4*i + 3] = ' ';
253 }
254 repr[chw + 4*i + 0] = '|';
255 repr[chw + 4*i + 1] = '\n';
256
257 /* ... and copy it onto the even-numbered lines */
258 for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
259
260 /* fill in the numbers */
261 for (i = 0; i < sz; ++i) {
262 const int x = i % w;
263 const int y = i / w;
264 if (board[i] == EMPTY) continue;
265 repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
266 }
267
268 repr[chlen] = '\0';
269 return repr;
270}
271
272static bool game_can_format_as_text_now(const game_params *params)
273{
274 return true;
275}
276
277static char *game_text_format(const game_state *state)
278{
279 const int w = state->shared->params.w;
280 const int h = state->shared->params.h;
281 return board_to_string(state->board, w, h);
282}
283
284/*****************************************************************************
285 * GAME GENERATION AND SOLVER *
286 *****************************************************************************/
287
288static const int dx[4] = {-1, 1, 0, 0};
289static const int dy[4] = {0, 0, -1, 1};
290
291struct solver_state
292{
293 DSF *dsf;
294 int *board;
295 int *connected;
296 int nempty;
297
298 /* Used internally by learn_bitmap_deductions; kept here to avoid
299 * mallocing/freeing them every time that function is called. */
300 int *bm, *bmminsize;
301 DSF *bmdsf;
302};
303
304static void print_board(int *board, int w, int h) {
305 if (verbose) {
306 char *repr = board_to_string(board, w, h);
307 printv("%s\n", repr);
308 free(repr);
309 }
310}
311
312static game_state *new_game(midend *, const game_params *, const char *);
313static void free_game(game_state *);
314
315#define SENTINEL (sz+1)
316
317static bool mark_region(int *board, int w, int h, int i, int n, int m) {
318 int j;
319
320 board[i] = -1;
321
322 for (j = 0; j < 4; ++j) {
323 const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x;
324 if (x < 0 || x >= w || y < 0 || y >= h) continue;
325 if (board[ii] == m) return false;
326 if (board[ii] != n) continue;
327 if (!mark_region(board, w, h, ii, n, m)) return false;
328 }
329 return true;
330}
331
332static int region_size(int *board, int w, int h, int i) {
333 const int sz = w * h;
334 int j, size, copy;
335 if (board[i] == 0) return 0;
336 copy = board[i];
337 mark_region(board, w, h, i, board[i], SENTINEL);
338 for (size = j = 0; j < sz; ++j) {
339 if (board[j] != -1) continue;
340 ++size;
341 board[j] = copy;
342 }
343 return size;
344}
345
346static void merge_ones(int *board, int w, int h)
347{
348 const int sz = w * h;
349 const int maxsize = min(max(max(w, h), 3), 9);
350 int i, j, k;
351 bool change;
352 do {
353 change = false;
354 for (i = 0; i < sz; ++i) {
355 if (board[i] != 1) continue;
356
357 for (j = 0; j < 4; ++j, board[i] = 1) {
358 const int x = (i % w) + dx[j], y = (i / w) + dy[j];
359 int oldsize, newsize, ii = w*y + x;
360 bool ok;
361
362 if (x < 0 || x >= w || y < 0 || y >= h) continue;
363 if (board[ii] == maxsize) continue;
364
365 oldsize = board[ii];
366 board[i] = oldsize;
367 newsize = region_size(board, w, h, i);
368
369 if (newsize > maxsize) continue;
370
371 ok = mark_region(board, w, h, i, oldsize, newsize);
372
373 for (k = 0; k < sz; ++k)
374 if (board[k] == -1)
375 board[k] = ok ? newsize : oldsize;
376
377 if (ok) break;
378 }
379 if (j < 4) change = true;
380 }
381 } while (change);
382}
383
384/* generate a random valid board; uses validate_board. */
385static void make_board(int *board, int w, int h, random_state *rs) {
386 const int sz = w * h;
387
388 /* w=h=2 is a special case which requires a number > max(w, h) */
389 /* TODO prove that this is the case ONLY for w=h=2. */
390 const int maxsize = min(max(max(w, h), 3), 9);
391
392 /* Note that if 1 in {w, h} then it's impossible to have a region
393 * of size > w*h, so the special case only affects w=h=2. */
394
395 int i;
396 DSF *dsf;
397 bool change;
398
399 assert(w >= 1);
400 assert(h >= 1);
401 assert(board);
402
403 /* I abuse the board variable: when generating the puzzle, it
404 * contains a shuffled list of numbers {0, ..., sz-1}. */
405 for (i = 0; i < sz; ++i) board[i] = i;
406
407 dsf = dsf_new(sz);
408retry:
409 dsf_reinit(dsf);
410 shuffle(board, sz, sizeof (int), rs);
411
412 do {
413 change = false; /* as long as the board potentially has errors */
414 for (i = 0; i < sz; ++i) {
415 const int square = dsf_canonify(dsf, board[i]);
416 const int size = dsf_size(dsf, square);
417 int merge = SENTINEL, min = maxsize - size + 1;
418 bool error = false;
419 int neighbour, neighbour_size, j;
420 int directions[4];
421
422 for (j = 0; j < 4; ++j)
423 directions[j] = j;
424 shuffle(directions, 4, sizeof(int), rs);
425
426 for (j = 0; j < 4; ++j) {
427 const int x = (board[i] % w) + dx[directions[j]];
428 const int y = (board[i] / w) + dy[directions[j]];
429 if (x < 0 || x >= w || y < 0 || y >= h) continue;
430
431 neighbour = dsf_canonify(dsf, w*y + x);
432 if (square == neighbour) continue;
433
434 neighbour_size = dsf_size(dsf, neighbour);
435 if (size == neighbour_size) error = true;
436
437 /* find the smallest neighbour to merge with, which
438 * wouldn't make the region too large. (This is
439 * guaranteed by the initial value of `min'.) */
440 if (neighbour_size < min && random_upto(rs, 10)) {
441 min = neighbour_size;
442 merge = neighbour;
443 }
444 }
445
446 /* if this square is not in error, leave it be */
447 if (!error) continue;
448
449 /* if it is, but we can't fix it, retry the whole board.
450 * Maybe we could fix it by merging the conflicting
451 * neighbouring region(s) into some of their neighbours,
452 * but just restarting works out fine. */
453 if (merge == SENTINEL) goto retry;
454
455 /* merge with the smallest neighbouring workable region. */
456 dsf_merge(dsf, square, merge);
457 change = true;
458 }
459 } while (change);
460
461 for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
462 merge_ones(board, w, h);
463
464 dsf_free(dsf);
465}
466
467static void merge(DSF *dsf, int *connected, int a, int b) {
468 int c;
469 assert(dsf);
470 assert(connected);
471 a = dsf_canonify(dsf, a);
472 b = dsf_canonify(dsf, b);
473 if (a == b) return;
474 dsf_merge(dsf, a, b);
475 c = connected[a];
476 connected[a] = connected[b];
477 connected[b] = c;
478}
479
480static void *memdup(const void *ptr, size_t len, size_t esz) {
481 void *dup = smalloc(len * esz);
482 assert(ptr);
483 memcpy(dup, ptr, len * esz);
484 return dup;
485}
486
487static void expand(struct solver_state *s, int w, int h, int t, int f) {
488 int j;
489 assert(s);
490 assert(s->board[t] == EMPTY); /* expand to empty square */
491 assert(s->board[f] != EMPTY); /* expand from non-empty square */
492 printv(
493 "learn: expanding %d from (%d, %d) into (%d, %d)\n",
494 s->board[f], f % w, f / w, t % w, t / w);
495 s->board[t] = s->board[f];
496 for (j = 0; j < 4; ++j) {
497 const int x = (t % w) + dx[j];
498 const int y = (t / w) + dy[j];
499 const int idx = w*y + x;
500 if (x < 0 || x >= w || y < 0 || y >= h) continue;
501 if (s->board[idx] != s->board[t]) continue;
502 merge(s->dsf, s->connected, t, idx);
503 }
504 --s->nempty;
505}
506
507static void clear_count(int *board, int sz) {
508 int i;
509 for (i = 0; i < sz; ++i) {
510 if (board[i] >= 0) continue;
511 else if (board[i] == -SENTINEL) board[i] = EMPTY;
512 else board[i] = -board[i];
513 }
514}
515
516static void flood_count(int *board, int w, int h, int i, int n, int *c) {
517 const int sz = w * h;
518 int k;
519
520 if (board[i] == EMPTY) board[i] = -SENTINEL;
521 else if (board[i] == n) board[i] = -board[i];
522 else return;
523
524 if (--*c == 0) return;
525
526 for (k = 0; k < 4; ++k) {
527 const int x = (i % w) + dx[k];
528 const int y = (i / w) + dy[k];
529 const int idx = w*y + x;
530 if (x < 0 || x >= w || y < 0 || y >= h) continue;
531 flood_count(board, w, h, idx, n, c);
532 if (*c == 0) return;
533 }
534}
535
536static bool check_capacity(int *board, int w, int h, int i) {
537 int n = board[i];
538 flood_count(board, w, h, i, board[i], &n);
539 clear_count(board, w * h);
540 return n == 0;
541}
542
543static int expandsize(const int *board, DSF *dsf, int w, int h, int i, int n) {
544 int j;
545 int nhits = 0;
546 int hits[4];
547 int size = 1;
548 for (j = 0; j < 4; ++j) {
549 const int x = (i % w) + dx[j];
550 const int y = (i / w) + dy[j];
551 const int idx = w*y + x;
552 int root;
553 int m;
554 if (x < 0 || x >= w || y < 0 || y >= h) continue;
555 if (board[idx] != n) continue;
556 root = dsf_canonify(dsf, idx);
557 for (m = 0; m < nhits && root != hits[m]; ++m);
558 if (m < nhits) continue;
559 printv("\t (%d, %d) contrib %d to size\n", x, y, dsf_size(dsf, root));
560 size += dsf_size(dsf, root);
561 assert(dsf_size(dsf, root) >= 1);
562 hits[nhits++] = root;
563 }
564 return size;
565}
566
567/*
568 * +---+---+---+---+---+---+---+
569 * | 6 | | | 2 | | | 2 |
570 * +---+---+---+---+---+---+---+
571 * | | 3 | | 6 | | 3 | |
572 * +---+---+---+---+---+---+---+
573 * | 3 | | | | | | 1 |
574 * +---+---+---+---+---+---+---+
575 * | | 2 | 3 | | 4 | 2 | |
576 * +---+---+---+---+---+---+---+
577 * | 2 | | | | | | 3 |
578 * +---+---+---+---+---+---+---+
579 * | | 5 | | 1 | | 4 | |
580 * +---+---+---+---+---+---+---+
581 * | 4 | | | 3 | | | 3 |
582 * +---+---+---+---+---+---+---+
583 */
584
585/* Solving techniques:
586 *
587 * CONNECTED COMPONENT FORCED EXPANSION (too big):
588 * When a CC can only be expanded in one direction, because all the
589 * other ones would make the CC too big.
590 * +---+---+---+---+---+
591 * | 2 | 2 | | 2 | _ |
592 * +---+---+---+---+---+
593 *
594 * CONNECTED COMPONENT FORCED EXPANSION (too small):
595 * When a CC must include a particular square, because otherwise there
596 * would not be enough room to complete it. This includes squares not
597 * adjacent to the CC through learn_critical_square.
598 * +---+---+
599 * | 2 | _ |
600 * +---+---+
601 *
602 * DROPPING IN A ONE:
603 * When an empty square has no neighbouring empty squares and only a 1
604 * will go into the square (or other CCs would be too big).
605 * +---+---+---+
606 * | 2 | 2 | _ |
607 * +---+---+---+
608 *
609 * TODO: generalise DROPPING IN A ONE: find the size of the CC of
610 * empty squares and a list of all adjacent numbers. See if only one
611 * number in {1, ..., size} u {all adjacent numbers} is possible.
612 * Probably this is only effective for a CC size < n for some n (4?)
613 *
614 * TODO: backtracking.
615 */
616
617static void filled_square(struct solver_state *s, int w, int h, int i) {
618 int j;
619 for (j = 0; j < 4; ++j) {
620 const int x = (i % w) + dx[j];
621 const int y = (i / w) + dy[j];
622 const int idx = w*y + x;
623 if (x < 0 || x >= w || y < 0 || y >= h) continue;
624 if (s->board[i] == s->board[idx])
625 merge(s->dsf, s->connected, i, idx);
626 }
627}
628
629static void init_solver_state(struct solver_state *s, int w, int h) {
630 const int sz = w * h;
631 int i;
632 assert(s);
633
634 s->nempty = 0;
635 for (i = 0; i < sz; ++i) s->connected[i] = i;
636 for (i = 0; i < sz; ++i)
637 if (s->board[i] == EMPTY) ++s->nempty;
638 else filled_square(s, w, h, i);
639}
640
641static bool learn_expand_or_one(struct solver_state *s, int w, int h) {
642 const int sz = w * h;
643 int i;
644 bool learn = false;
645
646 assert(s);
647
648 for (i = 0; i < sz; ++i) {
649 int j;
650 bool one = true;
651
652 if (s->board[i] != EMPTY) continue;
653
654 for (j = 0; j < 4; ++j) {
655 const int x = (i % w) + dx[j];
656 const int y = (i / w) + dy[j];
657 const int idx = w*y + x;
658 if (x < 0 || x >= w || y < 0 || y >= h) continue;
659 if (s->board[idx] == EMPTY) {
660 one = false;
661 continue;
662 }
663 if (one &&
664 (s->board[idx] == 1 ||
665 (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
666 i, s->board[idx]))))
667 one = false;
668 if (dsf_size(s->dsf, idx) == s->board[idx]) continue;
669 assert(s->board[i] == EMPTY);
670 s->board[i] = -SENTINEL;
671 if (check_capacity(s->board, w, h, idx)) continue;
672 assert(s->board[i] == EMPTY);
673 printv("learn: expanding in one\n");
674 expand(s, w, h, i, idx);
675 learn = true;
676 break;
677 }
678
679 if (j == 4 && one) {
680 printv("learn: one at (%d, %d)\n", i % w, i / w);
681 assert(s->board[i] == EMPTY);
682 s->board[i] = 1;
683 assert(s->nempty);
684 --s->nempty;
685 learn = true;
686 }
687 }
688 return learn;
689}
690
691static bool learn_blocked_expansion(struct solver_state *s, int w, int h) {
692 const int sz = w * h;
693 int i;
694 bool learn = false;
695
696 assert(s);
697 /* for every connected component */
698 for (i = 0; i < sz; ++i) {
699 int exp = SENTINEL;
700 int j;
701
702 if (s->board[i] == EMPTY) continue;
703 j = dsf_canonify(s->dsf, i);
704
705 /* (but only for each connected component) */
706 if (i != j) continue;
707
708 /* (and not if it's already complete) */
709 if (dsf_size(s->dsf, j) == s->board[j]) continue;
710
711 /* for each square j _in_ the connected component */
712 do {
713 int k;
714 printv(" looking at (%d, %d)\n", j % w, j / w);
715
716 /* for each neighbouring square (idx) */
717 for (k = 0; k < 4; ++k) {
718 const int x = (j % w) + dx[k];
719 const int y = (j / w) + dy[k];
720 const int idx = w*y + x;
721 int size;
722 /* int l;
723 int nhits = 0;
724 int hits[4]; */
725 if (x < 0 || x >= w || y < 0 || y >= h) continue;
726 if (s->board[idx] != EMPTY) continue;
727 if (exp == idx) continue;
728 printv("\ttrying to expand onto (%d, %d)\n", x, y);
729
730 /* find out the would-be size of the new connected
731 * component if we actually expanded into idx */
732 /*
733 size = 1;
734 for (l = 0; l < 4; ++l) {
735 const int lx = x + dx[l];
736 const int ly = y + dy[l];
737 const int idxl = w*ly + lx;
738 int root;
739 int m;
740 if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
741 if (board[idxl] != board[j]) continue;
742 root = dsf_canonify(dsf, idxl);
743 for (m = 0; m < nhits && root != hits[m]; ++m);
744 if (m != nhits) continue;
745 // printv("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
746 size += dsf_size(dsf, root);
747 assert(dsf_size(dsf, root) >= 1);
748 hits[nhits++] = root;
749 }
750 */
751
752 size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
753
754 /* ... and see if that size is too big, or if we
755 * have other expansion candidates. Otherwise
756 * remember the (so far) only candidate. */
757
758 printv("\tthat would give a size of %d\n", size);
759 if (size > s->board[j]) continue;
760 /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
761 if (exp != SENTINEL) goto next_i;
762 assert(exp != idx);
763 exp = idx;
764 }
765
766 j = s->connected[j]; /* next square in the same CC */
767 assert(s->board[i] == s->board[j]);
768 } while (j != i);
769 /* end: for each square j _in_ the connected component */
770
771 if (exp == SENTINEL) continue;
772 printv("learning to expand\n");
773 expand(s, w, h, exp, i);
774 learn = true;
775
776 next_i:
777 ;
778 }
779 /* end: for each connected component */
780 return learn;
781}
782
783static bool learn_critical_square(struct solver_state *s, int w, int h) {
784 const int sz = w * h;
785 int i;
786 bool learn = false;
787 assert(s);
788
789 /* for each connected component */
790 for (i = 0; i < sz; ++i) {
791 int j, slack;
792 if (s->board[i] == EMPTY) continue;
793 if (i != dsf_canonify(s->dsf, i)) continue;
794 slack = s->board[i] - dsf_size(s->dsf, i);
795 if (slack == 0) continue;
796 assert(s->board[i] != 1);
797 /* for each empty square */
798 for (j = 0; j < sz; ++j) {
799 if (s->board[j] == EMPTY) {
800 /* if it's too far away from the CC, don't bother */
801 int k = i, jx = j % w, jy = j / w;
802 do {
803 int kx = k % w, ky = k / w;
804 if (abs(kx - jx) + abs(ky - jy) <= slack) break;
805 k = s->connected[k];
806 } while (i != k);
807 if (i == k) continue; /* not within range */
808 } else continue;
809 s->board[j] = -SENTINEL;
810 if (check_capacity(s->board, w, h, i)) continue;
811 /* if not expanding s->board[i] to s->board[j] implies
812 * that s->board[i] can't reach its full size, ... */
813 assert(s->nempty);
814 printv(
815 "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
816 s->board[i], j % w, j / w, i % w, i / w);
817 --s->nempty;
818 s->board[j] = s->board[i];
819 filled_square(s, w, h, j);
820 learn = true;
821 }
822 }
823 return learn;
824}
825
826#if 0
827static void print_bitmap(int *bitmap, int w, int h) {
828 if (verbose) {
829 int x, y;
830 for (y = 0; y < h; y++) {
831 for (x = 0; x < w; x++) {
832 printv(" %03x", bm[y*w+x]);
833 }
834 printv("\n");
835 }
836 }
837}
838#endif
839
840static bool learn_bitmap_deductions(struct solver_state *s, int w, int h)
841{
842 const int sz = w * h;
843 int *bm = s->bm;
844 DSF *dsf = s->bmdsf;
845 int *minsize = s->bmminsize;
846 int x, y, i, j, n;
847 bool learn = false;
848
849 /*
850 * This function does deductions based on building up a bitmap
851 * which indicates the possible numbers that can appear in each
852 * grid square. If we can rule out all but one possibility for a
853 * particular square, then we've found out the value of that
854 * square. In particular, this is one of the few forms of
855 * deduction capable of inferring the existence of a 'ghost
856 * region', i.e. a region which has none of its squares filled in
857 * at all.
858 *
859 * The reasoning goes like this. A currently unfilled square S can
860 * turn out to contain digit n in exactly two ways: either S is
861 * part of an n-region which also includes some currently known
862 * connected component of squares with n in, or S is part of an
863 * n-region separate from _all_ currently known connected
864 * components. If we can rule out both possibilities, then square
865 * S can't contain digit n at all.
866 *
867 * The former possibility: if there's a region of size n
868 * containing both S and some existing component C, then that
869 * means the distance from S to C must be small enough that C
870 * could be extended to include S without becoming too big. So we
871 * can do a breadth-first search out from all existing components
872 * with n in them, to identify all the squares which could be
873 * joined to any of them.
874 *
875 * The latter possibility: if there's a region of size n that
876 * doesn't contain _any_ existing component, then it also can't
877 * contain any square adjacent to an existing component either. So
878 * we can identify all the EMPTY squares not adjacent to any
879 * existing square with n in, and group them into connected
880 * components; then any component of size less than n is ruled
881 * out, because there wouldn't be room to create a completely new
882 * n-region in it.
883 *
884 * In fact we process these possibilities in the other order.
885 * First we find all the squares not adjacent to an existing
886 * square with n in; then we winnow those by removing too-small
887 * connected components, to get the set of squares which could
888 * possibly be part of a brand new n-region; and finally we do the
889 * breadth-first search to add in the set of squares which could
890 * possibly be added to some existing n-region.
891 */
892
893 /*
894 * Start by initialising our bitmap to 'all numbers possible in
895 * all squares'.
896 */
897 for (y = 0; y < h; y++)
898 for (x = 0; x < w; x++)
899 bm[y*w+x] = (1 << 10) - (1 << 1); /* bits 1,2,...,9 now set */
900#if 0
901 printv("initial bitmap:\n");
902 print_bitmap(bm, w, h);
903#endif
904
905 /*
906 * Now completely zero out the bitmap for squares that are already
907 * filled in (we aren't interested in those anyway). Also, for any
908 * filled square, eliminate its number from all its neighbours
909 * (because, as discussed above, the neighbours couldn't be part
910 * of a _new_ region with that number in it, and that's the case
911 * we consider first).
912 */
913 for (y = 0; y < h; y++) {
914 for (x = 0; x < w; x++) {
915 i = y*w+x;
916 n = s->board[i];
917
918 if (n != EMPTY) {
919 bm[i] = 0;
920
921 if (x > 0)
922 bm[i-1] &= ~(1 << n);
923 if (x+1 < w)
924 bm[i+1] &= ~(1 << n);
925 if (y > 0)
926 bm[i-w] &= ~(1 << n);
927 if (y+1 < h)
928 bm[i+w] &= ~(1 << n);
929 }
930 }
931 }
932#if 0
933 printv("bitmap after filled squares:\n");
934 print_bitmap(bm, w, h);
935#endif
936
937 /*
938 * Now, for each n, we separately find the connected components of
939 * squares for which n is still a possibility. Then discard any
940 * component of size < n, because that component is too small to
941 * have a completely new n-region in it.
942 */
943 for (n = 1; n <= 9; n++) {
944 dsf_reinit(dsf);
945
946 /* Build the dsf */
947 for (y = 0; y < h; y++)
948 for (x = 0; x+1 < w; x++)
949 if (bm[y*w+x] & bm[y*w+(x+1)] & (1 << n))
950 dsf_merge(dsf, y*w+x, y*w+(x+1));
951 for (y = 0; y+1 < h; y++)
952 for (x = 0; x < w; x++)
953 if (bm[y*w+x] & bm[(y+1)*w+x] & (1 << n))
954 dsf_merge(dsf, y*w+x, (y+1)*w+x);
955
956 /* Query the dsf */
957 for (i = 0; i < sz; i++)
958 if ((bm[i] & (1 << n)) && dsf_size(dsf, i) < n)
959 bm[i] &= ~(1 << n);
960 }
961#if 0
962 printv("bitmap after winnowing small components:\n");
963 print_bitmap(bm, w, h);
964#endif
965
966 /*
967 * Now our bitmap includes every square which could be part of a
968 * completely new region, of any size. Extend it to include
969 * squares which could be part of an existing region.
970 */
971 for (n = 1; n <= 9; n++) {
972 /*
973 * We're going to do a breadth-first search starting from
974 * existing connected components with cell value n, to find
975 * all cells they might possibly extend into.
976 *
977 * The quantity we compute, for each square, is 'minimum size
978 * that any existing CC would have to have if extended to
979 * include this square'. So squares already _in_ an existing
980 * CC are initialised to the size of that CC; then we search
981 * outwards using the rule that if a square's score is j, then
982 * its neighbours can't score more than j+1.
983 *
984 * Scores are capped at n+1, because if a square scores more
985 * than n then that's enough to know it can't possibly be
986 * reached by extending an existing region - we don't need to
987 * know exactly _how far_ out of reach it is.
988 */
989 for (i = 0; i < sz; i++) {
990 if (s->board[i] == n) {
991 /* Square is part of an existing CC. */
992 minsize[i] = dsf_size(s->dsf, i);
993 } else {
994 /* Otherwise, initialise to the maximum score n+1;
995 * we'll reduce this later if we find a neighbouring
996 * square with a lower score. */
997 minsize[i] = n+1;
998 }
999 }
1000
1001 for (j = 1; j < n; j++) {
1002 /*
1003 * Find neighbours of cells scoring j, and set their score
1004 * to at most j+1.
1005 *
1006 * Doing the BFS this way means we need n passes over the
1007 * grid, which isn't entirely optimal but it seems to be
1008 * fast enough for the moment. This could probably be
1009 * improved by keeping a linked-list queue of cells in
1010 * some way, but I think you'd have to be a bit careful to
1011 * insert things into the right place in the queue; this
1012 * way is easier not to get wrong.
1013 */
1014 for (y = 0; y < h; y++) {
1015 for (x = 0; x < w; x++) {
1016 i = y*w+x;
1017 if (minsize[i] == j) {
1018 if (x > 0 && minsize[i-1] > j+1)
1019 minsize[i-1] = j+1;
1020 if (x+1 < w && minsize[i+1] > j+1)
1021 minsize[i+1] = j+1;
1022 if (y > 0 && minsize[i-w] > j+1)
1023 minsize[i-w] = j+1;
1024 if (y+1 < h && minsize[i+w] > j+1)
1025 minsize[i+w] = j+1;
1026 }
1027 }
1028 }
1029 }
1030
1031 /*
1032 * Now, every cell scoring at most n should have its 1<<n bit
1033 * in the bitmap reinstated, because we've found that it's
1034 * potentially reachable by extending an existing CC.
1035 */
1036 for (i = 0; i < sz; i++)
1037 if (minsize[i] <= n)
1038 bm[i] |= 1<<n;
1039 }
1040#if 0
1041 printv("bitmap after bfs:\n");
1042 print_bitmap(bm, w, h);
1043#endif
1044
1045 /*
1046 * Now our bitmap is complete. Look for entries with only one bit
1047 * set; those are squares with only one possible number, in which
1048 * case we can fill that number in.
1049 */
1050 for (i = 0; i < sz; i++) {
1051 if (bm[i] && !(bm[i] & (bm[i]-1))) { /* is bm[i] a power of two? */
1052 int val = bm[i];
1053
1054 /* Integer log2, by simple binary search. */
1055 n = 0;
1056 if (val >> 8) { val >>= 8; n += 8; }
1057 if (val >> 4) { val >>= 4; n += 4; }
1058 if (val >> 2) { val >>= 2; n += 2; }
1059 if (val >> 1) { val >>= 1; n += 1; }
1060
1061 /* Double-check that we ended up with a sensible
1062 * answer. */
1063 assert(1 <= n);
1064 assert(n <= 9);
1065 assert(bm[i] == (1 << n));
1066
1067 if (s->board[i] == EMPTY) {
1068 printv("learn: %d is only possibility at (%d, %d)\n",
1069 n, i % w, i / w);
1070 s->board[i] = n;
1071 filled_square(s, w, h, i);
1072 assert(s->nempty);
1073 --s->nempty;
1074 learn = true;
1075 }
1076 }
1077 }
1078
1079 return learn;
1080}
1081
1082static bool solver(const int *orig, int w, int h, char **solution) {
1083 const int sz = w * h;
1084
1085 struct solver_state ss;
1086 ss.board = memdup(orig, sz, sizeof (int));
1087 ss.dsf = dsf_new(sz); /* eqv classes: connected components */
1088 ss.connected = snewn(sz, int); /* connected[n] := n.next; */
1089 /* cyclic disjoint singly linked lists, same partitioning as dsf.
1090 * The lists lets you iterate over a partition given any member */
1091 ss.bm = snewn(sz, int);
1092 ss.bmdsf = dsf_new(sz);
1093 ss.bmminsize = snewn(sz, int);
1094
1095 printv("trying to solve this:\n");
1096 print_board(ss.board, w, h);
1097
1098 init_solver_state(&ss, w, h);
1099 do {
1100 if (learn_blocked_expansion(&ss, w, h)) continue;
1101 if (learn_expand_or_one(&ss, w, h)) continue;
1102 if (learn_critical_square(&ss, w, h)) continue;
1103 if (learn_bitmap_deductions(&ss, w, h)) continue;
1104 break;
1105 } while (ss.nempty);
1106
1107 printv("best guess:\n");
1108 print_board(ss.board, w, h);
1109
1110 if (solution) {
1111 int i;
1112 *solution = snewn(sz + 2, char);
1113 **solution = 's';
1114 for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0';
1115 (*solution)[sz + 1] = '\0';
1116 }
1117
1118 dsf_free(ss.dsf);
1119 sfree(ss.board);
1120 sfree(ss.connected);
1121 sfree(ss.bm);
1122 dsf_free(ss.bmdsf);
1123 sfree(ss.bmminsize);
1124
1125 return !ss.nempty;
1126}
1127
1128static DSF *make_dsf(DSF *dsf, int *board, const int w, const int h) {
1129 const int sz = w * h;
1130 int i;
1131
1132 if (!dsf)
1133 dsf = dsf_new_min(w * h);
1134 else
1135 dsf_reinit(dsf);
1136
1137 for (i = 0; i < sz; ++i) {
1138 int j;
1139 for (j = 0; j < 4; ++j) {
1140 const int x = (i % w) + dx[j];
1141 const int y = (i / w) + dy[j];
1142 const int k = w*y + x;
1143 if (x < 0 || x >= w || y < 0 || y >= h) continue;
1144 if (board[i] == board[k]) dsf_merge(dsf, i, k);
1145 }
1146 }
1147 return dsf;
1148}
1149
1150static void minimize_clue_set(int *board, int w, int h, random_state *rs)
1151{
1152 const int sz = w * h;
1153 int *shuf = snewn(sz, int), i;
1154 DSF *dsf;
1155 int *next;
1156
1157 for (i = 0; i < sz; ++i) shuf[i] = i;
1158 shuffle(shuf, sz, sizeof (int), rs);
1159
1160 /*
1161 * First, try to eliminate an entire region at a time if possible,
1162 * because inferring the existence of a completely unclued region
1163 * is a particularly good aspect of this puzzle type and we want
1164 * to encourage it to happen.
1165 *
1166 * Begin by identifying the regions as linked lists of cells using
1167 * the 'next' array.
1168 */
1169 dsf = make_dsf(NULL, board, w, h);
1170 next = snewn(sz, int);
1171 for (i = 0; i < sz; ++i) {
1172 int j = dsf_minimal(dsf, i);
1173 if (i == j) {
1174 /* First cell of a region; set next[i] = -1 to indicate
1175 * end-of-list. */
1176 next[i] = -1;
1177 } else {
1178 /* Add this cell to a region which already has a
1179 * linked-list head, by pointing the minimal element j
1180 * at this one, and pointing this one in turn at wherever
1181 * j previously pointed. (This should end up with the
1182 * elements linked in the order 1,n,n-1,n-2,...,2, which
1183 * is a bit weird-looking, but any order is fine.)
1184 */
1185 assert(j < i);
1186 next[i] = next[j];
1187 next[j] = i;
1188 }
1189 }
1190
1191 /*
1192 * Now loop over the grid cells in our shuffled order, and each
1193 * time we encounter a region for the first time, try to remove it
1194 * all. Then we set next[canonical index] to -2 rather than -1, to
1195 * mark it as already tried.
1196 *
1197 * Doing this in a loop over _cells_, rather than extracting and
1198 * shuffling a list of _regions_, is intended to skew the
1199 * probabilities towards trying to remove larger regions first
1200 * (but without anything as crudely predictable as enforcing that
1201 * we _always_ process regions in descending size order). Region
1202 * removals might well be mutually exclusive, and larger ghost
1203 * regions are more interesting, so we want to bias towards them
1204 * if we can.
1205 */
1206 for (i = 0; i < sz; ++i) {
1207 int j = dsf_minimal(dsf, shuf[i]);
1208 if (next[j] != -2) {
1209 int tmp = board[j];
1210 int k;
1211
1212 /* Blank out the whole thing. */
1213 for (k = j; k >= 0; k = next[k])
1214 board[k] = EMPTY;
1215
1216 if (!solver(board, w, h, NULL)) {
1217 /* Wasn't still solvable; reinstate it all */
1218 for (k = j; k >= 0; k = next[k])
1219 board[k] = tmp;
1220 }
1221
1222 /* Either way, don't try this region again. */
1223 next[j] = -2;
1224 }
1225 }
1226 sfree(next);
1227 dsf_free(dsf);
1228
1229 /*
1230 * Now go through individual cells, in the same shuffled order,
1231 * and try to remove each one by itself.
1232 */
1233 for (i = 0; i < sz; ++i) {
1234 int tmp = board[shuf[i]];
1235 board[shuf[i]] = EMPTY;
1236 if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp;
1237 }
1238
1239 sfree(shuf);
1240}
1241
1242static int encode_run(char *buffer, int run)
1243{
1244 int i = 0;
1245 for (; run > 26; run -= 26)
1246 buffer[i++] = 'z';
1247 if (run)
1248 buffer[i++] = 'a' - 1 + run;
1249 return i;
1250}
1251
1252static char *new_game_desc(const game_params *params, random_state *rs,
1253 char **aux, bool interactive)
1254{
1255 const int w = params->w, h = params->h, sz = w * h;
1256 int *board = snewn(sz, int), i, j, run;
1257 char *description = snewn(sz + 1, char);
1258
1259 make_board(board, w, h, rs);
1260 minimize_clue_set(board, w, h, rs);
1261
1262 for (run = j = i = 0; i < sz; ++i) {
1263 assert(board[i] >= 0);
1264 assert(board[i] < 10);
1265 if (board[i] == 0) {
1266 ++run;
1267 } else {
1268 j += encode_run(description + j, run);
1269 run = 0;
1270 description[j++] = board[i] + '0';
1271 }
1272 }
1273 j += encode_run(description + j, run);
1274 description[j++] = '\0';
1275
1276 sfree(board);
1277
1278 return sresize(description, j, char);
1279}
1280
1281static const char *validate_desc(const game_params *params, const char *desc)
1282{
1283 const int sz = params->w * params->h;
1284 const char m = '0' + max(max(params->w, params->h), 3);
1285 int area;
1286
1287 for (area = 0; *desc; ++desc) {
1288 if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1;
1289 else if (*desc >= '0' && *desc <= m) ++area;
1290 else {
1291 static char s[] = "Invalid character '%""' in game description";
1292 int n = sprintf(s, "Invalid character '%1c' in game description",
1293 *desc);
1294 assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */
1295 return s;
1296 }
1297 if (area > sz) return "Too much data to fit in grid";
1298 }
1299 return (area < sz) ? "Not enough data to fill grid" : NULL;
1300}
1301
1302static key_label *game_request_keys(const game_params *params, int *nkeys)
1303{
1304 int i;
1305 key_label *keys = snewn(11, key_label);
1306
1307 *nkeys = 11;
1308
1309 for(i = 0; i < 10; ++i)
1310 {
1311 keys[i].button = '0' + i;
1312 keys[i].label = NULL;
1313 }
1314 keys[10].button = '\b';
1315 keys[10].label = NULL;
1316
1317 return keys;
1318}
1319
1320static game_state *new_game(midend *me, const game_params *params,
1321 const char *desc)
1322{
1323 game_state *state = snew(game_state);
1324 int sz = params->w * params->h;
1325 int i;
1326
1327 state->cheated = false;
1328 state->completed = false;
1329 state->shared = snew(struct shared_state);
1330 state->shared->refcnt = 1;
1331 state->shared->params = *params; /* struct copy */
1332 state->shared->clues = snewn(sz, int);
1333
1334 for (i = 0; *desc; ++desc) {
1335 if (*desc >= 'a' && *desc <= 'z') {
1336 int j = *desc - 'a' + 1;
1337 assert(i + j <= sz);
1338 for (; j; --j) state->shared->clues[i++] = 0;
1339 } else state->shared->clues[i++] = *desc - '0';
1340 }
1341 state->board = memdup(state->shared->clues, sz, sizeof (int));
1342
1343 return state;
1344}
1345
1346static game_state *dup_game(const game_state *state)
1347{
1348 const int sz = state->shared->params.w * state->shared->params.h;
1349 game_state *ret = snew(game_state);
1350
1351 ret->board = memdup(state->board, sz, sizeof (int));
1352 ret->shared = state->shared;
1353 ret->cheated = state->cheated;
1354 ret->completed = state->completed;
1355 ++ret->shared->refcnt;
1356
1357 return ret;
1358}
1359
1360static void free_game(game_state *state)
1361{
1362 assert(state);
1363 sfree(state->board);
1364 if (--state->shared->refcnt == 0) {
1365 sfree(state->shared->clues);
1366 sfree(state->shared);
1367 }
1368 sfree(state);
1369}
1370
1371static char *solve_game(const game_state *state, const game_state *currstate,
1372 const char *aux, const char **error)
1373{
1374 if (aux == NULL) {
1375 const int w = state->shared->params.w;
1376 const int h = state->shared->params.h;
1377 char *new_aux;
1378 if (!solver(state->board, w, h, &new_aux))
1379 *error = "Sorry, I couldn't find a solution";
1380 return new_aux;
1381 }
1382 return dupstr(aux);
1383}
1384
1385/*****************************************************************************
1386 * USER INTERFACE STATE AND ACTION *
1387 *****************************************************************************/
1388
1389struct game_ui {
1390 bool *sel; /* w*h highlighted squares, or NULL */
1391 int cur_x, cur_y;
1392 bool cur_visible, keydragging;
1393};
1394
1395static game_ui *new_ui(const game_state *state)
1396{
1397 game_ui *ui = snew(game_ui);
1398
1399 ui->sel = NULL;
1400 ui->cur_x = ui->cur_y = 0;
1401 ui->cur_visible = getenv_bool("PUZZLES_SHOW_CURSOR", false);
1402 ui->keydragging = false;
1403
1404 return ui;
1405}
1406
1407static void free_ui(game_ui *ui)
1408{
1409 if (ui->sel)
1410 sfree(ui->sel);
1411 sfree(ui);
1412}
1413
1414static void game_changed_state(game_ui *ui, const game_state *oldstate,
1415 const game_state *newstate)
1416{
1417 /* Clear any selection */
1418 if (ui->sel) {
1419 sfree(ui->sel);
1420 ui->sel = NULL;
1421 }
1422 ui->keydragging = false;
1423}
1424
1425static const char *current_key_label(const game_ui *ui,
1426 const game_state *state, int button)
1427{
1428 const int w = state->shared->params.w;
1429
1430 if (IS_CURSOR_SELECT(button) && ui->cur_visible) {
1431 if (button == CURSOR_SELECT) {
1432 if (ui->keydragging) return "Stop";
1433 return "Multiselect";
1434 }
1435 if (button == CURSOR_SELECT2 &&
1436 !state->shared->clues[w*ui->cur_y + ui->cur_x])
1437 return (ui->sel[w*ui->cur_y + ui->cur_x]) ? "Deselect" : "Select";
1438 }
1439 return "";
1440}
1441
1442#define PREFERRED_TILE_SIZE 32
1443#define TILE_SIZE (ds->tilesize)
1444#define BORDER (TILE_SIZE / 2)
1445#define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1446
1447struct game_drawstate {
1448 struct game_params params;
1449 int tilesize;
1450 bool started;
1451 int *v, *flags;
1452 DSF *dsf_scratch;
1453 int *border_scratch;
1454};
1455
1456static char *interpret_move(const game_state *state, game_ui *ui,
1457 const game_drawstate *ds,
1458 int x, int y, int button)
1459{
1460 const int w = state->shared->params.w;
1461 const int h = state->shared->params.h;
1462
1463 const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1464 const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1465
1466 char *move = NULL;
1467 int i;
1468
1469 assert(ui);
1470 assert(ds);
1471
1472 button = STRIP_BUTTON_MODIFIERS(button);
1473
1474 if (button == LEFT_BUTTON || button == LEFT_DRAG) {
1475 /* A left-click anywhere will clear the current selection. */
1476 if (button == LEFT_BUTTON) {
1477 if (ui->sel) {
1478 sfree(ui->sel);
1479 ui->sel = NULL;
1480 }
1481 }
1482 if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
1483 if (!ui->sel) {
1484 ui->sel = snewn(w*h, bool);
1485 memset(ui->sel, 0, w*h*sizeof(bool));
1486 }
1487 if (!state->shared->clues[w*ty+tx])
1488 ui->sel[w*ty+tx] = true;
1489 }
1490 ui->cur_visible = false;
1491 return MOVE_UI_UPDATE;
1492 }
1493
1494 if (IS_CURSOR_MOVE(button)) {
1495 ui->cur_visible = true;
1496 move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, false, NULL);
1497 if (ui->keydragging) goto select_square;
1498 return MOVE_UI_UPDATE;
1499 }
1500 if (button == CURSOR_SELECT) {
1501 if (!ui->cur_visible) {
1502 ui->cur_visible = true;
1503 return MOVE_UI_UPDATE;
1504 }
1505 ui->keydragging = !ui->keydragging;
1506 if (!ui->keydragging) return MOVE_UI_UPDATE;
1507
1508 select_square:
1509 if (!ui->sel) {
1510 ui->sel = snewn(w*h, bool);
1511 memset(ui->sel, 0, w*h*sizeof(bool));
1512 }
1513 if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
1514 ui->sel[w*ui->cur_y + ui->cur_x] = true;
1515 return MOVE_UI_UPDATE;
1516 }
1517 if (button == CURSOR_SELECT2) {
1518 if (!ui->cur_visible) {
1519 ui->cur_visible = true;
1520 return MOVE_UI_UPDATE;
1521 }
1522 if (!ui->sel) {
1523 ui->sel = snewn(w*h, bool);
1524 memset(ui->sel, 0, w*h*sizeof(bool));
1525 }
1526 ui->keydragging = false;
1527 if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
1528 ui->sel[w*ui->cur_y + ui->cur_x] ^= 1;
1529 for (i = 0; i < w*h && !ui->sel[i]; i++);
1530 if (i == w*h) {
1531 sfree(ui->sel);
1532 ui->sel = NULL;
1533 }
1534 return MOVE_UI_UPDATE;
1535 }
1536
1537 if (button == 27) { /* Esc just cancels the current selection */
1538 sfree(ui->sel);
1539 ui->sel = NULL;
1540 ui->keydragging = false;
1541 return MOVE_UI_UPDATE;
1542 }
1543
1544 if (button == '\b')
1545 button = '0'; /* Backspace clears the current selection, like '0' */
1546 if (button < '0' || button > '9') return MOVE_UNUSED;
1547 button -= '0';
1548 if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return MOVE_UNUSED;
1549 ui->keydragging = false;
1550
1551 for (i = 0; i < w*h; i++) {
1552 char buf[32];
1553 if ((ui->sel && ui->sel[i]) ||
1554 (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) {
1555 if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */
1556 if (state->board[i] != button) {
1557 sprintf(buf, "%s%d", move ? "," : "", i);
1558 if (move) {
1559 move = srealloc(move, strlen(move)+strlen(buf)+1);
1560 strcat(move, buf);
1561 } else {
1562 move = smalloc(strlen(buf)+1);
1563 strcpy(move, buf);
1564 }
1565 }
1566 }
1567 }
1568 if (move) {
1569 char buf[32];
1570 sprintf(buf, "_%d", button);
1571 move = srealloc(move, strlen(move)+strlen(buf)+1);
1572 strcat(move, buf);
1573 }
1574 if (!ui->sel) return move ? move : MOVE_NO_EFFECT;
1575 sfree(ui->sel);
1576 ui->sel = NULL;
1577 /* Need to update UI at least, as we cleared the selection */
1578 return move ? move : MOVE_UI_UPDATE;
1579}
1580
1581static game_state *execute_move(const game_state *state, const char *move)
1582{
1583 game_state *new_state = NULL;
1584 const int sz = state->shared->params.w * state->shared->params.h;
1585
1586 if (*move == 's') {
1587 int i = 0;
1588 if (strlen(move) != sz + 1) return NULL;
1589 new_state = dup_game(state);
1590 for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
1591 new_state->cheated = true;
1592 } else {
1593 int value;
1594 char *endptr, *delim = strchr(move, '_');
1595 if (!delim) goto err;
1596 value = strtol(delim+1, &endptr, 0);
1597 if (*endptr || endptr == delim+1) goto err;
1598 if (value < 0 || value > 9) goto err;
1599 new_state = dup_game(state);
1600 while (*move) {
1601 const int i = strtol(move, &endptr, 0);
1602 if (endptr == move) goto err;
1603 if (i < 0 || i >= sz) goto err;
1604 new_state->board[i] = value;
1605 if (*endptr == '_') break;
1606 if (*endptr != ',') goto err;
1607 move = endptr + 1;
1608 }
1609 }
1610
1611 /*
1612 * Check for completion.
1613 */
1614 if (!new_state->completed) {
1615 const int w = new_state->shared->params.w;
1616 const int h = new_state->shared->params.h;
1617 const int sz = w * h;
1618 DSF *dsf = make_dsf(NULL, new_state->board, w, h);
1619 int i;
1620 for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1621 dsf_free(dsf);
1622 if (i == sz)
1623 new_state->completed = true;
1624 }
1625
1626 return new_state;
1627
1628err:
1629 if (new_state) free_game(new_state);
1630 return NULL;
1631}
1632
1633/* ----------------------------------------------------------------------
1634 * Drawing routines.
1635 */
1636
1637#define FLASH_TIME 0.4F
1638
1639#define COL_CLUE COL_GRID
1640enum {
1641 COL_BACKGROUND,
1642 COL_GRID,
1643 COL_HIGHLIGHT,
1644 COL_CORRECT,
1645 COL_ERROR,
1646 COL_USER,
1647 COL_CURSOR,
1648 NCOLOURS
1649};
1650
1651static void game_compute_size(const game_params *params, int tilesize,
1652 const game_ui *ui, int *x, int *y)
1653{
1654 *x = (params->w + 1) * tilesize;
1655 *y = (params->h + 1) * tilesize;
1656}
1657
1658static void game_set_size(drawing *dr, game_drawstate *ds,
1659 const game_params *params, int tilesize)
1660{
1661 ds->tilesize = tilesize;
1662}
1663
1664static float *game_colours(frontend *fe, int *ncolours)
1665{
1666 float *ret = snewn(3 * NCOLOURS, float);
1667
1668 frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1669
1670 ret[COL_GRID * 3 + 0] = 0.0F;
1671 ret[COL_GRID * 3 + 1] = 0.0F;
1672 ret[COL_GRID * 3 + 2] = 0.0F;
1673
1674 ret[COL_HIGHLIGHT * 3 + 0] = 0.7F * ret[COL_BACKGROUND * 3 + 0];
1675 ret[COL_HIGHLIGHT * 3 + 1] = 0.7F * ret[COL_BACKGROUND * 3 + 1];
1676 ret[COL_HIGHLIGHT * 3 + 2] = 0.7F * ret[COL_BACKGROUND * 3 + 2];
1677
1678 ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1679 ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1680 ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1681
1682 ret[COL_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1683 ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1684 ret[COL_CURSOR * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1685
1686 ret[COL_ERROR * 3 + 0] = 1.0F;
1687 ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1688 ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1689
1690 ret[COL_USER * 3 + 0] = 0.0F;
1691 ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1692 ret[COL_USER * 3 + 2] = 0.0F;
1693
1694 *ncolours = NCOLOURS;
1695 return ret;
1696}
1697
1698static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
1699{
1700 struct game_drawstate *ds = snew(struct game_drawstate);
1701 int i;
1702
1703 ds->tilesize = PREFERRED_TILE_SIZE;
1704 ds->started = false;
1705 ds->params = state->shared->params;
1706 ds->v = snewn(ds->params.w * ds->params.h, int);
1707 ds->flags = snewn(ds->params.w * ds->params.h, int);
1708 for (i = 0; i < ds->params.w * ds->params.h; i++)
1709 ds->v[i] = ds->flags[i] = -1;
1710 ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1711 ds->dsf_scratch = NULL;
1712
1713 return ds;
1714}
1715
1716static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1717{
1718 sfree(ds->v);
1719 sfree(ds->flags);
1720 sfree(ds->border_scratch);
1721 dsf_free(ds->dsf_scratch);
1722 sfree(ds);
1723}
1724
1725#define BORDER_U 0x001
1726#define BORDER_D 0x002
1727#define BORDER_L 0x004
1728#define BORDER_R 0x008
1729#define BORDER_UR 0x010
1730#define BORDER_DR 0x020
1731#define BORDER_UL 0x040
1732#define BORDER_DL 0x080
1733#define HIGH_BG 0x100
1734#define CORRECT_BG 0x200
1735#define ERROR_BG 0x400
1736#define USER_COL 0x800
1737#define CURSOR_SQ 0x1000
1738
1739static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1740 int n, int flags)
1741{
1742 assert(dr);
1743 assert(ds);
1744
1745 /*
1746 * Clip to the grid square.
1747 */
1748 clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1749 TILE_SIZE, TILE_SIZE);
1750
1751 /*
1752 * Clear the square.
1753 */
1754 draw_rect(dr,
1755 BORDER + x*TILE_SIZE,
1756 BORDER + y*TILE_SIZE,
1757 TILE_SIZE,
1758 TILE_SIZE,
1759 (flags & HIGH_BG ? COL_HIGHLIGHT :
1760 flags & ERROR_BG ? COL_ERROR :
1761 flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1762
1763 /*
1764 * Draw the grid lines.
1765 */
1766 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1767 BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1768 draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1769 BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1770
1771 /*
1772 * Draw the number.
1773 */
1774 if (n) {
1775 char buf[2];
1776 buf[0] = n + '0';
1777 buf[1] = '\0';
1778 draw_text(dr,
1779 (x + 1) * TILE_SIZE,
1780 (y + 1) * TILE_SIZE,
1781 FONT_VARIABLE,
1782 TILE_SIZE / 2,
1783 ALIGN_VCENTRE | ALIGN_HCENTRE,
1784 flags & USER_COL ? COL_USER : COL_CLUE,
1785 buf);
1786 }
1787
1788 /*
1789 * Draw bold lines around the borders.
1790 */
1791 if (flags & BORDER_L)
1792 draw_rect(dr,
1793 BORDER + x*TILE_SIZE + 1,
1794 BORDER + y*TILE_SIZE + 1,
1795 BORDER_WIDTH,
1796 TILE_SIZE - 1,
1797 COL_GRID);
1798 if (flags & BORDER_U)
1799 draw_rect(dr,
1800 BORDER + x*TILE_SIZE + 1,
1801 BORDER + y*TILE_SIZE + 1,
1802 TILE_SIZE - 1,
1803 BORDER_WIDTH,
1804 COL_GRID);
1805 if (flags & BORDER_R)
1806 draw_rect(dr,
1807 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1808 BORDER + y*TILE_SIZE + 1,
1809 BORDER_WIDTH,
1810 TILE_SIZE - 1,
1811 COL_GRID);
1812 if (flags & BORDER_D)
1813 draw_rect(dr,
1814 BORDER + x*TILE_SIZE + 1,
1815 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1816 TILE_SIZE - 1,
1817 BORDER_WIDTH,
1818 COL_GRID);
1819 if (flags & BORDER_UL)
1820 draw_rect(dr,
1821 BORDER + x*TILE_SIZE + 1,
1822 BORDER + y*TILE_SIZE + 1,
1823 BORDER_WIDTH,
1824 BORDER_WIDTH,
1825 COL_GRID);
1826 if (flags & BORDER_UR)
1827 draw_rect(dr,
1828 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1829 BORDER + y*TILE_SIZE + 1,
1830 BORDER_WIDTH,
1831 BORDER_WIDTH,
1832 COL_GRID);
1833 if (flags & BORDER_DL)
1834 draw_rect(dr,
1835 BORDER + x*TILE_SIZE + 1,
1836 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1837 BORDER_WIDTH,
1838 BORDER_WIDTH,
1839 COL_GRID);
1840 if (flags & BORDER_DR)
1841 draw_rect(dr,
1842 BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1843 BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1844 BORDER_WIDTH,
1845 BORDER_WIDTH,
1846 COL_GRID);
1847
1848 if (flags & CURSOR_SQ) {
1849 int coff = TILE_SIZE/8;
1850 draw_rect_outline(dr,
1851 BORDER + x*TILE_SIZE + coff,
1852 BORDER + y*TILE_SIZE + coff,
1853 TILE_SIZE - coff*2,
1854 TILE_SIZE - coff*2,
1855 COL_CURSOR);
1856 }
1857
1858 unclip(dr);
1859
1860 draw_update(dr,
1861 BORDER + x*TILE_SIZE,
1862 BORDER + y*TILE_SIZE,
1863 TILE_SIZE,
1864 TILE_SIZE);
1865}
1866
1867static void draw_grid(
1868 drawing *dr, game_drawstate *ds, const game_state *state,
1869 const game_ui *ui, bool flashy, bool borders, bool shading)
1870{
1871 const int w = state->shared->params.w;
1872 const int h = state->shared->params.h;
1873 int x;
1874 int y;
1875
1876 /*
1877 * Build a dsf for the board in its current state, to use for
1878 * highlights and hints.
1879 */
1880 ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1881
1882 /*
1883 * Work out where we're putting borders between the cells.
1884 */
1885 for (y = 0; y < w*h; y++)
1886 ds->border_scratch[y] = 0;
1887
1888 for (y = 0; y < h; y++)
1889 for (x = 0; x < w; x++) {
1890 int dx, dy;
1891 int v1, s1, v2, s2;
1892
1893 for (dx = 0; dx <= 1; dx++) {
1894 bool border = false;
1895
1896 dy = 1 - dx;
1897
1898 if (x+dx >= w || y+dy >= h)
1899 continue;
1900
1901 v1 = state->board[y*w+x];
1902 v2 = state->board[(y+dy)*w+(x+dx)];
1903 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1904 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1905
1906 /*
1907 * We only ever draw a border between two cells if
1908 * they don't have the same contents.
1909 */
1910 if (v1 != v2) {
1911 /*
1912 * But in that situation, we don't always draw
1913 * a border. We do if the two cells both
1914 * contain actual numbers...
1915 */
1916 if (v1 && v2)
1917 border = true;
1918
1919 /*
1920 * ... or if at least one of them is a
1921 * completed or overfull omino.
1922 */
1923 if (v1 && s1 >= v1)
1924 border = true;
1925 if (v2 && s2 >= v2)
1926 border = true;
1927 }
1928
1929 if (border)
1930 ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1931 }
1932 }
1933
1934 /*
1935 * Actually do the drawing.
1936 */
1937 for (y = 0; y < h; ++y)
1938 for (x = 0; x < w; ++x) {
1939 /*
1940 * Determine what we need to draw in this square.
1941 */
1942 int i = y*w+x, v = state->board[i];
1943 int flags = 0;
1944
1945 if (flashy || !shading) {
1946 /* clear all background flags */
1947 } else if (ui && ui->sel && ui->sel[i]) {
1948 flags |= HIGH_BG;
1949 } else if (v) {
1950 int size = dsf_size(ds->dsf_scratch, i);
1951 if (size == v)
1952 flags |= CORRECT_BG;
1953 else if (size > v)
1954 flags |= ERROR_BG;
1955 else {
1956 int rt = dsf_canonify(ds->dsf_scratch, i), j;
1957 for (j = 0; j < w*h; ++j) {
1958 int k;
1959 if (dsf_canonify(ds->dsf_scratch, j) != rt) continue;
1960 for (k = 0; k < 4; ++k) {
1961 const int xx = j % w + dx[k], yy = j / w + dy[k];
1962 if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
1963 state->board[yy*w + xx] == EMPTY)
1964 goto noflag;
1965 }
1966 }
1967 flags |= ERROR_BG;
1968 noflag:
1969 ;
1970 }
1971 }
1972 if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
1973 flags |= CURSOR_SQ;
1974
1975 /*
1976 * Borders at the very edges of the grid are
1977 * independent of the `borders' flag.
1978 */
1979 if (x == 0)
1980 flags |= BORDER_L;
1981 if (y == 0)
1982 flags |= BORDER_U;
1983 if (x == w-1)
1984 flags |= BORDER_R;
1985 if (y == h-1)
1986 flags |= BORDER_D;
1987
1988 if (borders) {
1989 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1990 flags |= BORDER_L;
1991 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1992 flags |= BORDER_U;
1993 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1994 flags |= BORDER_R;
1995 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1996 flags |= BORDER_D;
1997
1998 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1999 flags |= BORDER_UL;
2000 if (y > 0 && x < w-1 &&
2001 ((ds->border_scratch[(y-1)*w+x] & 1) ||
2002 (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
2003 flags |= BORDER_UR;
2004 if (y < h-1 && x > 0 &&
2005 ((ds->border_scratch[y*w+(x-1)] & 2) ||
2006 (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
2007 flags |= BORDER_DL;
2008 if (y < h-1 && x < w-1 &&
2009 ((ds->border_scratch[y*w+(x+1)] & 2) ||
2010 (ds->border_scratch[(y+1)*w+x] & 1)))
2011 flags |= BORDER_DR;
2012 }
2013
2014 if (!state->shared->clues[y*w+x])
2015 flags |= USER_COL;
2016
2017 if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
2018 draw_square(dr, ds, x, y, v, flags);
2019 ds->v[y*w+x] = v;
2020 ds->flags[y*w+x] = flags;
2021 }
2022 }
2023}
2024
2025static void game_redraw(drawing *dr, game_drawstate *ds,
2026 const game_state *oldstate, const game_state *state,
2027 int dir, const game_ui *ui,
2028 float animtime, float flashtime)
2029{
2030 const int w = state->shared->params.w;
2031 const int h = state->shared->params.h;
2032
2033 const bool flashy =
2034 flashtime > 0 &&
2035 (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
2036
2037 if (!ds->started) {
2038 /*
2039 * Black rectangle which is the main grid.
2040 */
2041 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2042 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2043 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2044 COL_GRID);
2045
2046 draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
2047
2048 ds->started = true;
2049 }
2050
2051 draw_grid(dr, ds, state, ui, flashy, true, true);
2052}
2053
2054static float game_anim_length(const game_state *oldstate,
2055 const game_state *newstate, int dir, game_ui *ui)
2056{
2057 return 0.0F;
2058}
2059
2060static float game_flash_length(const game_state *oldstate,
2061 const game_state *newstate, int dir, game_ui *ui)
2062{
2063 assert(oldstate);
2064 assert(newstate);
2065 assert(newstate->shared);
2066 assert(oldstate->shared == newstate->shared);
2067 if (!oldstate->completed && newstate->completed &&
2068 !oldstate->cheated && !newstate->cheated)
2069 return FLASH_TIME;
2070 return 0.0F;
2071}
2072
2073static void game_get_cursor_location(const game_ui *ui,
2074 const game_drawstate *ds,
2075 const game_state *state,
2076 const game_params *params,
2077 int *x, int *y, int *w, int *h)
2078{
2079 if(ui->cur_visible)
2080 {
2081 *x = BORDER + ui->cur_x * TILE_SIZE;
2082 *y = BORDER + ui->cur_y * TILE_SIZE;
2083 *w = *h = TILE_SIZE;
2084 }
2085}
2086
2087static int game_status(const game_state *state)
2088{
2089 return state->completed ? +1 : 0;
2090}
2091
2092static void game_print_size(const game_params *params, const game_ui *ui,
2093 float *x, float *y)
2094{
2095 int pw, ph;
2096
2097 /*
2098 * I'll use 6mm squares by default.
2099 */
2100 game_compute_size(params, 600, ui, &pw, &ph);
2101 *x = pw / 100.0F;
2102 *y = ph / 100.0F;
2103}
2104
2105static void game_print(drawing *dr, const game_state *state, const game_ui *ui,
2106 int tilesize)
2107{
2108 const int w = state->shared->params.w;
2109 const int h = state->shared->params.h;
2110 int c, i;
2111 bool borders;
2112
2113 /* Ick: fake up `ds->tilesize' for macro expansion purposes */
2114 game_drawstate *ds = game_new_drawstate(dr, state);
2115 game_set_size(dr, ds, NULL, tilesize);
2116
2117 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
2118 c = print_mono_colour(dr, 0); assert(c == COL_GRID);
2119 c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
2120 c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
2121 c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
2122 c = print_mono_colour(dr, 0); assert(c == COL_USER);
2123
2124 /*
2125 * Border.
2126 */
2127 draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
2128 w*TILE_SIZE + 2*BORDER_WIDTH + 1,
2129 h*TILE_SIZE + 2*BORDER_WIDTH + 1,
2130 COL_GRID);
2131
2132 /*
2133 * We'll draw borders between the ominoes iff the grid is not
2134 * pristine. So scan it to see if it is.
2135 */
2136 borders = false;
2137 for (i = 0; i < w*h; i++)
2138 if (state->board[i] && !state->shared->clues[i])
2139 borders = true;
2140
2141 /*
2142 * Draw grid.
2143 */
2144 print_line_width(dr, TILE_SIZE / 64);
2145 draw_grid(dr, ds, state, NULL, false, borders, false);
2146
2147 /*
2148 * Clean up.
2149 */
2150 game_free_drawstate(dr, ds);
2151}
2152
2153#ifdef COMBINED
2154#define thegame filling
2155#endif
2156
2157const struct game thegame = {
2158 "Filling", "games.filling", "filling",
2159 default_params,
2160 game_fetch_preset, NULL,
2161 decode_params,
2162 encode_params,
2163 free_params,
2164 dup_params,
2165 true, game_configure, custom_params,
2166 validate_params,
2167 new_game_desc,
2168 validate_desc,
2169 new_game,
2170 dup_game,
2171 free_game,
2172 true, solve_game,
2173 true, game_can_format_as_text_now, game_text_format,
2174 NULL, NULL, /* get_prefs, set_prefs */
2175 new_ui,
2176 free_ui,
2177 NULL, /* encode_ui */
2178 NULL, /* decode_ui */
2179 game_request_keys,
2180 game_changed_state,
2181 current_key_label,
2182 interpret_move,
2183 execute_move,
2184 PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
2185 game_colours,
2186 game_new_drawstate,
2187 game_free_drawstate,
2188 game_redraw,
2189 game_anim_length,
2190 game_flash_length,
2191 game_get_cursor_location,
2192 game_status,
2193 true, false, game_print_size, game_print,
2194 false, /* wants_statusbar */
2195 false, NULL, /* timing_state */
2196 REQUIRE_NUMPAD, /* flags */
2197};
2198
2199#ifdef STANDALONE_SOLVER /* solver? hah! */
2200
2201int main(int argc, char **argv) {
2202 if (!strcmp(argv[1], "--verbose")) {
2203 verbose = true;
2204 argv++;
2205 }
2206
2207 while (*++argv) {
2208 game_params *params;
2209 game_state *state;
2210 char *par;
2211 char *desc;
2212
2213 for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
2214 if (*desc == '\0') {
2215 fprintf(stderr, "bad puzzle id: %s", par);
2216 continue;
2217 }
2218
2219 *desc++ = '\0';
2220
2221 params = snew(game_params);
2222 decode_params(params, par);
2223 state = new_game(NULL, params, desc);
2224 if (solver(state->board, params->w, params->h, NULL))
2225 printf("%s:%s: solvable\n", par, desc);
2226 else
2227 printf("%s:%s: not solvable\n", par, desc);
2228 }
2229 return 0;
2230}
2231
2232#endif
2233
2234/* vim: set shiftwidth=4 tabstop=8: */