L’autre jour, un ami m’a lancé le défi de réaliser un solveur de Sudoku plus rapidemment qu’une personne ne mettrait pour le résoudre. J’ai mis à peu près autant de temps :-P. L’avantage, c’est que celui-ci résoud les Sudoku de n’importe quelle taille, même les rectangulaires. De plus, il est rapide (il résoud un Sudoku vide de 16×16 instantanément).
Bref, pour faire court, voici l’algorithme employé:
- trouver la case avec le moins de possibilités (en enployant les lignes, les colonnes et les carrés)
- si cette case a une seule possibilité, la remplir avec le seul chiffre possible, et retourner en 1.
- sinon, prendre une possibilité au hasard, et créer un nouveau problème (récursion). Si on trouve une solution, garder cette possibilité. Sinon, en prendre une autre.
Dans la foulée, voici le code source téléchargeable, vous pouvez en faire ce que vous voulez
Solveur.cpp