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
image from My racing tactic is obvious: I press the accelerator and I rush

My racing tactic is obvious: I press the accelerator and I rush

Appliqué sans discernement, le backtracking peut s’avérer redoutable de complexité, tant la voie qui mène à la solution peut être longue, tortueuse, pleine d’ornières, de pièges et de détours dans lesquels se perdre indéfiniment. Maitriser le problème permet néanmoins de tracer un chemin beaucoup plus direct vers la solution, nettoyé de tous ses obstacles et voies de traverses, et permettant finalement un gain de temps qu’aucune autre optimisation ou puissance de calcul herculéenne ne pourra jamais compenser. Grâce à la méthode exposée dans l’article précédent, nous avons à disposition une autoroute filant pratiquement en ligne droite vers la solution. Mais cela veut-il dire pour autant que nous désirons nous trainer le long de ce chemin à bord d’un vieux tacot fumant et tout cabossé ?

Follow