ref: 38c1f9b7028c4405e1e8145bc6639e33ffce147b
parent: 1c77e0df94e40f741934c9c4852136d6c2f32ced
author: Simon Tatham <anakin@pobox.com>
date: Wed May 4 08:52:51 EDT 2005
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. [originally from svn r5742]
--- a/twiddle.c
+++ b/twiddle.c
@@ -317,7 +317,7 @@
* 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;