X/ENS Informatique A MP 2017

Thème de l'épreuve Jeux à un joueur et solutions optimales
Principaux outils utilisés algorithmes, graphes, complexité
Mots clefs parcours de graphes, parcours en largeur, parcours en profondeur, taquin, horizon, IDA

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                    

Rapport du jury

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE -- ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2017

FILIERES

MP SPECIALITE INFO

COMPOSITION D'INFORMATIQUE ­ A ­ (XULCR)
(Duree : 4 heures)
L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.
Le langage de programmation sera obligatoirement Caml.





Jeux a un joueur et solutions optimales
Nous nous interessons ici a des jeux a un joueur ou une configuration initiale est donnee
et ou le joueur effectue une serie de deplacements pour parvenir a une configuration gagnante.
Des casse-tete tels que le Rubik's Cube, le solitaire, l'ane rouge ou encore le taquin entrent dans
cette categorie. L'objectif de ce probleme est d'etudier differents algorithmes pour trouver des
solutions a de tels jeux qui minimisent le nombre de deplacements effectues.
La partie I introduit la notion de jeu a un joueur et un premier algorithme pour trouver
une solution optimale. Les parties II et III proposent d'autres algorithmes, plus efficaces. La
partie IV a pour objectif de trouver une solution optimale au jeu du taquin.
Les parties I, II et III peuvent etre traitees independamment. Neanmoins, chaque partie
utilise des notations et des fonctions introduites dans les parties precedentes. La partie IV
suppose qu'on a lu entierement l'enonce de la partie III.

Complexite
Par complexite en temps d'un algorithme A on entend le nombre d'operations elementaires
(comparaison, addition, soustraction, multiplication, division, affectation, test, etc) necessaires
a l'execution de A dans le cas le pire. Par complexite en espace d'un algorithme A on entend
l'espace memoire minimal necessaire a l'execution de A dans le cas le pire. Lorsque la complexite
en temps ou en espace depend d'un ou plusieurs parametres 0 , · · · , r-1 , on dit que A a une
complexite en O(f (0 , · · · , r-1 )) s'il existe une constante C > 0 telle que, pour toutes les valeurs
de 0 , · · · , r-1 suffisamment grandes (c'est-a-dire plus grandes qu'un certain seuil), pour toute
instance du probleme de parametres 0 , · · · , r-1 , la complexite est au plus C f (0 , · · · , r-1 ).

1

BFS()
A  {e0 }
p0
tant que A 6= 
B
pour tout x  A
si x  F alors
renvoyer VRAI
B  s(x)  B
AB
pp+1
renvoyer FAUX
Figure 1 ­ Parcours en largeur.

Partie I. Jeu a un joueur, parcours en largeur
Un jeu a un joueur est la donnee d'un ensemble non vide E, d'un element e0  E, d'une
fonction s : E  P(E) et d'un sous-ensemble F de E. L'ensemble E represente les etats possibles
du jeu. L'element e0 est l'etat initial. Pour un etat e, l'ensemble s(e) represente tous les etats
atteignables en un coup a partir de e. Enfin, F est l'ensemble des etats gagnants du jeu. On dit
qu'un etat ep est a la profondeur p s'il existe une sequence finie de p + 1 etats
e0 e1 . . . ep
avec ei+1  s(ei ) pour tout 0  i < p. Si par ailleurs ep  F , une telle sequence est appelee une
solution du jeu, de profondeur p. Une solution optimale est une solution de profondeur minimale.
On notera qu'un meme etat peut etre a plusieurs profondeurs differentes.
Voici un exemple de jeu :
E = N?
e0 = 1
s(n) = { 2n, n + 1 }

(1)

Question 1. Donner une solution optimale pour ce jeu lorsque F = { 42 }.

