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, la perspective d'une conception unitaire du monde jusque-là insoupçonnée. Que l'on ait affaire aux objets inanimés, aux organismes, aux processus mentaux ou aux groupes sociaux, partout des principes généraux semblables émergent. (Bertalanffy)

 

Nous allons étudier de manière explicite le problème des n reines afin 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çons de placer n reines sur un échiquier n*n, de façon qu'elles soient toutes sur des lignes, colonnes et diagonales différentes ?

Ce type de problème ne peut être résolu par des méthodes de recherche incomplète comme le recuit simulé, l'algorithme génétique ou l'Ant-System. Mais uniquement par une recherche complète qui utilise des méthodes comme le backtracking chronologique, le forward checking ou l'approche formelle. Nous sommes bien dans une situation qui correspond à la description de Lapointe. Les situations complexes imbriquent plusieurs problèmes relativement simples à première vue mais qui ne peuvent se résoudre individuellement sans affecter les autres. Ici nous allons nous intéresser à l'approche formelle afin de comprendre la structure du paradigme. Il est évident que si notre but avait été uniquement de calculer le nombre de dispositions différentes pour une valeur de n la plus grande possible, nous aurions traité le problème avec un backtracking.

Une approche partielle du problème est exclue puisqu'il s'agit d'un problème combinatoire à structure indécomposable. Dans notre cas, nous retrouvons 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 son comportement à partir de la connaissance des comportements de ses parties.

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 des informations superfétatoires. Comme les cas des échiquiers pour n égal à 1, 2, 3 sont triviaux, voici une manière de faire à l'aide de Maple 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 de la mémoire qu'il nécessite pour sa résolution. En effet celle-ci devient très rapidement énorme et impose du coup une limitation sur la taille de l'échiquier.

Cette approche holistique pose des problèmes car elle est exhaustive : la fonction génératice représente une connaissance complète de l'objet dans le moindre de ses détails. Or certains d'entre eux sont superflus pour résoudre le problème donné. Aussi il faut savoir ce que nous cherchons pour se poser les bonnes questions. Et la difficulté provient du fait que nous ne voyons que ce que nous comprenons. Il est donc important et ce, même dans le cadre d'une approche holistique, de comprendre les caractéristiques essentielles du problème et de s'appuyer sur celles-ci pour élaborer la méthode de résolution. En d'autres termes, du point de vue cognitif au moins, nous montrons que le concept de global n'est pas seulement différent de celui de local 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 colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics 26, 1996

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

Lapointe : L'approche systémique et la technologie de l'é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







free counters


Opus