Série 4: Le problème des n-reines, méthode Las-Vegas et hybride

Introduction

Le problème des n-reines est un casse-tête se jouant sur un échiquier de taille nxn. Il s'agit de placer n pièces (les reines) sur l'échiquier, de manière à ce qu'aucune n'en menace une autre. Deux reines se menacent lorsqu'elles se trouvent soit sur la même ligne, la même colonne ou la même diagonale.

Ce problème se trouve être d'une complexité non-polynomiale, et est rapidement irrésoluble par un humain à partir d'une certaine taille (essayez-voir le cas n=8!).

Une approche simple: le backtracking

Le backtracking est une manière simple, mais néanmoins relativement efficace d'explorer toutes les possibilités de placer les reines, et d'en trouver une qui résolve le problème. Dans cette méthode, on place la première reine à un endroit “quelconque” (qu'il soit probabiliste ou déterministe) dans la première colonne. La deuxième reine est ensuite placée dans la deuxième colonne dans une des cases possibles, à partir de laquelle elle ne menace pas la première. Ce procédé est ensuite poursuivi de colonne en colonne, produisant à chaque fois une configuration dans laquelle aucune des reines n'en menace une autre. Vient en jeu ensuite un procédé récursif au cours duquel, à chaque fois qu'on est coincé, c'est-à-dire n'arrive plus à placer une nouvelle reine, on revient en arrière d'une colonne pour tester un autre placement pour la reine qui s'y trouve (et si tous les placements ont déjà été testés, on revient encore en arrière etc.).

Une approche probabiliste: l'algorithme Las Vegas

Une manière plus rapide de converger vers une solution peut consister en une recherche probabiliste de l'espace des configurations. Dans la méthode Las Vegas, le placement des reines parmis les cases possibles dans une colonne est toujours choisi de manière probabiliste. En outre, on ne revient jamais en arrière comme dans le backtracking. Dès qu'on est coincé, on recommence à la colonne 0.

Le meilleur des deux mondes: l'algorithme hybride

Le désavantage de la méthode Las Vegas, est qu'on risque de jeter une solution qui est presque bonne, qui a donc presque convergé. Pour éviter un tel effet, on la combine avec le backtracking. A partir d'une certaine colonne k, k<n donc, au lieu de poursuivre le Las Vegas, on termine par du backtracking pour déterminer de manière exhaustive si la configuration actuelle permet une solution.

Exercice

Implémentez les trois méthodes et vérifiez quel est le problème le plus grand que vous arrivez à résoudre.

Solution