Sudoku

Blogging after a long time, much due to lack of interest and a bit of time factor as these six months were the most happening months of the engineering life. Much has happened that is worth noticeable but that would merit a separate post.

Today my interest is SuDoKu - A long time passion for me.I have been developing a cpp code that would generate and solve a variety of types of SuDoKu problems in a fast and efficient way.I succeeded in developing a code that would satisfy my requirement a long time ago.i.e 3-4 months back. But now I am more interested in improving the code and its response time in case of solvers.

Interestingly, during any operation in SuDoKu one needs to check the validity of the number to be input at the given place in the 9X9 grid. This check involves checking 9 blocks for row,column and 3X3 block respectively. This would require 27 iterations for each check! This was the major time consuming part of the code. I started using different methods for decreasing the response time.

As I was using guessing along with logical analysis, solution time was never going to be constant.
So in order to obtain mean solution time, I devised a function to run the code on a standard problem 10,000 times and then take the mean. As for the need for reduction of the iterations, I used indexing of the positions in the SuDoKu grid. When any number is entered at any position it would trigger a flag index that contains information for a particular number at a particular position. This brought the number of iterations from 27 to just 3! But it cost 3 times as much memory. But from the context of overall memory requirement of program, it was drop in the ocean.

So I started chasing the fastest solution time with (+/-)5% error. Now I am proud to have succeeded in developing a code that solves the Hardest SuDoKu Puzzle. Now for an average sudoku puzzle it gives mean solution time of 9 millisecond on a P4-2.88 G Hz machine. Other factors other than that of processor speed may affect the time but that would be within 5% error range. So I feel pretty satisfied with my achievement.

You can get the source code here.

Most of the goals about SuDoKu other than cross platform compatibility(much due to lack of interest in learning new graphics library) have been fulfilled. So now it is full-stop to SuDoKu and I am all geared up for a new challenge. After all, only goal is to Excel!