From: simon <simon@cda61777-01e9-0310-a592-d414129be87e>
Date: Wed, 4 May 2005 12:52:51 +0000 (+0000)
Subject: The Twiddle shuffling algorithm was theoretically parity-unbalanced:
X-Git-Url: https://git.distorted.org.uk/~mdw/sgt/puzzles/commitdiff_plain/4b0cf9034e4e73a42d48326ec6f6fca3023a0661

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
--- 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;