/*
* 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>
unsigned char *grid;
int rowsize;
int *rowdata, *rowlen;
- int completed;
+ int completed, cheated;
};
#define FLASH_TIME 0.13F
for (q = -1; q <= +1; q++) {
if (i+p < 0 || i+p >= h || j+q < 0 || j+q >= w)
continue;
+ /*
+ * An additional special case not mentioned
+ * above: if a grid dimension is 2xn then
+ * we do not average across that dimension
+ * at all. Otherwise a 2x2 grid would
+ * contain four identical squares.
+ */
+ if ((h==2 && p!=0) || (w==2 && q!=0))
+ continue;
n++;
sx += fgrid[(i+p)*w+(j+q)];
}
for (i = 0; i < h; i++) {
for (j = 0; j < w; j++) {
- retgrid[i*w+j] = (fgrid[i*w+j] > threshold ? GRID_FULL :
+ retgrid[i*w+j] = (fgrid[i*w+j] >= threshold ? GRID_FULL :
GRID_EMPTY);
}
}
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_seed(game_params *params, random_state *rs,
+ game_aux_info **aux)
{
unsigned char *grid;
int i, j, max, rowlen, *rowdata;
return seed;
}
+static void game_free_aux_info(game_aux_info *aux)
+{
+ assert(!"Shouldn't happen");
+}
+
static char *validate_seed(game_params *params, char *seed)
{
int i, n, rowspace;
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;
(ret->w + ret->h) * sizeof(int));
ret->completed = state->completed;
+ ret->cheated = state->cheated;
return ret;
}
sfree(state);
}
+static game_state *solve_game(game_state *state, game_aux_info *aux,
+ char **error)
+{
+ game_state *ret;
+
+ /*
+ * I could have stored the grid I invented in the game_aux_info
+ * and extracted it here where available, but it seems easier
+ * just to run my internal solver in all cases.
+ */
+
+ ret = dup_game(state);
+ ret->completed = ret->cheated = TRUE;
+
+ {
+ int w = state->w, h = state->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, 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);
+
+ for (i = 0; i < h; i++) {
+ for (j = 0; j < w; j++) {
+ int c = (matrix[i*w+j] == BLOCK ? GRID_FULL :
+ matrix[i*w+j] == DOT ? GRID_EMPTY : GRID_UNKNOWN);
+ ret->grid[i*w+j] = c;
+ if (c == GRID_UNKNOWN)
+ ret->completed = FALSE;
+ }
+ }
+
+ if (!ret->completed) {
+ free_game(ret);
+ *error = "Solving algorithm cannot complete this puzzle";
+ return NULL;
+ }
+ }
+
+ return ret;
+}
+
+static char *game_text_format(game_state *state)
+{
+ return NULL;
+}
+
struct game_ui {
int dragging;
int drag_start_x;
static float game_flash_length(game_state *oldstate,
game_state *newstate, int dir)
{
- if (!oldstate->completed && newstate->completed)
+ if (!oldstate->completed && newstate->completed &&
+ !oldstate->cheated && !newstate->cheated)
return FLASH_TIME;
return 0.0F;
}
#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,
+ game_free_aux_info,
validate_seed,
new_game,
dup_game,
free_game,
+ TRUE, solve_game,
+ FALSE, game_text_format,
new_ui,
free_ui,
make_move,
game_flash_length,
game_wants_statusbar,
};
+
+#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 draw_polygon(frontend *fe, int *coords, int npoints,
+ int fill, 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, *seed, *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;
+ }
+
+ seed = strchr(id, ':');
+ if (!seed) {
+ fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
+ return 1;
+ }
+ *seed++ = '\0';
+
+ p = decode_params(id);
+ err = validate_seed(p, seed);
+ if (err) {
+ fprintf(stderr, "%s: %s\n", argv[0], err);
+ return 1;
+ }
+ s = new_game(p, seed);
+
+ {
+ 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