The Twiddle shuffling algorithm was theoretically parity-unbalanced:

it performed a fixed number of shuffling moves, and on each one it
had a 2/3 chance of flipping the permutation parity and a 1/3 chance
of keeping it the same. Markov analysis shows that over a run of
1500-odd shuffle moves this will end up being an undetectably small
actual bias in the parity of the generated grid, but it offends my
sense of pedantry nonetheless so here's a small change to make the
number of shuffling moves itself have randomly chosen parity. The
parity of generated grids should now be _exactly_ 50:50.

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

diff --git a/twiddle.c b/twiddle.c
index d67dc40..5209606 100644 (file)
--- a/twiddle.c
+++ b/twiddle.c
@@ -317,7 +317,7 @@ static char *new_game_seed(game_params *params, random_state *rs,
      * and simply shuffle the grid by making a long sequence of
      * randomly chosen moves.
      */
-    total_moves = w*h*n*n*2;
+    total_moves = w*h*n*n*2 + random_upto(rs, 1);
     for (i = 0; i < total_moves; i++) {
        int x, y;