Today is about a little pet work I did some years ago. In short is about a Sudoku generator I did in Javascript. The interest in doing it arise because at that time Sudoku was a kind of virus. It was spread everywhere. In coffee shops, bars, restaurants, libraries, metro and airports. Whenever you saw someone sit down the probability to be playing Sudoku was sky high. Apart from all the junkie strangers, there was a very special one, my mother. Yes this pretty old lady loves to sit on bed and go straight to newspaper last page. I remember the sad face whe she completed the game, pretty much saying something like this oh well, lets wait another week for one more game. I remember that in that year I gave her a book full of Sudoku game instances. That was like feeding a starving person or giving heroine to someone that was missing some days of fuel. These were funny days, for her at least. That magazine full of Sudoku makes me see that should be a automated way of creating suduku instances. At that time I just didn't figure how. That's what this post is all about. Those days I spend trying to find a way to automate the generation of Sudoku games.
The final result of that journey can be seen here sudoku generator, for those more intereste in the internal approach the source code is here. But lets back again for a moment and start to describe exactly what we mean by Sudoku game. I'm pretty sure I will not teach you anything at this time but at least lets remember what sudoku is all about.
Wikipedia defines sudoku as
Sudoku is a logic-based combinatorial number-placement puzzle The
objective is to fill a 9×9 grid with digits so that each
column, each row, and each of the nine 3×3 sub-grids that
compose the grid (also called "boxes", "blocks", "regions",
or "sub-squares") contains all of the digits from 1 to 9.
The puzzle setter provides a partially completed grid,
which for a well-posed puzzle has a unique solution.
Well that's a pretty accurate definition. If you are a visual person like me you'll appreciate some light to clarify the formality above, so there's an example
So the big question, at least at that time and for me, was. How can I generate random instances? At first this seams a very intractable problem. First of all it was not clear for me how to create deterministically just one instance, let alone random ones. But as every problem the secret is always try to find patterns we can exploit. So with that in mind I start the digging to find if I could find a rule by which I could, in a pretty certain way, build an apparently random sudoku. After few days struggling with this problem I could not find anything useful. So I start to think if there is possible to find a solution in a different way. I thought that if I was immortal I would have plenty of time for me. One approach that could be plausible, for all those eternal souls, would be to place numbers in a random way and each time I drop a number in the board I would check if all the rules still hold. If yes I would repeat this step, otherwise I would select another number and another place and repeat the process. If all goes well after some months of trying I would end up with a sudoku instance. It would be terribly boring but, hey, it would mean nothing in my life timeline. There's only one catch. It is, nevertheless, possible that after some steps there is simple no solution because we end up with a impossible system. The same kind of problems when you are trying to solve a system of equations and you find that by substituting some parameters you'll end up with a bunch of impossible equalities. This means that some of the steps were plain wrong and needed to be removed. How to solve this? Well, again, If I were imortal I would create a rule (technically an heuristic) that if I could not improve my sudoku state for over an year then I would remove the last valid step and replace for another one. Then it hits me, this is what people call backtracking in computer science. And curiously today you even have an example of this approach to tackle the sudoku problem, that was not true those days.
So the next step was to put all these ideas into code, you can check the entire generator is more or less 250 lines of code and the core is in the next piece of code
Sudoku.prototype.buildSudoku=function(){
this.clear();
var dx=Sudoku.DIMX;
var dy=Sudoku.DIMY;
var num;
var maxit=100;
var maxitt=1000;
var it=0;
var step;
var itt=0;
for(var i=0;i<dx*dy;){
it++;
num=Math.floor(Math.random() * 9)+1;
if(
this.checkLine(i,num)
&& this.checkColum(i,num)
&& this.checkBlock(i, num)
){//
it=0;
this._ mat[i]=num;
i++;
}
if(it>maxit){ //backtrack steps
pos=Math.max(0,i-Sudoku.BACK_TRACK_STEP);
this.clearLastValues(i, pos);
i=pos; //returns back
it=0; //reset the counter
itt++;
}
if(itt>maxitt){
i=maxitt;
}
}
if(i==maxitt)
return false;
return true;
};
So this sums all the ideas that were described. So the idea is to iterate, over a for loop, during a max number of times until we find a solution. We keep two counters, one of the counters track the number of tries for a specific cell, another keeps track of the all number of tries. I created the second counter to quick fail and to be able to start again. So the first counter has a maximum of 100 tries, if this threshold is hit we backtrack one step. The second counter with current value of 1000, serves as a treshold to the overall atempt number. If after 1000 steps we didn't find a valid sudoku matrix we exit and give this buildSudoku atempt as a failed one. Then we use this method here
for(var i=1;i<=nsud;i++){
while(!s.buildSudoku());
html+=s.getSudoku();
.
.
.
}
To create the requested number of Sudoku instances. The funny part of this algorithm is that it is not deterministic. I don't know what is the output or even if there will be one. In many cases the generator will return false values meaning that it is a degenerate solution, which is a fancy term to say big failure, there's no solution. There is not even guarantee for non repeated values, it is possible to build one by checking the values for the several solutions gathered but it is not an interesting approach since the probability for that to happen is ridiculously small, so again I have faith here. This turns out to be a very interesting solution because it is not even a solution. It is wishful thinking backed up by probability values that turns out to work pretty fine in reality. If someone ask me how I generate Sudoku games the real answer is I don't know, I just have faith it will eventually sort it out...