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