Improved the limited shuffle mechanism in Sixteen and Twiddle. They

were already making sure that no shuffle move was the precise
inverse of the previous one, or contributed to repeating the
previous one so many times as to turn it into effectively fewer
moves (doing the same rotation three times in Twiddle, or shifting a
row by more than half its length in Sixteen). However, they were
only checking against the _last_ move, which meant that in any
situation where there were completely disjoint move spaces (4x4n2
Twiddle, or any Sixteen at all) it was still possible to have A then
B then inv(A) occurring in the shuffle, leading to an unnecessarily
easy game.

Now both shuffle routines keep separate track of all
_non-overlapping_ recent moves, and will avoid inverting any move
which hasn't had another move overlap it since it was made. This
should reduce the incidence of too-easy limited shuffle games,
although it can't be prevented _entirely_ (since, if nothing else,
it's always possible to increase the shuffle limit past the maximum
group radius).

[originally from svn r5875]

diff --git a/sixteen.c b/sixteen.c
index fe3e8d1e03f0af4a63e9231f93c2d1b0629911d4..c6664c138720ff8bdf0794ff1dd8b6b4dd2189cb 100644 (file)
--- a/sixteen.c
+++ b/sixteen.c
@@ -207,7 +207,9 @@ static char *new_game_desc(game_params *params, random_state *rs,
     tiles = snewn(n, int);
 
     if (params->movetarget) {
-       int prevstart = -1, prevoffset = -1, prevdirection = 0, nrepeats = 0;
+       int prevoffset = -1;
+        int max = (params->w > params->h ? params->w : params->h);
+        int *prevmoves = snewn(max, int);
 
        /*
         * Shuffle the old-fashioned way, by making a series of
@@ -218,7 +220,7 @@ static char *new_game_desc(game_params *params, random_state *rs,
            tiles[i] = i;
 
        for (i = 0; i < params->movetarget; i++) {
-           int start, offset, len, direction;
+           int start, offset, len, direction, index;
            int j, tmp;
 
            /*
@@ -230,12 +232,14 @@ static char *new_game_desc(game_params *params, random_state *rs,
 
                if (j < params->w) {
                    /* Column. */
+                    index = j;
                    start = j;
                    offset = params->w;
                    len = params->h;
                } else {
                    /* Row. */
-                   start = (j - params->w) * params->w;
+                    index = j - params->w;
+                   start = index * params->w;
                    offset = 1;
                    len = params->w;
                }
@@ -243,36 +247,42 @@ static char *new_game_desc(game_params *params, random_state *rs,
                direction = -1 + 2 * random_upto(rs, 2);
 
                /*
-                * To at least _try_ to avoid boring cases, check that
-                * this move doesn't directly undo the previous one, or
-                * repeat it so many times as to turn it into fewer
-                * moves.
+                * To at least _try_ to avoid boring cases, check
+                * that this move doesn't directly undo a previous
+                * one, or repeat it so many times as to turn it
+                * into fewer moves in the opposite direction. (For
+                * example, in a row of length 4, we're allowed to
+                * move it the same way twice, but not three
+                * times.)
+                 * 
+                 * We track this for each individual row/column,
+                 * and clear all the counters as soon as a
+                 * perpendicular move is made. This isn't perfect
+                 * (it _can't_ guaranteeably be perfect - there
+                 * will always come a move count beyond which a
+                 * shorter solution will be possible than the one
+                 * which constructed the position) but it should
+                 * sort out all the obvious cases.
                 */
-               if (start == prevstart && offset == prevoffset) {
-                   if (direction == -prevdirection)
-                       continue;      /* inverse of previous move */
-                   else if (2 * (nrepeats+1) > len)
-                       continue;      /* previous move repeated too often */
-               }
+                if (offset == prevoffset) {
+                    tmp = prevmoves[index] + direction;
+                    if (abs(2*tmp) > len || abs(tmp) < abs(prevmoves[index]))
+                        continue;
+                }
 
                /* If we didn't `continue', we've found an OK move to make. */
+                if (offset != prevoffset) {
+                    int i;
+                    for (i = 0; i < max; i++)
+                        prevmoves[i] = 0;
+                    prevoffset = offset;
+                }
+                prevmoves[index] += direction;
                break;
            }
 
            /*
-            * Now save the move into the `prev' variables.
-            */
-           if (start == prevstart && offset == prevoffset) {
-               nrepeats++;
-           } else {
-               prevstart = start;
-               prevoffset = offset;
-               prevdirection = direction;
-               nrepeats = 1;
-           }
-
-           /*
-            * And make it.
+            * Make the move.
             */
            if (direction < 0) {
                start += (len-1) * offset;
@@ -284,6 +294,8 @@ static char *new_game_desc(game_params *params, random_state *rs,
            tiles[start + (len-1) * offset] = tmp;
        }
 
+        sfree(prevmoves);
+
     } else {
 
        used = snewn(n, int);

diff --git a/twiddle.c b/twiddle.c
index f6c8f4d9db767fc85688d3ec5d01a8021b2e1c69..f7bfd4a6e3b339452bb0e6979e2af4dbece121d3 100644 (file)
--- a/twiddle.c
+++ b/twiddle.c
@@ -333,38 +333,69 @@ static char *new_game_desc(game_params *params, random_state *rs,
      */
     total_moves = params->movetarget;
     if (!total_moves)
+        /* Add a random move to avoid parity issues. */
         total_moves = w*h*n*n*2 + random_upto(rs, 2);
 
     do {
-        int oldx = -1, oldy = -1, oldr = -1;
+        int *prevmoves;
+        int rw, rh;                    /* w/h of rotation centre space */
+
+        rw = w - n + 1;
+        rh = h - n + 1;
+        prevmoves = snewn(rw * rh, int);
+        for (i = 0; i < rw * rh; i++)
+            prevmoves[i] = 0;
 
         for (i = 0; i < total_moves; i++) {
-            int x, y, r;
+            int x, y, r, oldtotal, newtotal, dx, dy;
 
             do {
                 x = random_upto(rs, w - n + 1);
                 y = random_upto(rs, h - n + 1);
-                r = 1 + 2 * random_upto(rs, 2);
-            } while (x == oldx && y == oldy && (oldr == 0 || r == oldr));
-
-            do_rotate(grid, w, h, n, params->orientable,
-                      x, y, r);
+                r = 2 * random_upto(rs, 2) - 1;
+
+                /*
+                 * See if any previous rotations has happened at
+                 * this point which nothing has overlapped since.
+                 * If so, ensure we haven't either undone a
+                 * previous move or repeated one so many times that
+                 * it turns into fewer moves in the inverse
+                 * direction (i.e. three identical rotations).
+                 */
+                oldtotal = prevmoves[y*rw+x];
+                newtotal = oldtotal + r;
+            } while (abs(newtotal) < abs(oldtotal) || abs(newtotal) > 2);
+
+            do_rotate(grid, w, h, n, params->orientable, x, y, r);
 
             /*
-             * Prevent immediate reversal of a previous move, or
-             * execution of three consecutive identical moves
-             * adding up to a single inverse move. One exception is
-             * when we only _have_ one x,y setting.
+             * Log the rotation we've just performed at this point,
+             * for inversion detection in the next move.
+             * 
+             * Also zero a section of the prevmoves array, because
+             * any rotation area which _overlaps_ this one is now
+             * entirely safe to perform further moves in.
+             * 
+             * Two rotation areas overlap if their top left
+             * coordinates differ by strictly less than n in both
+             * directions
              */
-            if (w != n || h != n) {
-                if (oldx == x && oldy == y)
-                    oldr = 0;          /* now avoid _any_ move in this x,y */
-                else
-                    oldr = -r & 3;     /* only prohibit the exact inverse */
-                oldx = x;
-                oldy = y;
+            prevmoves[y*rw+x] += r;
+            for (dy = -n+1; dy <= n-1; dy++) {
+                if (y + dy < 0 || y + dy >= rh)
+                    continue;
+                for (dx = -n+1; dx <= n-1; dx++) {
+                    if (x + dx < 0 || x + dx >= rw)
+                        continue;
+                    if (dx == 0 && dy == 0)
+                        continue;
+                    prevmoves[(y+dy)*rw+(x+dx)] = 0;
+                }
             }
         }
+
+        sfree(prevmoves);
+
     } while (grid_complete(grid, wh, params->orientable));
 
     /*