Lu une heure après le post, je trouve ça assez clair.
J'aurais juste soumis le mot récursif, de récursion ou récursivité pour backtracking, ça peut éclaircir un poil plus.
Pour les 8 reines, je ne sais pas pourquoi mais j'y pensais récemment, et en ai ré-entendu parler tout autour de moi au début décembre ... Certainement des réminiscences suite à la réception des invits pour prologin (faudrait qu'ils arrêtent, j'ai plus l'âge pour ces bêtises :)
Pour illustrer, y a en gros trois grandes méthodes pour déterminer au moins une solution au problème :
. essayer toutes les combinaisons de manière déterminée, si par chance, on tombe sur une solution, c'est gagné => KISS mais lent, lent, lent, on devrait trouver toutes les solutions.
. partir de l'idée qu'il est possible de poser une reine sur une nouvelle ligne seulement si cela était possible pour la ligne précédente (aspect récursif de la chose) => plus rapide que précédemment, trouve toutes les solutions ...
. poser les 8 reines sur l'échiquier et les déplacer selon les minimas de contraintes => permet de trouver vite UNE solution, pour toutes les trouver, c'est une autre affaire ...
[^] # Re: quelqu'un ?
Posté par jerome . En réponse à la dépêche Interview de Richard Stallman sur KernelTrap. Évalué à 3.
J'aurais juste soumis le mot récursif, de récursion ou récursivité pour backtracking, ça peut éclaircir un poil plus.
Pour les 8 reines, je ne sais pas pourquoi mais j'y pensais récemment, et en ai ré-entendu parler tout autour de moi au début décembre ... Certainement des réminiscences suite à la réception des invits pour prologin (faudrait qu'ils arrêtent, j'ai plus l'âge pour ces bêtises :)
Pour illustrer, y a en gros trois grandes méthodes pour déterminer au moins une solution au problème :
. essayer toutes les combinaisons de manière déterminée, si par chance, on tombe sur une solution, c'est gagné => KISS mais lent, lent, lent, on devrait trouver toutes les solutions.
. partir de l'idée qu'il est possible de poser une reine sur une nouvelle ligne seulement si cela était possible pour la ligne précédente (aspect récursif de la chose) => plus rapide que précédemment, trouve toutes les solutions ...
. poser les 8 reines sur l'échiquier et les déplacer selon les minimas de contraintes => permet de trouver vite UNE solution, pour toutes les trouver, c'est une autre affaire ...