Before we begin, I have to confess: I don’t like crosswords. I understand that they can be interesting brain challenges but, from my point of view, they require too much general knowledge or verbal skills (which I do not have) and not enough logic. However, I do like logical riddles and that’s probably why I would never have written this article without the help of Sudoku.

All the source code related to this article is available on GitHub. For additional explanation, just keep reading.
image from The Long Way of Backtracking

The Long Way of Backtracking

Although the origin of Sudoku goes back as far as the last century, a surge of popularity can be noted during the year 2005. I remember it particularly well, because it was at that time that I discovered them while I was going to winter sports. I guess I had to come across a collection of grids at a gas station, during one of our stops to our destination. This totally new concept for me occupied me some time, the time to solve some grids.
Follow
image from The Right Way to Pave the Grid

The Right Way to Pave the Grid

The method used previously to fill the grid was excessively naive, because it is quite catastrophic to wait the grid is full before to test the validity of the solution. The problem being combinatorial, the exponential nature of the combinations of words appears as so many branches and twigs subdividing frightfully quickly. So it is better to realize as soon as possible that the chosen path is rather a dead end, so as to cut off the dead branch as soon as possible and avoiding to lose valuable computing time in the depths of its tree.

Follow