From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Mon, 7 May 2007 17:51:37 +0000 (+0000)
Subject: Slight solver speedup by tracking more carefully which block merges
X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/commitdiff_plain/39bdcaad9141c6fdb49d10d2f2ed2aae4d7acd18

Slight solver speedup by tracking more carefully which block merges
we've already tried, and not trying them again.


git-svn-id: svn://svn.tartarus.org/sgt/puzzles@7553 cda61777-01e9-0310-a592-d414129be87e
---

diff --git a/unfinished/slide.c b/unfinished/slide.c
index c9afe41..130c7b9 100644
--- a/unfinished/slide.c
+++ b/unfinished/slide.c
@@ -17,11 +17,31 @@
  *    cases.
  * 
  *  - Improve the generator.
+ *     * actually, we seem to be mostly sensible already now. I
+ * 	 want more choice over the type of main block and location
+ * 	 of the exit/target, and I think I probably ought to give
+ * 	 up on compactness and just bite the bullet and have the
+ * 	 target area right outside the main wall, but mostly I
+ * 	 think it's OK.
+ *     * but adjust the presets, because 8x6 is _slow_ to
+ * 	 generate.
+ *     * also, introduce a difficulty scheme, in the form of
+ * 	 limiting the minimum move count. This is obviously
+ * 	 sensible, because it also speeds up generation since the
+ * 	 solver can bomb out once it hits that ceiling!
+ * 	  + I was going to say I'd need to work out a minimum move
+ * 	    count for each grid size, but actually I think not: if
+ * 	    you ask for too few moves, it just has to remove still
+ * 	    more singletons, until at move count 1 you end up with
+ * 	    nothing in your way at all and it SERVES YOU RIGHT!
  * 
- *  - All the colours are a bit wishy-washy. _Some_ dark colours
- *    would surely not be excessive? Probably darken the tiles,
- *    the walls and the main block, and leave the target marker
- *    pale.
+ *  - Improve the graphics.
+ *     * All the colours are a bit wishy-washy. _Some_ dark
+ * 	 colours would surely not be excessive? Probably darken
+ * 	 the tiles, the walls and the main block, and leave the
+ * 	 target marker pale.
+ *     * The cattle grid effect is still disgusting. Think of
+ * 	 something completely different.
  */
 
 #include <stdio.h>
@@ -556,6 +576,8 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
 {
     int wh = w*h;
     unsigned char *board, *board2, *forcefield;
+    unsigned char *tried_merge;
+    int *dsf;
     int *list, nlist, pos;
     int tx, ty;
     int i, j;
@@ -575,6 +597,10 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
     for (i = 0; i < h; i++)
 	board[i*w] = board[i*w+(w-1)] = WALL;
 
+    tried_merge = snewn(wh * wh, unsigned char);
+    memset(tried_merge, 0, wh*wh);
+    dsf = snew_dsf(wh);
+
     /*
      * Invent a main piece at one extreme. (FIXME: vary the
      * extreme, and the piece.)
@@ -628,19 +654,11 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
     /*
      * Now go through that list in random order, trying to merge
      * the blocks on each side of each edge.
-     * 
-     * FIXME: this seems to produce unpleasantly unbalanced
-     * results. Perhaps we'd do better if we always tried to
-     * combine the _smallest_ block with something?
-     * 
-     * FIXME: also one reason it's slow might be because we aren't
-     * tracking which blocks we've already tried to merge, when
-     * another edge ends up linking the same ones.
      */
     shuffle(list, nlist, sizeof(*list), rs);
     while (nlist > 0) {
-	int x1, y1, p1;
-	int x2, y2, p2;
+	int x1, y1, p1, c1;
+	int x2, y2, p2, c2;
 
 	pos = list[--nlist];
 	y1 = y2 = pos / (w*2);
@@ -653,6 +671,18 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
 	p2 = y2*w+x2;
 
 	/*
+	 * Immediately abandon the attempt if we've already tried
+	 * to merge the same pair of blocks along a different
+	 * edge.
+	 */
+	c1 = dsf_canonify(dsf, p1);
+	c2 = dsf_canonify(dsf, p2);
+	if (tried_merge[c1 * wh + c2])
+{printf("aha\n");
+	    continue;
+}
+
+	/*
 	 * In order to be mergeable, these two squares must each
 	 * either be, or belong to, a non-main anchor, and their
 	 * anchors must also be distinct.
@@ -706,8 +736,20 @@ static void generate_board(int w, int h, int *rtx, int *rty, int *minmoves,
 	     * Didn't work. Revert the merge.
 	     */
 	    memcpy(board, board2, wh);
+	    tried_merge[c1 * wh + c2] = tried_merge[c2 * wh + c1] = TRUE;
 	} else {
+	    int c;
+
 	    moves = j;
+
+	    dsf_merge(dsf, c1, c2);
+	    c = dsf_canonify(dsf, c1);
+	    for (i = 0; i < wh; i++)
+		tried_merge[c*wh+i] = (tried_merge[c1*wh+i] |
+				       tried_merge[c2*wh+i]);
+	    for (i = 0; i < wh; i++)
+		tried_merge[i*wh+c] = (tried_merge[i*wh+c1] |
+				       tried_merge[i*wh+c2]);
 	}
     }
 
@@ -1835,7 +1877,7 @@ static void game_redraw(drawing *dr, game_drawstate *ds, game_state *oldstate,
 	sprintf(statusbuf, "%sMoves: %d",
 		(state->completed >= 0 ? "COMPLETED! " : ""),
 		(state->completed >= 0 ? state->completed : state->movecount));
-	if (state->minmoves)
+	if (state->minmoves >= 0)
 	    sprintf(statusbuf+strlen(statusbuf), " (min %d)",
 		    state->minmoves);