Bug#1013230: qqwing: Improved random number generation to allow running multiple instances of the program in parallel.

[Simon McVittie]

Control: retitle -1 qqwing: generates same boards if multiple instances are run during the same second
Control: severity -1 normal
Control: tags -1 + upstream

On Sun, 19 Jun 2022 at 16:23:02 +0200, Krzysztof Aleksander Pyrkosz wrote:
> 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.

Unfortunately this patch resulted in an ABI break which crashed
gnome-sudoku, so it had to be reverted. If you are interested in improving
(lib)qqwing's random number generation, I would recommend doing that
upstream rather than as a Debian-specific change.

One simple way to avoid the symptom that you originally reported would be
to continue using the global random number generator rand(), but change the
seed passed to srand() to one that is unique to a particular run, perhaps
taken from from getentropy(), or perhaps taking into account factors like
getpid() or applicationStartTime (which is in microseconds, so is much less
likely to be the same for two runs).

Or the std::mt19937 object could perhaps be global or thread-local,
depending what the thread-safety requirements of libqqwing are (I don't
know what those requirements are, and I'd suggest consulting upstream to
find out).

Or if it's absolutely necessary to break the ABI by making the data
structure larger, then that should be done in coordination with upstream
and accompanied by a SONAME bump, so that dependent programs will not crash
(they will use and require the old version until they're recompiled, after
which they'll use and require the new version).

Thanks,
    smcv