Introduction à l'algorithmique 15 - Les 8 reines

Hello! Nous voici déjà arrivé au 15^ème article sur l'algorithmique! Je vous propose de fêter ça avec un problème vraiment très populaire: Les 8 reines.

L'une des raisons de sa popularité est du fait qu'il est souvent utilisé en cours d'informatique pour introduire la récursivité... Ne croyez pas que ce problème soit simple pour autant! Surtout si la notion de récursivité est encore un peu vague pour vous.

Bon, rentrons dans le vif du sujet: les 8 reines. Le but de ce problème est de réussir à placer 8 reines d'un jeu d'échecs sur un échiquier classique (8x8 cases) sans que celles-ci ne puissent se menacer.

Pour ceux qui ne connaissent pas les règles des échecs: Chaque pièce se déplace d'une manière différente. La reine peut se déplacer du nombre de cases qu'elle désirs sur une rangée, colonne ou diagonale.

Exemple de solution:

J'ai trouvé sur le net un petit programme fait en JAVA qui permet de vraiment bien comprendre le déroulement de l'algorithme:

En bref: La fonction récursive empile les bons résultats au fur et à mesure qu'une reine supplémentaire peut être placée, a la première erreur, l'algorithme dépile le résultat de la fonction.

On appelle ce type d'algorithme "programmation par contrainte"

Bon, on s'y met?

Pseudo-code de la fonction principale:

DéBUT  lignes <- [0, 0, 0, 0, 0, 0, 0, 0]  HUIT_REINES(lignes, 1)FIN

Pseudo-code de la fonction HUIT_REINES

ENTRER lignes, y  POUR x <- 1 JUSQU'à COMPTER(lignes) FAIRE    SI PEUT_POSER(lignes, x, y) = 1 ALORS      lignes[y] <- x      SI y = 7 ALORS        AFFICHER_ECHIQUIER(lignes)      SINON        HUIT_REINES(lignes, y + 1)      FINSI    FINSI  FINPOURRETOURNER

Pseudo-code de la fonction PEUT_POSER

ENTRER lignes, x, y  boucler <- 1  i <- 1  ret <- 1  TANTQUE i < y ET boucler = 1 FAIRE    SI lignes[y-i] = x OU lignes[y-i] = x-i OU lignes[y-i] = x+i ALORS      boucler <- 0      ret <- 0    FINSI    i <- i + 1  FINTANTQUERETOURNER ret

Pseudo-code de la fonction AFFICHER_ECHIQUIER

ENTRER lignes  output <- ""  ECRIRE "Une solution possible:"  ECRIRE "-------------------------"  POUR y <- 1 JUSQU'à 8 FAIRE    POUR x <- 1 JUSQU'à 8 FAIRE      SI x = lignes[y] ALORS        output <- output + "| Q"      SINON        output <- output + "| "      FINSI    FINPOUR    output <- output + "|"    ECRIRE output    ECRIRE "-------------------------"    output <- ""  FINPOURRETOURNER

Voici qui conclu en beauté cette série d'introduction à l'algorithmique ! J'espère que celle-ci vous aura donné envie d'approfondir plus vos connaissances dans ce domaine !