Parcours en largeur. Pour chercher une solution optimale pour un jeu quelconque, on peut
utiliser un parcours en largeur. Un pseudo-code pour un tel parcours est donne figure 1.
Question 2. Montrer que le parcours en largeur renvoie VRAI si et seulement si une solution
existe.
Question 3. On se place dans le cas particulier du jeu (1) pour un ensemble F arbitraire
pour lequel le parcours en largeur de la figure 1 termine. Montrer alors que la complexite en
temps et en espace est exponentielle en la profondeur p de la solution trouvee. On demande
de montrer que la complexite est bornee a la fois inferieurement et superieurement par deux
fonctions exponentielles en p.

2

DFS(m, e, p)
si p > m alors
renvoyer FAUX
si e  F alors
renvoyer VRAI
pour chaque x dans s(e)
si DFS(m, x, p + 1) = VRAI alors
renvoyer VRAI
renvoyer FAUX
Figure 2 ­ Parcours en profondeur (partie II), limite par une profondeur maximale m.
Programmation. Dans la suite, on suppose donnes un type etat et les valeurs suivantes pour
representer un jeu en Caml :
initial: etat
suivants: etat -> etat list
final: etat -> bool
Question 4. Ecrire une fonction bfs: unit -> int qui effectue un parcours en largeur a
partir de l'etat initial et renvoie la profondeur de la premiere solution trouvee. Lorsqu'il n'y a
pas de solution, le comportement de cette fonction pourra etre arbitraire.
Indication : On pourra avantageusement realiser les ensembles A et B par des listes, sans
chercher a eliminer les doublons, et utiliser une fonction recursive plutot qu'une boucle while.
Question 5. Montrer que la fonction bfs renvoie toujours une profondeur optimale lorsqu'une
solution existe.

Partie II. Parcours en profondeur
Comme on vient de le montrer, l'algorithme BFS permet de trouver une solution optimale
mais il peut consommer un espace important pour cela, comme illustre dans le cas particulier du
jeu (1) qui necessite un espace exponentiel. On peut y remedier en utilisant plutot un parcours
en profondeur. La figure 2 contient le pseudo-code d'une fonction DFS effectuant un parcours
en profondeur a partir d'un etat e de profondeur p, sans depasser une profondeur maximale m
donnee.
Question 6. Montrer que DFS(m, e0 , 0) renvoie VRAI si et seulement si une solution de
profondeur inferieure ou egale a m existe.
Recherche iteree en profondeur. Pour trouver une solution optimale, une idee simple
consiste a effectuer un parcours en profondeur avec m = 0, puis avec m = 1, puis avec m = 2,
etc., jusqu'a ce que DFS(m, e0 , 0) renvoie VRAI.
Question 7. Ecrire une fonction ids: unit -> int qui effectue une recherche iteree en profondeur et renvoie la profondeur d'une solution optimale. Lorsqu'il n'y a pas de solution, cette
fonction ne termine pas.
3

Question 8. Montrer que la fonction ids renvoie toujours une profondeur optimale lorsqu'une
solution existe.
Question 9. Comparer les complexites en temps et en espace du parcours en largeur et de la
recherche iteree en profondeur dans les deux cas particuliers suivants :
1. il y a exactement un etat a chaque profondeur p ;
2. il y a exactement 2p etats a la profondeur p.
On demande de justifier les complexites qui seront donnees.

