148 - Le problème des n reines : un paradigme holistique extrême

N. Lygeros

De tout ce qui précède, se dégage une vision stupéfiante, laperspective d’une conception unitaire du monde jusque-làinsoupçonnée. Que l’on ait affaire aux objets inanimés, auxorganismes, aux processus mentaux ou aux groupes sociaux, partout desprincipes généraux semblables émergent. (Bertalanffy)

 

Nous allons étudier de manière explicite le problème des n reinesafin de mettre en évidence un aspect holistique de la systémique. L’énoncédu problème des n reines est le suivant : combien y a-t-il de façonsde placer n reines sur un échiquier n*n, de façon qu’elles soienttoutes sur des lignes, colonnes et diagonales différentes ?

Ce type de problème ne peut être résolu par des méthodes de rechercheincomplète comme le recuit simulé, l’algorithme génétique oul’Ant-System. Mais uniquement par une recherche complète qui utilisedes méthodes comme le backtracking chronologique, le forward checkingou l’approche formelle. Nous sommes bien dans une situation quicorrespond à la description de Lapointe. Les situations complexesimbriquent plusieurs problèmes relativement simples à première vuemais qui ne peuvent se résoudre individuellement sans affecter lesautres. Ici nous allons nous intéresser à l’approche formelle afin decomprendre la structure du paradigme. Il est évident que si notre butavait été uniquement de calculer le nombre de dispositions différentespour une valeur de n la plus grande possible, nous aurions traité leproblème avec un backtracking.

Une approche partielle du problème est exclue puisqu’il s’agit d’unproblème combinatoire à structure indécomposable. Dans notre cas, nousretrouvons ainsi la notion de complexité de Mélèze qui est l’incapacité que l’on a de décrire tout le système et de déduire soncomportement à partir de la connaissance des comportements de sesparties.

Par contre l’analyse globale du problème permet de reconnaître un motif combinatoire, àsavoir la fonction génératrice. En effet celle-ci étant simple àconstruire, la principale difficulté effective c’est l’élimination desinformations superfétatoires. Comme les cas des échiquiers pour n égalà 1, 2, 3sont triviaux, voici une manière de faire à l’aide deMaple pour les cas 4, 5, 6, 7 et 8 (cf. Gomez, Salvy et Zimmermann).

reines:=proc(n::integer)
construction de la procédure
local i,j,P,c,d,e,L:
P:=convert([seq(convert([seq(c[j]*d[i+j-1]*e[i-j+n],j=1..n)],’+’),i=1..n)],’*’);
calcul du coefficient d’une ligne
for i to n do P:=coeff(series(P,c[i],2),c[i],1) od;
développement de P par rapport à chacun des c[i]
L:=[seq(e[i]^2=0,i=1..2*n-1),seq(d[i]^2=0,i=1..2*n-1)];
P:=expand(subs(L,P));
élimination des carrés pour les diagonales
P:=P-select(hastype,P,’^’);
élimination des puissances
subs([seq(e[i]=1,i=1..2*n-1),seq(d[j]=1,j=1..2*n-1)],P)
obtention du coefficient
end:
seq(reines(k),k=4..8);
obtention des résultats : 2,10,4,40,92

L’aspect extrême de ce paradigme holistique provient de la taille dela mémoire qu’il nécessite pour sa résolution. En effet celle-cidevient très rapidement énorme et impose du coup une limitation sur lataille de l’échiquier.

Cette approche holistique pose des problèmescar elle est exhaustive : la fonction génératice représente uneconnaissance complète de l’objet dans le moindre de ses détails. Orcertains d’entre eux sont superflus pour résoudre le problèmedonné. Aussi il faut savoir ce que nous cherchons pour se poser lesbonnes questions. Et la difficulté provient du fait que nous ne voyonsque ce que nous comprenons. Il est donc important et ce, même dans lecadre d’une approcheholistique, de comprendre les caractéristiques essentielles du problème et des’appuyer sur celles-ci pour élaborer la méthode de résolution. End’autres termes, du point de vue cognitif au moins, nous montronsque le concept de global n’est pas seulement différent de celui delocal et de celui de total, parfois il leur est supérieur.

REFERENCES

Bertalanffy : General Systems Theory, Foundation, Development,Applications. 1968

Colorni, Dorigo, Maniezzo : The ant system : Optimization by a colonyof cooperating agents. IEEE Transactions on Systems, Man andCybernetics 26, 1996

Gomez, Salvy, Zimmermann : Calcul formel : Mode d’emploi. 1995

Lapointe : L’approche systémique et la technologie del’éducation. Éducatechnologiques 1, n.1, 1993

Mélèze : L’analyse modulaire des systèmes de gestion. 1972

Zimmermann : The n-queens problem. American Mathematical Monthly 101, n.7, 1994