ref: 8f1c713735316422cfe041400ccc49999d563d8b
parent: 18a8df1b9d06052ee3dba05202039cc2e8ee4f8d
author: Simon Tatham <anakin@pobox.com>
date: Wed May 11 16:38:10 EDT 2005
The two Rubik-like puzzles, Sixteen and Twiddle, now support an additional configuration parameter, which is the number of shuffle moves. By default the grid will be fully shuffled so that you need a general solution algorithm to untangle it, but if you prefer you can request a grid which has had (say) precisely four moves made on it, and then attempt to exactly reverse those four moves. Currently this feature is only available from the Custom box, and not in any presets. [originally from svn r5769]
--- a/puzzles.but
+++ b/puzzles.but
@@ -415,11 +415,43 @@
\H{sixteen-params} \I{parameters, for Sixteen}Sixteen parameters-The only parameters available from the \q{Custom...} option on the-\q{Type} menu are \e{Width} and \e{Height}, which are-self-explanatory.
+The parameters available from the \q{Custom...} option on the+\q{Type} menu are:+\b \e{Width} and \e{Height}, which are self-explanatory.+\b You can ask for a limited shuffling operation to be performed on
+the grid. By default, Sixteen will shuffle the grid in such a way
+that any arrangement is about as probable as any other. You can
+override this by requesting a precise number of shuffling moves to
+be performed. Typically your aim is then to determine the precise
+set of shuffling moves and invert them exactly, so that you answer
+(say) a four-move shuffle with a four-move solution. Note that the
+more moves you ask for, the more likely it is that solutions shorter
+than the target length will turn out to be possible.
+
+\H{sixteen-cmdline} \I{command line, for Sixteen}Additional+command-line configuration
+
+The limited shuffle parameter, described in \k{sixteen-params}, is+not mentioned by default in the game ID (see \k{common-id}). So if+you set your shuffling move count to (say) 4, and then you generate
+a normal 4\by\.4 grid, then the game ID will simply say
+\c{4x4:}\e{numbers}. This means that if you send the game ID to+another player and they paste it into their copy of Sixteen, their
+game will not be automatically configured to use the same shuffle
+limit in any subsequent grids it generates. (I don't think the
+average person examining a single grid sent to them by another
+player would want their configuration modified to that extent.)
+
+If you are specifying a game ID or game parameters on the command
+line (see \k{common-cmdline}) and you do want to configure the+shuffle limit, you can do it by suffixing the letter \cq{m} to the+parameters, followed by the move count as a decimal number. For
+example, \cq{sixteen 4x4m4} will start up Sixteen with a problem+guaranteed to be soluble in four moves or fewer.
+
+
\C{twiddle} \i{Twiddle} \cfg{winhelp-topic}{games.twiddle}@@ -475,6 +507,36 @@
drawn in it. All the triangles must be pointing upwards to complete
the puzzle.
+\b You can ask for a limited shuffling operation to be performed on
+the grid. By default, Twiddle will shuffle the grid so much that any
+arrangement is about as probable as any other. You can override this
+by requesting a precise number of shuffling moves to be performed.
+Typically your aim is then to determine the precise set of shuffling
+moves and invert them exactly, so that you answer (say) a four-move
+shuffle with a four-move solution. Note that the more moves you ask
+for, the more likely it is that solutions shorter than the target
+length will turn out to be possible.
+
+\H{twiddle-cmdline} \I{command line, for Twiddle}Additional+command-line configuration
+
+The limited shuffle parameter, described in \k{twiddle-parameters},+is not mentioned by default in the game ID (see \k{common-id}). So+if you set your shuffling move count to (say) 4, and then you
+generate a normal 3\by\.3 grid, then the game ID will simply say
+\c{3x3n2:}\e{numbers}. This means that if you send the game ID to+another player and they paste it into their copy of Twiddle, their
+game will not be automatically configured to use the same shuffle
+limit in any subsequent grids it generates. (I don't think the
+average person examining a single grid sent to them by another
+player would want their configuration modified to that extent.)
+
+If you are specifying a game ID or game parameters on the command
+line (see \k{common-cmdline}) and you do want to configure the+shuffle limit, you can do it by suffixing the letter \cq{m} to the+parameters, followed by the move count as a decimal number. For
+example, \cq{twiddle 3x3n2m4} will start up Twiddle with a problem+guaranteed to be soluble in four moves or fewer.
\C{rectangles} \i{Rectangles}--- a/sixteen.c
+++ b/sixteen.c
@@ -36,6 +36,7 @@
struct game_params {int w, h;
+ int movetarget;
};
struct game_state {@@ -44,7 +45,7 @@
int completed;
int just_used_solve; /* used to suppress undo animation */
int used_solve; /* used to suppress completion flash */
- int movecount;
+ int movecount, movetarget;
int last_movement_sense;
};
@@ -53,6 +54,7 @@
game_params *ret = snew(game_params);
ret->w = ret->h = 4;
+ ret->movetarget = 0;
return ret;
}
@@ -77,6 +79,7 @@
*params = ret = snew(game_params);
ret->w = w;
ret->h = h;
+ ret->movetarget = 0;
return TRUE;
}
@@ -101,7 +104,15 @@
if (*string == 'x') {string++;
ret->h = atoi(string);
+ while (*string && isdigit((unsigned char)*string))
+ string++;
}
+ if (*string == 'm') {+ string++;
+ ret->movetarget = atoi(string);
+ while (*string && isdigit((unsigned char)*string))
+ string++;
+ }
return ret;
}
@@ -120,7 +131,7 @@
config_item *ret;
char buf[80];
- ret = snewn(3, config_item);
+ ret = snewn(4, config_item);
ret[0].name = "Width";
ret[0].type = C_STRING;
@@ -134,11 +145,17 @@
ret[1].sval = dupstr(buf);
ret[1].ival = 0;
- ret[2].name = NULL;
- ret[2].type = C_END;
- ret[2].sval = NULL;
+ ret[2].name = "Number of shuffling moves";
+ ret[2].type = C_STRING;
+ sprintf(buf, "%d", params->movetarget);
+ ret[2].sval = dupstr(buf);
ret[2].ival = 0;
+ ret[3].name = NULL;
+ ret[3].type = C_END;
+ ret[3].sval = NULL;
+ ret[3].ival = 0;
+
return ret;
}
@@ -148,6 +165,7 @@
ret->w = atoi(cfg[0].sval);
ret->h = atoi(cfg[1].sval);
+ ret->movetarget = atoi(cfg[2].sval);
return ret;
}
@@ -186,75 +204,161 @@
n = params->w * params->h;
tiles = snewn(n, int);
- used = snewn(n, int);
- for (i = 0; i < n; i++) {- tiles[i] = -1;
- used[i] = FALSE;
- }
+ if (params->movetarget) {+ int prevstart = -1, prevoffset = -1, prevdirection = 0, nrepeats = 0;
- /*
- * If both dimensions are odd, there is a parity constraint.
- */
- if (params->w & params->h & 1)
- stop = 2;
- else
- stop = 0;
+ /*
+ * Shuffle the old-fashioned way, by making a series of
+ * single moves on the grid.
+ */
- /*
- * Place everything except (possibly) the last two tiles.
- */
- for (x = 0, i = n; i > stop; i--) {- int k = i > 1 ? random_upto(rs, i) : 0;
- int j;
+ for (i = 0; i < n; i++)
+ tiles[i] = i;
- for (j = 0; j < n; j++)
- if (!used[j] && (k-- == 0))
- break;
+ for (i = 0; i < params->movetarget; i++) {+ int start, offset, len, direction;
+ int j, tmp;
- assert(j < n && !used[j]);
- used[j] = TRUE;
+ /*
+ * Choose a move to make. We can choose from any row
+ * or any column.
+ */
+ while (1) {+ j = random_upto(rs, params->w + params->h);
- while (tiles[x] >= 0)
- x++;
- assert(x < n);
- tiles[x] = j;
- }
+ if (j < params->w) {+ /* Column. */
+ start = j;
+ offset = params->w;
+ len = params->h;
+ } else {+ /* Row. */
+ start = (j - params->w) * params->w;
+ offset = 1;
+ len = params->w;
+ }
- if (stop) {- /*
- * Find the last two locations, and the last two pieces.
- */
- while (tiles[x] >= 0)
- x++;
- assert(x < n);
- x1 = x;
- x++;
- while (tiles[x] >= 0)
- x++;
- assert(x < n);
- x2 = x;
+ direction = -1 + 2 * random_upto(rs, 2);
- for (i = 0; i < n; i++)
- if (!used[i])
- break;
- p1 = i;
- for (i = p1+1; i < n; i++)
- if (!used[i])
- break;
- p2 = i;
+ /*
+ * 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.
+ */
+ 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 */
+ }
- /*
- * Try the last two tiles one way round. If that fails, swap
- * them.
- */
- tiles[x1] = p1;
- tiles[x2] = p2;
- if (perm_parity(tiles, n) != 0) {- tiles[x1] = p2;
- tiles[x2] = p1;
- assert(perm_parity(tiles, n) == 0);
- }
+ /* If we didn't `continue', we've found an OK move to make. */
+ 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.
+ */
+ if (direction < 0) {+ start += (len-1) * offset;
+ offset = -offset;
+ }
+ tmp = tiles[start];
+ for (j = 0; j+1 < len; j++)
+ tiles[start + j*offset] = tiles[start + (j+1)*offset];
+ tiles[start + (len-1) * offset] = tmp;
+ }
+
+ } else {+
+ used = snewn(n, int);
+
+ for (i = 0; i < n; i++) {+ tiles[i] = -1;
+ used[i] = FALSE;
+ }
+
+ /*
+ * If both dimensions are odd, there is a parity
+ * constraint.
+ */
+ if (params->w & params->h & 1)
+ stop = 2;
+ else
+ stop = 0;
+
+ /*
+ * Place everything except (possibly) the last two tiles.
+ */
+ for (x = 0, i = n; i > stop; i--) {+ int k = i > 1 ? random_upto(rs, i) : 0;
+ int j;
+
+ for (j = 0; j < n; j++)
+ if (!used[j] && (k-- == 0))
+ break;
+
+ assert(j < n && !used[j]);
+ used[j] = TRUE;
+
+ while (tiles[x] >= 0)
+ x++;
+ assert(x < n);
+ tiles[x] = j;
+ }
+
+ if (stop) {+ /*
+ * Find the last two locations, and the last two
+ * pieces.
+ */
+ while (tiles[x] >= 0)
+ x++;
+ assert(x < n);
+ x1 = x;
+ x++;
+ while (tiles[x] >= 0)
+ x++;
+ assert(x < n);
+ x2 = x;
+
+ for (i = 0; i < n; i++)
+ if (!used[i])
+ break;
+ p1 = i;
+ for (i = p1+1; i < n; i++)
+ if (!used[i])
+ break;
+ p2 = i;
+
+ /*
+ * Try the last two tiles one way round. If that fails,
+ * swap them.
+ */
+ tiles[x1] = p1;
+ tiles[x2] = p2;
+ if (perm_parity(tiles, n) != 0) {+ tiles[x1] = p2;
+ tiles[x2] = p1;
+ assert(perm_parity(tiles, n) == 0);
+ }
+ }
+
+ sfree(used);
}
/*
@@ -276,7 +380,6 @@
ret[retlen-1] = '\0'; /* delete last comma */
sfree(tiles);
- sfree(used);
return ret;
}
@@ -361,6 +464,7 @@
assert(!*p);
state->completed = state->movecount = 0;
+ state->movetarget = params->movetarget;
state->used_solve = state->just_used_solve = FALSE;
state->last_movement_sense = 0;
@@ -378,6 +482,7 @@
memcpy(ret->tiles, state->tiles, state->w * state->h * sizeof(int));
ret->completed = state->completed;
ret->movecount = state->movecount;
+ ret->movetarget = state->movetarget;
ret->used_solve = state->used_solve;
ret->just_used_solve = state->just_used_solve;
ret->last_movement_sense = state->last_movement_sense;
@@ -816,10 +921,14 @@
if (state->used_solve)
sprintf(statusbuf, "Moves since auto-solve: %d",
state->movecount - state->completed);
- else
+ else {sprintf(statusbuf, "%sMoves: %d",
(state->completed ? "COMPLETED! " : ""),
(state->completed ? state->completed : state->movecount));
+ if (state->movetarget)
+ sprintf(statusbuf+strlen(statusbuf), " (target %d)",
+ state->movetarget);
+ }
status_bar(fe, statusbuf);
}
--- a/twiddle.c
+++ b/twiddle.c
@@ -39,6 +39,7 @@
int w, h, n;
int rowsonly;
int orientable;
+ int movetarget;
};
struct game_state {@@ -48,7 +49,7 @@
int completed;
int just_used_solve; /* used to suppress undo animation */
int used_solve; /* used to suppress completion flash */
- int movecount;
+ int movecount, movetarget;
int lastx, lasty, lastr; /* coordinates of last rotation */
};
@@ -59,6 +60,7 @@
ret->w = ret->h = 3;
ret->n = 2;
ret->rowsonly = ret->orientable = FALSE;
+ ret->movetarget = 0;
return ret;
}
@@ -108,6 +110,7 @@
ret->w = ret->h = atoi(string);
ret->n = 2;
ret->rowsonly = ret->orientable = FALSE;
+ ret->movetarget = 0;
while (*string && isdigit(*string)) string++;
if (*string == 'x') {string++;
@@ -124,6 +127,10 @@
ret->rowsonly = TRUE;
} else if (*string == 'o') {ret->orientable = TRUE;
+ } else if (*string == 'm') {+ string++;
+ ret->movetarget = atoi(string);
+ while (string[1] && isdigit(string[1])) string++;
}
string++;
}
@@ -145,7 +152,7 @@
config_item *ret;
char buf[80];
- ret = snewn(6, config_item);
+ ret = snewn(7, config_item);
ret[0].name = "Width";
ret[0].type = C_STRING;
@@ -175,11 +182,17 @@
ret[4].sval = NULL;
ret[4].ival = params->orientable;
- ret[5].name = NULL;
- ret[5].type = C_END;
- ret[5].sval = NULL;
+ ret[5].name = "Number of shuffling moves";
+ ret[5].type = C_STRING;
+ sprintf(buf, "%d", params->movetarget);
+ ret[5].sval = dupstr(buf);
ret[5].ival = 0;
+ ret[6].name = NULL;
+ ret[6].type = C_END;
+ ret[6].sval = NULL;
+ ret[6].ival = 0;
+
return ret;
}
@@ -192,6 +205,7 @@
ret->n = atoi(cfg[2].sval);
ret->rowsonly = cfg[3].ival;
ret->orientable = cfg[4].ival;
+ ret->movetarget = atoi(cfg[5].sval);
return ret;
}
@@ -317,24 +331,42 @@
* and simply shuffle the grid by making a long sequence of
* randomly chosen moves.
*/
- total_moves = w*h*n*n*2 + random_upto(rs, 1);
- for (i = 0; i < total_moves; i++) {- int x, y;
+ total_moves = params->movetarget;
+ if (!total_moves)
+ total_moves = w*h*n*n*2 + random_upto(rs, 2);
- x = random_upto(rs, w - n + 1);
- y = random_upto(rs, h - n + 1);
- do_rotate(grid, w, h, n, params->orientable,
- x, y, 1 + random_upto(rs, 3));
+ do {+ int oldx = -1, oldy = -1, oldr = -1;
- /*
- * Optionally one more move in case the entire grid has
- * happened to come out solved.
- */
- if (i == total_moves - 1 && grid_complete(grid, wh,
- params->orientable))
- i--;
- }
+ for (i = 0; i < total_moves; i++) {+ int x, y, r;
+ 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);
+
+ /*
+ * 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.
+ */
+ 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;
+ }
+ }
+ } while (grid_complete(grid, wh, params->orientable));
+
/*
* Now construct the game seed, by describing the grid as a
* simple sequence of integers. They're comma-separated, unless
@@ -410,6 +442,7 @@
state->completed = 0;
state->used_solve = state->just_used_solve = FALSE;
state->movecount = 0;
+ state->movetarget = params->movetarget;
state->lastx = state->lasty = state->lastr = -1;
state->grid = snewn(wh, int);
@@ -445,6 +478,7 @@
ret->orientable = state->orientable;
ret->completed = state->completed;
ret->movecount = state->movecount;
+ ret->movetarget = state->movetarget;
ret->lastx = state->lastx;
ret->lasty = state->lasty;
ret->lastr = state->lastr;
@@ -1021,10 +1055,14 @@
if (state->used_solve)
sprintf(statusbuf, "Moves since auto-solve: %d",
state->movecount - state->completed);
- else
+ else {sprintf(statusbuf, "%sMoves: %d",
(state->completed ? "COMPLETED! " : ""),
(state->completed ? state->completed : state->movecount));
+ if (state->movetarget)
+ sprintf(statusbuf+strlen(statusbuf), " (target %d)",
+ state->movetarget);
+ }
status_bar(fe, statusbuf);
}