/* 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?
+ * + replace int with something else (signed short?)
+ * - the type should be signed (for -board[i] and -SENTINEL)
+ * - the type should be somewhat big: board[i] = i
+ * - Using shorts gives us 181x181 puzzles as upper bound.
*
- * - make a somewhat more clever solver
+ * - in board generation, after having merged regions such that no
+ * more merges are necessary, try splitting (big) regions.
+ * + it seems that smaller regions make for better puzzles; see
+ * for instance the 7x7 puzzle in this file (grep for 7x7:).
+ *
+ * - symmetric hints (solo-style)
+ * + right now that means including _many_ hints, and the puzzles
+ * won't look any nicer. Not worth it (at the moment).
*
* - make the solver do recursion/backtracking.
* + This is for user-submitted puzzles, not for puzzle
*
* - solo-like pencil marks?
*
- * - speed up generation of puzzles of size >= 11x11
+ * - a user says that the difficulty is unevenly distributed.
+ * + partition into levels? Will they be non-crap?
*
* - 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).
+ * + [click, 1, 0, enter] => [10 in clicked square]?
* + How much information is needed to solve? Does one need to
* know the algorithm by which the largest number is set?
*
*
* - 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.
+ * + 7x9 @ .011s, 9x13 @ .075s, 17x13 @ .661s (all avg with n=100)
+ * + but the hints are independent, not linear, so... what?
*/
#include <assert.h>
#include <ctype.h>
-#include <errno.h>
#include <math.h>
+#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "puzzles.h"
+static unsigned char verbose;
+
+static void printv(char *fmt, ...) {
+#ifndef PALM
+ if (verbose) {
+ va_list va;
+ va_start(va, fmt);
+ vprintf(fmt, va);
+ va_end(va);
+ }
+#endif
+}
+
+/*****************************************************************************
+ * GAME CONFIGURATION AND PARAMETERS *
+ *****************************************************************************/
+
struct game_params {
int w, h;
};
int completed, cheated;
};
-static const struct game_params defaults[3] = {{5, 5}, {7, 7}, {9, 9}};
+static const struct game_params filling_defaults[3] = {
+ {9, 7}, {13, 9}, {17, 13}
+};
static game_params *default_params(void)
{
game_params *ret = snew(game_params);
- *ret = defaults[1]; /* struct copy */
+ *ret = filling_defaults[1]; /* struct copy */
return ret;
}
{
char buf[64];
- if (i < 0 || i >= lenof(defaults)) return FALSE;
+ if (i < 0 || i >= lenof(filling_defaults)) return FALSE;
*params = snew(game_params);
- **params = defaults[i]; /* struct copy */
- sprintf(buf, "%dx%d", defaults[i].w, defaults[i].h);
+ **params = filling_defaults[i]; /* struct copy */
+ sprintf(buf, "%dx%d", filling_defaults[i].w, filling_defaults[i].h);
*name = dupstr(buf);
return TRUE;
sfree(params);
}
-static game_params *dup_params(game_params *params)
+static game_params *dup_params(const game_params *params)
{
game_params *ret = snew(game_params);
*ret = *params; /* struct copy */
if (*string == 'x') ret->h = atoi(++string);
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const 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)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
char buf[64];
return ret;
}
-static game_params *custom_params(config_item *cfg)
+static game_params *custom_params(const config_item *cfg)
{
game_params *ret = snew(game_params);
return ret;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const 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";
/* 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';
+ 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)
+static int game_can_format_as_text_now(const game_params *params)
+{
+ return TRUE;
+}
+
+static char *game_text_format(const game_state *state)
{
const int w = state->shared->params.w;
const int h = state->shared->params.h;
static const int dx[4] = {-1, 1, 0, 0};
static const int dy[4] = {0, 0, -1, 1};
-/*
+struct solver_state
+{
+ int *dsf;
+ int *board;
+ int *connected;
+ int nempty;
+
+ /* Used internally by learn_bitmap_deductions; kept here to avoid
+ * mallocing/freeing them every time that function is called. */
+ int *bm, *bmdsf, *bmminsize;
+};
+
static void print_board(int *board, int w, int h) {
- char *repr = board_to_string(board, w, h);
- fputs(repr, stdout);
- free(repr);
+ if (verbose) {
+ char *repr = board_to_string(board, w, h);
+ printv("%s\n", repr);
+ free(repr);
+ }
}
-*/
+
+static game_state *new_game(midend *, const game_params *, const char *);
+static void free_game(game_state *);
#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) {
+static int mark_region(int *board, int w, int h, int i, int n, int m) {
+ int j;
+
+ board[i] = -1;
+
+ for (j = 0; j < 4; ++j) {
+ const int x = (i % w) + dx[j], y = (i / w) + dy[j], ii = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[ii] == m) return FALSE;
+ if (board[ii] != n) continue;
+ if (!mark_region(board, w, h, ii, n, m)) return FALSE;
+ }
+ return TRUE;
+}
+
+static int region_size(int *board, int w, int h, int i) {
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;
- }
+ int j, size, copy;
+ if (board[i] == 0) return 0;
+ copy = board[i];
+ mark_region(board, w, h, i, board[i], SENTINEL);
+ for (size = j = 0; j < sz; ++j) {
+ if (board[j] != -1) continue;
+ ++size;
+ board[j] = copy;
}
+ return size;
}
-static game_state *new_game(midend *, game_params *, char *);
-static void free_game(game_state *);
+static void merge_ones(int *board, int w, int h)
+{
+ const int sz = w * h;
+ const int maxsize = min(max(max(w, h), 3), 9);
+ int i, j, k, change;
+ do {
+ change = FALSE;
+ for (i = 0; i < sz; ++i) {
+ if (board[i] != 1) continue;
-/* generate a random valid board; uses validate_board. */
-void make_board(int *board, int w, int h, random_state *rs) {
- int *dsf;
+ for (j = 0; j < 4; ++j, board[i] = 1) {
+ const int x = (i % w) + dx[j], y = (i / w) + dy[j];
+ int oldsize, newsize, ok, ii = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (board[ii] == maxsize) continue;
+
+ oldsize = board[ii];
+ board[i] = oldsize;
+ newsize = region_size(board, w, h, i);
+
+ if (newsize > maxsize) continue;
+
+ ok = mark_region(board, w, h, i, oldsize, newsize);
+
+ for (k = 0; k < sz; ++k)
+ if (board[k] == -1)
+ board[k] = ok ? newsize : oldsize;
+
+ if (ok) break;
+ }
+ if (j < 4) change = TRUE;
+ }
+ } while (change);
+}
- const unsigned int sz = w * h;
+/* generate a random valid board; uses validate_board. */
+static void make_board(int *board, int w, int h, random_state *rs) {
+ const 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. */
/* 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;
+ int i, change, *dsf;
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}. */
+ * contains a shuffled list of numbers {0, ..., sz-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 = snewn(sz, int);
+retry:
+ dsf_init(dsf, sz);
+ shuffle(board, sz, sizeof (int), rs);
+
+ do {
+ change = FALSE; /* as long as the board potentially has errors */
+ for (i = 0; i < sz; ++i) {
+ const int square = dsf_canonify(dsf, board[i]);
+ const int size = dsf_size(dsf, square);
+ int merge = SENTINEL, min = maxsize - size + 1, error = FALSE;
+ int neighbour, neighbour_size, j;
+
+ for (j = 0; j < 4; ++j) {
+ const int x = (board[i] % w) + dx[j];
+ const int y = (board[i] / w) + dy[j];
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+
+ neighbour = dsf_canonify(dsf, w*y + x);
+ if (square == neighbour) continue;
+
+ neighbour_size = dsf_size(dsf, neighbour);
+ if (size == neighbour_size) error = TRUE;
+
+ /* find the smallest neighbour to merge with, which
+ * wouldn't make the region too large. (This is
+ * guaranteed by the initial value of `min'.) */
+ if (neighbour_size < min) {
+ min = neighbour_size;
+ merge = neighbour;
+ }
}
+
+ /* if this square is not in error, leave it be */
+ if (!error) continue;
+
+ /* if it is, but we can't fix it, retry the whole board.
+ * Maybe we could fix it by merging the conflicting
+ * neighbouring region(s) into some of their neighbours,
+ * but just restarting works out fine. */
+ if (merge == SENTINEL) goto retry;
+
+ /* merge with the smallest neighbouring workable region. */
+ dsf_merge(dsf, square, merge);
+ change = TRUE;
}
- dsf_init(dsf, sz); /* re-init the dsf */
- }
- assert(FALSE); /* unreachable */
-}
+ } while (change);
-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;
+ for (i = 0; i < sz; ++i) board[i] = dsf_size(dsf, i);
+ merge_ones(board, w, h);
+
+ sfree(dsf);
}
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;
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) {
return dup;
}
-static void expand(int *board, int *connected, int *dsf, int w, int h,
- int dst, int src, int *empty, int *learn) {
+static void expand(struct solver_state *s, int w, int h, int t, int f) {
int j;
- assert(board);
- assert(connected);
- assert(dsf);
- assert(empty);
- assert(learn);
- assert(board[dst] == EMPTY);
- assert(board[src] != EMPTY);
- board[dst] = board[src];
+ assert(s);
+ assert(s->board[t] == EMPTY); /* expand to empty square */
+ assert(s->board[f] != EMPTY); /* expand from non-empty square */
+ printv(
+ "learn: expanding %d from (%d, %d) into (%d, %d)\n",
+ s->board[f], f % w, f / w, t % w, t / w);
+ s->board[t] = s->board[f];
for (j = 0; j < 4; ++j) {
- const int x = (dst % w) + dx[j];
- const int y = (dst / w) + dy[j];
+ const int x = (t % w) + dx[j];
+ const int y = (t / 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);
+ if (s->board[idx] != s->board[t]) continue;
+ merge(s->dsf, s->connected, t, 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;
+ --s->nempty;
}
-static void flood(int *board, int w, int h, int i, int n) {
+static void clear_count(int *board, int sz) {
+ int i;
+ for (i = 0; i < sz; ++i) {
+ if (board[i] >= 0) continue;
+ else if (board[i] == -SENTINEL) board[i] = EMPTY;
+ else board[i] = -board[i];
+ }
+}
+
+static void flood_count(int *board, int w, int h, int i, int n, int *c) {
const int sz = w * h;
int k;
else if (board[i] == n) board[i] = -board[i];
else return;
+ if (--*c == 0) 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];
+ flood_count(board, w, h, idx, n, c);
+ if (*c == 0) return;
}
- 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 check_capacity(int *board, int w, int h, int i) {
+ int n = board[i];
+ flood_count(board, w, h, i, board[i], &n);
+ clear_count(board, w * h);
+ return n == 0;
}
static int expandsize(const int *board, int *dsf, int w, int h, int i, int n) {
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); */
+ printv("\t (%d, %d) contrib %d to size\n", x, y, dsf[root] >> 2);
size += dsf_size(dsf, root);
assert(dsf_size(dsf, root) >= 1);
hits[nhits++] = root;
*
* 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.
+ * would not be enough room to complete it. This includes squares not
+ * adjacent to the CC through learn_critical_square.
* +---+---+
* | 2 | _ |
* +---+---+
*
* 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) {
+static void filled_square(struct solver_state *s, int w, int h, int 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 idx = w*y + x;
+ if (x < 0 || x >= w || y < 0 || y >= h) continue;
+ if (s->board[i] == s->board[idx])
+ merge(s->dsf, s->connected, i, idx);
+ }
+}
+
+static void init_solver_state(struct solver_state *s, int w, int h) {
const int sz = w * h;
+ int i;
+ assert(s);
- 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 */
+ s->nempty = 0;
+ for (i = 0; i < sz; ++i) s->connected[i] = i;
+ for (i = 0; i < sz; ++i)
+ if (s->board[i] == EMPTY) ++s->nempty;
+ else filled_square(s, w, h, i);
+}
+
+static int learn_expand_or_one(struct solver_state *s, int w, int h) {
+ const int sz = w * h;
+ int i;
+ int learn = FALSE;
- int nempty = 0;
+ assert(s);
- int learn;
+ for (i = 0; i < sz; ++i) {
+ int j;
+ int one = TRUE;
+
+ if (s->board[i] != EMPTY) continue;
+
+ 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 (s->board[idx] == EMPTY) {
+ one = FALSE;
+ continue;
+ }
+ if (one &&
+ (s->board[idx] == 1 ||
+ (s->board[idx] >= expandsize(s->board, s->dsf, w, h,
+ i, s->board[idx]))))
+ one = FALSE;
+ if (dsf_size(s->dsf, idx) == s->board[idx]) continue;
+ assert(s->board[i] == EMPTY);
+ s->board[i] = -SENTINEL;
+ if (check_capacity(s->board, w, h, idx)) continue;
+ assert(s->board[i] == EMPTY);
+ printv("learn: expanding in one\n");
+ expand(s, w, h, i, idx);
+ learn = TRUE;
+ break;
+ }
+ if (j == 4 && one) {
+ printv("learn: one at (%d, %d)\n", i % w, i / w);
+ assert(s->board[i] == EMPTY);
+ s->board[i] = 1;
+ assert(s->nempty);
+ --s->nempty;
+ learn = TRUE;
+ }
+ }
+ return learn;
+}
+
+static int learn_blocked_expansion(struct solver_state *s, int w, int h) {
+ const int sz = w * h;
int i;
- for (i = 0; i < sz; i++) connected[i] = i;
+ int learn = FALSE;
+ assert(s);
+ /* for every connected component */
for (i = 0; i < sz; ++i) {
+ int exp = SENTINEL;
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); */
+ if (s->board[i] == EMPTY) continue;
+ j = dsf_canonify(s->dsf, i);
+
+ /* (but only for each connected component) */
+ if (i != j) continue;
+
+ /* (and not if it's already complete) */
+ if (dsf_size(s->dsf, j) == s->board[j]) continue;
+
+ /* for each square j _in_ the connected component */
+ do {
+ int k;
+ printv(" 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 (s->board[idx] != EMPTY) continue;
+ if (exp == idx) continue;
+ printv("\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;
+ // printv("\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;
+ }
+ */
- /* TODO: refactor this code, it's too long */
- do {
- int i;
- learn = FALSE;
+ size = expandsize(s->board, s->dsf, w, h, idx, s->board[j]);
- /* 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;
+ /* ... and see if that size is too big, or if we
+ * have other expansion candidates. Otherwise
+ * remember the (so far) only candidate. */
+
+ printv("\tthat would give a size of %d\n", size);
+ if (size > s->board[j]) continue;
+ /* printv("\tnow knowing %d expansions\n", nexpand + 1); */
+ if (exp != SENTINEL) goto next_i;
+ assert(exp != idx);
+ exp = idx;
}
- /* 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 */
+ j = s->connected[j]; /* next square in the same CC */
+ assert(s->board[i] == s->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);
+ if (exp == SENTINEL) continue;
+ printv("learning to expand\n");
+ expand(s, w, h, exp, i);
+ learn = TRUE;
- next_i:
- ;
- }
- /* end: for each connected component */
- } while (learn && nempty);
+ next_i:
+ ;
+ }
+ /* end: for each connected component */
+ return learn;
+}
- /* puts("best guess:");
- print_board(board, w, h); */
+static int learn_critical_square(struct solver_state *s, int w, int h) {
+ const int sz = w * h;
+ int i;
+ int learn = FALSE;
+ assert(s);
+
+ /* for each connected component */
+ for (i = 0; i < sz; ++i) {
+ int j, slack;
+ if (s->board[i] == EMPTY) continue;
+ if (i != dsf_canonify(s->dsf, i)) continue;
+ slack = s->board[i] - dsf_size(s->dsf, i);
+ if (slack == 0) continue;
+ assert(s->board[i] != 1);
+ /* for each empty square */
+ for (j = 0; j < sz; ++j) {
+ if (s->board[j] == EMPTY) {
+ /* if it's too far away from the CC, don't bother */
+ int k = i, jx = j % w, jy = j / w;
+ do {
+ int kx = k % w, ky = k / w;
+ if (abs(kx - jx) + abs(ky - jy) <= slack) break;
+ k = s->connected[k];
+ } while (i != k);
+ if (i == k) continue; /* not within range */
+ } else continue;
+ s->board[j] = -SENTINEL;
+ if (check_capacity(s->board, w, h, i)) continue;
+ /* if not expanding s->board[i] to s->board[j] implies
+ * that s->board[i] can't reach its full size, ... */
+ assert(s->nempty);
+ printv(
+ "learn: ds %d at (%d, %d) blocking (%d, %d)\n",
+ s->board[i], j % w, j / w, i % w, i / w);
+ --s->nempty;
+ s->board[j] = s->board[i];
+ filled_square(s, w, h, j);
+ learn = TRUE;
+ }
+ }
+ return learn;
+}
+
+#if 0
+static void print_bitmap(int *bitmap, int w, int h) {
+ if (verbose) {
+ int x, y;
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ printv(" %03x", bm[y*w+x]);
+ }
+ printv("\n");
+ }
+ }
+}
+#endif
+
+static int learn_bitmap_deductions(struct solver_state *s, int w, int h)
+{
+ const int sz = w * h;
+ int *bm = s->bm;
+ int *dsf = s->bmdsf;
+ int *minsize = s->bmminsize;
+ int x, y, i, j, n;
+ int learn = FALSE;
+
+ /*
+ * This function does deductions based on building up a bitmap
+ * which indicates the possible numbers that can appear in each
+ * grid square. If we can rule out all but one possibility for a
+ * particular square, then we've found out the value of that
+ * square. In particular, this is one of the few forms of
+ * deduction capable of inferring the existence of a 'ghost
+ * region', i.e. a region which has none of its squares filled in
+ * at all.
+ *
+ * The reasoning goes like this. A currently unfilled square S can
+ * turn out to contain digit n in exactly two ways: either S is
+ * part of an n-region which also includes some currently known
+ * connected component of squares with n in, or S is part of an
+ * n-region separate from _all_ currently known connected
+ * components. If we can rule out both possibilities, then square
+ * S can't contain digit n at all.
+ *
+ * The former possibility: if there's a region of size n
+ * containing both S and some existing component C, then that
+ * means the distance from S to C must be small enough that C
+ * could be extended to include S without becoming too big. So we
+ * can do a breadth-first search out from all existing components
+ * with n in them, to identify all the squares which could be
+ * joined to any of them.
+ *
+ * The latter possibility: if there's a region of size n that
+ * doesn't contain _any_ existing component, then it also can't
+ * contain any square adjacent to an existing component either. So
+ * we can identify all the EMPTY squares not adjacent to any
+ * existing square with n in, and group them into connected
+ * components; then any component of size less than n is ruled
+ * out, because there wouldn't be room to create a completely new
+ * n-region in it.
+ *
+ * In fact we process these possibilities in the other order.
+ * First we find all the squares not adjacent to an existing
+ * square with n in; then we winnow those by removing too-small
+ * connected components, to get the set of squares which could
+ * possibly be part of a brand new n-region; and finally we do the
+ * breadth-first search to add in the set of squares which could
+ * possibly be added to some existing n-region.
+ */
+
+ /*
+ * Start by initialising our bitmap to 'all numbers possible in
+ * all squares'.
+ */
+ for (y = 0; y < h; y++)
+ for (x = 0; x < w; x++)
+ bm[y*w+x] = (1 << 10) - (1 << 1); /* bits 1,2,...,9 now set */
+#if 0
+ printv("initial bitmap:\n");
+ print_bitmap(bm, w, h);
+#endif
+
+ /*
+ * Now completely zero out the bitmap for squares that are already
+ * filled in (we aren't interested in those anyway). Also, for any
+ * filled square, eliminate its number from all its neighbours
+ * (because, as discussed above, the neighbours couldn't be part
+ * of a _new_ region with that number in it, and that's the case
+ * we consider first).
+ */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ i = y*w+x;
+ n = s->board[i];
+
+ if (n != EMPTY) {
+ bm[i] = 0;
+
+ if (x > 0)
+ bm[i-1] &= ~(1 << n);
+ if (x+1 < w)
+ bm[i+1] &= ~(1 << n);
+ if (y > 0)
+ bm[i-w] &= ~(1 << n);
+ if (y+1 < h)
+ bm[i+w] &= ~(1 << n);
+ }
+ }
+ }
+#if 0
+ printv("bitmap after filled squares:\n");
+ print_bitmap(bm, w, h);
+#endif
+
+ /*
+ * Now, for each n, we separately find the connected components of
+ * squares for which n is still a possibility. Then discard any
+ * component of size < n, because that component is too small to
+ * have a completely new n-region in it.
+ */
+ for (n = 1; n <= 9; n++) {
+ dsf_init(dsf, sz);
+
+ /* Build the dsf */
+ for (y = 0; y < h; y++)
+ for (x = 0; x+1 < w; x++)
+ if (bm[y*w+x] & bm[y*w+(x+1)] & (1 << n))
+ dsf_merge(dsf, y*w+x, y*w+(x+1));
+ for (y = 0; y+1 < h; y++)
+ for (x = 0; x < w; x++)
+ if (bm[y*w+x] & bm[(y+1)*w+x] & (1 << n))
+ dsf_merge(dsf, y*w+x, (y+1)*w+x);
+
+ /* Query the dsf */
+ for (i = 0; i < sz; i++)
+ if ((bm[i] & (1 << n)) && dsf_size(dsf, i) < n)
+ bm[i] &= ~(1 << n);
+ }
+#if 0
+ printv("bitmap after winnowing small components:\n");
+ print_bitmap(bm, w, h);
+#endif
+
+ /*
+ * Now our bitmap includes every square which could be part of a
+ * completely new region, of any size. Extend it to include
+ * squares which could be part of an existing region.
+ */
+ for (n = 1; n <= 9; n++) {
+ /*
+ * We're going to do a breadth-first search starting from
+ * existing connected components with cell value n, to find
+ * all cells they might possibly extend into.
+ *
+ * The quantity we compute, for each square, is 'minimum size
+ * that any existing CC would have to have if extended to
+ * include this square'. So squares already _in_ an existing
+ * CC are initialised to the size of that CC; then we search
+ * outwards using the rule that if a square's score is j, then
+ * its neighbours can't score more than j+1.
+ *
+ * Scores are capped at n+1, because if a square scores more
+ * than n then that's enough to know it can't possibly be
+ * reached by extending an existing region - we don't need to
+ * know exactly _how far_ out of reach it is.
+ */
+ for (i = 0; i < sz; i++) {
+ if (s->board[i] == n) {
+ /* Square is part of an existing CC. */
+ minsize[i] = dsf_size(s->dsf, i);
+ } else {
+ /* Otherwise, initialise to the maximum score n+1;
+ * we'll reduce this later if we find a neighbouring
+ * square with a lower score. */
+ minsize[i] = n+1;
+ }
+ }
+
+ for (j = 1; j < n; j++) {
+ /*
+ * Find neighbours of cells scoring j, and set their score
+ * to at most j+1.
+ *
+ * Doing the BFS this way means we need n passes over the
+ * grid, which isn't entirely optimal but it seems to be
+ * fast enough for the moment. This could probably be
+ * improved by keeping a linked-list queue of cells in
+ * some way, but I think you'd have to be a bit careful to
+ * insert things into the right place in the queue; this
+ * way is easier not to get wrong.
+ */
+ for (y = 0; y < h; y++) {
+ for (x = 0; x < w; x++) {
+ i = y*w+x;
+ if (minsize[i] == j) {
+ if (x > 0 && minsize[i-1] > j+1)
+ minsize[i-1] = j+1;
+ if (x+1 < w && minsize[i+1] > j+1)
+ minsize[i+1] = j+1;
+ if (y > 0 && minsize[i-w] > j+1)
+ minsize[i-w] = j+1;
+ if (y+1 < h && minsize[i+w] > j+1)
+ minsize[i+w] = j+1;
+ }
+ }
+ }
+ }
+
+ /*
+ * Now, every cell scoring at most n should have its 1<<n bit
+ * in the bitmap reinstated, because we've found that it's
+ * potentially reachable by extending an existing CC.
+ */
+ for (i = 0; i < sz; i++)
+ if (minsize[i] <= n)
+ bm[i] |= 1<<n;
+ }
+#if 0
+ printv("bitmap after bfs:\n");
+ print_bitmap(bm, w, h);
+#endif
+
+ /*
+ * Now our bitmap is complete. Look for entries with only one bit
+ * set; those are squares with only one possible number, in which
+ * case we can fill that number in.
+ */
+ for (i = 0; i < sz; i++) {
+ if (bm[i] && !(bm[i] & (bm[i]-1))) { /* is bm[i] a power of two? */
+ int val = bm[i];
+
+ /* Integer log2, by simple binary search. */
+ n = 0;
+ if (val >> 8) { val >>= 8; n += 8; }
+ if (val >> 4) { val >>= 4; n += 4; }
+ if (val >> 2) { val >>= 2; n += 2; }
+ if (val >> 1) { val >>= 1; n += 1; }
+
+ /* Double-check that we ended up with a sensible
+ * answer. */
+ assert(1 <= n);
+ assert(n <= 9);
+ assert(bm[i] == (1 << n));
+
+ if (s->board[i] == EMPTY) {
+ printv("learn: %d is only possibility at (%d, %d)\n",
+ n, i % w, i / w);
+ s->board[i] = n;
+ filled_square(s, w, h, i);
+ assert(s->nempty);
+ --s->nempty;
+ learn = TRUE;
+ }
+ }
+ }
+
+ return learn;
+}
+
+static int solver(const int *orig, int w, int h, char **solution) {
+ const int sz = w * h;
+
+ struct solver_state ss;
+ ss.board = memdup(orig, sz, sizeof (int));
+ ss.dsf = snew_dsf(sz); /* eqv classes: connected components */
+ ss.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 */
+ ss.bm = snewn(sz, int);
+ ss.bmdsf = snew_dsf(sz);
+ ss.bmminsize = snewn(sz, int);
+
+ printv("trying to solve this:\n");
+ print_board(ss.board, w, h);
+
+ init_solver_state(&ss, w, h);
+ do {
+ if (learn_blocked_expansion(&ss, w, h)) continue;
+ if (learn_expand_or_one(&ss, w, h)) continue;
+ if (learn_critical_square(&ss, w, h)) continue;
+ if (learn_bitmap_deductions(&ss, w, h)) continue;
+ break;
+ } while (ss.nempty);
+
+ printv("best guess:\n");
+ print_board(ss.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';
+ for (i = 0; i < sz; ++i) (*solution)[i + 1] = ss.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);
+ sfree(ss.dsf);
+ sfree(ss.board);
+ sfree(ss.connected);
+ sfree(ss.bm);
+ sfree(ss.bmdsf);
+ sfree(ss.bmminsize);
- return !nempty;
+ return !ss.nempty;
}
static int *make_dsf(int *dsf, int *board, const int w, const int h) {
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)
+static void minimize_clue_set(int *board, int w, int h, random_state *rs)
{
- 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;
+ int *shuf = snewn(sz, int), i;
+ int *dsf, *next;
+
+ for (i = 0; i < sz; ++i) shuf[i] = i;
+ shuffle(shuf, sz, sizeof (int), rs);
+ /*
+ * First, try to eliminate an entire region at a time if possible,
+ * because inferring the existence of a completely unclued region
+ * is a particularly good aspect of this puzzle type and we want
+ * to encourage it to happen.
+ *
+ * Begin by identifying the regions as linked lists of cells using
+ * the 'next' array.
+ */
+ dsf = make_dsf(NULL, board, w, h);
+ next = snewn(sz, int);
for (i = 0; i < sz; ++i) {
- board[i] = EMPTY;
- randomize[i] = i;
+ int j = dsf_canonify(dsf, i);
+ if (i == j) {
+ /* First cell of a region; set next[i] = -1 to indicate
+ * end-of-list. */
+ next[i] = -1;
+ } else {
+ /* Add this cell to a region which already has a
+ * linked-list head, by pointing the canonical element j
+ * at this one, and pointing this one in turn at wherever
+ * j previously pointed. (This should end up with the
+ * elements linked in the order 1,n,n-1,n-2,...,2, which
+ * is a bit weird-looking, but any order is fine.)
+ */
+ assert(j < i);
+ next[i] = next[j];
+ next[j] = 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]. */
+ /*
+ * Now loop over the grid cells in our shuffled order, and each
+ * time we encounter a region for the first time, try to remove it
+ * all. Then we set next[canonical index] to -2 rather than -1, to
+ * mark it as already tried.
+ *
+ * Doing this in a loop over _cells_, rather than extracting and
+ * shuffling a list of _regions_, is intended to skew the
+ * probabilities towards trying to remove larger regions first
+ * (but without anything as crudely predictable as enforcing that
+ * we _always_ process regions in descending size order). Region
+ * removals might well be mutually exclusive, and larger ghost
+ * regions are more interesting, so we want to bias towards them
+ * if we can.
+ */
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]];
+ int j = dsf_canonify(dsf, shuf[i]);
+ if (next[j] != -2) {
+ int tmp = board[j];
+ int k;
+
+ /* Blank out the whole thing. */
+ for (k = j; k >= 0; k = next[k])
+ board[k] = EMPTY;
+
+ if (!solver(board, w, h, NULL)) {
+ /* Wasn't still solvable; reinstate it all */
+ for (k = j; k >= 0; k = next[k])
+ board[k] = tmp;
+ }
+
+ /* Either way, don't try this region again. */
+ next[j] = -2;
+ }
}
+ sfree(next);
+ sfree(dsf);
+ /*
+ * Now go through individual cells, in the same shuffled order,
+ * and try to remove each one by itself.
+ */
for (i = 0; i < sz; ++i) {
- assert(solver_board[i] >= 0);
- assert(solver_board[i] < 10);
- game_description[i] = solver_board[i] + '0';
+ int tmp = board[shuf[i]];
+ board[shuf[i]] = EMPTY;
+ if (!solver(board, w, h, NULL)) board[shuf[i]] = tmp;
}
- game_description[sz] = '\0';
-/*
- solver(solver_board, w, h, aux);
- print_board(solver_board, w, h);
-*/
+ sfree(shuf);
+}
+
+static int encode_run(char *buffer, int run)
+{
+ int i = 0;
+ for (; run > 26; run -= 26)
+ buffer[i++] = 'z';
+ if (run)
+ buffer[i++] = 'a' - 1 + run;
+ return i;
+}
+
+static char *new_game_desc(const game_params *params, random_state *rs,
+ char **aux, int interactive)
+{
+ const int w = params->w, h = params->h, sz = w * h;
+ int *board = snewn(sz, int), i, j, run;
+ char *description = snewn(sz + 1, char);
+
+ make_board(board, w, h, rs);
+ minimize_clue_set(board, w, h, rs);
+
+ for (run = j = i = 0; i < sz; ++i) {
+ assert(board[i] >= 0);
+ assert(board[i] < 10);
+ if (board[i] == 0) {
+ ++run;
+ } else {
+ j += encode_run(description + j, run);
+ run = 0;
+ description[j++] = board[i] + '0';
+ }
+ }
+ j += encode_run(description + j, run);
+ description[j++] = '\0';
- sfree(randomize);
- sfree(solver_board);
sfree(board);
- return game_description;
+ return sresize(description, j, char);
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const 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;
+ int area;
+
+ for (area = 0; *desc; ++desc) {
+ if (*desc >= 'a' && *desc <= 'z') area += *desc - 'a' + 1;
+ else if (*desc >= '0' && *desc <= m) ++area;
+ else {
+ static char s[] = "Invalid character '%""' in game description";
+ int n = sprintf(s, "Invalid character '%1c' in game description",
+ *desc);
+ assert(n + 1 <= lenof(s)); /* +1 for the terminating NUL */
+ return s;
+ }
+ if (area > sz) return "Too much data to fit in grid";
+ }
+ return (area < sz) ? "Not enough data to fill grid" : NULL;
}
-static game_state *new_game(midend *me, game_params *params, char *desc)
+static game_state *new_game(midend *me, const game_params *params,
+ const char *desc)
{
game_state *state = snew(game_state);
int sz = params->w * params->h;
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';
+
+ for (i = 0; *desc; ++desc) {
+ if (*desc >= 'a' && *desc <= 'z') {
+ int j = *desc - 'a' + 1;
+ assert(i + j <= sz);
+ for (; j; --j) state->shared->clues[i++] = 0;
+ } else state->shared->clues[i++] = *desc - '0';
+ }
state->board = memdup(state->shared->clues, sz, sizeof (int));
return state;
}
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
const int sz = state->shared->params.w * state->shared->params.h;
game_state *ret = snew(game_state);
sfree(state);
}
-static char *solve_game(game_state *state, game_state *currstate,
- char *aux, char **error)
+static char *solve_game(const game_state *state, const game_state *currstate,
+ const 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))
+ char *new_aux;
+ if (!solver(state->board, w, h, &new_aux))
*error = "Sorry, I couldn't find a solution";
+ return new_aux;
}
- return aux;
+ return dupstr(aux);
}
/*****************************************************************************
*****************************************************************************/
struct game_ui {
- int x, y; /* highlighted square, or (-1, -1) if none */
+ int *sel; /* w*h highlighted squares, or NULL */
+ int cur_x, cur_y, cur_visible, keydragging;
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
game_ui *ui = snew(game_ui);
- ui->x = ui->y = -1;
+ ui->sel = NULL;
+ ui->cur_x = ui->cur_y = ui->cur_visible = ui->keydragging = 0;
return ui;
}
static void free_ui(game_ui *ui)
{
+ if (ui->sel)
+ sfree(ui->sel);
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
}
-static void game_changed_state(game_ui *ui, game_state *oldstate,
- game_state *newstate)
+static void game_changed_state(game_ui *ui, const game_state *oldstate,
+ const game_state *newstate)
{
+ /* Clear any selection */
+ if (ui->sel) {
+ sfree(ui->sel);
+ ui->sel = NULL;
+ }
+ ui->keydragging = FALSE;
}
#define PREFERRED_TILE_SIZE 32
#define TILE_SIZE (ds->tilesize)
#define BORDER (TILE_SIZE / 2)
-#define BORDER_WIDTH (TILE_SIZE / 32)
+#define BORDER_WIDTH (max(TILE_SIZE / 32, 1))
struct game_drawstate {
struct game_params params;
int *dsf_scratch, *border_scratch;
};
-static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+static char *interpret_move(const game_state *state, game_ui *ui,
+ const game_drawstate *ds,
int x, int y, int button)
{
const int w = state->shared->params.w;
const int tx = (x + TILE_SIZE - BORDER) / TILE_SIZE - 1;
const int ty = (y + TILE_SIZE - BORDER) / TILE_SIZE - 1;
+ char *move = NULL;
+ int i;
+
assert(ui);
assert(ds);
button &= ~MOD_MASK;
- if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
+ if (button == LEFT_BUTTON || button == LEFT_DRAG) {
+ /* A left-click anywhere will clear the current selection. */
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 */
+ if (ui->sel) {
+ sfree(ui->sel);
+ ui->sel = NULL;
+ }
}
+ if (tx >= 0 && tx < w && ty >= 0 && ty < h) {
+ if (!ui->sel) {
+ ui->sel = snewn(w*h, int);
+ memset(ui->sel, 0, w*h*sizeof(int));
+ }
+ if (!state->shared->clues[w*ty+tx])
+ ui->sel[w*ty+tx] = 1;
+ }
+ ui->cur_visible = 0;
+ 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;
+ if (IS_CURSOR_MOVE(button)) {
+ ui->cur_visible = 1;
+ move_cursor(button, &ui->cur_x, &ui->cur_y, w, h, 0);
+ if (ui->keydragging) goto select_square;
+ return "";
}
+ if (button == CURSOR_SELECT) {
+ if (!ui->cur_visible) {
+ ui->cur_visible = 1;
+ return "";
+ }
+ ui->keydragging = !ui->keydragging;
+ if (!ui->keydragging) return "";
- {
- const int i = w*ui->y + ui->x;
- char buf[64];
- ui->x = ui->y = -1;
- if (state->board[i] == button) {
- return ""; /* no change - just update ui */
- } else {
- sprintf(buf, "%d_%d", i, button);
- return dupstr(buf);
+ select_square:
+ if (!ui->sel) {
+ ui->sel = snewn(w*h, int);
+ memset(ui->sel, 0, w*h*sizeof(int));
+ }
+ if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
+ ui->sel[w*ui->cur_y + ui->cur_x] = 1;
+ return "";
+ }
+ if (button == CURSOR_SELECT2) {
+ if (!ui->cur_visible) {
+ ui->cur_visible = 1;
+ return "";
+ }
+ if (!ui->sel) {
+ ui->sel = snewn(w*h, int);
+ memset(ui->sel, 0, w*h*sizeof(int));
+ }
+ ui->keydragging = FALSE;
+ if (!state->shared->clues[w*ui->cur_y + ui->cur_x])
+ ui->sel[w*ui->cur_y + ui->cur_x] ^= 1;
+ for (i = 0; i < w*h && !ui->sel[i]; i++);
+ if (i == w*h) {
+ sfree(ui->sel);
+ ui->sel = NULL;
}
+ return "";
}
+
+ if (button == '\b' || button == 27) {
+ sfree(ui->sel);
+ ui->sel = NULL;
+ ui->keydragging = FALSE;
+ return "";
+ }
+
+ if (button < '0' || button > '9') return NULL;
+ button -= '0';
+ if (button > (w == 2 && h == 2 ? 3 : max(w, h))) return NULL;
+ ui->keydragging = FALSE;
+
+ for (i = 0; i < w*h; i++) {
+ char buf[32];
+ if ((ui->sel && ui->sel[i]) ||
+ (!ui->sel && ui->cur_visible && (w*ui->cur_y+ui->cur_x) == i)) {
+ if (state->shared->clues[i] != 0) continue; /* in case cursor is on clue */
+ if (state->board[i] != button) {
+ sprintf(buf, "%s%d", move ? "," : "", i);
+ if (move) {
+ move = srealloc(move, strlen(move)+strlen(buf)+1);
+ strcat(move, buf);
+ } else {
+ move = smalloc(strlen(buf)+1);
+ strcpy(move, buf);
+ }
+ }
+ }
+ }
+ if (move) {
+ char buf[32];
+ sprintf(buf, "_%d", button);
+ move = srealloc(move, strlen(move)+strlen(buf)+1);
+ strcat(move, buf);
+ }
+ if (!ui->sel) return move ? move : NULL;
+ sfree(ui->sel);
+ ui->sel = NULL;
+ /* Need to update UI at least, as we cleared the selection */
+ return move ? move : "";
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
- game_state *new_state;
+ game_state *new_state = NULL;
+ const int sz = state->shared->params.w * state->shared->params.h;
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;
+ char *endptr, *delim = strchr(move, '_');
+ if (!delim) goto err;
+ value = strtol(delim+1, &endptr, 0);
+ if (*endptr || endptr == delim+1) goto err;
+ if (value < 0 || value > 9) goto err;
new_state = dup_game(state);
- new_state->board[i] = value;
+ while (*move) {
+ const int i = strtol(move, &endptr, 0);
+ if (endptr == move) goto err;
+ if (i < 0 || i >= sz) goto err;
+ new_state->board[i] = value;
+ if (*endptr == '_') break;
+ if (*endptr != ',') goto err;
+ move = endptr + 1;
+ }
}
/*
}
return new_state;
+
+err:
+ if (new_state) free_game(new_state);
+ return NULL;
}
/* ----------------------------------------------------------------------
COL_CORRECT,
COL_ERROR,
COL_USER,
+ COL_CURSOR,
NCOLOURS
};
-static void game_compute_size(game_params *params, int tilesize,
+static void game_compute_size(const game_params *params, int tilesize,
int *x, int *y)
{
*x = (params->w + 1) * tilesize;
}
static void game_set_size(drawing *dr, game_drawstate *ds,
- game_params *params, int tilesize)
+ const game_params *params, int tilesize)
{
ds->tilesize = tilesize;
}
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_CURSOR * 3 + 0] = 0.5F * ret[COL_BACKGROUND * 3 + 0];
+ ret[COL_CURSOR * 3 + 1] = 0.5F * ret[COL_BACKGROUND * 3 + 1];
+ ret[COL_CURSOR * 3 + 2] = 0.5F * 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];
return ret;
}
-static game_drawstate *game_new_drawstate(drawing *dr, game_state *state)
+static game_drawstate *game_new_drawstate(drawing *dr, const game_state *state)
{
struct game_drawstate *ds = snew(struct game_drawstate);
int i;
#define BORDER_DR 0x020
#define BORDER_UL 0x040
#define BORDER_DL 0x080
-#define CURSOR_BG 0x100
+#define HIGH_BG 0x100
#define CORRECT_BG 0x200
#define ERROR_BG 0x400
#define USER_COL 0x800
+#define CURSOR_SQ 0x1000
static void draw_square(drawing *dr, game_drawstate *ds, int x, int y,
int n, int flags)
BORDER + y*TILE_SIZE,
TILE_SIZE,
TILE_SIZE,
- (flags & CURSOR_BG ? COL_HIGHLIGHT :
+ (flags & HIGH_BG ? COL_HIGHLIGHT :
flags & ERROR_BG ? COL_ERROR :
flags & CORRECT_BG ? COL_CORRECT : COL_BACKGROUND));
BORDER_WIDTH,
COL_GRID);
+ if (flags & CURSOR_SQ) {
+ int coff = TILE_SIZE/8;
+ draw_rect_outline(dr,
+ BORDER + x*TILE_SIZE + coff,
+ BORDER + y*TILE_SIZE + coff,
+ TILE_SIZE - coff*2,
+ TILE_SIZE - coff*2,
+ COL_CURSOR);
+ }
+
unclip(dr);
draw_update(dr,
TILE_SIZE);
}
-static void draw_grid(drawing *dr, game_drawstate *ds, game_state *state,
- game_ui *ui, int flashy, int borders, int shading)
+static void draw_grid(drawing *dr, game_drawstate *ds, const game_state *state,
+ const game_ui *ui, int flashy, int borders, int shading)
{
const int w = state->shared->params.w;
const int h = state->shared->params.h;
/*
* Determine what we need to draw in this square.
*/
- int v = state->board[y*w+x];
+ int i = y*w+x, v = state->board[i];
int flags = 0;
if (flashy || !shading) {
/* clear all background flags */
- } else if (x == ui->x && y == ui->y) {
- flags |= CURSOR_BG;
+ } else if (ui && ui->sel && ui->sel[i]) {
+ flags |= HIGH_BG;
} else if (v) {
- int size = dsf_size(ds->dsf_scratch, y*w+x);
+ int size = dsf_size(ds->dsf_scratch, i);
if (size == v)
flags |= CORRECT_BG;
else if (size > v)
flags |= ERROR_BG;
+ else {
+ int rt = dsf_canonify(ds->dsf_scratch, i), j;
+ for (j = 0; j < w*h; ++j) {
+ int k;
+ if (dsf_canonify(ds->dsf_scratch, j) != rt) continue;
+ for (k = 0; k < 4; ++k) {
+ const int xx = j % w + dx[k], yy = j / w + dy[k];
+ if (xx >= 0 && xx < w && yy >= 0 && yy < h &&
+ state->board[yy*w + xx] == EMPTY)
+ goto noflag;
+ }
+ }
+ flags |= ERROR_BG;
+ noflag:
+ ;
+ }
}
+ if (ui && ui->cur_visible && x == ui->cur_x && y == ui->cur_y)
+ flags |= CURSOR_SQ;
/*
* Borders at the very edges of the grid are
}
}
-static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
+static void game_redraw(drawing *dr, game_drawstate *ds,
+ const game_state *oldstate, const game_state *state,
+ int dir, const game_ui *ui,
float animtime, float flashtime)
{
const int w = state->shared->params.w;
* 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);
+ draw_rect(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER,
+ COL_BACKGROUND);
/*
* Smaller black rectangle which is the main grid.
h*TILE_SIZE + 2*BORDER_WIDTH + 1,
COL_GRID);
+ draw_update(dr, 0, 0, w*TILE_SIZE + 2*BORDER, h*TILE_SIZE + 2*BORDER);
+
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)
+static float game_anim_length(const game_state *oldstate,
+ const 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)
+static float game_flash_length(const game_state *oldstate,
+ const game_state *newstate, int dir, game_ui *ui)
{
assert(oldstate);
assert(newstate);
return 0.0F;
}
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_status(const game_state *state)
+{
+ return state->completed ? +1 : 0;
+}
+
+static int game_timing_state(const game_state *state, game_ui *ui)
{
return TRUE;
}
-static void game_print_size(game_params *params, float *x, float *y)
+static void game_print_size(const 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;
+ *x = pw / 100.0F;
+ *y = ph / 100.0F;
}
-static void game_print(drawing *dr, game_state *state, int tilesize)
+static void game_print(drawing *dr, const game_state *state, int tilesize)
{
const int w = state->shared->params.w;
const int h = state->shared->params.h;
dup_game,
free_game,
TRUE, solve_game,
- TRUE, game_text_format,
+ TRUE, game_can_format_as_text_now, game_text_format,
new_ui,
free_ui,
encode_ui,
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
FALSE, /* wants_statusbar */
FALSE, game_timing_state,
- 0, /* flags */
+ REQUIRE_NUMPAD, /* flags */
};
#ifdef STANDALONE_SOLVER /* solver? hah! */
}
#endif
+
+/* vim: set shiftwidth=4 tabstop=8: */
~ian / sgt-puzzles.git / blobdiff