Le sudoku, est un jeu en forme de grille dont le but est de la remplir avec une série des chiffres (ou des lettres ou des symboles) tous différents qui ne se trouvent jamais plus d’une fois sur la même ligne, dans la même colonne ou dans la même région (également appelée «bloc», «groupe», «secteur »ou «sous-grille»), Puisque le jeu est destiné aux enfants, et pour simplifier, la forme de sudoku sera une grille de 4 régions, les régions étant alors des carrés de 2x2 à remplir par des objets qui attirent l’attention de l’enfant.
Dans un premier temps, on s’intéresse à la génération de grilles bien formées (les quelles il existe au moins une solution). Pour cela, il s’agit de générer des grilles complètes vérifiant toutes les conditions et en suite de retirer certaines valeurs. Pour que le jeu soit intéressant, il faut au moins retirer la moitié des valeurs des cases. Une première approche pourra consister à générer aléatoirement des grilles et ensuite à vérifier qu’elle vérifie bien les conditions pour être un sudoku valide. Dans un second temps, on pourra expérimenter avec des algorithmes un peu plus efficaces pour construire la grille. On évitera par exemple de mettre plusieurs fois la même valeur sur la même ligne.
Pour résoudre le sudoku en basant sur l’état initiale donnée on commencera par implémenter un premier algorithme consistant simplement à explorer toutes les possibilités et de remplir de plus en plus de cases de la grille tout en respectant les contraintes. Quand on se trouve bloqué, c’est à dire qu’aucune nouvelle case ne peut être complétée sans violer les contraintes, on revient au dernier embranchement non encore emprunté dans l’arbre des possibilités.