Partie III. Parcours en profondeur avec horizon
On peut ameliorer encore la recherche d'une solution optimale en evitant de considerer
successivement toutes les profondeurs possibles. L'idee consiste a introduire une fonction h :
E  N qui, pour chaque etat, donne un minorant du nombre de coups restant a jouer avant de
trouver une solution. Lorsqu'un etat ne permet pas d'atteindre une solution, cette fonction peut
renvoyer n'importe quelle valeur.
Commencons par definir la notion de distance entre deux etats. S'il existe une sequence de
k + 1 etats x0 x1 · · · xk avec xi+1  s(xi ) pour tout 0  i < k, on dit qu'il y a un chemin de
longueur k entre x0 et xk . Si de plus k est minimal, on dit que la distance entre x0 et xk est k.
On dit alors que la fonction h est admissible si elle ne surestime jamais la distance entre un
etat et une solution, c'est-a-dire que pour tout etat e, il n'existe pas d'etat f  F situe a une
distance de e strictement inferieure a h(e).
On procede alors comme pour la recherche iteree en profondeur, mais pour chaque etat e
considere a la profondeur p on s'interrompt des que p + h(e) depasse la profondeur maximale m
(au lieu de s'arreter simplement lorsque p > m). Initialement, on fixe m a h(e0 ). Apres chaque
parcours en profondeur infructueux, on donne a m la plus petite valeur p + h(e) qui a depasse m
pendant ce parcours, le cas echeant, pour l'ensemble des etats e rencontres dans ce parcours. La
figure 3 donne le pseudo-code d'un tel algorithme, appele IDA? , ou la variable globale min est
utilisee pour retenir la plus petite valeur ayant depasse m.
Question 10. Ecrire une fonction idastar: unit -> int qui realise l'algorithme IDA? et
renvoie la profondeur de la premiere solution rencontree. Lorsqu'il n'y a pas de solution, le
comportement de cette fonction pourra etre arbitraire. Il est suggere de decomposer le code en
plusieurs fonctions. On utilisera une reference globale min dont on precisera le type et la valeur
retenue pour representer .
Question 11. Proposer une fonction h admissible pour le jeu (1), non constante, en supposant
que l'ensemble F est un singleton {t} avec t  N? . On demande de justifier que h est admissible.
Question 12. Montrer que, si la fonction h est admissible, la fonction idastar renvoie toujours
une profondeur optimale lorsqu'une solution existe.

4

def

def

IDA? () =
DFS? (m, e, p) =
m  h(e0 )
c  p + h(e)
tant que m 6= 
si c > m alors
min  
si c < min alors
si DFS? (m, e0 , 0) = VRAI alors
min  c
renvoyer VRAI
renvoyer FAUX
m  min
si e  F alors
renvoyer FAUX
renvoyer VRAI
pour chaque x dans s(e)
si DFS? (m, x, p + 1) = VRAI alors
renvoyer VRAI
renvoyer FAUX
Figure 3 ­ Pseudo-code de l'algorithme IDA? .

Partie IV. Application au jeu du taquin
Le jeu du taquin est constitue d'une grille 4 × 4 dans laquelle sont disposes les entiers de 0
a 14, une case etant laissee libre. Dans tout ce qui suit, les lignes et les colonnes sont numerotees
de 0 a 3, les lignes etant numerotees du haut vers le bas et les colonnes de la gauche vers la
droite. Voici un etat initial possible :
0

1

2

3

0

2

3

1

6

1

14

5

8

4

2

12

7

9

3

10 13 11

0

On obtient un nouvel etat du jeu en deplacant dans la case libre le contenu de la case situee
au-dessus, a gauche, en dessous ou a droite, au choix. Si on deplace par exemple le contenu de
la case situee a droite de la case libre, c'est-a-dire 12, on obtient le nouvel etat suivant :
2

3

1

6

14

5

8

4

7

9

10 13 11

0

12

Le but du jeu du taquin est de parvenir a l'etat final suivant :
0

1

2

3

4

5

6

7

8

9

10 11

12 13 14

5

Ici, on peut le faire a l'aide de 49 deplacements supplementaires et il n'est pas possible de faire
moins.
Question 13. En estimant le nombre d'etats du jeu du taquin, et la place memoire necessaire
a la representation d'un etat, expliquer pourquoi il n'est pas realiste d'envisager le parcours en
largeur de la figure 1 pour chercher une solution optimale du taquin.

Fonction h. On se propose d'utiliser l'algorithme IDA? pour trouver une solution optimale
du taquin et il faut donc choisir une fonction h. On repere une case de la grille par sa ligne i
(avec 0  i  3, de haut en bas) et sa colonne j (avec 0  j  3, de gauche a droite). Si e est
un etat du taquin et v un entier entre 0 et 14, on note eiv la ligne de l'entier v dans e et ejv la
colonne de l'entier v dans e. On definit alors une fonction h pour le taquin de la facon suivante :
h(e) =

14
X

|eiv - bv/4c| + |ejv - (v mod 4)|.

v=0

Question 14. Montrer que cette fonction h est admissible.

Programmation. Pour programmer le jeu de taquin, on abandonne l'idee d'un type etat et
d'une fonction suivants, au profit d'un unique etat global et modifiable. On se donne pour cela
une matrice grid de taille 4 × 4 contenant l'etat courant e ainsi qu'une reference h contenant la
valeur de h(e).
grid: int vect vect
h: int ref
La matrice grid est indexee d'abord par i puis par j. Ainsi grid.(i).(j) est l'entier situe a
la ligne i et a la colonne j. Par ailleurs, la position de la case libre est maintenue par deux
references :
li: int ref
lj: int ref
La valeur contenue dans grid a cette position est non significative.
Question 15. Ecrire une fonction move: int -> int -> unit telle que move i j deplace
l'entier situe dans la case (i, j) vers la case libre supposee etre adjacente. On prendra soin de
bien mettre a jour les references h, li et lj. On ne demande pas de verifier que la case libre est
effectivement adjacente.

Deplacements et solution. De cette fonction move, on deduit facilement quatre fonctions
qui deplacent un entier vers la case libre, respectivement vers le haut, la gauche, le bas et la
droite.
6

let
let
let
let

haut
gauche
bas
droite

()
()
()
()

=
=
=
=

move
move
move
move

(!li + 1) !lj;;
!li (!lj + 1);;
(!li - 1) !lj;;
!li (!lj - 1);;

Ces quatre fonctions supposent que le mouvement est possible.
Pour conserver la solution du taquin, on se donne un type deplacement pour representer
les quatre mouvements possibles et une reference globale solution contenant la liste des
deplacements qui ont ete faits jusqu'a present.
type deplacement = Gauche | Bas | Droite | Haut
solution: deplacement list ref
La liste !solution contient les deplacement effectues dans l'ordre inverse, i.e., la tete de liste
est le deplacement le plus recent.
Question 16. Ecrire une fonction tente gauche: unit -> bool qui tente d'effectuer un
deplacement vers la gauche si cela est possible et si le dernier deplacement effectue, le cas
echeant, n'etait pas un deplacement vers la droite. Le booleen renvoye indique si le deplacement
vers la gauche a ete effectue. On veillera a mettre a jour solution lorsque c'est necessaire.
On suppose avoir ecrit de meme trois autres fonctions
tente_bas
: unit -> bool
tente_droite: unit -> bool
tente_haut : unit -> bool
Question 17. Ecrire une fonction dfs: int -> int -> bool correspondant a la fonction
DFS? de la figure 3 pour le jeu du taquin. Elle prend en argument la profondeur maximale m
et la profondeur courante p. (L'etat e est maintenant global.)
Question 18. En deduire enfin une fonction taquin: unit -> deplacement list qui renvoie
une solution optimale, lorsqu'une solution existe.

Note : Trouver une solution au taquin n'est pas tres complique, mais trouver une
solution optimale est nettement plus difficile. Avec ce qui est propose dans la derniere
partie de ce sujet, on y parvient en moins d'une minute pour la plupart des etats
initiaux et en une dizaine de minutes pour les problemes les plus difficiles.





7



Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique A MP 2017 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (enseignant-chercheur à 
l'université) ; il a été relu par William Aufort (professeur en CPGE).

Ce sujet propose la résolution de jeux à un joueur tels que le Rubik's Cube, le
solitaire ou le taquin, qui fait d'ailleurs l'objet de la dernière partie. Ces 
jeux peuvent
être modélisés à l'aide d'un graphe orienté dont les sommets sont les 
configurations
du jeu et les arcs sont les coups possibles à partir de chaque état. Le but du 
jeu
est d'atteindre une configuration finale. Il s'agit donc d'un objectif 
d'accessibilité,
que l'on résout à l'aide de parcours en largeur ou en profondeur. Il est 
important de
traiter les quatre parties dans l'ordre.
· La première partie introduit le modèle de jeu avec un exemple simple, puis
propose une première résolution utilisant un parcours en largeur.
· La deuxième partie étudie ensuite une option qui s'appuie sur le parcours en
profondeur. Puisque l'on cherche une solution optimale en nombre de coups
pour atteindre une configuration finale, la recherche se fait de manière itérée
en augmentant progressivement la profondeur.
· La troisième partie étudie l'algorithme IDA qui affine la recherche itérée en
profondeur en introduisant une fonction d'horizon qui estime (sans jamais 
surestimer) la distance entre une configuration et une solution du jeu. Cela 
permet
d'explorer nettement moins de configurations, au prix de la recherche manuelle
d'une fonction d'horizon admissible.
· Finalement, la quatrième partie applique l'algorithme IDA au jeu de taquin
en proposant une fonction d'horizon.
Le sujet est très intéressant. Il contient plusieurs questions assez délicates 
demandant de prouver la correction ou la complexité des algorithmes de parcours 
étudiés.
Les fonctions OCaml à écrire sont, pour la plupart, des retranscriptions 
d'algorithmes
donnés par l'énoncé ; il faut cependant être vigilant sur les transformations à 
apporter. Dans l'ensemble, c'est un bon énoncé pour réviser les parcours de 
graphes. Le
problème est assez motivant, puisqu'à la fin on obtient un code complet pour la
résolution du jeu de taquin.
Dans le corrigé, les codes sont écrits en OCaml plutôt qu'en Caml Light, comme
le demandait pourtant l'énoncé, car c'est le langage qui est devenu obligatoire 
aux
concours à partir de la session 2019.

Indications
Partie I
1 L'énoncé ne demande pas de justifier l'optimalité de la solution proposée.
2 Montrer d'abord par récurrence sur p  N, inférieur à la profondeur d'une 
solution optimale du jeu, qu'au début de la p-ième itération de la boucle tant 
que,
l'ensemble A contient l'ensemble des états à profondeur p.
3 Relier les complexités en temps et en espace avec le nombre d'états insérés 
dans B.
Pour la minoration, il faut faire attention au fait que les doublons ne comptent
pas dans la complexité spatiale. Cependant, on pourra par exemple montrer que
tous les entiers entre 1 et 2i ont été insérés dans B lors d'au moins une des 2i
premières étapes.
4 Faire attention au changement de type entre le pseudo-code, qui renvoie un 
booléen, et la fonction bfs demandée, qui doit renvoyer la profondeur optimale.
5 Utiliser les arguments avancés lors de la question 2.
Partie II
6 Montrer par récurrence descendante sur p  [[ 0 ; m + 1 ]] que pour tout état 
e,
DFS(m, e, p) renvoie VRAI si et seulement si une solution de profondeur au
plus m - p existe depuis l'état e.
7 Commencer par implémenter une fonction dfs réalisant le parcours en profondeur
avant de l'utiliser dans la fonction ids.
8 Utiliser la question 6.
9 Huit résultats de complexité sont ici demandés, avec justification : il vaut 
mieux
remplir un tableau pour être sûr de ne pas en oublier. Pour la recherche itérée
en profondeur, ne pas oublier de compter l'espace mémoire requis par la pile
d'appels récursifs.
Partie III
10 On pourra utiliser la constante max_int, définie par le langage OCaml comme 
la
plus grande valeur de type int, pour représenter la valeur . S'inspirer ensuite
des fonctions de la question 7.
11 Essayer avec h(n) = log2 (t/n), pour tout n 6 t.
12 Reprendre la récurrence de la question 6. Expliquer ensuite l'effet sur la 
variable
min de l'appel à DFS (m, e0 , 0) (appelée avec la valeur initiale  pour min).
Partie IV
13 Connaître le nombre d'états permet de minorer l'espace mémoire nécessaire 
pour
représenter un état. Conclure en utilisant l'information délivrée par l'énoncé
que le nombre de déplacements nécessaire pour résoudre le taquin peut être de
l'ordre de 50.
15 Il est inutile de recalculer h : il suffit de mettre à jour sa valeur en 
observant que
peu de termes changent. On pourra utiliser la fonction abs d'OCaml pour calculer
la valeur absolue d'un élément de type int.
17 S'inspirer de la fonction réalisant l'algorithme DFS de la question 10 en 
modifiant
le test pour savoir si la grille est finale (utiliser la fonction h pour cela) 
et l'énumération des voisins. Lors de cette énumération, si un voisin ne 
convient pas, ne
pas oublier de revenir en arrière en remettant à jour la grille et la liste 
!solution.

I. Jeu à un joueur, parcours en largeur
1 Les coups optimaux du jeu sont liés à la décomposition en binaire des entiers
de F. Dans le cas où F = {42}, l'écriture binaire de 42 est 101010, ce qui peut 
s'écrire
42 = 2 × (1 + 2 × 2 × (1 + 2 × 2 × 1))
À partir de 1, on multiplie donc deux fois par 2, puis on ajoute 1, puis à 
nouveau on
multiplie deux fois par 2, avant d'ajouter 1 et de multiplier une dernière fois 
par 2.
Ainsi, on en déduit que
La séquence 1 2 4 5 10 20 21 42 est une
solution optimale du jeu, de profondeur 7.
L'énoncé ne demande pas de prouver l'optimalité et le rapport insiste
sur le fait qu'il était inutile de perdre du temps à la prouver. Cependant, il 
n'est pas très difficile de montrer par récurrence sur n  N
que la profondeur d'une solution optimale lorsque F = {n} est égale
à (k - 1) + (u - 1), avec k = 1 + log2 n le nombre de chiffres dans l'écriture
binaire ak-1 ak-2 · · · a1 a0 de n et u = Card ({i  [[ 0 ; k - 1 ]] | ai = 1}) 
le
nombre de bits à 1 dans cette écriture binaire. On trouve aussi la solution
optimale : le terme k - 1 est le nombre de multiplications par 2 à effectuer,
et le terme u - 1 est le nombre d'incrémentations. Une autre stratégie pour
trouver la solution consiste à énumérer l'ensemble des entiers de profondeur
1, 2, 3, etc. jusqu'à trouver le nombre 42 : c'est d'ailleurs plus ou moins 
l'idée
de la partie III.
2 Montrons par récurrence que la propriété
P(p) :

« au début de la p-ième itération de la boucle tant que,
l'ensemble A contient l'ensemble des états à profondeur p »

est vraie pour tout p  N inférieur à la profondeur d'une solution optimale du 
jeu.

· P(0) est vraie car A est initialisé à {e0 }, e0 étant l'unique état à 
profondeur 0.

· P(p) = P(p + 1) : supposons qu'au début de la p-ième itération de la boucle
tant que l'ensemble A contient l'ensemble des états à profondeur p et que p est
strictement inférieur à la profondeur d'une solution optimale du jeu. La boucle
pour tout considère les états de A et ajoute dans B tous leurs successeurs
par s. D'après l'hypothèse sur p, le test x  F ne sera jamais satisfait, puisque
cela impliquerait que le jeu possède une solution optimale de profondeur p.
Un état e ayant profondeur p + 1 si et seulement s'il existe un état e ayant
profondeur p tel que s(e ) = e, on a bien que B contient l'ensemble des états
à profondeur p + 1 à la fin de l'itération. La mise à jour de l'ensemble A avec
l'ensemble B permet d'obtenir P(p + 1).
· Conclusion : pour tout p  N inférieur à la profondeur d'une solution optimale
du jeu, P(p) est vraie.
Ainsi, si une solution existe de profondeur p minimale, lors de la p-ième 
itération
de la boucle tant que, le test x  F permet de renvoyer VRAI. Sinon, aucune
solution n'existe, donc ce test n'est jamais concluant. Il y a alors deux 
possibilités :
soit le programme ne s'arrête jamais (et ne renvoie donc pas VRAI), soit il 
s'arrête
du fait que A devient vide, auquel cas le programme renvoie FAUX. Finalement,
Le parcours en largeur renvoie VRAI si et seulement si une solution existe.

Rappelons que BFS est le sigle de breadth-first search, le nom anglais du
parcours en largeur.
3 Le nombre d'opérations élémentaires effectuées par le parcours en largeur est 
de
l'ordre du nombre d'éléments insérés dans B au total, c'est-à-dire le nombre 
total
d'occurrences d'états atteignables depuis e0 (il peut y avoir des doublons) 
avant
d'arriver à la profondeur p où un état de F est atteint pour la première fois. 
Ce nombre
est inférieur au nombre de séquences possibles de longueur au plus p : 
puisqu'il y a
deux coups possibles à chaque étape, le nombre total d'états insérés dans B est 
ainsi
majoré par
p
P
i=1

2i = 2p+1 - 1

Minorons ensuite ce nombre d'états insérés dans B. Montrons que, pour i  N, tous
les entiers entre 1 et 2i ont été insérés dans B lors d'au moins une des 2i 
premières
étapes. Fixons donc un entier n  [[ 1 ; 2i ]]. Son écriture en binaire est de 
la forme
ak ak-1 · · · a1 a0 avec k 6 i et ak = 1 : on peut ainsi décomposer n sous la 
forme
n=

k
P

j=0

aj 2j = a0 + 2 × (a1 + 2 × (a2 + · · · + 2 × (ak-1 + 2 × ak ) · · · ))

Par conséquent, il existe une séquence d'au plus 2k 6 2i états allant de 1 à n 
: on
commence par aller de 1 à 2 × ak = 2 en une étape, puis vers 2 × (ak-1 + 2 × ak 
) en
une ou deux étapes supplémentaires, etc. jusqu'à l'ajout éventuel de a0 en au 
plus
une étape. Ainsi, p étant la profondeur de la solution trouvée, tous
 les entiers entre 1
et 2p/2 ont été insérés. On a donc inséré au moins 2p/2 > ( 2)p-1 états 
distincts
dans B lors du parcours en largeur, ce qui donne un minorant de la complexité en
temps.
Considérons ensuite la complexité en espace. L'espace mémoire requis est de
l'ordre de la taille maximale de l'ensemble B, majorée par le nombre d'états 
atteignables à la profondeur p, inférieur à 2p . Pour obtenir une minoration, 
utilisons la
borne 2p/2 sur le nombre total d'états distincts insérés dans B : puisqu'on 
réalise p
étapes, le principe des tiroirs assure qu'il y a au moins une étape qui insère 
2p/2 /p
éléments distincts dans B. Or, pour tout entier p supérieur à 16, on a p 6 2p/4 
, de
sorte que
2p/2
2(p-1)/2
2p/4
>
= 
p/4
p
2
2
ce qui minore donc la complexité en espace par une fonction exponentielle de p, 
pour
p assez grand. Ainsi,
Dans le cas particulier du jeu (1) pour un ensemble F arbitraire pour lequel
le parcours en largeur de la figure 1 termine, la complexité en temps et
en espace est exponentielle en la profondeur p de la solution trouvée.
4 Représentons les ensembles A et B par des listes a et b d'états et utilisons 
une fonction auxiliaire récursive voisins : etat list -> etat list -> int -> 
int pour
simuler les deux boucles tant que et pour tout simultanément. Ainsi, l'appel à
voisins [initial] [] 0 renvoie la profondeur d'une solution du jeu, si le jeu 
admet une solution, ou renvoie une erreur si elle s'arrête sans avoir trouver 
de solution
(il se peut aussi que la fonction ne s'arrête jamais).