chiark / gitweb /
Changed my mind about midend_is_solved: I've now reprototyped it as
[sgt-puzzles.git] / filling.c
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  *  - make a somewhat more clever solver
15  *     + enable "ghost regions" of size > 1
16  *        - one can put an upper bound on the size of a ghost region
17  *          by considering the board size and summing present hints.
18  *     + for each square, for i=1..n, what is the distance to a region
19  *       containing i?  How full is the region?  How is this useful?
20  *
21  *  - in board generation, after having merged regions such that no
22  *    more merges are necessary, try splitting (big) regions.
23  *     + it seems that smaller regions make for better puzzles; see
24  *       for instance the 7x7 puzzle in this file (grep for 7x7:).
25  *
26  *  - symmetric hints (solo-style)
27  *     + right now that means including _many_ hints, and the puzzles
28  *       won't look any nicer.  Not worth it (at the moment).
29  *
30  *  - make the solver do recursion/backtracking.
31  *     + This is for user-submitted puzzles, not for puzzle
32  *       generation (on the other hand, never say never).
33  *
34  *  - prove that only w=h=2 needs a special case
35  *
36  *  - solo-like pencil marks?
37  *
38  *  - a user says that the difficulty is unevenly distributed.
39  *     + partition into levels?  Will they be non-crap?
40  *
41  *  - Allow square contents > 9?
42  *     + I could use letters for digits (solo does this), but
43  *       letters don't have numeric significance (normal people hate
44  *       base36), which is relevant here (much more than in solo).
45  *     + [click, 1, 0, enter] => [10 in clicked square]?
46  *     + How much information is needed to solve?  Does one need to
47  *       know the algorithm by which the largest number is set?
48  *
49  *  - eliminate puzzle instances with done chunks (1's in particular)?
50  *     + that's what the qsort call is all about.
51  *     + the 1's don't bother me that much.
52  *     + but this takes a LONG time (not always possible)?
53  *        - this may be affected by solver (lack of) quality.
54  *        - weed them out by construction instead of post-cons check
55  *           + but that interleaves make_board and new_game_desc: you
56  *             have to alternate between changing the board and
57  *             changing the hint set (instead of just creating the
58  *             board once, then changing the hint set once -> done).
59  *
60  *  - use binary search when discovering the minimal sovable point
61  *     + profile to show a need (but when the solver gets slower...)
62  *     + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100)
63  *     + but the hints are independent, not linear, so... what?
64  */
65
66 #include <assert.h>
67 #include <ctype.h>
68 #include <math.h>
69 #include <stdarg.h>
70 #include <stdio.h>
71 #include <stdlib.h>
72 #include <string.h>
73
74 #include "puzzles.h"
75
76 static unsigned char verbose;
77
78 static void printv(char *fmt, ...) {
79 #ifndef PALM
80     if (verbose) {
81         va_list va;
82         va_start(va, fmt);
83         vprintf(fmt, va);
84         va_end(va);
85     }
86 #endif
87 }
88
89 /*****************************************************************************
90  * GAME CONFIGURATION AND PARAMETERS                                         *
91  *****************************************************************************/
92
93 struct game_params {
94     int h, w;
95 };
96
97 struct shared_state {
98     struct game_params params;
99     int *clues;
100     int refcnt;
101 };
102
103 struct game_state {
104     int *board;
105     struct shared_state *shared;
106     int completed, cheated;
107 };
108
109 static const struct game_params filling_defaults[3] = {{7, 9}, {9, 13}, {13, 17}};
110
111 static game_params *default_params(void)
112 {
113     game_params *ret = snew(game_params);
114
115     *ret = filling_defaults[1]; /* struct copy */
116
117     return ret;
118 }
119
120 static int game_fetch_preset(int i, char **name, game_params **params)
121 {
122     char buf[64];
123
124     if (i < 0 || i >= lenof(filling_defaults)) return FALSE;
125     *params = snew(game_params);
126     **params = filling_defaults[i]; /* struct copy */
127     sprintf(buf, "%dx%d", filling_defaults[i].h, filling_defaults[i].w);
128     *name = dupstr(buf);
129
130     return TRUE;
131 }
132
133 static void free_params(game_params *params)
134 {
135     sfree(params);
136 }
137
138 static game_params *dup_params(game_params *params)
139 {
140     game_params *ret = snew(game_params);
141     *ret = *params; /* struct copy */
142     return ret;
143 }
144
145 static void decode_params(game_params *ret, char const *string)
146 {
147     ret->w = ret->h = atoi(string);
148     while (*string && isdigit((unsigned char) *string)) ++string;
149     if (*string == 'x') ret->h = atoi(++string);
150 }
151
152 static char *encode_params(game_params *params, int full)
153 {
154     char buf[64];
155     sprintf(buf, "%dx%d", params->w, params->h);
156     return dupstr(buf);
157 }
158
159 static config_item *game_configure(game_params *params)
160 {
161     config_item *ret;
162     char buf[64];
163
164     ret = snewn(3, config_item);
165
166     ret[0].name = "Width";
167     ret[0].type = C_STRING;
168     sprintf(buf, "%d", params->w);
169     ret[0].sval = dupstr(buf);
170     ret[0].ival = 0;
171
172     ret[1].name = "Height";
173     ret[1].type = C_STRING;
174     sprintf(buf, "%d", params->h);
175     ret[1].sval = dupstr(buf);
176     ret[1].ival = 0;
177
178     ret[2].name = NULL;
179     ret[2].type = C_END;
180     ret[2].sval = NULL;
181     ret[2].ival = 0;
182
183     return ret;
184 }
185
186 static game_params *custom_params(config_item *cfg)
187 {
188     game_params *ret = snew(game_params);
189
190     ret->w = atoi(cfg[0].sval);
191     ret->h = atoi(cfg[1].sval);
192
193     return ret;
194 }
195
196 static char *validate_params(game_params *params, int full)
197 {
198     if (params->w < 1) return "Width must be at least one";
199     if (params->h < 1) return "Height must be at least one";
200
201     return NULL;
202 }
203
204 /*****************************************************************************
205  * STRINGIFICATION OF GAME STATE                                             *
206  *****************************************************************************/
207
208 #define EMPTY 0
209
210 /* Example of plaintext rendering:
211  *  +---+---+---+---+---+---+---+
212  *  | 6 |   |   | 2 |   |   | 2 |
213  *  +---+---+---+---+---+---+---+
214  *  |   | 3 |   | 6 |   | 3 |   |
215  *  +---+---+---+---+---+---+---+
216  *  | 3 |   |   |   |   |   | 1 |
217  *  +---+---+---+---+---+---+---+
218  *  |   | 2 | 3 |   | 4 | 2 |   |
219  *  +---+---+---+---+---+---+---+
220  *  | 2 |   |   |   |   |   | 3 |
221  *  +---+---+---+---+---+---+---+
222  *  |   | 5 |   | 1 |   | 4 |   |
223  *  +---+---+---+---+---+---+---+
224  *  | 4 |   |   | 3 |   |   | 3 |
225  *  +---+---+---+---+---+---+---+
226  *
227  * This puzzle instance is taken from the nikoli website
228  * Encoded (unsolved and solved), the strings are these:
229  * 7x7:6002002030603030000010230420200000305010404003003
230  * 7x7:6662232336663232331311235422255544325413434443313
231  */
232 static char *board_to_string(int *board, int w, int h) {
233     const int sz = w * h;
234     const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
235     const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
236     const int chlen = chw * chh;
237     char *repr = snewn(chlen + 1, char);
238     int i;
239
240     assert(board);
241
242     /* build the first line ("^(\+---){n}\+$") */
243     for (i = 0; i < w; ++i) {
244         repr[4*i + 0] = '+';
245         repr[4*i + 1] = '-';
246         repr[4*i + 2] = '-';
247         repr[4*i + 3] = '-';
248     }
249     repr[4*i + 0] = '+';
250     repr[4*i + 1] = '\n';
251
252     /* ... and copy it onto the odd-numbered lines */
253     for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
254
255     /* build the second line ("^(\|\t){n}\|$") */
256     for (i = 0; i < w; ++i) {
257         repr[chw + 4*i + 0] = '|';
258         repr[chw + 4*i + 1] = ' ';
259         repr[chw + 4*i + 2] = ' ';
260         repr[chw + 4*i + 3] = ' ';
261     }
262     repr[chw + 4*i + 0] = '|';
263     repr[chw + 4*i + 1] = '\n';
264
265     /* ... and copy it onto the even-numbered lines */
266     for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
267
268     /* fill in the numbers */
269     for (i = 0; i < sz; ++i) {
270         const int x = i % w;
271         const int y = i / w;
272         if (board[i] == EMPTY) continue;
273         repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
274     }
275
276     repr[chlen] = '\0';
277     return repr;
278 }
279
280 static int game_can_format_as_text_now(game_params *params)
281 {
282     return TRUE;
283 }
284
285 static char *game_text_format(game_state *state)
286 {
287     const int w = state->shared->params.w;
288     const int h = state->shared->params.h;
289     return board_to_string(state->board, w, h);
290 }
291
292 /*****************************************************************************
293  * GAME GENERATION AND SOLVER                                                *
294  *****************************************************************************/
295
296 static const int dx[4] = {-1, 1, 0, 0};
297 static const int dy[4] = {0, 0, -1, 1};
298
299 struct solver_state
300 {
301     int *dsf;
302     int *board;
303     int *connected;
304     int nempty;
305 };
306
307 static void print_board(int *board, int w, int h) {
308     if (verbose) {
309         char *repr = board_to_string(board, w, h);
310         printv("%s\n", repr);
311         free(repr);
312     }
313 }
314
315 static game_state *new_game(midend *, game_params *, char *);
316 static void free_game(game_state *);
317
318 #define SENTINEL sz
319
320 /* generate a random valid board; uses validate_board. */
321 static void make_board(int *board, int w, int h, random_state *rs) {
322     int *dsf;
323
324     const unsigned int sz = w * h;
325
326     /* w=h=2 is a special case which requires a number > max(w, h) */
327     /* TODO prove that this is the case ONLY for w=h=2. */
328     const int maxsize = min(max(max(w, h), 3), 9);
329
330     /* Note that if 1 in {w, h} then it's impossible to have a region
331      * of size > w*h, so the special case only affects w=h=2. */
332
333     int nboards = 0;
334     int i;
335
336     assert(w >= 1);
337     assert(h >= 1);
338
339     assert(board);
340
341     dsf = snew_dsf(sz); /* implicit dsf_init */
342
343     /* I abuse the board variable: when generating the puzzle, it
344      * contains a shuffled list of numbers {0, ..., nsq-1}. */
345     for (i = 0; i < (int)sz; ++i) board[i] = i;
346
347     while (1) {
348         int change;
349         ++nboards;
350         shuffle(board, sz, sizeof (int), rs);
351         /* while the board can in principle be fixed */
352         do {
353             change = FALSE;
354             for (i = 0; i < (int)sz; ++i) {
355                 int a = SENTINEL;
356                 int b = SENTINEL;
357                 int c = SENTINEL;
358                 const int aa = dsf_canonify(dsf, board[i]);
359                 int cc = sz;
360                 int j;
361                 for (j = 0; j < 4; ++j) {
362                     const int x = (board[i] % w) + dx[j];
363                     const int y = (board[i] / w) + dy[j];
364                     int bb;
365                     if (x < 0 || x >= w || y < 0 || y >= h) continue;
366                     bb = dsf_canonify(dsf, w*y + x);
367                     if (aa == bb) continue;
368                     else if (dsf_size(dsf, aa) == dsf_size(dsf, bb)) {
369                         a = aa;
370                         b = bb;
371                         c = cc;
372                     } else if (cc == sz) c = cc = bb;
373                 }
374                 if (a != SENTINEL) {
375                     a = dsf_canonify(dsf, a);
376                     assert(a != dsf_canonify(dsf, b));
377                     if (c != sz) assert(a != dsf_canonify(dsf, c));
378                     dsf_merge(dsf, a, c == sz? b: c);
379                     /* if repair impossible; make a new board */
380                     if (dsf_size(dsf, a) > maxsize) goto retry;
381                     change = TRUE;
382                 }
383             }
384         } while (change);
385
386         for (i = 0; i < (int)sz; ++i) board[i] = dsf_size(dsf, i);
387
388         sfree(dsf);
389         printv("returning board number %d\n", nboards);
390         return;
391
392     retry:
393         dsf_init(dsf, sz);
394     }
395     assert(FALSE); /* unreachable */
396 }
397
398 static int rhofree(int *hop, int start) {
399     int turtle = start, rabbit = hop[start];
400     while (rabbit != turtle) { /* find a cycle */
401         turtle = hop[turtle];
402         rabbit = hop[hop[rabbit]];
403     }
404     do { /* check that start is in the cycle */
405         rabbit = hop[rabbit];
406         if (start == rabbit) return 1;
407     } while (rabbit != turtle);
408     return 0;
409 }
410
411 static void merge(int *dsf, int *connected, int a, int b) {
412     int c;
413     assert(dsf);
414     assert(connected);
415     assert(rhofree(connected, a));
416     assert(rhofree(connected, b));
417     a = dsf_canonify(dsf, a);
418     b = dsf_canonify(dsf, b);
419     if (a == b) return;
420     dsf_merge(dsf, a, b);
421     c = connected[a];
422     connected[a] = connected[b];
423     connected[b] = c;
424     assert(rhofree(connected, a));
425     assert(rhofree(connected, b));
426 }
427
428 static void *memdup(const void *ptr, size_t len, size_t esz) {
429     void *dup = smalloc(len * esz);
430     assert(ptr);
431     memcpy(dup, ptr, len * esz);
432     return dup;
433 }
434
435 static void expand(struct solver_state *s, int w, int h, int t, int f) {
436     int j;
437     assert(s);
438     assert(s->board[t] == EMPTY); /* expand to empty square */
439     assert(s->board[f] != EMPTY); /* expand from non-empty square */
440     printv(
441         "learn: expanding %d from (%d, %d) into (%d, %d)\n",
442         s->board[f], f % w, f / w, t % w, t / w);
443     s->board[t] = s->board[f];
444     for (j = 0; j < 4; ++j) {
445         const int x = (t % w) + dx[j];
446         const int y = (t / w) + dy[j];
447         const int idx = w*y + x;
448         if (x < 0 || x >= w || y < 0 || y >= h) continue;
449         if (s->board[idx] != s->board[t]) continue;
450         merge(s->dsf, s->connected, t, idx);
451     }
452     --s->nempty;
453 }
454
455 static void clear_count(int *board, int sz) {
456     int i;
457     for (i = 0; i < sz; ++i) {
458         if (board[i] >= 0) continue;
459         else if (board[i] == -SENTINEL) board[i] = EMPTY;
460         else board[i] = -board[i];
461     }
462 }
463
464 static void flood_count(int *board, int w, int h, int i, int n, int *c) {
465     const int sz = w * h;
466     int k;
467
468     if (board[i] == EMPTY) board[i] = -SENTINEL;
469     else if (board[i] == n) board[i] = -board[i];
470     else return;
471
472     if (--*c == 0) return;
473
474     for (k = 0; k < 4; ++k) {
475         const int x = (i % w) + dx[k];
476         const int y = (i / w) + dy[k];
477         const int idx = w*y + x;
478         if (x < 0 || x >= w || y < 0 || y >= h) continue;
479         flood_count(board, w, h, idx, n, c);
480         if (*c == 0) return;
481     }
482 }
483
484 static int check_capacity(int *board, int w, int h, int i) {
485     int n = board[i];
486     flood_count(board, w, h, i, board[i], &n);
487     clear_count(board, w * h);
488     return n == 0;
489 }
490
491 static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
492     int j;
493     int nhits = 0;
494     int hits[4];
495     int size = 1;
496     for (j = 0; j < 4; ++j) {
497         const int x = (i % w) + dx[j];
498         const int y = (i / w) + dy[j];
499         const int idx = w*y + x;
500         int root;
501         int m;
502         if (x < 0 || x >= w || y < 0 || y >= h) continue;
503         if (board[idx] != n) continue;
504         root = dsf_canonify(dsf, idx);
505         for (m = 0; m < nhits && root != hits[m]; ++m);
506         if (m < nhits) continue;
507         printv("\t  (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2);
508         size += dsf_size(dsf, root);
509         assert(dsf_size(dsf, root) >= 1);
510         hits[nhits++] = root;
511     }
512     return size;
513 }
514
515 /*
516  *  +---+---+---+---+---+---+---+
517  *  | 6 |   |   | 2 |   |   | 2 |
518  *  +---+---+---+---+---+---+---+
519  *  |   | 3 |   | 6 |   | 3 |   |
520  *  +---+---+---+---+---+---+---+
521  *  | 3 |   |   |   |   |   | 1 |
522  *  +---+---+---+---+---+---+---+
523  *  |   | 2 | 3 |   | 4 | 2 |   |
524  *  +---+---+---+---+---+---+---+
525  *  | 2 |   |   |   |   |   | 3 |
526  *  +---+---+---+---+---+---+---+
527  *  |   | 5 |   | 1 |   | 4 |   |
528  *  +---+---+---+---+---+---+---+
529  *  | 4 |   |   | 3 |   |   | 3 |
530  *  +---+---+---+---+---+---+---+
531  */
532
533 /* Solving techniques:
534  *
535  * CONNECTED COMPONENT FORCED EXPANSION (too big):
536  * When a CC can only be expanded in one direction, because all the
537  * other ones would make the CC too big.
538  *  +---+---+---+---+---+
539  *  | 2 | 2 |   | 2 | _ |
540  *  +---+---+---+---+---+
541  *
542  * CONNECTED COMPONENT FORCED EXPANSION (too small):
543  * When a CC must include a particular square, because otherwise there
544  * would not be enough room to complete it.  This includes squares not
545  * adjacent to the CC through learn_critical_square.
546  *  +---+---+
547  *  | 2 | _ |
548  *  +---+---+
549  *
550  * DROPPING IN A ONE:
551  * When an empty square has no neighbouring empty squares and only a 1
552  * will go into the square (or other CCs would be too big).
553  *  +---+---+---+
554  *  | 2 | 2 | _ |
555  *  +---+---+---+
556  *
557  * TODO: generalise DROPPING IN A ONE: find the size of the CC of
558  * empty squares and a list of all adjacent numbers.  See if only one
559  * number in {1, ..., size} u {all adjacent numbers} is possible.
560  * Probably this is only effective for a CC size < n for some n (4?)
561  *
562  * TODO: backtracking.
563  */
564
565 static void filled_square(struct solver_state *s, int w, int h, int i) {
566     int j;
567     for (j = 0; j < 4; ++j) {
568         const int x = (i % w) + dx[j];
569         const int y = (i / w) + dy[j];
570         const int idx = w*y + x;
571         if (x < 0 || x >= w || y < 0 || y >= h) continue;
572         if (s->board[i] == s->board[idx])
573             merge(s->dsf, s->connected, i, idx);
574     }
575 }
576
577 static void init_solver_state(struct solver_state *s, int w, int h) {
578     const int sz = w * h;
579     int i;
580     assert(s);
581
582     s->nempty = 0;
583     for (i = 0; i < sz; ++i) s->connected[i] = i;
584     for (i = 0; i < sz; ++i)
585         if (s->board[i] == EMPTY) ++s->nempty;
586         else filled_square(s, w, h, i);
587 }
588
589 static int learn_expand_or_one(struct solver_state *s, int w, int h) {
590     const int sz = w * h;
591     int i;
592     int learn = FALSE;
593
594     assert(s);
595
596     for (i = 0; i < sz; ++i) {
597         int j;
598         int one = TRUE;
599
600         if (s->board[i] != EMPTY) continue;
601
602         for (j = 0; j < 4; ++j) {
603             const int x = (i % w) + dx[j];
604             const int y = (i / w) + dy[j];
605             const int idx = w*y + x;
606             if (x < 0 || x >= w || y < 0 || y >= h) continue;
607             if (s->board[idx] == EMPTY) {
608                 one = FALSE;
609                 continue;
610             }
611             if (one &&
612                 (s->board[idx] == 1 ||
613                  (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
614                                               i, s->board[idx]))))
615                 one = FALSE;
616             assert(s->board[i] == EMPTY);
617             s->board[i] = -SENTINEL;
618             if (check_capacity(s->board, w, h, idx)) continue;
619             assert(s->board[i] == EMPTY);
620             printv("learn: expanding in one\n");
621             expand(s, w, h, i, idx);
622             learn = TRUE;
623             break;
624         }
625
626         if (j == 4 && one) {
627             printv("learn: one at (%d, %d)\n", i % w, i / w);
628             assert(s->board[i] == EMPTY);
629             s->board[i] = 1;
630             assert(s->nempty);
631             --s->nempty;
632             learn = TRUE;
633         }
634     }
635     return learn;
636 }
637
638 static int learn_blocked_expansion(struct solver_state *s, int w, int h) {
639     const int sz = w * h;
640     int i;
641     int learn = FALSE;
642
643     assert(s);
644     /* for every connected component */
645     for (i = 0; i < sz; ++i) {
646         int exp = SENTINEL;
647         int j;
648
649         if (s->board[i] == EMPTY) continue;
650         j = dsf_canonify(s->dsf, i);
651
652         /* (but only for each connected component) */
653         if (i != j) continue;
654
655         /* (and not if it's already complete) */
656         if (dsf_size(s->dsf, j) == s->board[j]) continue;
657
658         /* for each square j _in_ the connected component */
659         do {
660             int k;
661             printv("  looking at (%d, %d)\n", j % w, j / w);
662
663             /* for each neighbouring square (idx) */
664             for (k = 0; k < 4; ++k) {
665                 const int x = (j % w) + dx[k];
666                 const int y = (j / w) + dy[k];
667                 const int idx = w*y + x;
668                 int size;
669                 /* int l;
670                    int nhits = 0;
671                    int hits[4]; */
672                 if (x < 0 || x >= w || y < 0 || y >= h) continue;
673                 if (s->board[idx] != EMPTY) continue;
674                 if (exp == idx) continue;
675                 printv("\ttrying to expand onto (%d, %d)\n", x, y);
676
677                 /* find out the would-be size of the new connected
678                  * component if we actually expanded into idx */
679                 /*
680                 size = 1;
681                 for (l = 0; l < 4; ++l) {
682                     const int lx = x + dx[l];
683                     const int ly = y + dy[l];
684                     const int idxl = w*ly + lx;
685                     int root;
686                     int m;
687                     if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
688                     if (board[idxl] != board[j]) continue;
689                     root = dsf_canonify(dsf, idxl);
690                     for (m = 0; m < nhits && root != hits[m]; ++m);
691                     if (m != nhits) continue;
692                     // printv("\t  (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);
693                     size += dsf_size(dsf, root);
694                     assert(dsf_size(dsf, root) >= 1);
695                     hits[nhits++] = root;
696                 }
697                 */
698
699                 size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
700
701                 /* ... and see if that size is too big, or if we
702                  * have other expansion candidates.  Otherwise
703                  * remember the (so far) only candidate. */
704
705                 printv("\tthat would give a size of %d\n", size);
706                 if (size > s->board[j]) continue;
707                 /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
708                 if (exp != SENTINEL) goto next_i;
709                 assert(exp != idx);
710                 exp = idx;
711             }
712
713             j = s->connected[j]; /* next square in the same CC */
714             assert(s->board[i] == s->board[j]);
715         } while (j != i);
716         /* end: for each square j _in_ the connected component */
717
718         if (exp == SENTINEL) continue;
719         printv("learning to expand\n");
720         expand(s, w, h, exp, i);
721         learn = TRUE;
722
723         next_i:
724         ;
725     }
726     /* end: for each connected component */
727     return learn;
728 }
729
730 static int learn_critical_square(struct solver_state *s, int w, int h) {
731     const int sz = w * h;
732     int i;
733     int learn = FALSE;
734     assert(s);
735
736     /* for each connected component */
737     for (i = 0; i < sz; ++i) {
738         int j;
739         if (s->board[i] == EMPTY) continue;
740         if (i != dsf_canonify(s->dsf, i)) continue;
741         if (dsf_size(s->dsf, i) == s->board[i]) continue;
742         assert(s->board[i] != 1);
743         /* for each empty square */
744         for (j = 0; j < sz; ++j) {
745             if (s->board[j] != EMPTY) continue;
746             s->board[j] = -SENTINEL;
747             if (check_capacity(s->board, w, h, i)) continue;
748             /* if not expanding s->board[i] to s->board[j] implies
749              * that s->board[i] can't reach its full size, ... */
750             assert(s->nempty);
751             printv(
752                 "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
753                 s->board[i], j % w, j / w, i % w, i / w);
754             --s->nempty;
755             s->board[j] = s->board[i];
756             filled_square(s, w, h, j);
757             learn = TRUE;
758         }
759     }
760     return learn;
761 }
762
763 static int solver(const int *orig, int w, int h, char **solution) {
764     const int sz = w * h;
765
766     struct solver_state ss;
767     ss.board = memdup(orig, sz, sizeof (int));
768     ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
769     ss.connected = snewn(sz, int); /* connected[n] := n.next; */
770     /* cyclic disjoint singly linked lists, same partitioning as dsf.
771      * The lists lets you iterate over a partition given any member */
772
773     printv("trying to solve this:\n");
774     print_board(ss.board, w, h);
775
776     init_solver_state(&ss, w, h);
777     do {
778         if (learn_blocked_expansion(&ss, w, h)) continue;
779         if (learn_expand_or_one(&ss, w, h)) continue;
780         if (learn_critical_square(&ss, w, h)) continue;
781         break;
782     } while (ss.nempty);
783
784     printv("best guess:\n");
785     print_board(ss.board, w, h);
786
787     if (solution) {
788         int i;
789         assert(*solution == NULL);
790         *solution = snewn(sz + 2, char);
791         **solution = 's';
792         for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.board[i] + '0';
793         (*solution)[sz + 1] = '\0';
794         /* We don't need the \0 for execute_move (the only user)
795          * I'm just being printf-friendly in case I wanna print */
796     }
797
798     sfree(ss.dsf);
799     sfree(ss.board);
800     sfree(ss.connected);
801
802     return !ss.nempty;
803 }
804
805 static int *make_dsf(int *dsf, int *board, const int w, const int h) {
806     const int sz = w * h;
807     int i;
808
809     if (!dsf)
810         dsf = snew_dsf(w * h);
811     else
812         dsf_init(dsf, w * h);
813
814     for (i = 0; i < sz; ++i) {
815         int j;
816         for (j = 0; j < 4; ++j) {
817             const int x = (i % w) + dx[j];
818             const int y = (i / w) + dy[j];
819             const int k = w*y + x;
820             if (x < 0 || x >= w || y < 0 || y >= h) continue;
821             if (board[i] == board[k]) dsf_merge(dsf, i, k);
822         }
823     }
824     return dsf;
825 }
826
827 /*
828 static int filled(int *board, int *randomize, int k, int n) {
829     int i;
830     if (board == NULL) return FALSE;
831     if (randomize == NULL) return FALSE;
832     if (k > n) return FALSE;
833     for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE;
834     for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE;
835     return TRUE;
836 }
837 */
838
839 static int *g_board;
840 static int compare(const void *pa, const void *pb) {
841     if (!g_board) return 0;
842     return g_board[*(const int *)pb] - g_board[*(const int *)pa];
843 }
844
845 static void minimize_clue_set(int *board, int w, int h, int *randomize) {
846     const int sz = w * h;
847     int i;
848     int *board_cp = snewn(sz, int);
849     memcpy(board_cp, board, sz * sizeof (int));
850
851     /* since more clues only helps and never hurts, one pass will do
852      * just fine: if we can remove clue n with k clues of index > n,
853      * we could have removed clue n with >= k clues of index > n.
854      * So an additional pass wouldn't do anything [use induction]. */
855     for (i = 0; i < sz; ++i) {
856         if (board[randomize[i]] == EMPTY) continue;
857         board[randomize[i]] = EMPTY;
858         /* (rot.) symmetry tends to include _way_ too many hints */
859         /* board[sz - randomize[i] - 1] = EMPTY; */
860         if (!solver(board, w, h, NULL)) {
861             board[randomize[i]] = board_cp[randomize[i]];
862             /* board[sz - randomize[i] - 1] =
863                board_cp[sz - randomize[i] - 1]; */
864         }
865     }
866
867     sfree(board_cp);
868 }
869
870 static char *new_game_desc(game_params *params, random_state *rs,
871                            char **aux, int interactive)
872 {
873     const int w = params->w;
874     const int h = params->h;
875     const int sz = w * h;
876     int *board = snewn(sz, int);
877     int *randomize = snewn(sz, int);
878     char *game_description = snewn(sz + 1, char);
879     int i;
880
881     for (i = 0; i < sz; ++i) {
882         board[i] = EMPTY;
883         randomize[i] = i;
884     }
885
886     make_board(board, w, h, rs);
887     g_board = board;
888     qsort(randomize, sz, sizeof (int), compare);
889     minimize_clue_set(board, w, h, randomize);
890
891     for (i = 0; i < sz; ++i) {
892         assert(board[i] >= 0);
893         assert(board[i] < 10);
894         game_description[i] = board[i] + '0';
895     }
896     game_description[sz] = '\0';
897
898 /*
899     solver(board, w, h, aux);
900     print_board(board, w, h);
901 */
902
903     sfree(randomize);
904     sfree(board);
905
906     return game_description;
907 }
908
909 static char *validate_desc(game_params *params, char *desc)
910 {
911     int i;
912     const int sz = params->w * params->h;
913     const char m = '0' + max(max(params->w, params->h), 3);
914
915     printv("desc = '%s'; sz = %d\n", desc, sz);
916
917     for (i = 0; desc[i] && i < sz; ++i)
918         if (!isdigit((unsigned char) *desc))
919             return "non-digit in string";
920         else if (desc[i] > m)
921             return "too large digit in string";
922     if (desc[i]) return "string too long";
923     else if (i < sz) return "string too short";
924     return NULL;
925 }
926
927 static game_state *new_game(midend *me, game_params *params, char *desc)
928 {
929     game_state *state = snew(game_state);
930     int sz = params->w * params->h;
931     int i;
932
933     state->cheated = state->completed = FALSE;
934     state->shared = snew(struct shared_state);
935     state->shared->refcnt = 1;
936     state->shared->params = *params; /* struct copy */
937     state->shared->clues = snewn(sz, int);
938     for (i = 0; i < sz; ++i) state->shared->clues[i] = desc[i] - '0';
939     state->board = memdup(state->shared->clues, sz, sizeof (int));
940
941     return state;
942 }
943
944 static game_state *dup_game(game_state *state)
945 {
946     const int sz = state->shared->params.w * state->shared->params.h;
947     game_state *ret = snew(game_state);
948
949     ret->board = memdup(state->board, sz, sizeof (int));
950     ret->shared = state->shared;
951     ret->cheated = state->cheated;
952     ret->completed = state->completed;
953     ++ret->shared->refcnt;
954
955     return ret;
956 }
957
958 static void free_game(game_state *state)
959 {
960     assert(state);
961     sfree(state->board);
962     if (--state->shared->refcnt == 0) {
963         sfree(state->shared->clues);
964         sfree(state->shared);
965     }
966     sfree(state);
967 }
968
969 static char *solve_game(game_state *state, game_state *currstate,
970                         char *aux, char **error)
971 {
972     if (aux == NULL) {
973         const int w = state->shared->params.w;
974         const int h = state->shared->params.h;
975         if (!solver(state->board, w, h, &aux))
976             *error = "Sorry, I couldn't find a solution";
977     }
978     return aux;
979 }
980
981 /*****************************************************************************
982  * USER INTERFACE STATE AND ACTION                                           *
983  *****************************************************************************/
984
985 struct game_ui {
986     int *sel; /* w*h highlighted squares, or NULL */
987     int cur_x, cur_y, cur_visible;
988 };
989
990 static game_ui *new_ui(game_state *state)
991 {
992     game_ui *ui = snew(game_ui);
993
994     ui->sel = NULL;
995     ui->cur_x = ui->cur_y = ui->cur_visible = 0;
996
997     return ui;
998 }
999
1000 static void free_ui(game_ui *ui)
1001 {
1002     if (ui->sel)
1003         sfree(ui->sel);
1004     sfree(ui);
1005 }
1006
1007 static char *encode_ui(game_ui *ui)
1008 {
1009     return NULL;
1010 }
1011
1012 static void decode_ui(game_ui *ui, char *encoding)
1013 {
1014 }
1015
1016 static void game_changed_state(game_ui *ui, game_state *oldstate,
1017                                game_state *newstate)
1018 {
1019     /* Clear any selection */
1020     if (ui->sel) {
1021         sfree(ui->sel);
1022         ui->sel = NULL;
1023     }
1024 }
1025
1026 #define PREFERRED_TILE_SIZE 32
1027 #define TILE_SIZE (ds->tilesize)
1028 #define BORDER (TILE_SIZE / 2)
1029 #define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
1030
1031 struct game_drawstate {
1032     struct game_params params;
1033     int tilesize;
1034     int started;
1035     int *v, *flags;
1036     int *dsf_scratch, *border_scratch;
1037 };
1038
1039 static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
1040                             int x, int y, int button)
1041 {
1042     const int w = state->shared->params.w;
1043     const int h = state->shared->params.h;
1044
1045     const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1046     const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
1047
1048     char *move = NULL;
1049     int i;
1050
1051     assert(ui);
1052     assert(ds);
1053
1054     button &= ~MOD_MASK;
1055
1056     if (button == LEFT_BUTTON || button == LEFT_DRAG) {
1057         /* A left-click anywhere will clear the current selection. */
1058         if (button == LEFT_BUTTON) {
1059             if (ui->sel) {
1060                 sfree(ui->sel);
1061                 ui->sel = NULL;
1062             }
1063         }
1064         if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
1065             if (!ui->sel) {
1066                 ui->sel = snewn(w*h, int);
1067                 memset(ui->sel, 0, w*h*sizeof(int));
1068             }
1069             if (!state->shared->clues[w*ty+tx])
1070                 ui->sel[w*ty+tx] = 1;
1071         }
1072         ui->cur_visible = 0;
1073         return ""; /* redraw */
1074     }
1075
1076     if (IS_CURSOR_MOVE(button)) {
1077         ui->cur_visible = 1;
1078         move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0);
1079         return "";
1080     }
1081     if (IS_CURSOR_SELECT(button)) {
1082         if (!ui->cur_visible) {
1083             ui->cur_visible = 1;
1084             return "";
1085         }
1086         if (!ui->sel) {
1087             ui->sel = snewn(w*h, int);
1088             memset(ui->sel, 0, w*h*sizeof(int));
1089         }
1090         if (state->shared->clues[w*ui->cur_y + ui->cur_x] == 0)
1091             ui->sel[w*ui->cur_y + ui->cur_x] ^= 1;
1092         return "";
1093     }
1094
1095     switch (button) {
1096       case ' ':
1097       case '\r':
1098       case '\n':
1099       case '\b':
1100         button = 0;
1101         break;
1102       default:
1103         if (button < '0' || button > '9') return NULL;
1104         button -= '0';
1105         if (button > (w == 2 && h == 2? 3: max(w, h))) return NULL;
1106     }
1107
1108     for (i = 0; i < w*h; i++) {
1109         char buf[32];
1110         if ((ui->sel && ui->sel[i]) ||
1111             (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) {
1112             if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */
1113             if (state->board[i] != button) {
1114                 sprintf(buf, "%s%d", move ? "," : "", i);
1115                 if (move) {
1116                     move = srealloc(move, strlen(move)+strlen(buf)+1);
1117                     strcat(move, buf);
1118                 } else {
1119                     move = smalloc(strlen(buf)+1);
1120                     strcpy(move, buf);
1121                 }
1122             }
1123         }
1124     }
1125     if (move) {
1126         char buf[32];
1127         sprintf(buf, "_%d", button);
1128         move = srealloc(move, strlen(move)+strlen(buf)+1);
1129         strcat(move, buf);
1130     }
1131     if (!ui->sel) return move ? move : NULL;
1132     sfree(ui->sel);
1133     ui->sel = NULL;
1134     /* Need to update UI at least, as we cleared the selection */
1135     return move ? move : "";
1136 }
1137
1138 static game_state *execute_move(game_state *state, char *move)
1139 {
1140     game_state *new_state = NULL;
1141     const int sz = state->shared->params.w * state->shared->params.h;
1142
1143     if (*move == 's') {
1144         int i = 0;
1145         new_state = dup_game(state);
1146         for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
1147         new_state->cheated = TRUE;
1148     } else {
1149         int value;
1150         char *endptr, *delim = strchr(move, '_');
1151         if (!delim) goto err;
1152         value = strtol(delim+1, &endptr, 0);
1153         if (*endptr || endptr == delim+1) goto err;
1154         if (value < 0 || value > 9) goto err;
1155         new_state = dup_game(state);
1156         while (*move) {
1157             const int i = strtol(move, &endptr, 0);
1158             if (endptr == move) goto err;
1159             if (i < 0 || i >= sz) goto err;
1160             new_state->board[i] = value;
1161             if (*endptr == '_') break;
1162             if (*endptr != ',') goto err;
1163             move = endptr + 1;
1164         }
1165     }
1166
1167     /*
1168      * Check for completion.
1169      */
1170     if (!new_state->completed) {
1171         const int w = new_state->shared->params.w;
1172         const int h = new_state->shared->params.h;
1173         const int sz = w * h;
1174         int *dsf = make_dsf(NULL, new_state->board, w, h);
1175         int i;
1176         for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
1177         sfree(dsf);
1178         if (i == sz)
1179             new_state->completed = TRUE;
1180     }
1181
1182     return new_state;
1183
1184 err:
1185     if (new_state) free_game(new_state);
1186     return NULL;
1187 }
1188
1189 /* ----------------------------------------------------------------------
1190  * Drawing routines.
1191  */
1192
1193 #define FLASH_TIME 0.4F
1194
1195 #define COL_CLUE COL_GRID
1196 enum {
1197     COL_BACKGROUND,
1198     COL_GRID,
1199     COL_HIGHLIGHT,
1200     COL_CORRECT,
1201     COL_ERROR,
1202     COL_USER,
1203     COL_CURSOR,
1204     NCOLOURS
1205 };
1206
1207 static void game_compute_size(game_params *params, int tilesize,
1208                               int *x, int *y)
1209 {
1210     *x = (params->w + 1) * tilesize;
1211     *y = (params->h + 1) * tilesize;
1212 }
1213
1214 static void game_set_size(drawing *dr, game_drawstate *ds,
1215                           game_params *params, int tilesize)
1216 {
1217     ds->tilesize = tilesize;
1218 }
1219
1220 static float *game_colours(frontend *fe, int *ncolours)
1221 {
1222     float *ret = snewn(3 * NCOLOURS, float);
1223
1224     frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
1225
1226     ret[COL_GRID * 3 + 0] = 0.0F;
1227     ret[COL_GRID * 3 + 1] = 0.0F;
1228     ret[COL_GRID * 3 + 2] = 0.0F;
1229
1230     ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
1231     ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1232     ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1233
1234     ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
1235     ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
1236     ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
1237
1238     ret[COL_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
1239     ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
1240     ret[COL_CURSOR * 3 + 2] = 0.5F * ret[COL_BACKGROUND * 3 + 2];
1241
1242     ret[COL_ERROR * 3 + 0] = 1.0F;
1243     ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
1244     ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
1245
1246     ret[COL_USER * 3 + 0] = 0.0F;
1247     ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
1248     ret[COL_USER * 3 + 2] = 0.0F;
1249
1250     *ncolours = NCOLOURS;
1251     return ret;
1252 }
1253
1254 static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
1255 {
1256     struct game_drawstate *ds = snew(struct game_drawstate);
1257     int i;
1258
1259     ds->tilesize = PREFERRED_TILE_SIZE;
1260     ds->started = 0;
1261     ds->params = state->shared->params;
1262     ds->v = snewn(ds->params.w * ds->params.h, int);
1263     ds->flags = snewn(ds->params.w * ds->params.h, int);
1264     for (i = 0; i < ds->params.w * ds->params.h; i++)
1265         ds->v[i] = ds->flags[i] = -1;
1266     ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
1267     ds->dsf_scratch = NULL;
1268
1269     return ds;
1270 }
1271
1272 static void game_free_drawstate(drawing *dr, game_drawstate *ds)
1273 {
1274     sfree(ds->v);
1275     sfree(ds->flags);
1276     sfree(ds->border_scratch);
1277     sfree(ds->dsf_scratch);
1278     sfree(ds);
1279 }
1280
1281 #define BORDER_U   0x001
1282 #define BORDER_D   0x002
1283 #define BORDER_L   0x004
1284 #define BORDER_R   0x008
1285 #define BORDER_UR  0x010
1286 #define BORDER_DR  0x020
1287 #define BORDER_UL  0x040
1288 #define BORDER_DL  0x080
1289 #define HIGH_BG    0x100
1290 #define CORRECT_BG 0x200
1291 #define ERROR_BG   0x400
1292 #define USER_COL   0x800
1293 #define CURSOR_SQ 0x1000
1294
1295 static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
1296                         int n, int flags)
1297 {
1298     assert(dr);
1299     assert(ds);
1300
1301     /*
1302      * Clip to the grid square.
1303      */
1304     clip(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1305          TILE_SIZE, TILE_SIZE);
1306
1307     /*
1308      * Clear the square.
1309      */
1310     draw_rect(dr,
1311               BORDER + x*TILE_SIZE,
1312               BORDER + y*TILE_SIZE,
1313               TILE_SIZE,
1314               TILE_SIZE,
1315               (flags & HIGH_BG ? COL_HIGHLIGHT :
1316                flags & ERROR_BG ? COL_ERROR :
1317                flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
1318
1319     /*
1320      * Draw the grid lines.
1321      */
1322     draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1323               BORDER + (x+1)*TILE_SIZE, BORDER + y*TILE_SIZE, COL_GRID);
1324     draw_line(dr, BORDER + x*TILE_SIZE, BORDER + y*TILE_SIZE,
1325               BORDER + x*TILE_SIZE, BORDER + (y+1)*TILE_SIZE, COL_GRID);
1326
1327     /*
1328      * Draw the number.
1329      */
1330     if (n) {
1331         char buf[2];
1332         buf[0] = n + '0';
1333         buf[1] = '\0';
1334         draw_text(dr,
1335                   (x + 1) * TILE_SIZE,
1336                   (y + 1) * TILE_SIZE,
1337                   FONT_VARIABLE,
1338                   TILE_SIZE / 2,
1339                   ALIGN_VCENTRE | ALIGN_HCENTRE,
1340                   flags & USER_COL ? COL_USER : COL_CLUE,
1341                   buf);
1342     }
1343
1344     /*
1345      * Draw bold lines around the borders.
1346      */
1347     if (flags & BORDER_L)
1348         draw_rect(dr,
1349                   BORDER + x*TILE_SIZE + 1,
1350                   BORDER + y*TILE_SIZE + 1,
1351                   BORDER_WIDTH,
1352                   TILE_SIZE - 1,
1353                   COL_GRID);
1354     if (flags & BORDER_U)
1355         draw_rect(dr,
1356                   BORDER + x*TILE_SIZE + 1,
1357                   BORDER + y*TILE_SIZE + 1,
1358                   TILE_SIZE - 1,
1359                   BORDER_WIDTH,
1360                   COL_GRID);
1361     if (flags & BORDER_R)
1362         draw_rect(dr,
1363                   BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1364                   BORDER + y*TILE_SIZE + 1,
1365                   BORDER_WIDTH,
1366                   TILE_SIZE - 1,
1367                   COL_GRID);
1368     if (flags & BORDER_D)
1369         draw_rect(dr,
1370                   BORDER + x*TILE_SIZE + 1,
1371                   BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1372                   TILE_SIZE - 1,
1373                   BORDER_WIDTH,
1374                   COL_GRID);
1375     if (flags & BORDER_UL)
1376         draw_rect(dr,
1377                   BORDER + x*TILE_SIZE + 1,
1378                   BORDER + y*TILE_SIZE + 1,
1379                   BORDER_WIDTH,
1380                   BORDER_WIDTH,
1381                   COL_GRID);
1382     if (flags & BORDER_UR)
1383         draw_rect(dr,
1384                   BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1385                   BORDER + y*TILE_SIZE + 1,
1386                   BORDER_WIDTH,
1387                   BORDER_WIDTH,
1388                   COL_GRID);
1389     if (flags & BORDER_DL)
1390         draw_rect(dr,
1391                   BORDER + x*TILE_SIZE + 1,
1392                   BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1393                   BORDER_WIDTH,
1394                   BORDER_WIDTH,
1395                   COL_GRID);
1396     if (flags & BORDER_DR)
1397         draw_rect(dr,
1398                   BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
1399                   BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
1400                   BORDER_WIDTH,
1401                   BORDER_WIDTH,
1402                   COL_GRID);
1403
1404     if (flags & CURSOR_SQ) {
1405         int coff = TILE_SIZE/8;
1406         draw_rect_outline(dr,
1407                           BORDER + x*TILE_SIZE + coff,
1408                           BORDER + y*TILE_SIZE + coff,
1409                           TILE_SIZE - coff*2,
1410                           TILE_SIZE - coff*2,
1411                           COL_CURSOR);
1412     }
1413
1414     unclip(dr);
1415
1416     draw_update(dr,
1417                 BORDER + x*TILE_SIZE,
1418                 BORDER + y*TILE_SIZE,
1419                 TILE_SIZE,
1420                 TILE_SIZE);
1421 }
1422
1423 static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state,
1424                       game_ui *ui, int flashy, int borders, int shading)
1425 {
1426     const int w = state->shared->params.w;
1427     const int h = state->shared->params.h;
1428     int x;
1429     int y;
1430
1431     /*
1432      * Build a dsf for the board in its current state, to use for
1433      * highlights and hints.
1434      */
1435     ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
1436
1437     /*
1438      * Work out where we're putting borders between the cells.
1439      */
1440     for (y = 0; y < w*h; y++)
1441         ds->border_scratch[y] = 0;
1442
1443     for (y = 0; y < h; y++)
1444         for (x = 0; x < w; x++) {
1445             int dx, dy;
1446             int v1, s1, v2, s2;
1447
1448             for (dx = 0; dx <= 1; dx++) {
1449                 int border = FALSE;
1450
1451                 dy = 1 - dx;
1452
1453                 if (x+dx >= w || y+dy >= h)
1454                     continue;
1455
1456                 v1 = state->board[y*w+x];
1457                 v2 = state->board[(y+dy)*w+(x+dx)];
1458                 s1 = dsf_size(ds->dsf_scratch, y*w+x);
1459                 s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
1460
1461                 /*
1462                  * We only ever draw a border between two cells if
1463                  * they don't have the same contents.
1464                  */
1465                 if (v1 != v2) {
1466                     /*
1467                      * But in that situation, we don't always draw
1468                      * a border. We do if the two cells both
1469                      * contain actual numbers...
1470                      */
1471                     if (v1 && v2)
1472                         border = TRUE;
1473
1474                     /*
1475                      * ... or if at least one of them is a
1476                      * completed or overfull omino.
1477                      */
1478                     if (v1 && s1 >= v1)
1479                         border = TRUE;
1480                     if (v2 && s2 >= v2)
1481                         border = TRUE;
1482                 }
1483
1484                 if (border)
1485                     ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
1486             }
1487         }
1488
1489     /*
1490      * Actually do the drawing.
1491      */
1492     for (y = 0; y < h; ++y)
1493         for (x = 0; x < w; ++x) {
1494             /*
1495              * Determine what we need to draw in this square.
1496              */
1497             int v = state->board[y*w+x];
1498             int flags = 0;
1499
1500             if (flashy || !shading) {
1501                 /* clear all background flags */
1502             } else if (ui && ui->sel && ui->sel[y*w+x]) {
1503                 flags |= HIGH_BG;
1504             } else if (v) {
1505                 int size = dsf_size(ds->dsf_scratch, y*w+x);
1506                 if (size == v)
1507                     flags |= CORRECT_BG;
1508                 else if (size > v)
1509                     flags |= ERROR_BG;
1510             }
1511             if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
1512               flags |= CURSOR_SQ;
1513
1514             /*
1515              * Borders at the very edges of the grid are
1516              * independent of the `borders' flag.
1517              */
1518             if (x == 0)
1519                 flags |= BORDER_L;
1520             if (y == 0)
1521                 flags |= BORDER_U;
1522             if (x == w-1)
1523                 flags |= BORDER_R;
1524             if (y == h-1)
1525                 flags |= BORDER_D;
1526
1527             if (borders) {
1528                 if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
1529                     flags |= BORDER_L;
1530                 if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
1531                     flags |= BORDER_U;
1532                 if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
1533                     flags |= BORDER_R;
1534                 if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
1535                     flags |= BORDER_D;
1536
1537                 if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
1538                     flags |= BORDER_UL;
1539                 if (y > 0 && x < w-1 &&
1540                     ((ds->border_scratch[(y-1)*w+x] & 1) ||
1541                      (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
1542                     flags |= BORDER_UR;
1543                 if (y < h-1 && x > 0 &&
1544                     ((ds->border_scratch[y*w+(x-1)] & 2) ||
1545                      (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
1546                     flags |= BORDER_DL;
1547                 if (y < h-1 && x < w-1 &&
1548                     ((ds->border_scratch[y*w+(x+1)] & 2) ||
1549                      (ds->border_scratch[(y+1)*w+x] & 1)))
1550                     flags |= BORDER_DR;
1551             }
1552
1553             if (!state->shared->clues[y*w+x])
1554                 flags |= USER_COL;
1555
1556             if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {
1557                 draw_square(dr, ds, x, y, v, flags);
1558                 ds->v[y*w+x] = v;
1559                 ds->flags[y*w+x] = flags;
1560             }
1561         }
1562 }
1563
1564 static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
1565                         game_state *state, int dir, game_ui *ui,
1566                         float animtime, float flashtime)
1567 {
1568     const int w = state->shared->params.w;
1569     const int h = state->shared->params.h;
1570
1571     const int flashy =
1572         flashtime > 0 &&
1573         (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
1574
1575     if (!ds->started) {
1576         /*
1577          * The initial contents of the window are not guaranteed and
1578          * can vary with front ends. To be on the safe side, all games
1579          * should start by drawing a big background-colour rectangle
1580          * covering the whole window.
1581          */
1582         draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
1583                   COL_BACKGROUND);
1584
1585         /*
1586          * Smaller black rectangle which is the main grid.
1587          */
1588         draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1589                   w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1590                   h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1591                   COL_GRID);
1592
1593         draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
1594
1595         ds->started = TRUE;
1596     }
1597
1598     draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
1599 }
1600
1601 static float game_anim_length(game_state *oldstate, game_state *newstate,
1602                               int dir, game_ui *ui)
1603 {
1604     return 0.0F;
1605 }
1606
1607 static float game_flash_length(game_state *oldstate, game_state *newstate,
1608                                int dir, game_ui *ui)
1609 {
1610     assert(oldstate);
1611     assert(newstate);
1612     assert(newstate->shared);
1613     assert(oldstate->shared == newstate->shared);
1614     if (!oldstate->completed && newstate->completed &&
1615         !oldstate->cheated && !newstate->cheated)
1616         return FLASH_TIME;
1617     return 0.0F;
1618 }
1619
1620 static int game_status(game_state *state)
1621 {
1622     return state->completed ? +1 : 0;
1623 }
1624
1625 static int game_timing_state(game_state *state, game_ui *ui)
1626 {
1627     return TRUE;
1628 }
1629
1630 static void game_print_size(game_params *params, float *x, float *y)
1631 {
1632     int pw, ph;
1633
1634     /*
1635      * I'll use 6mm squares by default.
1636      */
1637     game_compute_size(params, 600, &pw, &ph);
1638     *x = pw / 100.0F;
1639     *y = ph / 100.0F;
1640 }
1641
1642 static void game_print(drawing *dr, game_state *state, int tilesize)
1643 {
1644     const int w = state->shared->params.w;
1645     const int h = state->shared->params.h;
1646     int c, i, borders;
1647
1648     /* Ick: fake up `ds->tilesize' for macro expansion purposes */
1649     game_drawstate *ds = game_new_drawstate(dr, state);
1650     game_set_size(dr, ds, NULL, tilesize);
1651
1652     c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1653     c = print_mono_colour(dr, 0); assert(c == COL_GRID);
1654     c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
1655     c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
1656     c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
1657     c = print_mono_colour(dr, 0); assert(c == COL_USER);
1658
1659     /*
1660      * Border.
1661      */
1662     draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
1663               w*TILE_SIZE + 2*BORDER_WIDTH + 1,
1664               h*TILE_SIZE + 2*BORDER_WIDTH + 1,
1665               COL_GRID);
1666
1667     /*
1668      * We'll draw borders between the ominoes iff the grid is not
1669      * pristine. So scan it to see if it is.
1670      */
1671     borders = FALSE;
1672     for (i = 0; i < w*h; i++)
1673         if (state->board[i] && !state->shared->clues[i])
1674             borders = TRUE;
1675
1676     /*
1677      * Draw grid.
1678      */
1679     print_line_width(dr, TILE_SIZE / 64);
1680     draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
1681
1682     /*
1683      * Clean up.
1684      */
1685     game_free_drawstate(dr, ds);
1686 }
1687
1688 #ifdef COMBINED
1689 #define thegame filling
1690 #endif
1691
1692 const struct game thegame = {
1693     "Filling", "games.filling", "filling",
1694     default_params,
1695     game_fetch_preset,
1696     decode_params,
1697     encode_params,
1698     free_params,
1699     dup_params,
1700     TRUE, game_configure, custom_params,
1701     validate_params,
1702     new_game_desc,
1703     validate_desc,
1704     new_game,
1705     dup_game,
1706     free_game,
1707     TRUE, solve_game,
1708     TRUE, game_can_format_as_text_now, game_text_format,
1709     new_ui,
1710     free_ui,
1711     encode_ui,
1712     decode_ui,
1713     game_changed_state,
1714     interpret_move,
1715     execute_move,
1716     PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
1717     game_colours,
1718     game_new_drawstate,
1719     game_free_drawstate,
1720     game_redraw,
1721     game_anim_length,
1722     game_flash_length,
1723     game_status,
1724     TRUE, FALSE, game_print_size, game_print,
1725     FALSE,                                 /* wants_statusbar */
1726     FALSE, game_timing_state,
1727     REQUIRE_NUMPAD,                    /* flags */
1728 };
1729
1730 #ifdef STANDALONE_SOLVER /* solver? hah! */
1731
1732 int main(int argc, char **argv) {
1733     while (*++argv) {
1734         game_params *params;
1735         game_state *state;
1736         char *par;
1737         char *desc;
1738
1739         for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
1740         if (*desc == '\0') {
1741             fprintf(stderr, "bad puzzle id: %s", par);
1742             continue;
1743         }
1744
1745         *desc++ = '\0';
1746
1747         params = snew(game_params);
1748         decode_params(params, par);
1749         state = new_game(NULL, params, desc);
1750         if (solver(state->board, params->w, params->h, NULL))
1751             printf("%s:%s: solvable\n", par, desc);
1752         else
1753             printf("%s:%s: not solvable\n", par, desc);
1754     }
1755     return 0;
1756 }
1757
1758 #endif
1759
1760 /* vim: set shiftwidth=4 tabstop=8: */