/*
* pattern.c: the pattern-reconstruction game known as `nonograms'.
- *
- * TODO before checkin:
- *
- * - make some sort of stab at number-of-numbers judgment
*/
#include <stdio.h>
#include "puzzles.h"
-#define max(x,y) ( (x)>(y) ? (x):(y) )
-#define min(x,y) ( (x)<(y) ? (x):(y) )
-
enum {
COL_BACKGROUND,
COL_EMPTY,
NCOLOURS
};
-#define BORDER 18
+#define PREFERRED_TILE_SIZE 24
+#define TILE_SIZE (ds->tilesize)
+#define BORDER (3 * TILE_SIZE / 4)
#define TLBORDER(d) ( (d) / 5 + 2 )
-#define GUTTER 12
-#define TILE_SIZE 24
+#define GUTTER (TILE_SIZE / 2)
#define FROMCOORD(d, x) \
( ((x) - (BORDER + GUTTER + TILE_SIZE * TLBORDER(d))) / TILE_SIZE )
#define SIZE(d) (2*BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (d)))
+#define GETTILESIZE(d, w) ((double)w / (2.0 + (double)TLBORDER(d) + (double)(d)))
#define TOCOORD(d, x) (BORDER + GUTTER + TILE_SIZE * (TLBORDER(d) + (x)))
unsigned char *grid;
int rowsize;
int *rowdata, *rowlen;
- int completed;
+ int completed, cheated;
};
#define FLASH_TIME 0.13F
return ret;
}
+static const struct game_params pattern_presets[] = {
+ {10, 10},
+ {15, 15},
+ {20, 20},
+#ifndef SLOW_SYSTEM
+ {25, 25},
+ {30, 30},
+#endif
+};
+
static int game_fetch_preset(int i, char **name, game_params **params)
{
game_params *ret;
char str[80];
- static const struct { int x, y; } values[] = {
- {10, 10},
- {15, 15},
- {20, 20},
- {25, 25},
- {30, 30},
- };
-
- if (i < 0 || i >= lenof(values))
+
+ if (i < 0 || i >= lenof(pattern_presets))
return FALSE;
ret = snew(game_params);
- ret->w = values[i].x;
- ret->h = values[i].y;
+ *ret = pattern_presets[i];
sprintf(str, "%dx%d", ret->w, ret->h);
return ret;
}
-static game_params *decode_params(char const *string)
+static void decode_params(game_params *ret, char const *string)
{
- game_params *ret = default_params();
char const *p = string;
ret->w = atoi(p);
} else {
ret->h = ret->w;
}
-
- return ret;
}
-static char *encode_params(game_params *params)
+static char *encode_params(game_params *params, int full)
{
char ret[400];
int len;
static char *validate_params(game_params *params)
{
- if (params->w <= 0 && params->h <= 0)
+ if (params->w <= 0 || params->h <= 0)
return "Width and height must both be greater than zero";
- if (params->w <= 0)
- return "Width must be greater than zero";
- if (params->h <= 0)
- return "Height must be greater than zero";
return NULL;
}
generate(rs, w, h, grid);
+ /*
+ * The game is a bit too easy if any row or column is
+ * completely black or completely white. An exception is
+ * made for rows/columns that are under 3 squares,
+ * otherwise nothing will ever be successfully generated.
+ */
+ ok = TRUE;
+ if (w > 2) {
+ for (i = 0; i < h; i++) {
+ int colours = 0;
+ for (j = 0; j < w; j++)
+ colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
+ if (colours != 3)
+ ok = FALSE;
+ }
+ }
+ if (h > 2) {
+ for (j = 0; j < w; j++) {
+ int colours = 0;
+ for (i = 0; i < h; i++)
+ colours |= (grid[i*w+j] == GRID_FULL ? 2 : 1);
+ if (colours != 3)
+ ok = FALSE;
+ }
+ }
+ if (!ok)
+ continue;
+
memset(matrix, 0, w*h);
do {
return grid;
}
-static char *new_game_seed(game_params *params, random_state *rs)
+static char *new_game_desc(game_params *params, random_state *rs,
+ char **aux, int interactive)
{
unsigned char *grid;
int i, j, max, rowlen, *rowdata;
- char intbuf[80], *seed;
- int seedlen, seedpos;
+ char intbuf[80], *desc;
+ int desclen, descpos;
grid = generate_soluble(rs, params->w, params->h);
max = max(params->w, params->h);
rowdata = snewn(max, int);
/*
+ * Save the solved game in aux.
+ */
+ {
+ char *ai = snewn(params->w * params->h + 2, char);
+
+ /*
+ * String format is exactly the same as a solve move, so we
+ * can just dupstr this in solve_game().
+ */
+
+ ai[0] = 'S';
+
+ for (i = 0; i < params->w * params->h; i++)
+ ai[i+1] = grid[i] ? '1' : '0';
+
+ ai[params->w * params->h + 1] = '\0';
+
+ *aux = ai;
+ }
+
+ /*
* Seed is a slash-separated list of row contents; each row
* contents section is a dot-separated list of integers. Row
* contents are listed in the order (columns left to right,
* passes, first computing the seed size and then writing it
* out.
*/
- seedlen = 0;
+ desclen = 0;
for (i = 0; i < params->w + params->h; i++) {
if (i < params->w)
rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
params->w, 1);
if (rowlen > 0) {
for (j = 0; j < rowlen; j++) {
- seedlen += 1 + sprintf(intbuf, "%d", rowdata[j]);
+ desclen += 1 + sprintf(intbuf, "%d", rowdata[j]);
}
} else {
- seedlen++;
+ desclen++;
}
}
- seed = snewn(seedlen, char);
- seedpos = 0;
+ desc = snewn(desclen, char);
+ descpos = 0;
for (i = 0; i < params->w + params->h; i++) {
if (i < params->w)
rowlen = compute_rowdata(rowdata, grid+i, params->h, params->w);
params->w, 1);
if (rowlen > 0) {
for (j = 0; j < rowlen; j++) {
- int len = sprintf(seed+seedpos, "%d", rowdata[j]);
+ int len = sprintf(desc+descpos, "%d", rowdata[j]);
if (j+1 < rowlen)
- seed[seedpos + len] = '.';
+ desc[descpos + len] = '.';
else
- seed[seedpos + len] = '/';
- seedpos += len+1;
+ desc[descpos + len] = '/';
+ descpos += len+1;
}
} else {
- seed[seedpos++] = '/';
+ desc[descpos++] = '/';
}
}
- assert(seedpos == seedlen);
- assert(seed[seedlen-1] == '/');
- seed[seedlen-1] = '\0';
+ assert(descpos == desclen);
+ assert(desc[desclen-1] == '/');
+ desc[desclen-1] = '\0';
sfree(rowdata);
- return seed;
+ sfree(grid);
+ return desc;
}
-static char *validate_seed(game_params *params, char *seed)
+static char *validate_desc(game_params *params, char *desc)
{
int i, n, rowspace;
char *p;
else
rowspace = params->w + 1;
- if (*seed && isdigit((unsigned char)*seed)) {
+ if (*desc && isdigit((unsigned char)*desc)) {
do {
- p = seed;
- while (seed && isdigit((unsigned char)*seed)) seed++;
+ p = desc;
+ while (desc && isdigit((unsigned char)*desc)) desc++;
n = atoi(p);
rowspace -= n+1;
else
return "at least one row contains more numbers than will fit";
}
- } while (*seed++ == '.');
+ } while (*desc++ == '.');
} else {
- seed++; /* expect a slash immediately */
+ desc++; /* expect a slash immediately */
}
- if (seed[-1] == '/') {
+ if (desc[-1] == '/') {
if (i+1 == params->w + params->h)
return "too many row/column specifications";
- } else if (seed[-1] == '\0') {
+ } else if (desc[-1] == '\0') {
if (i+1 < params->w + params->h)
return "too few row/column specifications";
} else
return NULL;
}
-static game_state *new_game(game_params *params, char *seed)
+static game_state *new_game(midend_data *me, game_params *params, char *desc)
{
int i;
char *p;
state->rowdata = snewn(state->rowsize * (state->w + state->h), int);
state->rowlen = snewn(state->w + state->h, int);
- state->completed = FALSE;
+ state->completed = state->cheated = FALSE;
for (i = 0; i < params->w + params->h; i++) {
state->rowlen[i] = 0;
- if (*seed && isdigit((unsigned char)*seed)) {
+ if (*desc && isdigit((unsigned char)*desc)) {
do {
- p = seed;
- while (seed && isdigit((unsigned char)*seed)) seed++;
+ p = desc;
+ while (desc && isdigit((unsigned char)*desc)) desc++;
state->rowdata[state->rowsize * i + state->rowlen[i]++] =
atoi(p);
- } while (*seed++ == '.');
+ } while (*desc++ == '.');
} else {
- seed++; /* expect a slash immediately */
+ desc++; /* expect a slash immediately */
}
}
(ret->w + ret->h) * sizeof(int));
ret->completed = state->completed;
+ ret->cheated = state->cheated;
return ret;
}
sfree(state);
}
+static char *solve_game(game_state *state, game_state *currstate,
+ char *ai, char **error)
+{
+ unsigned char *matrix;
+ int w = state->w, h = state->h;
+ int i;
+ char *ret;
+ int done_any, max;
+ unsigned char *workspace;
+ int *rowdata;
+
+ /*
+ * If we already have the solved state in ai, copy it out.
+ */
+ if (ai)
+ return dupstr(ai);
+
+ matrix = snewn(w*h, unsigned char);
+ max = max(w, h);
+ workspace = snewn(max*3, unsigned char);
+ rowdata = snewn(max+1, int);
+
+ memset(matrix, 0, w*h);
+
+ do {
+ done_any = 0;
+ for (i=0; i<h; i++) {
+ memcpy(rowdata, state->rowdata + state->rowsize*(w+i),
+ max*sizeof(int));
+ rowdata[state->rowlen[w+i]] = 0;
+ done_any |= do_row(workspace, workspace+max, workspace+2*max,
+ matrix+i*w, w, 1, rowdata);
+ }
+ for (i=0; i<w; i++) {
+ memcpy(rowdata, state->rowdata + state->rowsize*i, max*sizeof(int));
+ rowdata[state->rowlen[i]] = 0;
+ done_any |= do_row(workspace, workspace+max, workspace+2*max,
+ matrix+i, h, w, rowdata);
+ }
+ } while (done_any);
+
+ sfree(workspace);
+ sfree(rowdata);
+
+ for (i = 0; i < w*h; i++) {
+ if (matrix[i] != BLOCK && matrix[i] != DOT) {
+ sfree(matrix);
+ *error = "Solving algorithm cannot complete this puzzle";
+ return NULL;
+ }
+ }
+
+ ret = snewn(w*h+2, char);
+ ret[0] = 'S';
+ for (i = 0; i < w*h; i++) {
+ assert(matrix[i] == BLOCK || matrix[i] == DOT);
+ ret[i+1] = (matrix[i] == BLOCK ? '1' : '0');
+ }
+ ret[w*h+1] = '\0';
+
+ sfree(matrix);
+
+ return ret;
+}
+
+static char *game_text_format(game_state *state)
+{
+ return NULL;
+}
+
struct game_ui {
int dragging;
int drag_start_x;
sfree(ui);
}
-static game_state *make_move(game_state *from, game_ui *ui,
- int x, int y, int button)
+static char *encode_ui(game_ui *ui)
{
- game_state *ret;
+ return NULL;
+}
- x = FROMCOORD(from->w, x);
- y = FROMCOORD(from->h, y);
+static void decode_ui(game_ui *ui, char *encoding)
+{
+}
+
+static void game_changed_state(game_ui *ui, game_state *oldstate,
+ game_state *newstate)
+{
+}
- if (x >= 0 && x < from->w && y >= 0 && y < from->h &&
+struct game_drawstate {
+ int started;
+ int w, h;
+ int tilesize;
+ unsigned char *visible;
+};
+
+static char *interpret_move(game_state *state, game_ui *ui, game_drawstate *ds,
+ int x, int y, int button)
+{
+ button &= ~MOD_MASK;
+
+ x = FROMCOORD(state->w, x);
+ y = FROMCOORD(state->h, y);
+
+ if (x >= 0 && x < state->w && y >= 0 && y < state->h &&
(button == LEFT_BUTTON || button == RIGHT_BUTTON ||
button == MIDDLE_BUTTON)) {
ui->drag_start_x = ui->drag_end_x = x;
ui->drag_start_y = ui->drag_end_y = y;
- return from; /* UI activity occurred */
+ return ""; /* UI activity occurred */
}
if (ui->dragging && button == ui->drag) {
if (x < 0) x = 0;
if (y < 0) y = 0;
- if (x >= from->w) x = from->w - 1;
- if (y >= from->h) y = from->h - 1;
+ if (x >= state->w) x = state->w - 1;
+ if (y >= state->h) y = state->h - 1;
ui->drag_end_x = x;
ui->drag_end_y = y;
- return from; /* UI activity occurred */
+ return ""; /* UI activity occurred */
}
if (ui->dragging && button == ui->release) {
for (yy = y1; yy <= y2; yy++)
for (xx = x1; xx <= x2; xx++)
- if (from->grid[yy * from->w + xx] != ui->state)
+ if (state->grid[yy * state->w + xx] != ui->state)
move_needed = TRUE;
ui->dragging = FALSE;
if (move_needed) {
- ret = dup_game(from);
- for (yy = y1; yy <= y2; yy++)
- for (xx = x1; xx <= x2; xx++)
- ret->grid[yy * ret->w + xx] = ui->state;
-
- /*
- * An actual change, so check to see if we've completed
- * the game.
- */
- if (!ret->completed) {
- int *rowdata = snewn(ret->rowsize, int);
- int i, len;
-
- ret->completed = TRUE;
-
- for (i=0; i<ret->w; i++) {
- len = compute_rowdata(rowdata,
- ret->grid+i, ret->h, ret->w);
- if (len != ret->rowlen[i] ||
- memcmp(ret->rowdata+i*ret->rowsize, rowdata,
- len * sizeof(int))) {
- ret->completed = FALSE;
- break;
- }
- }
- for (i=0; i<ret->h; i++) {
- len = compute_rowdata(rowdata,
- ret->grid+i*ret->w, ret->w, 1);
- if (len != ret->rowlen[i+ret->w] ||
- memcmp(ret->rowdata+(i+ret->w)*ret->rowsize, rowdata,
- len * sizeof(int))) {
- ret->completed = FALSE;
- break;
- }
- }
-
- sfree(rowdata);
- }
-
- return ret;
+ char buf[80];
+ sprintf(buf, "%c%d,%d,%d,%d",
+ (char)(ui->state == GRID_FULL ? 'F' :
+ ui->state == GRID_EMPTY ? 'E' : 'U'),
+ x1, y1, x2-x1+1, y2-y1+1);
+ return dupstr(buf);
} else
- return from; /* UI activity occurred */
+ return ""; /* UI activity occurred */
}
return NULL;
}
+static game_state *execute_move(game_state *from, char *move)
+{
+ game_state *ret;
+ int x1, x2, y1, y2, xx, yy;
+ int val;
+
+ if (move[0] == 'S' && strlen(move) == from->w * from->h + 1) {
+ int i;
+
+ ret = dup_game(from);
+
+ for (i = 0; i < ret->w * ret->h; i++)
+ ret->grid[i] = (move[i+1] == '1' ? GRID_FULL : GRID_EMPTY);
+
+ ret->completed = ret->cheated = TRUE;
+
+ return ret;
+ } else if ((move[0] == 'F' || move[0] == 'E' || move[0] == 'U') &&
+ sscanf(move+1, "%d,%d,%d,%d", &x1, &y1, &x2, &y2) == 4 &&
+ x1 >= 0 && x2 >= 0 && x1+x2 <= from->w &&
+ y1 >= 0 && y2 >= 0 && y1+y2 <= from->h) {
+
+ x2 += x1;
+ y2 += y1;
+ val = (move[0] == 'F' ? GRID_FULL :
+ move[0] == 'E' ? GRID_EMPTY : GRID_UNKNOWN);
+
+ ret = dup_game(from);
+ for (yy = y1; yy < y2; yy++)
+ for (xx = x1; xx < x2; xx++)
+ ret->grid[yy * ret->w + xx] = val;
+
+ /*
+ * An actual change, so check to see if we've completed the
+ * game.
+ */
+ if (!ret->completed) {
+ int *rowdata = snewn(ret->rowsize, int);
+ int i, len;
+
+ ret->completed = TRUE;
+
+ for (i=0; i<ret->w; i++) {
+ len = compute_rowdata(rowdata,
+ ret->grid+i, ret->h, ret->w);
+ if (len != ret->rowlen[i] ||
+ memcmp(ret->rowdata+i*ret->rowsize, rowdata,
+ len * sizeof(int))) {
+ ret->completed = FALSE;
+ break;
+ }
+ }
+ for (i=0; i<ret->h; i++) {
+ len = compute_rowdata(rowdata,
+ ret->grid+i*ret->w, ret->w, 1);
+ if (len != ret->rowlen[i+ret->w] ||
+ memcmp(ret->rowdata+(i+ret->w)*ret->rowsize, rowdata,
+ len * sizeof(int))) {
+ ret->completed = FALSE;
+ break;
+ }
+ }
+
+ sfree(rowdata);
+ }
+
+ return ret;
+ } else
+ return NULL;
+}
+
/* ----------------------------------------------------------------------
* Drawing routines.
*/
-struct game_drawstate {
- int started;
- int w, h;
- unsigned char *visible;
-};
-
-static void game_size(game_params *params, int *x, int *y)
+static void game_size(game_params *params, game_drawstate *ds,
+ int *x, int *y, int expand)
{
+ double ts;
+
+ ts = min(GETTILESIZE(params->w, *x), GETTILESIZE(params->h, *y));
+ if (expand)
+ ds->tilesize = (int)(ts + 0.5);
+ else
+ ds->tilesize = min((int)ts, PREFERRED_TILE_SIZE);
+
*x = SIZE(params->w);
*y = SIZE(params->h);
}
ds->w = state->w;
ds->h = state->h;
ds->visible = snewn(ds->w * ds->h, unsigned char);
+ ds->tilesize = 0; /* not decided yet */
memset(ds->visible, 255, ds->w * ds->h);
return ds;
}
static void game_redraw(frontend *fe, game_drawstate *ds, game_state *oldstate,
- game_state *state, int dir, game_ui *ui,
- float animtime, float flashtime)
+ game_state *state, int dir, game_ui *ui,
+ float animtime, float flashtime)
{
int i, j;
int x1, x2, y1, y2;
}
static float game_anim_length(game_state *oldstate,
- game_state *newstate, int dir)
+ 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_state *newstate, int dir, game_ui *ui)
{
- if (!oldstate->completed && newstate->completed)
+ if (!oldstate->completed && newstate->completed &&
+ !oldstate->cheated && !newstate->cheated)
return FLASH_TIME;
return 0.0F;
}
return FALSE;
}
+static int game_timing_state(game_state *state)
+{
+ return TRUE;
+}
+
#ifdef COMBINED
#define thegame pattern
#endif
const struct game thegame = {
- "Pattern", "games.pattern", TRUE,
+ "Pattern", "games.pattern",
default_params,
game_fetch_preset,
decode_params,
encode_params,
free_params,
dup_params,
- game_configure,
- custom_params,
+ TRUE, game_configure, custom_params,
validate_params,
- new_game_seed,
- validate_seed,
+ new_game_desc,
+ validate_desc,
new_game,
dup_game,
free_game,
+ TRUE, solve_game,
+ FALSE, game_text_format,
new_ui,
free_ui,
- make_move,
+ encode_ui,
+ decode_ui,
+ game_changed_state,
+ interpret_move,
+ execute_move,
game_size,
game_colours,
game_new_drawstate,
game_anim_length,
game_flash_length,
game_wants_statusbar,
+ FALSE, game_timing_state,
+ 0, /* mouse_priorities */
};
+
+#ifdef STANDALONE_SOLVER
+
+/*
+ * gcc -DSTANDALONE_SOLVER -o patternsolver pattern.c malloc.c
+ */
+
+#include <stdarg.h>
+
+void frontend_default_colour(frontend *fe, float *output) {}
+void draw_text(frontend *fe, int x, int y, int fonttype, int fontsize,
+ int align, int colour, char *text) {}
+void draw_rect(frontend *fe, int x, int y, int w, int h, int colour) {}
+void draw_line(frontend *fe, int x1, int y1, int x2, int y2, int colour) {}
+void clip(frontend *fe, int x, int y, int w, int h) {}
+void unclip(frontend *fe) {}
+void start_draw(frontend *fe) {}
+void draw_update(frontend *fe, int x, int y, int w, int h) {}
+void end_draw(frontend *fe) {}
+unsigned long random_upto(random_state *state, unsigned long limit)
+{ assert(!"Shouldn't get randomness"); return 0; }
+
+void fatal(char *fmt, ...)
+{
+ va_list ap;
+
+ fprintf(stderr, "fatal error: ");
+
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+
+ fprintf(stderr, "\n");
+ exit(1);
+}
+
+int main(int argc, char **argv)
+{
+ game_params *p;
+ game_state *s;
+ int recurse = TRUE;
+ char *id = NULL, *desc, *err;
+ int y, x;
+ int grade = FALSE;
+
+ while (--argc > 0) {
+ char *p = *++argv;
+ if (*p == '-') {
+ fprintf(stderr, "%s: unrecognised option `%s'\n", argv[0]);
+ return 1;
+ } else {
+ id = p;
+ }
+ }
+
+ if (!id) {
+ fprintf(stderr, "usage: %s <game_id>\n", argv[0]);
+ return 1;
+ }
+
+ desc = strchr(id, ':');
+ if (!desc) {
+ fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+ return 1;
+ }
+ *desc++ = '\0';
+
+ p = default_params();
+ decode_params(p, id);
+ err = validate_desc(p, desc);
+ if (err) {
+ fprintf(stderr, "%s: %s\n", argv[0], err);
+ return 1;
+ }
+ s = new_game(NULL, p, desc);
+
+ {
+ int w = p->w, h = p->h, i, j, done_any, max;
+ unsigned char *matrix, *workspace;
+ int *rowdata;
+
+ matrix = snewn(w*h, unsigned char);
+ max = max(w, h);
+ workspace = snewn(max*3, unsigned char);
+ rowdata = snewn(max+1, int);
+
+ memset(matrix, 0, w*h);
+
+ do {
+ done_any = 0;
+ for (i=0; i<h; i++) {
+ memcpy(rowdata, s->rowdata + s->rowsize*(w+i),
+ max*sizeof(int));
+ rowdata[s->rowlen[w+i]] = 0;
+ done_any |= do_row(workspace, workspace+max, workspace+2*max,
+ matrix+i*w, w, 1, rowdata);
+ }
+ for (i=0; i<w; i++) {
+ memcpy(rowdata, s->rowdata + s->rowsize*i, max*sizeof(int));
+ rowdata[s->rowlen[i]] = 0;
+ done_any |= do_row(workspace, workspace+max, workspace+2*max,
+ matrix+i, h, w, rowdata);
+ }
+ } while (done_any);
+
+ for (i = 0; i < h; i++) {
+ for (j = 0; j < w; j++) {
+ int c = (matrix[i*w+j] == UNKNOWN ? '?' :
+ matrix[i*w+j] == BLOCK ? '#' :
+ matrix[i*w+j] == DOT ? '.' :
+ '!');
+ putchar(c);
+ }
+ printf("\n");
+ }
+ }
+
+ return 0;
+}
+
+#endif
~mdw / sgt / puzzles / blobdiff