Package: qqwing
Version: 1.3.4-1.1+b1
Severity: important
Tags: patch
X-Debbugs-Cc: krzpyrk...@gmail.com
Dear Maintainer,
Current version of qqwing uses srand(time(0)) and rand() as a way to
generate the board. It makes running multiple instances of the program
in parallel for faster sudoku generation impossible, because all are
started in the same second, generating exactly the same sequence of
numbers, and as a result, sequence of boards.
The solution is to replace the randomness based on time with one based on
a truly random seed, and rand() with a random generator that does not
rely on a global state like srand.
My patch makes use of several C++11 features such as std::random_device,
std::uniform_int_distribution and std::shuffle that are state of the art
solutions to the aforementioned issue.
diff --git a/main.cpp b/main.cpp
index 13a4355..ae1def7 100644
--- a/main.cpp
+++ b/main.cpp
@@ -200,9 +200,6 @@ int main(int argc, char *argv[]){
return 1;
}
- // Initialize the random number generator
- srand ( unsigned ( time(0) ) );
-
// If printing out CSV, print a header
if (printStyle == SudokuBoard::CSV){
if (printPuzzle) cout << "Puzzle,";
diff --git a/qqwing.cpp b/qqwing.cpp
index ed18ff0..a923398 100644
--- a/qqwing.cpp
+++ b/qqwing.cpp
@@ -23,6 +23,7 @@
#include <cstdlib>
#include <iostream>
+#include <algorithm>
#include "qqwing.hpp"
@@ -109,6 +110,7 @@ namespace qqwing {
* Create a new Sudoku board
*/
SudokuBoard::SudokuBoard() :
+ rand_generator(random_device{}()),
puzzle ( new int[BOARD_SIZE] ),
solution ( new int[BOARD_SIZE] ),
solutionRound ( new int[BOARD_SIZE] ),
@@ -1528,18 +1530,13 @@ namespace qqwing {
/**
* Shuffle the values in an array of integers.
*/
- void shuffleArray(int* array, int size){
- {for (int i=0; i<size; i++){
- int tailSize = size-i;
- int randTailPos = rand()%tailSize+i;
- int temp = array[i];
- array[i] = array[randTailPos];
- array[randTailPos] = temp;
- }}
+ void SudokuBoard::shuffleArray(int* array, int size){
+ std::shuffle(array, array + size, rand_generator);
}
- SudokuBoard::Symmetry getRandomSymmetry(){
- switch (rand()%4){
+ SudokuBoard::Symmetry SudokuBoard::getRandomSymmetry(){
+ std::uniform_int_distribution<int> dist(0, 3);
+ switch (dist(rand_generator)){
case 0: return SudokuBoard::ROTATE90;
case 1: return SudokuBoard::ROTATE180;
case 2: return SudokuBoard::MIRROR;
diff --git a/qqwing.hpp b/qqwing.hpp
index 54a7872..9a9c752 100644
--- a/qqwing.hpp
+++ b/qqwing.hpp
@@ -24,6 +24,7 @@
#include <string>
#include <vector>
+ #include <random>
namespace qqwing {
@@ -120,6 +121,13 @@
~SudokuBoard();
private:
+ /**
+ * Random number generator seeded with true
randomness
+ * in the constructor. Replacement for
srand(time(0)).
+ * Now, multiple instances of the program
running
+ * in parallel generate different boards.
+ */
+ std::mt19937 rand_generator;
/**
* The 81 integers that make up a sudoku puzzle.
* Givens are 1-9, unknowns are 0.
@@ -230,6 +238,8 @@
bool arePossibilitiesSame(int position1, int
position2);
void addHistoryItem(LogItem* l);
void shuffleRandomArrays();
+ void shuffleArray(int* array, int size);
+ SudokuBoard::Symmetry getRandomSymmetry();
void print(int* sudoku);
void rollbackNonGuesses();
void clearPuzzle();
