Travaux : Php
Résolveur de sudoku en PHP (dans Php, le 29/12/2009 à 22h 56min)
Petit retour dans le temps avec ce script retrouvé au fond de mon disque dur, et datant de Mars 2006. C'est mes premiers pas dans l'algorithmique, et dans l'utilisation du brute-force pour résoudre un problème : on test toutes les possibilités, jusqu'à ce qu'on trouve la solution.
Bien sûr, on respecte tout le temps les règles du sudoku, ce qui nous permet de largement limiter les essais. Cependant, il arrive souvent que l'on se retrouve dans une configuration où l'on ne peut plus rajouter de chiffre sans violer une des règles; dans ce cas, le sudoku est bloqué, il faut alors revenir en arrière et essayer une autre possibilité. On peut donc assimiler la recherche de la solution au parcours d'un arbre de possibilités en profondeur.
Avec le recul, je me dis qu'il faudrait reprendre au moins la moitié de ce script, qui me semble maintenant bien compliqué et bien mal pensé (surtout au niveau de la représentation des données et de l'organisation de l'algorithme; je pense qu'il y a beaucoup de calculs redondants), mais je n'ai pas forcément le temps ni l'envie.
Vous pourrez trouver ici :
Voilà, vous pourrez maintenant épater vos amis en résolvant n'importe quel sudoku !
Petit retour dans le temps avec ce script retrouvé au fond de mon disque dur, et datant de Mars 2006. C'est mes premiers pas dans l'algorithmique, et dans l'utilisation du brute-force pour résoudre un problème : on test toutes les possibilités, jusqu'à ce qu'on trouve la solution.
Bien sûr, on respecte tout le temps les règles du sudoku, ce qui nous permet de largement limiter les essais. Cependant, il arrive souvent que l'on se retrouve dans une configuration où l'on ne peut plus rajouter de chiffre sans violer une des règles; dans ce cas, le sudoku est bloqué, il faut alors revenir en arrière et essayer une autre possibilité. On peut donc assimiler la recherche de la solution au parcours d'un arbre de possibilités en profondeur.
Avec le recul, je me dis qu'il faudrait reprendre au moins la moitié de ce script, qui me semble maintenant bien compliqué et bien mal pensé (surtout au niveau de la représentation des données et de l'organisation de l'algorithme; je pense qu'il y a beaucoup de calculs redondants), mais je n'ai pas forcément le temps ni l'envie.
Vous pourrez trouver ici :
- la source php
- une démonstration du script : la grille de test proposée par défaut fait planter le script chez Free, je pense qu'il bouffe trop de mémoire. Quand je dis que ce n'est pas optimisé...
Voilà, vous pourrez maintenant épater vos amis en résolvant n'importe quel sudoku !