ref: df31d4f4195ea2cc3a1213da14717813aacbf404
parent: 8b1b6bc9a38d90ab30bf6abdd3c14a8e98f29b26
author: Simon Tatham <[email protected]>
date: Sun Feb 25 06:37:05 EST 2007
New puzzle: `Filling', a Fillomino implementation by Jonas Koelker. [originally from svn r7326]
--- a/LICENCE
+++ b/LICENCE
@@ -1,6 +1,7 @@
This software is copyright (c) 2004-2007 Simon Tatham.
-Portions copyright Richard Boulton, James Harvey and Mike Pinna.
+Portions copyright Richard Boulton, James Harvey, Mike Pinna and
+Jonas K�lker.
Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation files
--- a/dsf.c
+++ b/dsf.c
@@ -64,11 +64,13 @@
{int i;
- for (i = 0; i < size; i++) {- /* Bottom bit of each element of this array stores whether that element
- * is opposite to its parent, which starts off as false */
- dsf[i] = i << 1;
- }
+ for (i = 0; i < size; i++) dsf[i] = 6;
+ /* Bottom bit of each element of this array stores whether that
+ * element is opposite to its parent, which starts off as
+ * false. Second bit of each element stores whether that element
+ * is the root of its tree or not. If it's not the root, the
+ * remaining 30 bits are the parent, otherwise the remaining 30
+ * bits are the number of elements in the tree. */
}
int *snew_dsf(int size)
@@ -93,6 +95,10 @@
edsf_merge(dsf, v1, v2, FALSE);
}
+int dsf_size(int *dsf, int index) {+ return dsf[dsf_canonify(dsf, index)] >> 2;
+}
+
int edsf_canonify(int *dsf, int index, int *inverse_return)
{int start_index = index, canonical_index;
@@ -106,9 +112,9 @@
/* Find the index of the canonical element of the 'equivalence class' of
* which start_index is a member, and figure out whether start_index is the
* same as or inverse to that. */
- while ((dsf[index] >> 1) != index) {+ while ((dsf[index] & 2) == 0) {inverse ^= (dsf[index] & 1);
- index = dsf[index] >> 1;
+ index = dsf[index] >> 2;
/* fprintf(stderr, "index = %2d, ", index); */
/* fprintf(stderr, "inverse = %d\n", inverse); */
}
@@ -121,9 +127,9 @@
* canonical member. */
index = start_index;
while (index != canonical_index) {- int nextindex = dsf[index] >> 1;
+ int nextindex = dsf[index] >> 2;
int nextinverse = inverse ^ (dsf[index] & 1);
- dsf[index] = (canonical_index << 1) | inverse;
+ dsf[index] = (canonical_index << 2) | inverse;
inverse = nextinverse;
index = nextindex;
}
@@ -138,13 +144,15 @@
void edsf_merge(int *dsf, int v1, int v2, int inverse)
{int i1, i2;
-
+
/* fprintf(stderr, "dsf = %p\n", dsf); */
/* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
v1 = edsf_canonify(dsf, v1, &i1);
+ assert(dsf[v1] & 2);
inverse ^= i1;
v2 = edsf_canonify(dsf, v2, &i2);
+ assert(dsf[v2] & 2);
inverse ^= i2;
/* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
@@ -151,8 +159,16 @@
if (v1 == v2)
assert(!inverse);
- else
- dsf[v2] = (v1 << 1) | !!inverse;
+ else {+ assert(inverse == 0 || inverse == 1);
+ if ((dsf[v2] >> 2) > (dsf[v1] >> 2)) {+ int v3 = v1;
+ v1 = v2;
+ v2 = v3;
+ }
+ dsf[v1] += (dsf[v2] >> 2) << 2;
+ dsf[v2] = (v1 << 2) | !!inverse;
+ }
v2 = edsf_canonify(dsf, v2, &i2);
assert(v2 == v1);
--- /dev/null
+++ b/filling.R
@@ -1,0 +1,24 @@
+# -*- makefile -*-
+
+FILLING = filling dsf filling-icon|no-icon
+
+fillingsolver : [U] filling[STANDALONE_SOLVER] dsf STANDALONE
+fillingsolver : [C] filling[STANDALONE_SOLVER] dsf STANDALONE
+
+filling : [X] GTK COMMON FILLING
+
+filling : [G] WINDOWS COMMON FILLING
+
+ALL += filling
+
+!begin gtk
+GAMES += filling
+!end
+
+!begin >list.c
+ A(filling) \
+!end
+
+!begin >wingames.lst
+filling.exe:Filling
+!end
--- /dev/null
+++ b/filling.c
@@ -1,0 +1,1539 @@
+/* -*- tab-width: 8; indent-tabs-mode: t -*-
+ * filling.c: An implementation of the Nikoli game fillomino.
+ * Copyright (C) 2007 Jonas K�lker. See LICENSE for the license.
+ */
+
+/* TODO:
+ *
+ * - use a typedef instead of int for numbers on the board
+ * + replace int with something else (signed char?)
+ * - the type should be signed (I use -board[i] temporarily)
+ * - problems are small (<= 9?): type can be char?
+ *
+ * - make a somewhat more clever solver
+ *
+ * - make the solver do recursion/backtracking.
+ * + This is for user-submitted puzzles, not for puzzle
+ * generation (on the other hand, never say never).
+ *
+ * - prove that only w=h=2 needs a special case
+ *
+ * - solo-like pencil marks?
+ *
+ * - speed up generation of puzzles of size >= 11x11
+ *
+ * - Allow square contents > 9?
+ * + I could use letters for digits (solo does this), but
+ * letters don't have numeric significance (normal people hate
+ * base36), which is relevant here (much more than in solo).
+ * + How much information is needed to solve? Does one need to
+ * know the algorithm by which the largest number is set?
+ *
+ * - eliminate puzzle instances with done chunks (1's in particular)?
+ * + that's what the qsort call is all about.
+ * + the 1's don't bother me that much.
+ * + but this takes a LONG time (not always possible)?
+ * - this may be affected by solver (lack of) quality.
+ * - weed them out by construction instead of post-cons check
+ * + but that interleaves make_board and new_game_desc: you
+ * have to alternate between changing the board and
+ * changing the hint set (instead of just creating the
+ * board once, then changing the hint set once -> done).
+ *
+ * - use binary search when discovering the minimal sovable point
+ * + profile to show a need (but when the solver gets slower...)
+ * + avg 0.1s per 9x9, which _is_ human-patience noticable.
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <errno.h>
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "puzzles.h"
+
+struct game_params {+ int w, h;
+};
+
+struct shared_state {+ struct game_params params;
+ int *clues;
+ int refcnt;
+};
+
+struct game_state {+ int *board;
+ struct shared_state *shared;
+ int completed, cheated;
+};
+
+static const struct game_params defaults[3] = {{5, 5}, {7, 7}, {9, 9}};+
+static game_params *default_params(void)
+{+ game_params *ret = snew(game_params);
+
+ *ret = defaults[1]; /* struct copy */
+
+ return ret;
+}
+
+static int game_fetch_preset(int i, char **name, game_params **params)
+{+ char buf[64];
+
+ if (i < 0 || i >= lenof(defaults)) return FALSE;
+ *params = snew(game_params);
+ **params = defaults[i]; /* struct copy */
+ sprintf(buf, "%dx%d", defaults[i].w, defaults[i].h);
+ *name = dupstr(buf);
+
+ return TRUE;
+}
+
+static void free_params(game_params *params)
+{+ sfree(params);
+}
+
+static game_params *dup_params(game_params *params)
+{+ game_params *ret = snew(game_params);
+ *ret = *params; /* struct copy */
+ return ret;
+}
+
+static void decode_params(game_params *ret, char const *string)
+{+ ret->w = ret->h = atoi(string);
+ while (*string && isdigit((unsigned char) *string)) ++string;
+ if (*string == 'x') ret->h = atoi(++string);
+}
+
+static char *encode_params(game_params *params, int full)
+{+ char buf[64];
+ sprintf(buf, "%dx%d", params->w, params->h);
+ return dupstr(buf);
+}
+
+static config_item *game_configure(game_params *params)
+{+ config_item *ret;
+ char buf[64];
+
+ ret = snewn(3, config_item);
+
+ ret[0].name = "Width";
+ ret[0].type = C_STRING;
+ sprintf(buf, "%d", params->w);
+ ret[0].sval = dupstr(buf);
+ ret[0].ival = 0;
+
+ ret[1].name = "Height";
+ ret[1].type = C_STRING;
+ sprintf(buf, "%d", params->h);
+ ret[1].sval = dupstr(buf);
+ ret[1].ival = 0;
+
+ ret[2].name = NULL;
+ ret[2].type = C_END;
+ ret[2].sval = NULL;
+ ret[2].ival = 0;
+
+ return ret;
+}
+
+static game_params *custom_params(config_item *cfg)
+{+ game_params *ret = snew(game_params);
+
+ ret->w = atoi(cfg[0].sval);
+ ret->h = atoi(cfg[1].sval);
+
+ return ret;
+}
+
+static char *validate_params(game_params *params, int full)
+{+ if (params->w < 1) return "Width must be at least one";
+ if (params->h < 1) return "Height must be at least one";
+
+ return NULL;
+}
+
+/*****************************************************************************
+ * STRINGIFICATION OF GAME STATE *
+ *****************************************************************************/
+
+#define EMPTY 0
+
+/* Example of plaintext rendering:
+ * +---+---+---+---+---+---+---+
+ * | 6 | | | 2 | | | 2 |
+ * +---+---+---+---+---+---+---+
+ * | | 3 | | 6 | | 3 | |
+ * +---+---+---+---+---+---+---+
+ * | 3 | | | | | | 1 |
+ * +---+---+---+---+---+---+---+
+ * | | 2 | 3 | | 4 | 2 | |
+ * +---+---+---+---+---+---+---+
+ * | 2 | | | | | | 3 |
+ * +---+---+---+---+---+---+---+
+ * | | 5 | | 1 | | 4 | |
+ * +---+---+---+---+---+---+---+
+ * | 4 | | | 3 | | | 3 |
+ * +---+---+---+---+---+---+---+
+ *
+ * This puzzle instance is taken from the nikoli website
+ * Encoded (unsolved and solved), the strings are these:
+ * 7x7:6002002030603030000010230420200000305010404003003
+ * 7x7:6662232336663232331311235422255544325413434443313
+ */
+static char *board_to_string(int *board, int w, int h) {+ const int sz = w * h;
+ const int chw = (4*w + 2); /* +2 for trailing '+' and '\n' */
+ const int chh = (2*h + 1); /* +1: n fence segments, n+1 posts */
+ const int chlen = chw * chh;
+ char *repr = snewn(chlen + 1, char);
+ int i;
+
+ assert(board);
+
+ /* build the first line ("^(\+---){n}\+$") */+ for (i = 0; i < w; ++i) {+ repr[4*i + 0] = '+';
+ repr[4*i + 1] = '-';
+ repr[4*i + 2] = '-';
+ repr[4*i + 3] = '-';
+ }
+ repr[4*i + 0] = '+';
+ repr[4*i + 1] = '\n';
+
+ /* ... and copy it onto the odd-numbered lines */
+ for (i = 0; i < h; ++i) memcpy(repr + (2*i + 2) * chw, repr, chw);
+
+ /* build the second line ("^(\|\t){n}\|$") */+ for (i = 0; i < w; ++i) {+ repr[chw + 4*i + 0] = '|';
+ repr[chw + 4*i + 1] = ' ';
+ repr[chw + 4*i + 2] = ' ';
+ repr[chw + 4*i + 3] = ' ';
+ }
+ repr[chw + 4*i + 0] = '|';
+ repr[chw + 4*i + 1] = '\n';
+
+ /* ... and copy it onto the even-numbered lines */
+ for (i = 1; i < h; ++i) memcpy(repr + (2*i + 1) * chw, repr + chw, chw);
+
+ /* fill in the numbers */
+ for (i = 0; i < sz; ++i) {+ const int x = i % w;
+ const int y = i / w;
+ if (board[i] == EMPTY) continue;
+ repr[chw*(2*y + 1) + (4*x + 2)] = board[i] + '0';
+ }
+
+ repr[chlen] = '\0';
+ return repr;
+}
+
+static char *game_text_format(game_state *state)
+{+ const int w = state->shared->params.w;
+ const int h = state->shared->params.h;
+ return board_to_string(state->board, w, h);
+}
+
+/*****************************************************************************
+ * GAME GENERATION AND SOLVER *
+ *****************************************************************************/
+
+static const int dx[4] = {-1, 1, 0, 0};+static const int dy[4] = {0, 0, -1, 1};+
+/*
+static void print_board(int *board, int w, int h) {+ char *repr = board_to_string(board, w, h);
+ fputs(repr, stdout);
+ free(repr);
+}
+*/
+
+#define SENTINEL sz
+
+/* determines whether a board (in dsf form) is valid. If possible,
+ * return a conflicting pair in *a and *b and a non-*b neighbour of *a
+ * in *c. If not possible, leave them unmodified. */
+static void
+validate_board(int *dsf, int w, int h, int *sq, int *a, int *b, int *c) {+ const int sz = w * h;
+ int i;
+ assert(*a == SENTINEL);
+ assert(*b == SENTINEL);
+ assert(*c == SENTINEL);
+ for (i = 0; i < sz && *a == sz; ++i) {+ const int aa = dsf_canonify(dsf, sq[i]);
+ int cc = sz;
+ int j;
+ for (j = 0; j < 4; ++j) {+ const int x = (sq[i] % w) + dx[j];
+ const int y = (sq[i] / w) + dy[j];
+ int bb;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ bb = dsf_canonify(dsf, w*y + x);
+ if (aa == bb) continue;
+ else if (dsf_size(dsf, aa) == dsf_size(dsf, bb)) {+ *a = aa;
+ *b = bb;
+ *c = cc;
+ } else if (cc == sz) *c = cc = bb;
+ }
+ }
+}
+
+static game_state *new_game(midend *, game_params *, char *);
+static void free_game(game_state *);
+
+/* generate a random valid board; uses validate_board. */
+void make_board(int *board, int w, int h, random_state *rs) {+ int *dsf;
+
+ const unsigned int sz = w * h;
+
+ /* w=h=2 is a special case which requires a number > max(w, h) */
+ /* TODO prove that this is the case ONLY for w=h=2. */
+ const int maxsize = min(max(max(w, h), 3), 9);
+
+ /* Note that if 1 in {w, h} then it's impossible to have a region+ * of size > w*h, so the special case only affects w=h=2. */
+
+ int nboards = 0;
+
+ int i;
+
+ assert(w >= 1);
+ assert(h >= 1);
+
+ assert(board);
+
+ dsf = snew_dsf(sz); /* implicit dsf_init */
+
+ /* I abuse the board variable: when generating the puzzle, it
+ * contains a shuffled list of numbers {0, ..., nsq-1}. */+ for (i = 0; i < sz; ++i) board[i] = i;
+
+ while (1) {+ ++nboards;
+ shuffle(board, sz, sizeof (int), rs);
+ /* while the board can in principle be fixed */
+ while (1) {+ int a = SENTINEL;
+ int b = SENTINEL;
+ int c = SENTINEL;
+ validate_board(dsf, w, h, board, &a, &b, &c);
+ if (a == SENTINEL /* meaning the board is valid */) {+ int i;
+ for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
+ sfree(dsf);
+ /* printf("returning board number %d\n", nboards); */+ return;
+ } else {+ /* try to repair the invalid board */
+ a = dsf_canonify(dsf, a);
+ assert(a != dsf_canonify(dsf, b));
+ if (c != sz) assert(a != dsf_canonify(dsf, c));
+ dsf_merge(dsf, a, c == sz? b: c);
+ /* if repair impossible; make a new board */
+ if (dsf_size(dsf, a) > maxsize) break;
+ }
+ }
+ dsf_init(dsf, sz); /* re-init the dsf */
+ }
+ assert(FALSE); /* unreachable */
+}
+
+static int rhofree(int *hop, int start) {+ int turtle = start, rabbit = hop[start];
+ while (rabbit != turtle) { /* find a cycle */+ turtle = hop[turtle];
+ rabbit = hop[hop[rabbit]];
+ }
+ do { /* check that start is in the cycle */+ rabbit = hop[rabbit];
+ if (start == rabbit) return 1;
+ } while (rabbit != turtle);
+ return 0;
+}
+
+static void merge(int *dsf, int *connected, int a, int b) {+ int c;
+ assert(dsf);
+ assert(connected);
+ assert(rhofree(connected, a));
+ assert(rhofree(connected, b));
+ a = dsf_canonify(dsf, a);
+ b = dsf_canonify(dsf, b);
+ if (a == b) return;
+ dsf_merge(dsf, a, b);
+ c = connected[a];
+ connected[a] = connected[b];
+ connected[b] = c;
+ assert(rhofree(connected, a));
+ assert(rhofree(connected, b));
+}
+
+static void *memdup(const void *ptr, size_t len, size_t esz) {+ void *dup = smalloc(len * esz);
+ assert(ptr);
+ memcpy(dup, ptr, len * esz);
+ return dup;
+}
+
+static void expand(int *board, int *connected, int *dsf, int w, int h,
+ int dst, int src, int *empty, int *learn) {+ int j;
+ assert(board);
+ assert(connected);
+ assert(dsf);
+ assert(empty);
+ assert(learn);
+ assert(board[dst] == EMPTY);
+ assert(board[src] != EMPTY);
+ board[dst] = board[src];
+ for (j = 0; j < 4; ++j) {+ const int x = (dst % w) + dx[j];
+ const int y = (dst / w) + dy[j];
+ const int idx = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[idx] != board[dst]) continue;
+ merge(dsf, connected, dst, idx);
+ }
+/* printf("set board[%d] = board[%d], which is %d; size(%d) = %d\n", dst, src, board[src], src, dsf[dsf_canonify(dsf, src)] >> 2); */+ --*empty;
+ *learn = TRUE;
+}
+
+static void flood(int *board, int w, int h, int i, int n) {+ const int sz = w * h;
+ int k;
+
+ if (board[i] == EMPTY) board[i] = -SENTINEL;
+ else if (board[i] == n) board[i] = -board[i];
+ else return;
+
+ for (k = 0; k < 4; ++k) {+ const int x = (i % w) + dx[k];
+ const int y = (i / w) + dy[k];
+ const int idx = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ flood(board, w, h, idx, n);
+ }
+}
+
+static int count_and_clear(int *board, int sz) {+ int count = -1;
+ int i;
+ for (i = 0; i < sz; ++i) {+ if (board[i] >= 0) continue;
+ ++count;
+ if (board[i] == -SENTINEL) board[i] = EMPTY;
+ else board[i] = -board[i];
+ }
+ return count;
+}
+
+static int count(int *board, int w, int h, int i) {+ flood(board, w, h, i, board[i]);
+ return count_and_clear(board, w * h);
+}
+
+static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {+ int j;
+ int nhits = 0;
+ int hits[4];
+ int size = 1;
+ for (j = 0; j < 4; ++j) {+ const int x = (i % w) + dx[j];
+ const int y = (i / w) + dy[j];
+ const int idx = w*y + x;
+ int root;
+ int m;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[idx] != n) continue;
+ root = dsf_canonify(dsf, idx);
+ for (m = 0; m < nhits && root != hits[m]; ++m);
+ if (m < nhits) continue;
+ /* printf("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2); */+ size += dsf_size(dsf, root);
+ assert(dsf_size(dsf, root) >= 1);
+ hits[nhits++] = root;
+ }
+ return size;
+}
+
+/*
+ * +---+---+---+---+---+---+---+
+ * | 6 | | | 2 | | | 2 |
+ * +---+---+---+---+---+---+---+
+ * | | 3 | | 6 | | 3 | |
+ * +---+---+---+---+---+---+---+
+ * | 3 | | | | | | 1 |
+ * +---+---+---+---+---+---+---+
+ * | | 2 | 3 | | 4 | 2 | |
+ * +---+---+---+---+---+---+---+
+ * | 2 | | | | | | 3 |
+ * +---+---+---+---+---+---+---+
+ * | | 5 | | 1 | | 4 | |
+ * +---+---+---+---+---+---+---+
+ * | 4 | | | 3 | | | 3 |
+ * +---+---+---+---+---+---+---+
+ */
+
+/* Solving techniques:
+ *
+ * CONNECTED COMPONENT FORCED EXPANSION (too big):
+ * When a CC can only be expanded in one direction, because all the
+ * other ones would make the CC too big.
+ * +---+---+---+---+---+
+ * | 2 | 2 | | 2 | _ |
+ * +---+---+---+---+---+
+ *
+ * CONNECTED COMPONENT FORCED EXPANSION (too small):
+ * When a CC must include a particular square, because otherwise there
+ * would not be enough room to complete it.
+ * +---+---+
+ * | 2 | _ |
+ * +---+---+
+ *
+ * DROPPING IN A ONE:
+ * When an empty square has no neighbouring empty squares and only a 1
+ * will go into the square (or other CCs would be too big).
+ * +---+---+---+
+ * | 2 | 2 | _ |
+ * +---+---+---+
+ *
+ * TODO: generalise DROPPING IN A ONE: find the size of the CC of
+ * empty squares and a list of all adjacent numbers. See if only one
+ * number in {1, ..., size} u {all adjacent numbers} is possible.+ * Probably this is only effective for a CC size < n for some n (4?)
+ *
+ * TODO: backtracking.
+ */
+#define EXPAND(a, b)\
+expand(board, connected, dsf, w, h, a, b, &nempty, &learn)
+
+static int solver(const int *orig, int w, int h, char **solution) {+ const int sz = w * h;
+
+ int *board = memdup(orig, sz, sizeof (int));
+ int *dsf = snew_dsf(sz); /* eqv classes: connected components */
+ int *connected = snewn(sz, int); /* connected[n] := n.next; */
+ /* cyclic disjoint singly linked lists, same partitioning as dsf.
+ * The lists lets you iterate over a partition given any member */
+
+ int nempty = 0;
+
+ int learn;
+
+ int i;
+ for (i = 0; i < sz; i++) connected[i] = i;
+
+ for (i = 0; i < sz; ++i) {+ int j;
+ if (board[i] == EMPTY) ++nempty;
+ else for (j = 0; j < 4; ++j) {+ const int x = (i % w) + dx[j];
+ const int y = (i / w) + dy[j];
+ const int idx = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[i] == board[idx]) merge(dsf, connected, i, idx);
+ }
+ }
+
+/* puts("trying to solve this:");+ print_board(board, w, h); */
+
+ /* TODO: refactor this code, it's too long */
+ do {+ int i;
+ learn = FALSE;
+
+ /* for every connected component */
+ for (i = 0; i < sz; ++i) {+ int exp = SENTINEL;
+ int j;
+
+ /* If the component consists of empty squares */
+ if (board[i] == EMPTY) {+ int k;
+ int one = TRUE;
+ for (k = 0; k < 4; ++k) {+ const int x = (i % w) + dx[k];
+ const int y = (i / w) + dy[k];
+ const int idx = w*y + x;
+ int n;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[idx] == EMPTY) {+ one = FALSE;
+ continue;
+ }
+ if (one &&
+ (board[idx] == 1 ||
+ (board[idx] >= expandsize(board, dsf, w, h,
+ i, board[idx]))))
+ one = FALSE;
+ assert(board[i] == EMPTY);
+ board[i] = -SENTINEL;
+ n = count(board, w, h, idx);
+ assert(board[i] == EMPTY);
+ if (n >= board[idx]) continue;
+ EXPAND(i, idx);
+ break;
+ }
+ if (k == 4 && one) {+ assert(board[i] == EMPTY);
+ board[i] = 1;
+ assert(nempty);
+ --nempty;
+ learn = TRUE;
+ }
+ continue;
+ }
+ /* printf("expanding blob of (%d, %d)\n", i % w, i / w); */+
+ j = dsf_canonify(dsf, i);
+
+ /* (but only for each connected component) */
+ if (i != j) continue;
+
+ /* (and not if it's already complete) */
+ if (dsf_size(dsf, j) == board[j]) continue;
+
+ /* for each square j _in_ the connected component */
+ do {+ int k;
+ /* printf(" looking at (%d, %d)\n", j % w, j / w); */+
+ /* for each neighbouring square (idx) */
+ for (k = 0; k < 4; ++k) {+ const int x = (j % w) + dx[k];
+ const int y = (j / w) + dy[k];
+ const int idx = w*y + x;
+ int size;
+ /* int l;
+ int nhits = 0;
+ int hits[4]; */
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[idx] != EMPTY) continue;
+ if (exp == idx) continue;
+ /* printf("\ttrying to expand onto (%d, %d)\n", x, y); */+
+ /* find out the would-be size of the new connected
+ * component if we actually expanded into idx */
+ /*
+ size = 1;
+ for (l = 0; l < 4; ++l) {+ const int lx = x + dx[l];
+ const int ly = y + dy[l];
+ const int idxl = w*ly + lx;
+ int root;
+ int m;
+ if (lx < 0 || lx >= w || ly < 0 || ly >= h) continue;
+ if (board[idxl] != board[j]) continue;
+ root = dsf_canonify(dsf, idxl);
+ for (m = 0; m < nhits && root != hits[m]; ++m);
+ if (m != nhits) continue;
+ // printf("\t (%d, %d) contributed %d to size\n", lx, ly, dsf[root] >> 2);+ size += dsf_size(dsf, root);
+ assert(dsf_size(dsf, root) >= 1);
+ hits[nhits++] = root;
+ }
+ */
+
+ size = expandsize(board, dsf, w, h, idx, board[j]);
+
+ /* ... and see if that size is too big, or if we
+ * have other expansion candidates. Otherwise
+ * remember the (so far) only candidate. */
+
+ /* printf("\tthat would give a size of %d\n", size); */+ if (size > board[j]) continue;
+ /* printf("\tnow knowing %d expansions\n", nexpand + 1); */+ if (exp != SENTINEL) goto next_i;
+ assert(exp != idx);
+ exp = idx;
+ }
+
+ j = connected[j]; /* next square in the same CC */
+ assert(board[i] == board[j]);
+ } while (j != i);
+ /* end: for each square j _in_ the connected component */
+
+ if (exp == SENTINEL) continue;
+ /* printf("expand b: %d -> %d\n", i, exp); */+ EXPAND(exp, i);
+
+ next_i:
+ ;
+ }
+ /* end: for each connected component */
+ } while (learn && nempty);
+
+ /* puts("best guess:");+ print_board(board, w, h); */
+
+ if (solution) {+ int i;
+ assert(*solution == NULL);
+ *solution = snewn(sz + 2, char);
+ **solution = 's';
+ for (i = 0; i < sz; ++i) (*solution)[i + 1] = board[i] + '0';
+ (*solution)[sz + 1] = '\0';
+ /* We don't need the \0 for execute_move (the only user)
+ * I'm just being printf-friendly in case I wanna print */
+ }
+
+ sfree(dsf);
+ sfree(board);
+ sfree(connected);
+
+ return !nempty;
+}
+
+static int *make_dsf(int *dsf, int *board, const int w, const int h) {+ const int sz = w * h;
+ int i;
+
+ if (!dsf)
+ dsf = snew_dsf(w * h);
+ else
+ dsf_init(dsf, w * h);
+
+ for (i = 0; i < sz; ++i) {+ int j;
+ for (j = 0; j < 4; ++j) {+ const int x = (i % w) + dx[j];
+ const int y = (i / w) + dy[j];
+ const int k = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[i] == board[k]) dsf_merge(dsf, i, k);
+ }
+ }
+ return dsf;
+}
+
+/*
+static int filled(int *board, int *randomize, int k, int n) {+ int i;
+ if (board == NULL) return FALSE;
+ if (randomize == NULL) return FALSE;
+ if (k > n) return FALSE;
+ for (i = 0; i < k; ++i) if (board[randomize[i]] == 0) return FALSE;
+ for (; i < n; ++i) if (board[randomize[i]] != 0) return FALSE;
+ return TRUE;
+}
+*/
+
+static int *g_board;
+static int compare(const void *pa, const void *pb) {+ if (!g_board) return 0;
+ return g_board[*(const int *)pb] - g_board[*(const int *)pa];
+}
+
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
+{+ const int w = params->w;
+ const int h = params->h;
+ const int sz = w * h;
+ int *board = snewn(sz, int);
+ int *randomize = snewn(sz, int);
+ int *solver_board = snewn(sz, int);
+ char *game_description = snewn(sz + 1, char);
+ int i;
+
+ for (i = 0; i < sz; ++i) {+ board[i] = EMPTY;
+ randomize[i] = i;
+ }
+
+ make_board(board, w, h, rs);
+ memcpy(solver_board, board, sz * sizeof (int));
+
+ g_board = board;
+ qsort(randomize, sz, sizeof (int), compare);
+
+ /* since more clues only helps and never hurts, one pass will do
+ * just fine: if we can remove clue n with k clues of index > n,
+ * we could have removed clue n with >= k clues of index > n.
+ * So an additional pass wouldn't do anything [use induction]. */
+ for (i = 0; i < sz; ++i) {+ solver_board[randomize[i]] = EMPTY;
+ if (!solver(solver_board, w, h, NULL))
+ solver_board[randomize[i]] = board[randomize[i]];
+ }
+
+ for (i = 0; i < sz; ++i) {+ assert(solver_board[i] >= 0);
+ assert(solver_board[i] < 10);
+ game_description[i] = solver_board[i] + '0';
+ }
+ game_description[sz] = '\0';
+
+/*
+ solver(solver_board, w, h, aux);
+ print_board(solver_board, w, h);
+*/
+
+ sfree(randomize);
+ sfree(solver_board);
+ sfree(board);
+
+ return game_description;
+}
+
+static char *validate_desc(game_params *params, char *desc)
+{+ int i;
+ const int sz = params->w * params->h;
+ const char m = '0' + max(max(params->w, params->h), 3);
+
+ /* printf("desc = '%s'; sz = %d\n", desc, sz); */+
+ for (i = 0; desc[i] && i < sz; ++i)
+ if (!isdigit((unsigned char) *desc))
+ return "non-digit in string";
+ else if (desc[i] > m)
+ return "too large digit in string";
+ if (desc[i]) return "string too long";
+ else if (i < sz) return "string too short";
+ return NULL;
+}
+
+static game_state *new_game(midend *me, game_params *params, char *desc)
+{+ game_state *state = snew(game_state);
+ int sz = params->w * params->h;
+ int i;
+
+ state->cheated = state->completed = FALSE;
+ state->shared = snew(struct shared_state);
+ state->shared->refcnt = 1;
+ state->shared->params = *params; /* struct copy */
+ state->shared->clues = snewn(sz, int);
+ for (i = 0; i < sz; ++i) state->shared->clues[i] = desc[i] - '0';
+ state->board = memdup(state->shared->clues, sz, sizeof (int));
+
+ return state;
+}
+
+static game_state *dup_game(game_state *state)
+{+ const int sz = state->shared->params.w * state->shared->params.h;
+ game_state *ret = snew(game_state);
+
+ ret->board = memdup(state->board, sz, sizeof (int));
+ ret->shared = state->shared;
+ ret->cheated = state->cheated;
+ ret->completed = state->completed;
+ ++ret->shared->refcnt;
+
+ return ret;
+}
+
+static void free_game(game_state *state)
+{+ assert(state);
+ sfree(state->board);
+ if (--state->shared->refcnt == 0) {+ sfree(state->shared->clues);
+ sfree(state->shared);
+ }
+ sfree(state);
+}
+
+static char *solve_game(game_state *state, game_state *currstate,
+ char *aux, char **error)
+{+ if (aux == NULL) {+ const int w = state->shared->params.w;
+ const int h = state->shared->params.h;
+ if (!solver(state->board, w, h, &aux))
+ *error = "Sorry, I couldn't find a solution";
+ }
+ return aux;
+}
+
+/*****************************************************************************
+ * USER INTERFACE STATE AND ACTION *
+ *****************************************************************************/
+
+struct game_ui {+ int x, y; /* highlighted square, or (-1, -1) if none */
+};
+
+static game_ui *new_ui(game_state *state)
+{+ game_ui *ui = snew(game_ui);
+
+ ui->x = ui->y = -1;
+
+ return ui;
+}
+
+static void free_ui(game_ui *ui)
+{+ sfree(ui);
+}
+
+static char *encode_ui(game_ui *ui)
+{+ return NULL;
+}
+
+static void decode_ui(game_ui *ui, char *encoding)
+{+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{+}
+
+#define PREFERRED_TILE_SIZE 32
+#define TILE_SIZE (ds->tilesize)
+#define BORDER (TILE_SIZE / 2)
+#define BORDER_WIDTH (TILE_SIZE / 32)
+
+struct game_drawstate {+ struct game_params params;
+ int tilesize;
+ int started;
+ int *v, *flags;
+ int *dsf_scratch, *border_scratch;
+};
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{+ const int w = state->shared->params.w;
+ const int h = state->shared->params.h;
+
+ const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
+ const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
+
+ assert(ui);
+ assert(ds);
+
+ button &= ~MOD_MASK;
+
+ if (tx >= 0 && tx < w && ty >= 0 && ty < h) {+ if (button == LEFT_BUTTON) {+ if ((tx == ui->x && ty == ui->y) || state->shared->clues[w*ty+tx])
+ ui->x = ui->y = -1;
+ else ui->x = tx, ui->y = ty;
+ return ""; /* redraw */
+ }
+ }
+
+ assert((ui->x == -1) == (ui->y == -1));
+ if (ui->x == -1) return NULL;
+ assert(state->shared->clues[w*ui->y + ui->x] == 0);
+
+ switch (button) {+ case ' ':
+ case '\r':
+ case '\n':
+ case '\b':
+ case '\177':
+ button = 0;
+ break;
+ default:
+ if (!isdigit(button)) return NULL;
+ button -= '0';
+ if (button > (w == 2 && h == 2? 3: max(w, h))) return NULL;
+ }
+
+ {+ const int i = w*ui->y + ui->x;
+ char buf[64];
+ sprintf(buf, "%d_%d", i, button);
+ ui->x = ui->y = -1;
+ return dupstr(buf);
+ }
+}
+
+static game_state *execute_move(game_state *state, char *move)
+{+ game_state *new_state;
+
+ if (*move == 's') {+ const int sz = state->shared->params.w * state->shared->params.h;
+ int i = 0;
+ new_state = dup_game(state);
+ for (++move; i < sz; ++i) new_state->board[i] = move[i] - '0';
+ new_state->cheated = TRUE;
+ } else {+ char *endptr;
+ const int i = strtol(move, &endptr, errno = 0);
+ int value;
+ if (errno == ERANGE) return NULL;
+ if (endptr == move) return NULL;
+ if (*endptr != '_') return NULL;
+ move = endptr + 1;
+ value = strtol(move, &endptr, 0);
+ if (endptr == move) return NULL;
+ if (*endptr != '\0') return NULL;
+ new_state = dup_game(state);
+ new_state->board[i] = value;
+ }
+
+ /*
+ * Check for completion.
+ */
+ if (!new_state->completed) {+ const int w = new_state->shared->params.w;
+ const int h = new_state->shared->params.h;
+ const int sz = w * h;
+ int *dsf = make_dsf(NULL, new_state->board, w, h);
+ int i;
+ for (i = 0; i < sz && new_state->board[i] == dsf_size(dsf, i); ++i);
+ sfree(dsf);
+ if (i == sz)
+ new_state->completed = TRUE;
+ }
+
+ return new_state;
+}
+
+/* ----------------------------------------------------------------------
+ * Drawing routines.
+ */
+
+#define FLASH_TIME 0.4F
+
+#define COL_CLUE COL_GRID
+enum {+ COL_BACKGROUND,
+ COL_GRID,
+ COL_HIGHLIGHT,
+ COL_CORRECT,
+ COL_ERROR,
+ COL_USER,
+ NCOLOURS
+};
+
+static void game_compute_size(game_params *params, int tilesize,
+ int *x, int *y)
+{+ *x = (params->w + 1) * tilesize;
+ *y = (params->h + 1) * tilesize;
+}
+
+static void game_set_size(drawing *dr, game_drawstate *ds,
+ game_params *params, int tilesize)
+{+ ds->tilesize = tilesize;
+}
+
+static float *game_colours(frontend *fe, int *ncolours)
+{+ float *ret = snewn(3 * NCOLOURS, float);
+
+ frontend_default_colour(fe, &ret[COL_BACKGROUND * 3]);
+
+ ret[COL_GRID * 3 + 0] = 0.0F;
+ ret[COL_GRID * 3 + 1] = 0.0F;
+ ret[COL_GRID * 3 + 2] = 0.0F;
+
+ ret[COL_HIGHLIGHT * 3 + 0] = 0.85F * ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_HIGHLIGHT * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_HIGHLIGHT * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
+
+ ret[COL_CORRECT * 3 + 0] = 0.9F * ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_CORRECT * 3 + 1] = 0.9F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_CORRECT * 3 + 2] = 0.9F * ret[COL_BACKGROUND * 3 + 2];
+
+ ret[COL_ERROR * 3 + 0] = 1.0F;
+ ret[COL_ERROR * 3 + 1] = 0.85F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_ERROR * 3 + 2] = 0.85F * ret[COL_BACKGROUND * 3 + 2];
+
+ ret[COL_USER * 3 + 0] = 0.0F;
+ ret[COL_USER * 3 + 1] = 0.6F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_USER * 3 + 2] = 0.0F;
+
+ *ncolours = NCOLOURS;
+ return ret;
+}
+
+static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+{+ struct game_drawstate *ds = snew(struct game_drawstate);
+ int i;
+
+ ds->tilesize = PREFERRED_TILE_SIZE;
+ ds->started = 0;
+ ds->params = state->shared->params;
+ ds->v = snewn(ds->params.w * ds->params.h, int);
+ ds->flags = snewn(ds->params.w * ds->params.h, int);
+ for (i = 0; i < ds->params.w * ds->params.h; i++)
+ ds->v[i] = ds->flags[i] = -1;
+ ds->border_scratch = snewn(ds->params.w * ds->params.h, int);
+ ds->dsf_scratch = NULL;
+
+ return ds;
+}
+
+static void game_free_drawstate(drawing *dr, game_drawstate *ds)
+{+ sfree(ds->v);
+ sfree(ds->flags);
+ sfree(ds->border_scratch);
+ sfree(ds->dsf_scratch);
+ sfree(ds);
+}
+
+#define BORDER_U 0x001
+#define BORDER_D 0x002
+#define BORDER_L 0x004
+#define BORDER_R 0x008
+#define BORDER_UR 0x010
+#define BORDER_DR 0x020
+#define BORDER_UL 0x040
+#define BORDER_DL 0x080
+#define CURSOR_BG 0x100
+#define CORRECT_BG 0x200
+#define ERROR_BG 0x400
+#define USER_COL 0x800
+
+static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
+ int n, int flags)
+{+ assert(dr);
+ assert(ds);
+
+ /*
+ * Clear the square.
+ */
+ draw_rect(dr,
+ BORDER + x*TILE_SIZE + 1,
+ BORDER + y*TILE_SIZE + 1,
+ TILE_SIZE - 1,
+ TILE_SIZE - 1,
+ (flags & CURSOR_BG ? COL_HIGHLIGHT :
+ flags & ERROR_BG ? COL_ERROR :
+ flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
+
+ /*
+ * Draw the number.
+ */
+ if (n) {+ char buf[2];
+ buf[0] = n + '0';
+ buf[1] = '\0';
+ draw_text(dr,
+ (x + 1) * TILE_SIZE,
+ (y + 1) * TILE_SIZE,
+ FONT_VARIABLE,
+ TILE_SIZE / 2,
+ ALIGN_VCENTRE | ALIGN_HCENTRE,
+ flags & USER_COL ? COL_USER : COL_CLUE,
+ buf);
+ }
+
+ /*
+ * Draw bold lines around the borders.
+ */
+ if (flags & BORDER_L)
+ draw_rect(dr,
+ BORDER + x*TILE_SIZE + 1,
+ BORDER + y*TILE_SIZE + 1,
+ BORDER_WIDTH,
+ TILE_SIZE - 1,
+ COL_GRID);
+ if (flags & BORDER_U)
+ draw_rect(dr,
+ BORDER + x*TILE_SIZE + 1,
+ BORDER + y*TILE_SIZE + 1,
+ TILE_SIZE - 1,
+ BORDER_WIDTH,
+ COL_GRID);
+ if (flags & BORDER_R)
+ draw_rect(dr,
+ BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
+ BORDER + y*TILE_SIZE + 1,
+ BORDER_WIDTH,
+ TILE_SIZE - 1,
+ COL_GRID);
+ if (flags & BORDER_D)
+ draw_rect(dr,
+ BORDER + x*TILE_SIZE + 1,
+ BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
+ TILE_SIZE - 1,
+ BORDER_WIDTH,
+ COL_GRID);
+ if (flags & BORDER_UL)
+ draw_rect(dr,
+ BORDER + x*TILE_SIZE + 1,
+ BORDER + y*TILE_SIZE + 1,
+ BORDER_WIDTH,
+ BORDER_WIDTH,
+ COL_GRID);
+ if (flags & BORDER_UR)
+ draw_rect(dr,
+ BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
+ BORDER + y*TILE_SIZE + 1,
+ BORDER_WIDTH,
+ BORDER_WIDTH,
+ COL_GRID);
+ if (flags & BORDER_DL)
+ draw_rect(dr,
+ BORDER + x*TILE_SIZE + 1,
+ BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
+ BORDER_WIDTH,
+ BORDER_WIDTH,
+ COL_GRID);
+ if (flags & BORDER_DR)
+ draw_rect(dr,
+ BORDER + (x+1)*TILE_SIZE - BORDER_WIDTH,
+ BORDER + (y+1)*TILE_SIZE - BORDER_WIDTH,
+ BORDER_WIDTH,
+ BORDER_WIDTH,
+ COL_GRID);
+
+ draw_update(dr,
+ BORDER + x*TILE_SIZE - 1,
+ BORDER + y*TILE_SIZE - 1,
+ TILE_SIZE + 3,
+ TILE_SIZE + 3);
+}
+
+static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state,
+ game_ui *ui, int flashy, int borders, int shading)
+{+ const int w = state->shared->params.w;
+ const int h = state->shared->params.h;
+ int x;
+ int y;
+
+ /*
+ * Build a dsf for the board in its current state, to use for
+ * highlights and hints.
+ */
+ ds->dsf_scratch = make_dsf(ds->dsf_scratch, state->board, w, h);
+
+ /*
+ * Work out where we're putting borders between the cells.
+ */
+ for (y = 0; y < w*h; y++)
+ ds->border_scratch[y] = 0;
+
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++) {+ int dx, dy;
+ int v1, s1, v2, s2;
+
+ for (dx = 0; dx <= 1; dx++) {+ int border = FALSE;
+
+ dy = 1 - dx;
+
+ if (x+dx >= w || y+dy >= h)
+ continue;
+
+ v1 = state->board[y*w+x];
+ v2 = state->board[(y+dy)*w+(x+dx)];
+ s1 = dsf_size(ds->dsf_scratch, y*w+x);
+ s2 = dsf_size(ds->dsf_scratch, (y+dy)*w+(x+dx));
+
+ /*
+ * We only ever draw a border between two cells if
+ * they don't have the same contents.
+ */
+ if (v1 != v2) {+ /*
+ * But in that situation, we don't always draw
+ * a border. We do if the two cells both
+ * contain actual numbers...
+ */
+ if (v1 && v2)
+ border = TRUE;
+
+ /*
+ * ... or if at least one of them is a
+ * completed or overfull omino.
+ */
+ if (v1 && s1 >= v1)
+ border = TRUE;
+ if (v2 && s2 >= v2)
+ border = TRUE;
+ }
+
+ if (border)
+ ds->border_scratch[y*w+x] |= (dx ? 1 : 2);
+ }
+ }
+
+ /*
+ * Actually do the drawing.
+ */
+ for (y = 0; y < h; ++y)
+ for (x = 0; x < w; ++x) {+ /*
+ * Determine what we need to draw in this square.
+ */
+ int v = state->board[y*w+x];
+ int flags = 0;
+
+ if (flashy || !shading) {+ /* clear all background flags */
+ } else if (x == ui->x && y == ui->y) {+ flags |= CURSOR_BG;
+ } else if (v) {+ int size = dsf_size(ds->dsf_scratch, y*w+x);
+ if (size == v)
+ flags |= CORRECT_BG;
+ else if (size > v)
+ flags |= ERROR_BG;
+ }
+
+ /*
+ * Borders at the very edges of the grid are
+ * independent of the `borders' flag.
+ */
+ if (x == 0)
+ flags |= BORDER_L;
+ if (y == 0)
+ flags |= BORDER_U;
+ if (x == w-1)
+ flags |= BORDER_R;
+ if (y == h-1)
+ flags |= BORDER_D;
+
+ if (borders) {+ if (x == 0 || (ds->border_scratch[y*w+(x-1)] & 1))
+ flags |= BORDER_L;
+ if (y == 0 || (ds->border_scratch[(y-1)*w+x] & 2))
+ flags |= BORDER_U;
+ if (x == w-1 || (ds->border_scratch[y*w+x] & 1))
+ flags |= BORDER_R;
+ if (y == h-1 || (ds->border_scratch[y*w+x] & 2))
+ flags |= BORDER_D;
+
+ if (y > 0 && x > 0 && (ds->border_scratch[(y-1)*w+(x-1)]))
+ flags |= BORDER_UL;
+ if (y > 0 && x < w-1 &&
+ ((ds->border_scratch[(y-1)*w+x] & 1) ||
+ (ds->border_scratch[(y-1)*w+(x+1)] & 2)))
+ flags |= BORDER_UR;
+ if (y < h-1 && x > 0 &&
+ ((ds->border_scratch[y*w+(x-1)] & 2) ||
+ (ds->border_scratch[(y+1)*w+(x-1)] & 1)))
+ flags |= BORDER_DL;
+ if (y < h-1 && x < w-1 &&
+ ((ds->border_scratch[y*w+(x+1)] & 2) ||
+ (ds->border_scratch[(y+1)*w+x] & 1)))
+ flags |= BORDER_DR;
+ }
+
+ if (!state->shared->clues[y*w+x])
+ flags |= USER_COL;
+
+ if (ds->v[y*w+x] != v || ds->flags[y*w+x] != flags) {+ draw_square(dr, ds, x, y, v, flags);
+ ds->v[y*w+x] = v;
+ ds->flags[y*w+x] = flags;
+ }
+ }
+}
+
+static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
+{+ const int w = state->shared->params.w;
+ const int h = state->shared->params.h;
+
+ const int flashy =
+ flashtime > 0 &&
+ (flashtime <= FLASH_TIME/3 || flashtime >= FLASH_TIME*2/3);
+
+ if (!ds->started) {+ /*
+ * The initial contents of the window are not guaranteed and
+ * can vary with front ends. To be on the safe side, all games
+ * should start by drawing a big background-colour rectangle
+ * covering the whole window.
+ */
+ draw_rect(dr, 0, 0, 10*ds->tilesize, 10*ds->tilesize, COL_BACKGROUND);
+
+ /*
+ * Smaller black rectangle which is the main grid.
+ */
+ draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
+ w*TILE_SIZE + 2*BORDER_WIDTH + 1,
+ h*TILE_SIZE + 2*BORDER_WIDTH + 1,
+ COL_GRID);
+
+ ds->started = TRUE;
+ }
+
+ draw_grid(dr, ds, state, ui, flashy, TRUE, TRUE);
+}
+
+static float game_anim_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{+ return 0.0F;
+}
+
+static float game_flash_length(game_state *oldstate, game_state *newstate,
+ int dir, game_ui *ui)
+{+ assert(oldstate);
+ assert(newstate);
+ assert(newstate->shared);
+ assert(oldstate->shared == newstate->shared);
+ if (!oldstate->completed && newstate->completed &&
+ !oldstate->cheated && !newstate->cheated)
+ return FLASH_TIME;
+ return 0.0F;
+}
+
+static int game_timing_state(game_state *state, game_ui *ui)
+{+ return TRUE;
+}
+
+static void game_print_size(game_params *params, float *x, float *y)
+{+ int pw, ph;
+
+ /*
+ * I'll use 6mm squares by default.
+ */
+ game_compute_size(params, 600, &pw, &ph);
+ *x = pw / 100.0;
+ *y = ph / 100.0;
+}
+
+static void game_print(drawing *dr, game_state *state, int tilesize)
+{+ const int w = state->shared->params.w;
+ const int h = state->shared->params.h;
+ int c, i, borders;
+
+ /* Ick: fake up `ds->tilesize' for macro expansion purposes */
+ game_drawstate *ds = game_new_drawstate(dr, state);
+ game_set_size(dr, ds, NULL, tilesize);
+
+ c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
+ c = print_mono_colour(dr, 0); assert(c == COL_GRID);
+ c = print_mono_colour(dr, 1); assert(c == COL_HIGHLIGHT);
+ c = print_mono_colour(dr, 1); assert(c == COL_CORRECT);
+ c = print_mono_colour(dr, 1); assert(c == COL_ERROR);
+ c = print_mono_colour(dr, 0); assert(c == COL_USER);
+
+ /*
+ * Border.
+ */
+ draw_rect(dr, BORDER - BORDER_WIDTH, BORDER - BORDER_WIDTH,
+ w*TILE_SIZE + 2*BORDER_WIDTH + 1,
+ h*TILE_SIZE + 2*BORDER_WIDTH + 1,
+ COL_GRID);
+
+ /*
+ * We'll draw borders between the ominoes iff the grid is not
+ * pristine. So scan it to see if it is.
+ */
+ borders = FALSE;
+ for (i = 0; i < w*h; i++)
+ if (state->board[i] && !state->shared->clues[i])
+ borders = TRUE;
+
+ /*
+ * Draw grid.
+ */
+ draw_grid(dr, ds, state, NULL, FALSE, borders, FALSE);
+
+ /*
+ * Clean up.
+ */
+ game_free_drawstate(dr, ds);
+}
+
+#ifdef COMBINED
+#define thegame filling
+#endif
+
+const struct game thegame = {+ "Filling", "games.filling", "filling",
+ default_params,
+ game_fetch_preset,
+ decode_params,
+ encode_params,
+ free_params,
+ dup_params,
+ TRUE, game_configure, custom_params,
+ validate_params,
+ new_game_desc,
+ validate_desc,
+ new_game,
+ dup_game,
+ free_game,
+ TRUE, solve_game,
+ TRUE, game_text_format,
+ new_ui,
+ free_ui,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
+ PREFERRED_TILE_SIZE, game_compute_size, game_set_size,
+ game_colours,
+ game_new_drawstate,
+ game_free_drawstate,
+ game_redraw,
+ game_anim_length,
+ game_flash_length,
+ TRUE, FALSE, game_print_size, game_print,
+ FALSE, /* wants_statusbar */
+ FALSE, game_timing_state,
+ 0, /* flags */
+};
+
+#ifdef STANDALONE_SOLVER /* solver? hah! */
+
+int main(int argc, char **argv) {+ while (*++argv) {+ game_params *params;
+ game_state *state;
+ char *par;
+ char *desc;
+
+ for (par = desc = *argv; *desc != '\0' && *desc != ':'; ++desc);
+ if (*desc == '\0') {+ fprintf(stderr, "bad puzzle id: %s", par);
+ continue;
+ }
+
+ *desc++ = '\0';
+
+ params = snew(game_params);
+ decode_params(params, par);
+ state = new_game(NULL, params, desc);
+ if (solver(state->board, params->w, params->h, NULL))
+ printf("%s:%s: solvable\n", par, desc);+ else
+ printf("%s:%s: not solvable\n", par, desc);+ }
+ return 0;
+}
+
+#endif
--- a/icons/Makefile
+++ b/icons/Makefile
@@ -1,8 +1,8 @@
# Makefile for Puzzles icons.
-PUZZLES = blackbox bridges cube dominosa fifteen flip galaxies guess inertia \
- lightup loopy map mines net netslide pattern pegs rect samegame \
- sixteen slant solo tents twiddle unequal untangle
+PUZZLES = blackbox bridges cube dominosa fifteen filling flip galaxies guess \
+ inertia lightup loopy map mines net netslide pattern pegs rect \
+ samegame sixteen slant solo tents twiddle unequal untangle
BASE = $(patsubst %,%-base.png,$(PUZZLES))
WEB = $(patsubst %,%-web.png,$(PUZZLES))
@@ -55,6 +55,7 @@
bridges-ibase.png : override CROP=264x264 107x107+157+157
dominosa-ibase.png : override CROP=304x272 152x152+152+0
fifteen-ibase.png : override CROP=240x240 120x120+0+120
+filling-ibase.png : override CROP=256x256 131x131+15+79
flip-ibase.png : override CROP=288x288 145x145+120+72
galaxies-ibase.png : override CROP=288x288 165x165+0+0
guess-ibase.png : override CROP=263x420 178x178+75+17
--- /dev/null
+++ b/icons/filling.sav
@@ -1,0 +1,38 @@
+SAVEFILE:41:Simon Tatham's Portable Puzzle Collection
+VERSION :1:1
+GAME :7:Filling
+PARAMS :3:7x7
+CPARAMS :3:7x7
+SEED :15:279172739852696
+DESC :49:0000000031051240010004000001106171000400001013105
+NSTATES :2:30
+STATEPOS:2:13
+MOVE :4:38_3
+MOVE :4:39_3
+MOVE :4:36_4
+MOVE :4:43_4
+MOVE :4:35_4
+MOVE :4:47_5
+MOVE :4:40_5
+MOVE :4:34_5
+MOVE :4:41_5
+MOVE :4:25_7
+MOVE :4:23_6
+MOVE :4:16_6
+MOVE :4:18_7
+MOVE :4:19_7
+MOVE :4:20_7
+MOVE :4:26_7
+MOVE :4:24_7
+MOVE :4:29_6
+MOVE :4:22_6
+MOVE :4:15_6
+MOVE :3:7_4
+MOVE :3:0_4
+MOVE :3:1_3
+MOVE :3:2_3
+MOVE :3:6_2
+MOVE :3:5_5
+MOVE :3:4_5
+MOVE :3:3_5
+MOVE :4:10_5
--- a/puzzles.but
+++ b/puzzles.but
@@ -2204,12 +2204,52 @@
+\C{filling} \i{Filling}+\cfg{winhelp-topic}{games.filling}+
+You have a grid of squares, some of which contain digits, and the
+rest of which are empty. Your job is to fill in digits in the empty
+squares, in such a way that each connected region of squares all
+containing the same digit has an area equal to that digit.
+
+(\q{Connected region}, for the purposes of this game, does not count+diagonally separated squares as adjacent.)
+
+For example, it follows that no square can contain a zero, and that
+two adjacent squares can not both contain a one. No region has an
+area greater than 9 (because then its area would not be a single
+digit).
+
+Credit for this puzzle goes to \i{Nikoli} \k{nikoli-fillomino}.+
+Filling was contributed to this collection by Jonas K\u00F6{oe}lker.+
+\B{nikoli-fillomino}+\W{http://www.nikoli.co.jp/en/puzzles/fillomino/}\cw{http://www.nikoli.co.jp/en/puzzles/fillomino/}+
+\H{filling-controls} \I{controls, for Filling}Filling controls+
+To play Filling, simply click the mouse in any empty square and then
+type a digit on the keyboard to fill that square. If you make a
+mistake, click the mouse in the incorrect square and press 0, Space,
+Backspace or Enter to clear it again (or use the Undo feature).
+
+(All the actions described in \k{common-actions} are also available.)+
+\H{filling-parameters} \I{parameters, for Filling}Filling parameters+
+Filling allows you to configure the number of rows and columns of the
+grid, through the \q{Type} menu.+
+
+
\A{licence} \I{MIT licence}\ii{Licence} This software is \i{copyright} 2004-2007 Simon Tatham.-Portions copyright Richard Boulton, James Harvey and Mike Pinna.
+Portions copyright Richard Boulton, James Harvey, Mike Pinna and
+Jonas K\u00F6{oe}lker.Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation files
--- a/puzzles.h
+++ b/puzzles.h
@@ -288,6 +288,7 @@
* indicating whether the canonical element is inverse to val. */
int edsf_canonify(int *dsf, int val, int *inverse);
int dsf_canonify(int *dsf, int val);
+int dsf_size(int *dsf, int val);
/* Allow the caller to specify that two elements should be in the same
* equivalence class. If 'inverse' is TRUE, the elements are actually opposite