Encapsulating

Sudoku v2.2

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;
return ret;
}

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.

To do:

– 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
– Threads

My aim was to be faster than this program, which I’ve done. Now I’m targeting this program.

Version history:

v2.2
v2

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s