===== Recherche en force brute =====

Dans un jeu, on déploie l'arbre de toutes les options qui s'offrent à nous, comme si nous parcourions tous les univers parallèles découlant de nos choix. Une fois l'arbre parcouru, il ne reste qu'à choisir la meilleure option.

Le cas des jeux avec un adversaire -- morpion, échecs, puissance 4... -- sont plus difficiles car il faut tenir compte du choix de l'adversaire. Cet aspect est traité dans l'algorithme [[nsi:tds:jeux:minmax|min-max]].

Dans le cadre de ce projet, on souhaite rester plus simple et on envisage :
  * Le [[nsi:jeu:sudoku|sudoku]]
  * Le [[nsi:jeu:demineur|démineur]]
  * Le [[nsi:jeu:serpent|serpent]]


<WRAP tip>Il y a beaucoup de jeux de logiques comme le sudoku, libre à vous d'en choisir un autre.</WRAP>

===== Parcourir l'arbre des possibles =====

Les jeux proposés sont des jeux de grille à compléter. Je vais donc parler de grille. Vous pouvez adapter aux cas où ce n'est pas une grille. Prenons l'exemple d'un jeu consistant à remplir des cases en blanc ou en noir.

{{ :nsi:tds:jeux:grille_1.png?direct&400 |}}

Les chiffres à gauche et en haut indiquent le nombre de cases pleines (en noir) qui devraient se trouver sur les lignes / colonnes correspondantes. Les cases jaunes sont celles pour lesquelles on n'a pas encore décidé. À la fin, on veut remplir les cases en blanc ou en noir tout en respectant la contrainte du jeu (nombre de cases noirs dans les lignes et colonnes)

==== Un module pour le jeu ====

On va devoir manipuler la grille de jeu :
  * chercher les cases encore non traitées,
  * chercher les possibilités pour ces cases,
  * vérifier qu'un choix est valable,
  * vérifier si la grille est terminé...

Dans l'exemple, voici le genre de méthodes dont nous aurions besoin :
<code python>
# module grille.py

class Grille
    def __init__(self, top, left):
        '''
        top: liste donnant les chiffres sur le dessus
        left: liste donnant les chiffres sur la gauche
        '''
    
    def set_full(self, line, col):
        '''
        met la case line, col en noir
        '''
    
    def set_empty(self, line, col):
        '''
        met la case line, col en blanc
        '''
    
    def get_unknown_cell(self):
        '''
        renvoie les coordonnées d'une case dont on ne sait pas encore le contenu
        '''
    
    def is_finished(self):
        '''
        renvoie True si la grille est totalement remplie
        '''
    
    #etc.
</code>
        
==== Construction / parcours de l'arbre ====

On veut parcourir l'arbre des grilles possibles.

=== Initialisation de l'arbre ===

Au début, l'arbre ne comporte qu'une racine.

{{ :nsi:tds:jeux:grille_2.png?direct&200 |}}

=== Amorce du parcours ===

Suivant si on choisit un [[nsi:terminales:arbres:parcours|parcours en largeur ou en profondeur]], on utilise une pile ou une file. Pour l'exemple, j'utilise une **file** et c'est donc un parcours en **largeur**.

  * Création de la file
  * on place la grille A dans la file

=== Boucle ===

On procède selon le principe du parcours en largeur : Tant que la file n'est pas vide,

  * défiler le prochain nœud,
  * exécuter le traitement voulu sur le nœud,
  * enfiler les enfants de ce nœud

<WRAP important>Ici il faut faire le traitement avant d'enfiler les enfants car on parcours l'arbre en même temps qu'on le construit. Le traitement consiste justement à créer les enfants du nœud !</WRAP>

=== Traitement ===

Comme on vient de le signaler, le traitement consiste à construire l'arbre, c'est à dire les enfants du nœud :
  * chercher une case inconnue,
  * envisager les deux possibilités : case pleine (en noir) ou vide (en blanc)
  * ne garder que les possibilités valides
  * créer des nœuds enfants pour chacune de ces possibilités

{{ :nsi:tds:jeux:grille_3.png?direct&400 |}}


Et si le nœud en cours correspond à une grille terminée, il faut mettre cette grille de côté.

=== Fin ===

À mesure qu'elles s'allongent, les branches de l'arbre correspondent à des grilles de plus en plus pleines. Quand il n'y a plus de cases inconnues dans une grille, il ne peut plus y avoir d'enfant.

Donc, l'arbre finit par arrêter de grandir et le parcours s'arrête lui aussi.

Quand le parcours se termine, l'arbre n'a plus d'utilité. C'est la liste des grilles terminées et valides que l'on a mis de côté pendant le parcours qui va nous être utile.


Dans notre exemple, l'arbre va grandir et atteindre ceci :

{{ :nsi:tds:jeux:grille_4.png?direct&400 |}}

Vous pouvez noter que :
  * C n'a pas d'enfant parce qu'il n'y a pas moyen de remplir la case jaune suivante en respectant les contraintes.
  * B n'a qu'un enfant parce qu'en respectant les contraintes, seul le blanc est possible pour la prochaine case.
  * N et O sont des grilles terminées et valides. Se sont des solutions possibles au problème.

<WRAP tip>Les nœuds C et I étant des impasses, on pourrait arranger le programme en lui faisant supprimer progressivement ces branches inutiles. Ce serait important si le problème était volumineux et qu'il fallait économiser de la mémoire. Si le problème reste assez petit et que la mémoire n'est pas trop sollicitée, inutile de compliquer le programme.</WRAP>

==== La liste des solutions ====

Il se pourrait que la liste des solutions :
  * ne contiennent rien. Alors le problème n'a pas de solution. Le problème est mal conçu.
  * contienne exactement une solution. C'est le cas normal. Le problème est bien posé et n'a qu'une solution.
  * contienne plusieurs solutions. Le problème est mal construit. Par exemple, une grille de Sudoku bien construite n'admet qu'une solution.

Dans l'exemple, on est dans le 3e cas car il y a deux solutions.

<WRAP tip>Un parcours en profondeur produirait exactement le même résultat mais les nœuds sont parcourus dans un ordre différent ce qui peut avoir de l'importance :
  * parcours en largeur : A, B, C, D, E, F, G, H, I, J, K, L, M, N, O

Les solutions N et O sont trouvées quasiment en même temps.

  * parcours en profondeur : A, B, D, E, G, J, L, N, F, H, K, M, O, C

La solution N est trouvé très vite, O beaucoup plus tard.

Dans l'exemple de la grille, si nous pouvons supposer qu'il n'y a qu'une solution, on peut s'arrêter dès qu'on en a trouvé une et alors le parcours en profondeur permet de terminer plus vite. Mais ce n'est pas si évident en général. Le parcours en profondeur consiste à continuer sur son choix jusqu'au bout tandis que le parcours en profondeur consiste à examiner tous les choix en même temps. Si par chance le premier choix est le bon, le parcours en profondeur gagne. Mais ce n'est pas garanti !
</WRAP>