I’ve been working more on my Sudoku generator for the past couple weeks and I’ve made some leaps. v2.2 can generate around 150 000 puzzles every 10 seconds (one every 0.000066667 seconds), and it’s not fully optimized – my code wastes cycles. You can view the source here.
I’ve made a number of improvements to the code, with an immediate note to my power function. In v2 my power function looked like:
int power(int a, int b)
int ret = 1, i=0;
for(i=0;i<b;i++) ret = ret * a;
Now it looks like:
int power(int a)
return 1 << (a-1);
My code now creates rows at a time instead of blocks, which is a lot less wasteful cycle-wise. In v2, if one part of a 9×3 (3 block) grid was wrong, it would start again. With v2.2, it only starts from the beginning of the row. This isn’t perfect, but it is a thousand times better than v2. I also changed the sequential approach to something more exotic, by generating numbers per block. So the first number in the first block, then the first number in the second block and so on. This seemed to drastically reduce conflicts which would force my program to start from the beginning, increasing the time it takes to generate grids.
– Kill tmp array in favor of direct input to mat array – should increase performance
– Try inputting first number in first block, second number in second block, third number in third block and so on
– Try generating diagonally