From: simon Date: Sun, 25 Feb 2007 11:37:05 +0000 (+0000) Subject: New puzzle: `Filling', a Fillomino implementation by Jonas Koelker. X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/commitdiff_plain/8b3b322359561c6c1ba4d00927400c0e5c6eecf2 New puzzle: `Filling', a Fillomino implementation by Jonas Koelker. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7326 cda61777-01e9-0310-a592-d414129be87e --- diff --git a/LICENCE b/LICENCE index 7785137..8cfd89d 100644 --- 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 diff --git a/dsf.c b/dsf.c index ecb2858..32179a6 100644 --- a/dsf.c +++ b/dsf.c @@ -64,11 +64,13 @@ void dsf_init(int *dsf, int size) { 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 @@ void dsf_merge(int *dsf, int v1, int v2) 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 @@ int edsf_canonify(int *dsf, int index, int *inverse_return) /* 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 @@ int edsf_canonify(int *dsf, int index, int *inverse_return) * 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,21 +144,31 @@ int edsf_canonify(int *dsf, int index, int *inverse_return) 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); */ 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); diff --git a/filling.R b/filling.R new file mode 100644 index 0000000..850b0be --- /dev/null +++ b/filling.R @@ -0,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 diff --git a/filling.c b/filling.c new file mode 100644 index 0000000..ac5b6d9 --- /dev/null +++ b/filling.c @@ -0,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 +#include +#include +#include +#include +#include +#include + +#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 diff --git a/icons/Makefile b/icons/Makefile index 35e04ce..3f11d7b 100644 --- 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 @@ blackbox-ibase.png : override CROP=352x352 144x144+0+208 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 diff --git a/icons/filling.sav b/icons/filling.sav new file mode 100644 index 0000000..caf0bb2 --- /dev/null +++ b/icons/filling.sav @@ -0,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 diff --git a/puzzles.but b/puzzles.but index 401419e..85b497d 100644 --- a/puzzles.but +++ b/puzzles.but @@ -2204,12 +2204,52 @@ difficulty level may require backtracking. +\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 diff --git a/puzzles.h b/puzzles.h index 129ddd1..30ffcb0 100644 --- a/puzzles.h +++ b/puzzles.h @@ -288,6 +288,7 @@ void print_dsf(int *dsf, int size); * 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