X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/9b4b03d31e30089e9f45f6ea166561c4c0c25a9c..50ff573008fcfcc1cf1e9c071d36f5c84e2684dc:/pattern.c

diff --git a/pattern.c b/pattern.c
index 6dda1f4..438243d 100644
--- a/pattern.c
+++ b/pattern.c
@@ -1,9 +1,5 @@
 /*
  * 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>
@@ -52,7 +48,7 @@ struct game_state {
     unsigned char *grid;
     int rowsize;
     int *rowdata, *rowlen;
-    int completed;
+    int completed, cheated;
 };
 
 #define FLASH_TIME 0.13F
@@ -104,9 +100,8 @@ static game_params *dup_params(game_params *params)
     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);
@@ -118,11 +113,9 @@ static game_params *decode_params(char const *string)
     } 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;
@@ -476,18 +469,38 @@ static unsigned char *generate_soluble(random_state *rs, int w, int h)
     return grid;
 }
 
-static char *new_game_seed(game_params *params, random_state *rs)
+struct game_aux_info {
+    int w, h;
+    unsigned char *grid;
+};
+
+static char *new_game_desc(game_params *params, random_state *rs,
+			   game_aux_info **aux)
 {
     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 an aux_info.
+     */
+    {
+	game_aux_info *ai = snew(game_aux_info);
+
+	ai->w = params->w;
+	ai->h = params->h;
+	ai->grid = snewn(ai->w * ai->h, unsigned char);
+	memcpy(ai->grid, grid, ai->w * ai->h);
+
+	*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,
@@ -497,7 +510,7 @@ static char *new_game_seed(game_params *params, random_state *rs)
      * 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);
@@ -506,14 +519,14 @@ static char *new_game_seed(game_params *params, random_state *rs)
                                      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);
@@ -522,25 +535,31 @@ static char *new_game_seed(game_params *params, random_state *rs)
                                      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;
+    return desc;
 }
 
-static char *validate_seed(game_params *params, char *seed)
+static void game_free_aux_info(game_aux_info *aux)
+{
+    sfree(aux->grid);
+    sfree(aux);
+}
+
+static char *validate_desc(game_params *params, char *desc)
 {
     int i, n, rowspace;
     char *p;
@@ -551,10 +570,10 @@ static char *validate_seed(game_params *params, char *seed)
         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;
 
@@ -564,15 +583,15 @@ static char *validate_seed(game_params *params, char *seed)
                     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
@@ -582,7 +601,7 @@ static char *validate_seed(game_params *params, char *seed)
     return NULL;
 }
 
-static game_state *new_game(game_params *params, char *seed)
+static game_state *new_game(game_params *params, char *desc)
 {
     int i;
     char *p;
@@ -598,19 +617,19 @@ static game_state *new_game(game_params *params, char *seed)
     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 */
         }
     }
 
@@ -636,6 +655,7 @@ static game_state *dup_game(game_state *state)
            (ret->w + ret->h) * sizeof(int));
 
     ret->completed = state->completed;
+    ret->cheated = state->cheated;
 
     return ret;
 }
@@ -648,6 +668,73 @@ static void free_game(game_state *state)
     sfree(state);
 }
 
+static game_state *solve_game(game_state *state, game_aux_info *ai,
+			      char **error)
+{
+    game_state *ret;
+
+    ret = dup_game(state);
+    ret->completed = ret->cheated = TRUE;
+
+    /*
+     * If we already have the solved state in an aux_info, copy it
+     * out.
+     */
+    if (ai) {
+
+	assert(ret->w == ai->w);
+	assert(ret->h == ai->h);
+	memcpy(ret->grid, ai->grid, ai->w * ai->h);
+
+    } else {
+	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;
@@ -1005,7 +1092,8 @@ static float game_anim_length(game_state *oldstate,
 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;
 }
@@ -1029,11 +1117,13 @@ const struct game thegame = {
     dup_params,
     TRUE, game_configure, custom_params,
     validate_params,
-    new_game_seed,
-    validate_seed,
+    new_game_desc,
+    game_free_aux_info,
+    validate_desc,
     new_game,
     dup_game,
     free_game,
+    TRUE, solve_game,
     FALSE, game_text_format,
     new_ui,
     free_ui,
@@ -1090,7 +1180,7 @@ int main(int argc, char **argv)
     game_params *p;
     game_state *s;
     int recurse = TRUE;
-    char *id = NULL, *seed, *err;
+    char *id = NULL, *desc, *err;
     int y, x;
     int grade = FALSE;
 
@@ -1109,20 +1199,20 @@ int main(int argc, char **argv)
         return 1;
     }
 
-    seed = strchr(id, ':');
-    if (!seed) {
+    desc = strchr(id, ':');
+    if (!desc) {
         fprintf(stderr, "%s: game id expects a colon in it\n", argv[0]);
         return 1;
     }
-    *seed++ = '\0';
+    *desc++ = '\0';
 
     p = decode_params(id);
-    err = validate_seed(p, seed);
+    err = validate_desc(p, desc);
     if (err) {
         fprintf(stderr, "%s: %s\n", argv[0], err);
         return 1;
     }
-    s = new_game(p, seed);
+    s = new_game(p, desc);
 
     {
 	int w = p->w, h = p->h, i, j, done_any, max;