X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/blobdiff_plain/6f2d8d7c70f6bbf8bce982ced1fa879e967afbbf..48a10826fef7777bb8b061f4a121f481ced98bc0:/pattern.c?ds=sidebyside

diff --git a/pattern.c b/pattern.c
index 55f840f..a728e15 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
@@ -476,6 +472,11 @@ static unsigned char *generate_soluble(random_state *rs, int w, int h)
     return grid;
 }
 
+struct game_aux_info {
+    int w, h;
+    unsigned char *grid;
+};
+
 static char *new_game_seed(game_params *params, random_state *rs,
 			   game_aux_info **aux)
 {
@@ -489,6 +490,20 @@ static char *new_game_seed(game_params *params, random_state *rs,
     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,
@@ -541,9 +556,10 @@ static char *new_game_seed(game_params *params, random_state *rs,
     return seed;
 }
 
-void game_free_aux_info(game_aux_info *aux)
+static void game_free_aux_info(game_aux_info *aux)
 {
-    assert(!"Shouldn't happen");
+    sfree(aux->grid);
+    sfree(aux);
 }
 
 static char *validate_seed(game_params *params, char *seed)
@@ -604,7 +620,7 @@ 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;
@@ -642,6 +658,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;
 }
@@ -654,6 +671,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;
@@ -1011,7 +1095,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;
 }
@@ -1041,6 +1126,7 @@ const struct game thegame = {
     new_game,
     dup_game,
     free_game,
+    TRUE, solve_game,
     FALSE, game_text_format,
     new_ui,
     free_ui,