* cell. Then n must equal h + v - 1.
*/
-/* example instance with its encoding:
+/* example instance with its encoding and textual representation, both
+ * solved and unsolved (made by thegame.solve and thegame.text_format)
*
* +--+--+--+--+--+--+--+
* | | | | | 7| | |
* +--+--+--+--+--+--+--+
*
* 7x7:d7b3e8e5c7a7c13e4d8b4d
+ *
+ * +--+--+--+--+--+--+--+
+ * |..|..|..|..| 7|..|..|
+ * +--+--+--+--+--+--+--+
+ * | 3|..|##|..|##|..| 8|
+ * +--+--+--+--+--+--+--+
+ * |##|..|..|##|..| 5|..|
+ * +--+--+--+--+--+--+--+
+ * |..|..| 7|..| 7|##|..|
+ * +--+--+--+--+--+--+--+
+ * |..|13|..|..|..|..|..|
+ * +--+--+--+--+--+--+--+
+ * | 4|..|##|..|##|..| 8|
+ * +--+--+--+--+--+--+--+
+ * |##|..| 4|..|..|##|..|
+ * +--+--+--+--+--+--+--+
*/
#include <stdio.h>
#define setmember(obj, field) ( (obj) . field = field )
-char *nfmtstr(int n, char *fmt, ...) {
+static char *nfmtstr(int n, char *fmt, ...) {
va_list va;
char *ret = snewn(n+1, char);
va_start(va, fmt);
};
#define DEFAULT_PRESET 0
-static struct game_params presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}};
+static struct game_params range_presets[] = {{9, 6}, {12, 8}, {13, 9}, {16, 11}};
/* rationale: I want all four combinations of {odd/even, odd/even}, as
* they play out differently with respect to two-way symmetry. I also
* want them to be generated relatively fast yet still be large enough
static game_params *default_params(void)
{
game_params *ret = snew(game_params);
- *ret = presets[DEFAULT_PRESET]; /* structure copy */
+ *ret = range_presets[DEFAULT_PRESET]; /* structure copy */
return ret;
}
-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; /* structure copy */
static int game_fetch_preset(int i, char **name, game_params **params)
{
- if (i < 0 || i >= lenof(presets)) return FALSE;
+ game_params *ret;
+
+ if (i < 0 || i >= lenof(range_presets)) return FALSE;
- *name = nfmtstr(40, "%d x %d", presets[i].w, presets[i].h);
- *params = dup_params(&presets[i]);
+ ret = default_params();
+ *ret = range_presets[i]; /* struct copy */
+ *params = ret;
+
+ *name = nfmtstr(40, "%d x %d", range_presets[i].w, range_presets[i].h);
return TRUE;
}
}
}
-static char *encode_params(game_params *params, int full)
+static char *encode_params(const game_params *params, int full)
{
char str[80];
sprintf(str, "%dx%d", params->w, params->h);
return dupstr(str);
}
-static config_item *game_configure(game_params *params)
+static config_item *game_configure(const game_params *params)
{
config_item *ret;
return ret;
}
-static game_params *custom_params(config_item *configuration)
+static game_params *custom_params(const config_item *configuration)
{
game_params *ret = snew(game_params);
ret->w = atoi(configuration[0].sval);
memcpy(dst, src, n * sizeof (type)); \
} while (0)
-static game_state *dup_game(game_state *state)
+static game_state *dup_game(const game_state *state)
{
game_state *ret = snew(game_state);
int const n = state->params.w * state->params.h;
DIFF_RECURSION
};
-static move *solve_internal(game_state *state, move *base, int diff);
+static move *solve_internal(const game_state *state, move *base, int diff);
-static char *solve_game(game_state *orig, game_state *curpos,
- char *aux, char **error)
+static char *solve_game(const game_state *orig, const game_state *curpos,
+ const char *aux, char **error)
{
int const n = orig->params.w * orig->params.h;
move *const base = snewn(n, move);
return ret;
}
-static square *find_clues(game_state *state, int *ret_nclues);
+static square *find_clues(const game_state *state, int *ret_nclues);
static move *do_solve(game_state *state,
int nclues,
const square *clues,
int difficulty);
/* new_game_desc entry point in the solver subsystem */
-static move *solve_internal(game_state *state, move *base, int diff)
+static move *solve_internal(const game_state *state, move *base, int diff)
{
int nclues;
square *const clues = find_clues(state, &nclues);
return moves;
}
+static reasoning *const reasonings[] = {
+ solver_reasoning_not_too_big,
+ solver_reasoning_adjacency,
+ solver_reasoning_connectedness,
+ solver_reasoning_recursion
+};
+
static move *do_solve(game_state *state,
int nclues,
const square *clues,
move *move_buffer,
int difficulty)
{
- reasoning *reasonings[] = {
- solver_reasoning_not_too_big,
- solver_reasoning_adjacency,
- solver_reasoning_connectedness,
- solver_reasoning_recursion
- };
-
struct move *buf = move_buffer, *oldbuf;
int i;
static int runlength(puzzle_size r, puzzle_size c,
puzzle_size dr, puzzle_size dc,
- game_state *state, int colourmask)
+ const game_state *state, int colourmask)
{
int const w = state->params.w, h = state->params.h;
int sz = 0;
return buf;
}
-static square *find_clues(game_state *state, int *ret_nclues)
+static square *find_clues(const game_state *state, int *ret_nclues)
{
int r, c, i, nclues = 0;
square *ret = snewn(state->params.w * state->params.h, struct square);
static int newdesc_strip_clues(game_state *state, int *shuffle_1toN);
static char *newdesc_encode_game_description(int n, puzzle_size *grid);
-static char *new_game_desc(game_params *params, random_state *rs,
+static char *new_game_desc(const game_params *params, random_state *rs,
char **aux, int interactive)
{
int const w = params->w, h = params->h, n = w * h;
return k;
}
-static char *validate_params(game_params *params, int full)
+static char *validate_params(const game_params *params, int full)
{
int const w = params->w, h = params->h;
if (w < 1) return "Error: width is less than 1";
return desc;
}
-static char *validate_desc(game_params *params, char *desc)
+static char *validate_desc(const game_params *params, const char *desc)
{
int const n = params->w * params->h;
int squares = 0;
return 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)
{
int i;
- char *p;
+ const char *p;
int const n = params->w * params->h;
game_state *state = snew(game_state);
* User interface: ascii
*/
-static int game_can_format_as_text_now(game_params *params)
+static int game_can_format_as_text_now(const game_params *params)
{
return TRUE;
}
-static char *game_text_format(game_state *state)
+static char *game_text_format(const game_state *state)
{
int cellsize, r, c, i, w_string, h_string, n_string;
char *ret, *buf, *gridline;
cellsize = 0; /* or may be used uninitialized */
for (c = 0; c < w; ++c) {
- for (r = 1; r < h; ++r) {
+ for (r = 0; r < h; ++r) {
puzzle_size k = state->grid[idx(r, c, w)];
int d;
for (d = 0; k; k /= 10, ++d);
struct game_ui {
puzzle_size r, c; /* cursor position */
unsigned int cursor_show: 1;
- unsigned int cheated: 1;
};
-static game_ui *new_ui(game_state *state)
+static game_ui *new_ui(const game_state *state)
{
struct game_ui *ui = snew(game_ui);
ui->r = ui->c = 0;
- ui->cursor_show = ui->cheated = FALSE;
+ ui->cursor_show = FALSE;
return ui;
}
sfree(ui);
}
-static char *encode_ui(game_ui *ui)
+static char *encode_ui(const game_ui *ui)
{
- return dupstr(ui->cheated ? "1" : "0");
+ return NULL;
}
-static void decode_ui(game_ui *ui, char *encoding)
+static void decode_ui(game_ui *ui, const char *encoding)
{
- ui->cheated = (*encoding == '1');
}
typedef struct drawcell {
#define COORD(x) ((x) * TILESIZE + BORDER)
#define FROMCOORD(x) (((x) - BORDER) / TILESIZE)
-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)
{
enum {none, forwards, backwards, hint};
int const w = state->params.w, h = state->params.h;
int r = ui->r, c = ui->c, action = none, cell;
+ int shift = button & MOD_SHFT;
+ button &= ~shift;
if (IS_CURSOR_SELECT(button) && !ui->cursor_show) return NULL;
int i;
for (i = 0; i < 4 && cursors[i] != button; ++i);
assert (i < 4);
- if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
+ if (shift) {
+ int pre_r = r, pre_c = c, do_pre, do_post;
+ cell = state->grid[idx(r, c, state->params.w)];
+ do_pre = (cell == EMPTY);
+
+ if (out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
+ if (do_pre)
+ return nfmtstr(40, "W,%d,%d", pre_r, pre_c);
+ else
+ return NULL;
+ }
+
+ ui->r += dr[i];
+ ui->c += dc[i];
+
+ cell = state->grid[idx(ui->r, ui->c, state->params.w)];
+ do_post = (cell == EMPTY);
+
+ /* (do_pre ? "..." : "") concat (do_post ? "..." : "") */
+ if (do_pre && do_post)
+ return nfmtstr(80, "W,%d,%dW,%d,%d",
+ pre_r, pre_c, ui->r, ui->c);
+ else if (do_pre)
+ return nfmtstr(40, "W,%d,%d", pre_r, pre_c);
+ else if (do_post)
+ return nfmtstr(40, "W,%d,%d", ui->r, ui->c);
+ else
+ return "";
+
+ } else if (!out_of_bounds(ui->r + dr[i], ui->c + dc[i], w, h)) {
ui->r += dr[i];
ui->c += dc[i];
}
ret = nfmtstr(40, "%c,%d,%d",
buf->colour == M_BLACK ? 'B' : 'W',
buf->square.r, buf->square.c);
- ui->cheated = TRUE; /* you are being naughty ;-) */
+ /* We used to set a flag here in the game_ui indicating
+ * that the player had used the hint function. I (SGT)
+ * retired it, on grounds of consistency with other games
+ * (most of these games will still flash to indicate
+ * completion if you solved and undid it, so why not if
+ * you got a hint?) and because the flash is as much about
+ * checking you got it all right than about congratulating
+ * you on a job well done. */
}
sfree(buf);
return ret;
return NULL;
}
-static int find_errors(game_state *state, int *report)
+static int find_errors(const game_state *state, int *report)
{
int const w = state->params.w, h = state->params.h, n = w * h;
+ int *dsf;
int r, c, i;
}
}
- for (i = 0; i < n; ++i) if (dup->grid[i] != BLACK) dup->grid[i] = WHITE;
- if (nblack + dfs_count_white(dup, any_white_cell) < n) {
+ /*
+ * Check that all the white cells form a single connected component.
+ */
+ dsf = snew_dsf(n);
+ for (r = 0; r < h-1; ++r)
+ for (c = 0; c < w; ++c)
+ if (state->grid[r*w+c] != BLACK &&
+ state->grid[(r+1)*w+c] != BLACK)
+ dsf_merge(dsf, r*w+c, (r+1)*w+c);
+ for (r = 0; r < h; ++r)
+ for (c = 0; c < w-1; ++c)
+ if (state->grid[r*w+c] != BLACK &&
+ state->grid[r*w+(c+1)] != BLACK)
+ dsf_merge(dsf, r*w+c, r*w+(c+1));
+ if (nblack + dsf_size(dsf, any_white_cell) < n) {
+ int biggest, canonical;
+
if (!report) {
- printf("dfs fail at %d\n", any_white_cell);
+ sfree(dsf);
goto found_error;
}
- for (i = 0; i < n; ++i) if (state->grid[i] != BLACK) report[i] = TRUE;
+
+ /*
+ * Report this error by choosing one component to be the
+ * canonical one (we pick the largest, arbitrarily
+ * tie-breaking towards lower array indices) and highlighting
+ * as an error any square in a different component.
+ */
+ canonical = -1;
+ biggest = 0;
+ for (i = 0; i < n; ++i)
+ if (state->grid[i] != BLACK) {
+ int size = dsf_size(dsf, i);
+ if (size > biggest) {
+ biggest = size;
+ canonical = dsf_canonify(dsf, i);
+ }
+ }
+
+ for (i = 0; i < n; ++i)
+ if (state->grid[i] != BLACK && dsf_canonify(dsf, i) != canonical)
+ report[i] = TRUE;
}
+ sfree(dsf);
free_game(dup);
return FALSE; /* if report != NULL, this is ignored */
return TRUE;
}
-static game_state *execute_move(game_state *state, char *move)
+static game_state *execute_move(const game_state *state, const char *move)
{
signed int r, c, value, nchars, ntok;
signed char what_to_do;
return NULL;
}
-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)
{
- if (newstate->has_cheated) ui->cheated = 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;
}
#define FLASH_TIME 0.7F
-static float game_flash_length(game_state *from, game_state *to,
- int dir, game_ui *ui)
+static float game_flash_length(const game_state *from,
+ const game_state *to, int dir, game_ui *ui)
{
- if (!from->was_solved && to->was_solved && !ui->cheated)
+ if (!from->was_solved && to->was_solved && !to->has_cheated)
return FLASH_TIME;
return 0.0F;
}
+static int game_status(const game_state *state)
+{
+ return state->was_solved ? +1 : 0;
+}
+
/* ----------------------------------------------------------------------
* Drawing routines.
*/
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 = (1 + params->w) * 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;
}
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)
{
int const w = state->params.w, h = state->params.h, n = w * h;
struct game_drawstate *ds = snew(struct game_drawstate);
static void draw_cell(drawing *dr, game_drawstate *ds, int r, int c,
drawcell cell);
-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)
{
int const w = state->params.w, h = state->params.h, n = w * h;
if (!ds->started) {
ds->started = TRUE;
draw_rect(dr, 0, 0, wpx, hpx, COL_BACKGROUND);
- draw_rect(dr, BORDER-1, BORDER-1,
- ds->tilesize*w+2, ds->tilesize*h+2, COL_GRID);
draw_update(dr, 0, 0, wpx, hpx);
}
cell.flash || cell.cursor ?
COL_LOWLIGHT : COL_BACKGROUND);
- draw_rect (draw, x, y, ts, ts, colour);
- draw_rect_outline(draw, x, y, ts, ts, COL_GRID);
+ draw_rect_outline(draw, x, y, ts + 1, ts + 1, COL_GRID);
+ draw_rect (draw, x + 1, y + 1, ts - 1, ts - 1, colour);
+ if (cell.error)
+ draw_rect_outline(draw, x + 1, y + 1, ts - 1, ts - 1, COL_ERROR);
switch (cell.value) {
case WHITE: draw_rect(draw, tx - dotsz / 2, ty - dotsz / 2, dotsz, dotsz,
cell.error ? COL_ERROR : COL_USER);
- case BLACK: break;
- case EMPTY:
- if (cell.error)
- draw_circle(draw, tx, ty, dotsz / 2, COL_ERROR, COL_GRID);
- break;
+ case BLACK: case EMPTY: break;
default:
{
int const colour = (cell.error ? COL_ERROR : COL_GRID);
}
}
- draw_update(draw, x, y, ts, ts);
+ draw_update(draw, x, y, ts + 1, ts + 1);
}
-static int game_timing_state(game_state *state, game_ui *ui)
+static int game_timing_state(const game_state *state, game_ui *ui)
{
puts("warning: game_timing_state was called (this shouldn't happen)");
return FALSE; /* the (non-existing) timer should not be running */
* User interface: print
*/
-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 print_width, print_height;
game_compute_size(params, 800, &print_width, &print_height);
*y = print_height / 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)
{
int const w = state->params.w, h = state->params.h;
game_drawstate ds_obj, *ds = &ds_obj;
game_redraw,
game_anim_length,
game_flash_length,
+ game_status,
TRUE, FALSE, game_print_size, game_print,
FALSE, /* wants_statusbar */
FALSE, game_timing_state,
~ian / sgt-puzzles.git / blobdiff