Working on a simple Sudoku solver, I’ve run across a memory-related issue, which isn’t uncommon when developing C/C++ programs, but in my case it seemed somewhat weird since I haven’t been doing any dynamic memory allocations or using pointers explicitly.

After spending some time searching for the bug, I realized that the problem lied in the array shuffling code, which was similar to the code below:

#include <vector>
#include <algorithm>
 
...
 
bool random_cmp(const int a, const int b)
{
    return (rand() % 2 == 0);
}
 
...
 
vector<int> a;
sort(a.begin(), a.end(), random_cmp);

After running it a couple of times in the loop, we get a “double free or corruption” error with a couple dozen lines long backtrace and memory map (program was compiled with G++ 4.1.3). The reason of this, at the first glance, strange behaviour was the fact that comparison function must be deterministic (if a < b and b < c then a < c must be true as well). In the other case, the sort() behaviour is undefined, which it really was in our case. :)

This just teaches me once more to read the documentation carefully before doing something.

P. S. In the end, I used a simple shuffling algorithm, suggested by Sergij Tyhanskij:

void shuffle(vector<int> nums)
{
    int a, b, count = nums.size();
    for (int i = 0; i < count; i++)
    {
        a = rand() % count;
        b = rand() % count;
        swap(nums[a], nums[b]);
    }
}

As for the Sudoku solver, I have added a dedicated page for it and updated this website projects section.