Récursivité

Pour programmer de façon récursive les fonctions demandées, essayez de suivre le schéma suivant :

  1. Définir directement l'image dans les cas simples.
  2. Dans les autres cas, définir l'image en fonction d'un cas plus 'simple'.

Dans ce descriptif schématique, 'simple' peut désigner diverses situations :

  1. Dans le cas d'une liste, le cas le plus simple peut être le cas d'une liste vide ou d'une liste n'ayant qu'un seul élément et 'plus simple' désigne alors une liste ayant strictement moins d'éléments.
  2. Dans le cas du travail sur un entier, 'définir en fonction d'un cas plus simple' peut être 'définir en fonction d'un entier plus petit' ou dans d'autres cas 'définir en fonction d'un entier ayant strictement moins de chiffres', ou encore d'un 'entier ayant moins de facteurs premiers' ou encore ...
  3. ...

Somme d'une liste.

Écrire une fonction python récursive :

  1. Entrée : une liste de nombres,
  2. Sortie : la somme des nombres de cette liste.

Résolution de l'exercice " Somme d'une liste".

Le cas de base : lorsque la liste est vide, la somme est 0. Lorsque la liste ne contient qu'un seul élément, la somme est la valeur de cet élément.

Dans les autres cas, la somme des éléments de L=[a0, a1, a2, ..., an] est la somme de la liste L'=[a0, a1, a2, ..., an-1] et de l'élément an.

Dans cette définition, on exprime la somme des éléments de L en fonction de la somme des éléments d'une liste strictement moins longue. Donc en réitérant le procédé, on arrivera nécessairement au cas de base et le processus récursif se terminera.


def SommeListe(L) :
	if L==[] : return 0
	a=L.pop() # on supprime le dernier élément de la liste L
	          # et on l'affecte à a
	return a+SommeListe(L)
	
	
print(SommeListe([1,2,3,4])) 

Pour une liste L, le dernier élément est obtenu par L[-1] et la liste constituée de tous les éléments de L sauf le dernier est L[ : -1].
On peut donc réécrire le programme précédent comme suit :


def SommeListe(L) :
	if L==[] : return 0
	return L[-1]+SommeListe(L[:-1])
	
	
print(SommeListe([1,2,3,4]))

On peut bien entendu ajouter le premier élément de la liste au lieu du dernier :


def SommeListe(L) :
	if L==[] : return 0
	return L[0]+SommeListe(L[1:])
	
	
print(SommeListe([1,2,3,4]))

Variante :

Dans cette version, on voit l'une des utilisations intéressantes de la possibilité de donner une valeur par défaut à un paramètre : lors de l'appel initial, on n'a pas besoin d'indiquer un second paramètre. Mais ce second paramètre joue un rôle essentiel dans les appels récursifs.


def SommeListe(L, s=0) :
	if L==[] : return s
	a=L.pop() # on supprime le dernier élément de la liste L
	          # et on l'affecte à a
	return SommeListe(L, s+a)
	
	
print(SommeListe([1,2,3,4])) 

que l'on pourrait aussi écrire comme suit :


def SommeListe(L, s=0) :
	if L==[] : return s
	return SommeListe(L[:-1], s+L[-1])
	
	
print(SommeListe([1,2,3,4])) 

Produit d'une liste.

Écrire une fonction python récursive :

  1. Entrée : une liste de nombres,
  2. Sortie : le produit des nombres de cette liste.

Résolution de l'exercice " Produit d'une liste".

Il suffit d'adapter un peu le cas de la somme vue précédemment.


def ProduitListe(L) :
	if L==[] : return 1
	a=L.pop() # on supprime le dernier élément de la liste L
	          # et on l'affecte à a
	return a*ProduitListe(L)
	
	
print(ProduitListe([1,2,3,4]))  

Variante :


def ProduitListe(L, p=1) :
	if L==[] : return p
	a=L.pop() # on supprime le dernier élément de la liste L
	          # et on l'affecte à a
	return ProduitListe(L, p*a)
	
	
print(ProduitListe([1,2,3,4])) 

Minimum d'une liste.

Écrire une fonction python récursive :

  1. Entrée : une liste de nombres.
  2. Sortie : le plus petit des nombres de cette liste.

Résolution de l'exercice " Minimum d'une liste".

Cas de base : si la liste ne contient qu'un élément, cet élément est le minimum.

Lorsque la liste L=[a0, a1, a2, ..., an] contient plus d'un élément, le minimum de la liste L est le plus petit des deux nombres an et minimum([a0, a1, a2, ..., an-1]).


def MinimumListe(L) :
	"""L est une liste de nombres non vide.
	La fonction retourne un élément de valeur minimum."""
	if len(L)==1 : return L[0]
	a=L.pop() # on supprime le dernier élément de la liste L
	          # et on l'affecte à a
	b=MinimumListe(L) # minimum de la liste sans l'élément de fin
	if a<b : return a
	else : return b
	 
print(MinimumListe([10,2,15,3,4,21]))  

On peut décomposer comme suit cette fonction :


def minimum(a,b) :
	""" retourne le plus petit des nombres a et b."""
	if a<b : return a
	else : return b
	

def minimumListe(L) :
	""" L : liste non vide.
	Retourne un des éléments de plus petite valeur de la liste."""
	if len(L)==1 : return L[0]
	return minimum(L[0], minimumListe(L[1:]))
	
	
print(minimumListe([2,8,-2,45,74,0]))

Variante :


def MinimumListe(L) :
	"""L est une liste de nombres non vide.
	La fonction retourne un élément de valeur minimum."""
	if len(L)==1 : return L[0]
	
	if L[0]<L[1] :  # on efface le  plus grand entre L[0] et L[1]
		del(L[1])
	else :
		del(L[0])
		
	return MinimumListe(L)
	
print(MinimumListe([10,2,15,3, -3,4,21]))  

Variante.

Dans cette variante, on utilise le fait que n < float('inf') (où n est de type int) vaut toujours True (on "compare" la valeur de n à l'infini).

Les cas de base : si L est vide, le minimum sera infini. Si L est de longueur 1, le minimum est l'unique élément de la liste.

Cas générique : le minimum d'une liste L=[a1, a1, a2, ..., an] est le plus petit des deux nombres minimumListe( L=[a1, a1, a2, ..., an//2-1] ) et minimumListe( L=[an//2, an//2+1, ..., an] ).


def minimum(a,b) :
	""" retourne le plus petit de deux nombres."""
	if a < b : return a
	else : return b
	

def miniListe(L) :
	if L==[] : return float('inf')
	if len(L)==1 : return L[0]
	l=len(L)//2
	return minimum(miniListe(L[:l]),miniListe(L[l:]))
 
	
L=[3,8,1,45,0,47,145,2,-5,9]

print(miniListe(L))

Présence dans une liste.

Recherche 1.

Écrire une fonction python récursive :

  1. Entrée : une liste L de nombres et un nombre x.
  2. Sortie : False si x n'est pas dans L, True sinon.

Recherche 2.

Écrire une fonction python récursive :

  1. Entrée : une liste L de nombres et un nombre x.
  2. Sortie : None si x n'est pas dans L, l'indice d'une occurrence de x dans L lorsque x est présent dans L.

Résolution de l'exercice " Présence dans une liste".

Recherche 1.


def RechercheDansListe(L,a) :
	"""L est une liste de nombres.
	La fonction retourne False si le nombre a n'est pas dans L,
	True s'il est dans L."""
	if  L==[] : return False
	b=L.pop() # on supprime le dernier élément
	          # de la liste et l'affecte à b
	if a==b : return True
	return RechercheDansListe(L,a)
		
	 
L=[10,2,5,7,8,9,15,21]	 
a=35
	
print(RechercheDansListe(L,a)) 

Recherche 2.


def RechercheDansListe(L,a) :
	"""L est une liste de nombres.
	La fonction retourne None si le nombre n'est pas dans L,
	l'indice d'une occurrence de a dans L sinon."""
	if  L==[] : return  
	b=L.pop() # on supprime le dernier élément
	          # de la liste et l'affecte à b
	if a==b : return len(L)
	return RechercheDansListe(L,a)
		
	 
L=[10,2,5,7, 2,8,9,15,21]	 
a=35
	
print(RechercheDansListe(L,a)) 

Variante :


def RechercheDansListe(L,a,indice=0) :
	"""L est une liste de nombres.
	La fonction retourne None si le nombre n'est pas dans L,
	l'indice d'une occurrence de a dans L sinon."""
	if  indice==len(L) : return  
	if a==L[indice] : return indice
	return RechercheDansListe(L,a, indice+1)
		
	 
L=[10,2,5,7, 2,8,9,15,21]	 
a=21
	
print(RechercheDansListe(L,a)) 

Nombre de 'a'.

Écrire une fonction python récursive :

  1. Entrée : une chaîne de caractères.
  2. Sortie : le nombre d'occurrences de la lettre 'a' dans la chaîne.

Résolution de l'exercice "Nombre de 'a'".


def Nombre_a(ch, s=0) :
	if ch=='' : return s
	if ch[0]=='a' : return Nombre_a(ch[1:], s+1)
	else : return Nombre_a(ch[1:], s)
	
print(Nombre_a('abracadabra'))

print(Nombre_a('python'))

On rappelle que ch[1:] est la sous-chaîne de ch constituée de tous les caractères de ch sauf le premier.

La même programmation avec une "astuce" pour un code plus concis :


def Nombre_a(ch, s=0) :
	if ch=='' : return s
	return Nombre_a(ch[1:], s+(ch[0]=='a'))
	
	
print(Nombre_a('abracadabra'))
print(Nombre_a('python'))

Variante :


def Nombre_a(ch, indice=0) :
	if indice==len(ch) : return 0
	if ch[indice]=='a' : return 1+Nombre_a(ch, indice+1)
	else : return Nombre_a(ch, indice+1)
	
print(Nombre_a('abracadabra'))

print(Nombre_a('python'))

Avec le même gain en concision que plus haut :


def Nombre_a(ch, indice=0) :
	if indice==len(ch) : return 0
	return (ch[indice]=='a')+Nombre_a(ch, indice+1)
	 
	
print(Nombre_a('abracadabra'))
print(Nombre_a('python'))

Du binaire au décimal.

Écrire une fonction python récursive :

  1. Entrée : l'écriture binaire d'un entier (type str). Par exemple 2 est donné par '10'.
  2. Sortie : l'écriture décimale de cet entier (type int).

Résolution de l'exercice "Du binaire au décimal".


def binToDec( n , p=0 ) :
	""" n est un entier en binaire, type string. 
	Par exemple 3 est donné par n='11'.
	p sera un exposant d'une puissance de 2."""
	if n=='' : return 0
	unite=int(n[-1]) # chiffre des unités
	n=n[:-1] # on tronque n en enlevant le chiffre des unités
	return   unite*2**p + binToDec( n, p+1 )
	
print(binToDec('101')) 

Variante.

Dans cette variante, on utilise la remarque suivante (à généraliser) : \[ n = a_4 \times 2^4 +a_3 \times 2^3 + a_2 \times 2^2 + a_1 \times 2^1 + a_0 \] s'écrit aussi : \[ n = \left(\left(\left( \left( a_4 \times 2 +a_3 \right) \times 2 + a_2 \right) \times 2 + a_1 \right) \times 2 \right) + a_0 \]


def binToDec(n, s=0) :
	if n=='' : return s
	return binToDec(n[1:], s*2+int(n[0]))
	
	
n=24
n=bin(n)[2:]

print(binToDec(n))

Du décimal au binaire.

Écrire une version récursive de l'algorithme des divisions en cascade permettant de donner l'écriture binaire (type list) de l'entier donné en entrée (type int).

Par exemple, decToBin(13) retournera la liste [1,1,0,1].

Résolution de l'exercice "Du décimal au binaire".


def decToBin(n, L=[]) :
	if n==0 : 
		L.reverse()
		return L
	L.append(n%2) # ajout du reste n%2 en fin de liste
	return decToBin( n//2, L)
	
print(decToBin(13))
[1, 1, 0, 1]

On peut éviter le reverse() en insérant à chaque étape le nouveau bit en début de liste :


def decToBin(n, L=[]) :
	if n==0 : return L
	L.insert(0,n%2) # insertion du reste n%2 en position 0
	return decToBin( n//2, L)
	
print(decToBin(13))

Recherche dans une liste triée.

On dispose d'une liste de nombres, triée dans l'ordre croissant.

L'objectif est de rechercher si un nombre x est présent dans cette liste (et de retourner un indice correspondant).

Donnez une fonction récursive d'une telle recherche.

Le nombre d'appels à votre fonction est-il, dans le cas le plus défavorable, une fonction affine de la taille de la liste ?
Si oui, cherchez encore !

Résolution de l'exercice " Recherche dans une liste triée".

Avec un nombre linéaire d'appels

On utilise un indicateur entier qui marquera une position dans la liste, en commençant par la position 0.

Cas de base : lorsque l'indicateur dépasse l'indice maximal dans la liste, l'élément est absent. Lorsque l'élément d'indice indicateur est l'élément cherché, on peut répondre immédiatement également (élément trouvé à l'indice 'valeur de indicateur').

Dans les autres cas (L[indicateur] est distinct de l'élément cherché) : on lance une recherche dans la liste en incrémentant d'une unité la valeur de l'indicateur.

Comme l'indicateur augmente d'une unité à chaque étape :

  1. soit l'élément cherché est présent dans la liste et l'indicateur finira par prendre la valeur d'un indice correspondant à une occurrence de l'élément,
  2. soit l'élément cherché est absent de la liste et l'indicateur finira par dépasser l'indice maximal des éléments de la liste.

Dans tous les cas, l' algorithme terminera.

Dans le cas le plus défavorable (l'élément cherché est en fin de liste), on aura n appels de la fonction. Nous chercherons donc ci-après, conformément à la demande de l'énoncé, une solution plus rapide.


def recherche(liste, element, indice=0) :
	""" recherche l'élément element dans liste.
	Retourne -1 si non trouvé, retourne un indice 
	d'une occurrence de element dans liste si  trouvé."""
	if indice>=len(liste)  : return -1
	if liste[indice]==element :
		return indice
	else :
		return recherche(liste, element, indice+1)
		
		
		
L=[2,4,9,15,41]

print( recherche(L,43) )

Avec un nombre d'appels de l'ordre de log2(n).

Le défaut majeur de la procédure précédente est qu'elle n'exploite pas le fait que la liste de départ soit déjà triée.

On met ici en oeuvre le principe de dichotomie (binary search).

On dispose de deux indices mini et maxi et à tout moment on cherche entre ces deux indices. On testera plus précisément L[ (mini+maxi)//2].


def recherche(liste, element) :
	def search(mini, maxi) :
		if mini>maxi : return -1
		m=(mini+maxi)//2
		if liste[m]==element : return m
		elif liste[m]<element : return search(m+1,maxi)
		else : return search(mini,m-1)
	return search(0, len(liste)-1)
		
L=[2,4,9,15,41]
print( recherche(L,16) )

Anagrammes.

Une anagramme d'un mot est un mot s'écrivant avec les mêmes lettres que le mot initial.

Exemples :

  1. Marie et aimer.
  2. Léna et élan.
  3. ironique et onirique.
  4. baignade et badinage.
  5. estival et vitales.
  6. ...

Ici, nous ne demandons pas que les mots envisagés soient des mots du dictionnaire.

Ainsi 'abc' et 'bca' sont deux anagrammes.

Écrire une fonction récursive :

  1. Entrée : un mot (type str)
  2. Sortie : la liste de ses anagrammes.

Résolution de l'exercice "Anagrammes".

Si le mot n'a qu'une seule lettre, la liste de ses anagrammes ne contient qu'un seul élément : le mot lui-même.

Regardons le cas d'un mot de trois lettres 'abc'. On peut définir la liste de ses anagrammes en fonction de la liste des anagrammes du mot 'bc'.
La liste des anagrammes de 'bc' est ['bc', 'cb'].
Pour constituer la liste des anagrammes de 'abc', il suffit de placer la lettre 'a' dans toutes les positions possibles des anagrammes de 'bc'. On obtient la liste ['abc', 'bac', 'bca', 'acb', 'cab', 'cba'].

De la même façon, on obtiendra la liste de toutes les anagrammes du mot 'dabc' en glissant la lettre 'd' dans toutes les positions possibles de toutes les anagrammes de 'abc'.

On tient donc là une définition de la liste des anagrammes d'un mot de longueur n en fonction de la liste des anagrammes d'un mot de longueur n-1. Comme nous savons traiter de façon directe le cas d'un mot de longueur 1, nous tenons notre définition récursive.


def listeAnagramme(mot) :
	# cas de base :
	if len(mot)==1 : return [mot]
	# les autres cas :
	liste=[]
	for anagr in listeAnagramme(mot[1:]) :
		for k in range(len(mot)) :
			liste.append(anagr[:k]+mot[0]+anagr[k:])
	return liste
	

print(listeAnagramme('abc'))

Cette notion d'anagramme n'est pas anecdotique. Il s'agit, dans un cadre plus général, de la notion de permutation.

Tours de Hanoï.

Le problème des tours de Hanoï est un problème très connu. Vous trouverez de nombreuses références sur le web à ce sujet. Par exemple : sur wikipedia.

Dans le jeu des tours de Hanoï, on dispose de trois piquets : le piquet de départ, le piquet objectif et un piquet intermédiaire.

Au départ, n disques de rayons différents sont empilés sur le piquet de départ. Le disque de plus grand rayon est le disque le plus bas, le disque de plus petit rayon est le disque le plus haut.

Tout disque est posé sur un disque de plus grand rayon que lui. Et ceci devra être conservé lors des déplacements de disque : interdiction absolue de poser à un moment donné un disque sur un disque de rayon plus petit.

L'objectif est de déplacer les disques du piquet de départ vers le piquet objectif. On ne peut déplacer qu'un seul disque à la fois, la règle énoncée ci-dessus sur les rayons est à respecter et on peut bien entendu utiliser le piquet intermédiaire.

Programmation

Donner une programmation récursive. Les affichages seront constitués de messages indiquant les déplacements à faire.

Le nombre n de disques sera un paramètre de la fonction. Les disques seront numérotés de 1 à n, le numéro d'un disque pourra être considéré comme son rayon.

Nombre de déplacements

Combien de déplacements de disques utilisez-vous dans votre procédure ? Est-il possible de faire mieux (c'est à dire de déplacer la tour de disques d'un anneau à l'autre en utilisant moins de déplacements de disques) ?

Temps des déplacements

En utilisant le module timeit, évaluer le temps nécessaire aux déplacements des disques sur votre machine dans le cas d'une quinzaine de disques. En déduire une estimation du temps de déplacement des disques dans le cas d'une tour de 64 disques.

Résolution de l'exercice "Tours de Hanoï".

Programmation

Il est clair que l'on sait résoudre le problème s'il n'y a qu'un seul anneau.

Si l'on sait déplacer n-1 anneaux d'un piquet à un autre, alors on sait déplacer n anneaux :

  1. on déplace les n-1 anneaux du dessus du piquet de départ vers l'intermédiaire,
  2. on déplace l'anneau restant sur le piquet de départ (c'est le plus grand) vers le piquet objectif.
  3. on déplace les n-1 anneaux du piquet intermédiaire vers l'objectif.

Traduction en langage python :


def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
	""" a piquet de départ.
	b piquet intermédiaire.
	c piquet d'arrivée.
	n nombre d'anneaux à déplacer.
	z anneau déplacé."""
	
	if n==1:
		print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
	else:
		hanoi(n-1,a,c,b)
		hanoi( 1,a,b,c, n)
		hanoi(n-1,b,a,c)
		
		
		
n=3
hanoi(n)

On obtient :

Déplacer l'anneau 1 du piquet départ vers le piquet objectif.
Déplacer l'anneau 2 du piquet départ vers le piquet intermédiaire.
Déplacer l'anneau 1 du piquet objectif vers le piquet intermédiaire.
Déplacer l'anneau 3 du piquet départ vers le piquet objectif.
Déplacer l'anneau 1 du piquet intermédiaire vers le piquet départ.
Déplacer l'anneau 2 du piquet intermédiaire vers le piquet objectif.
Déplacer l'anneau 1 du piquet départ vers le piquet objectif.

Nombre de déplacements

Notons \( T_n \) le nombre de déplacements de disques lors d'un appel à la fonction hanoi(n) (en toute rigueur, il faut se convaincre que les valeurs des autres paramètres n'influencent pas le nombre de déplacements de disques).

Pour exécuter hanoi(n), on fait appel à hanoi(1) une fois et à hanoi(n-1) à deux reprises. hanoi(1) ne demande qu'un seul déplacement de disque (c'est le cas de base). Nous en déduisons la relation : \[ T_{n} = 2\times T_{n-1} + 1 \]

En posant \( v_n = T_n +1 \), nous obtenons une suite \((v_n)\) géométrique de raison 2 : on vérifie en effet facilement que \( v_n = 2v_{n-1} \). Nous avons donc \( v_n = 2^n\times v_0 \), c'est à dire \( v_n = 2^n \).

Finalement : \[ T_n = 2^n -1 \]

Peut-on faire mieux ?

Notons \( s_n \) le nombre minimal de déplacements de disques qu'il est possible de réaliser.

Nous savons déjà que : \( s_n \leqslant 2^n-1 \).

Avec n disques, pour déplacer le plus grand disque de l'anneau de départ vers l'anneau but, il faut avoir déplacer tous les autres anneaux vers l'anneau intermédiaire, c'est à dire avoir exécuté au moins \( s_{n-1} \) mouvements de disques. On déplace ensuite le grand disque de l'anneau de départ vers l'anneau but : on a donc fait, à ce moment, au moins \( s_{n-1} +1 \) mouvements de disques. On doit ensuite déplacer les n-1 plus petits disques vers l'anneau but, c'est à dire exécuter à nouveau au moins \( s_{n-1} \) mouvements de disques. Au total, pour déplacer n disques, il est nécessaire de faire au moins \( 2 s_{n-1} +1 \) mouvements de disques.
Nous avons donc : \( s_n \geqslant 2s_{n-1} +1 \). Et il est facile, à partir de cette inégalité, de démontrer par récurrence que l'on a \( s_n \geqslant 2^n-1 \).
\( 2^n -1 \) est donc le nombre minimal de déplacements de disques pour déplacer la tour.

Estimation du temps

Avec le programme suivant, on "mesure" le temps utilisé par la machine sur laquelle on exécute pour déplacer 15 disques, le déplacement complet étant répété une centaine de fois.

On a supprimé les affichages (qui augmenteraient ici considérablement les temps d'exécution) pour les remplacer par une "action vide" (pass).


from timeit import timeit

def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
	""" a piquet de départ.
	b piquet intermédiaire.
	c piquet d'arrivée.
	n nombre d'anneaux à déplacer.
	z anneau déplacé."""
	
	if n==1:
		pass
		#print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
	else:
		hanoi(n-1,a,c,b)
		hanoi( 1,a,b,c, n)
		hanoi(n-1,b,a,c)
		
		

a=timeit(stmt='hanoi(15)',setup="from __main__ import hanoi",number=100) 
print("Avec 15 : ", a)

On conjecture que le temps d'exécution est à peu près proportionnel au nombre de déplacements de disques.

Pour 20 disques par exemple, on multiplie par environ \( 2^5 = 32 \) le nombre de déplacements par rapport au cas de 15 disques. Le temps d'exécution devrait donc être à peu près multiplié par 32 si notre conjecture est correcte.

Cherchons à tester expérimentalement cette hypothèse.


from timeit import timeit

def hanoi(n,a='départ',b='intermédiaire',c='objectif',z=1):
	""" a piquet de départ.
	b piquet intermédiaire.
	c piquet d'arrivée.
	n nombre d'anneaux à déplacer.
	z anneau déplacé."""
	
	if n==1:
		pass
		#print("Déplacer l'anneau {} du piquet {} vers le piquet {}.".format(z,a,c))
	else:
		hanoi(n-1,a,c,b)
		hanoi( 1,a,b,c, n)
		hanoi(n-1,b,a,c)
		
		

a=timeit(stmt='hanoi(15)',setup="from __main__ import hanoi",number=100) 
print("Avec 15 : ", a)
b=timeit(stmt='hanoi(20)',setup="from __main__ import hanoi",number=100) 
print(" a*2^5 :", a*2**5)
print("Avec 20 : ", b)

Une expérimentation sur ma machine m'a donné ceci :

Avec 15 :  1.431151767999836
 a*2^5 : 45.79685657599475
Avec 20 :  45.39163709599961

La plausibilité de la conjecture est renforcée...

Estimons alors le temps pour 64 disques. Le temps nécessaire pour 20 disques doit être multiplié par environ \( 2^{44} \).

Pour 20 disques, le temps d'exécution est d'environ 0,45 secondes. \[ \frac{0.45 \times 2^{44}}{60\times 60\times 24 \times 365} \approx 251030 \]

Plus de 250 000 ans pour exécuter les déplacements avec 64 disques !

Les huit reines.

Sur un échiquier n sur n, une dame peut prendre les pions se trouvant sur sa ligne, sur sa colonne, sur ses diagonales.

La question : peut-on placer n dames sur un échiquier n*n de façon à ce qu'aucune ne puisse être prise par une autre ?

Programmer la recherche des solutions.

Résolution de l'exercice "Les huit reines".

Raisonnons sur un échiquier 8*8.

Plaçons déjà la reine de la colonne 1. Elle peut être placée sur n'importe quelle ligne. Notons ['1', '2', '3', '4', '5', '6', '7', '8'] la liste des lignes sur lesquelles elle peut être placée.

Cherchons maintenant à placer une reine en colonne 2. Pour chaque emplacement possible de la reine de la colonne 1, on dresse la liste des emplacements possibles pour la reine de la colonne 2.

Par exemple pour l'emplacement reine colonne 1 en ligne 1, la reine de la colonne 2 peut occuper toute ligne sauf les lignes 1 et 2.

R non
non
ok
ok
ok
ok
ok
ok

Dans la liste des 'solutions' pour deux reines, nous aurons donc déjà '13', '14', '15', '16', '17', '18'.

Lorsque la reine de la colonne 1 est en ligne 2, la reine de la colonne 2 peut se placer partout sauf sur les lignes 1, 2 ou 3.

non
Rnon
non
ok
ok
ok
ok
ok

A la liste des solutions pour deux reines, on peut donc ajouter '24', '25', '26', '27', '28'.

On poursuit ainsi pour chacune des positions possibles de la reine 1. On obtient la liste complète suivante : ['13', '14', '15', '16', '17', '18', '24', '25', '26', '27', '28', '31', '35', '36', '37', '38', '41', '42', '46', '47', '48', '51', '52', '53', '57', '58', '61', '62', '63', '64', '68', '71', '72', '73', '74', '75', '81', '82', '83', '84', '85', '86'].

Ayant obtenu la liste complète des solutions possibles pour les deux premières reines, comment construire la liste pour les trois premières reines ?

Pour chacune des solutions pour les deux premières, on teste chacune des lignes pour la reine de la colonne 3 et on ne retient que les positions telles que cette reine colonne 3 ne soit pas en prise avec les deux premières reines.
On obtient la liste suivante : ['135', '136', '137', '138', '142', '146', '147', '148', '152', '157', '158', '162', '164', '168', '172', '174', '175', '182', '184', '185', '186', '241', '246', '247', '248', '251', '253', '257', '258', '261', '263', '268', '271', '273', '275', '281', '283', '285', '286', '314', '316', '317', '318', '352', '357', '358', '362', '364', '368', '372', '374', '382', '384', '386', '413', '415', '417', '418', '425', '427', '428', '461', '463', '468', '471', '473', '475', '481', '483', '485', '514', '516', '518', '524', '526', '528', '531', '536', '538', '571', '572', '574', '581', '582', '584', '586', '613', '615', '617', '625', '627', '631', '635', '637', '641', '642', '647', '681', '682', '683', '685', '713', '714', '716', '718', '724', '726', '728', '731', '736', '738', '741', '742', '746', '748', '751', '752', '753', '758', '813', '814', '815', '817', '824', '825', '827', '831', '835', '837', '841', '842', '847', '851', '852', '853', '857', '861', '862', '863', '864'].

On a ainsi défini notre processus récursif.

Traduction en langage python :



def ok(c) :
	""" 
	c='*254' signifie 
	reine colonne 1, ligne 2;
	reine colonne 2, ligne 5; 
	reine colonne 3, ligne 4.
	Retourne True si reines non en prise.
	On teste seulement la dernière reine
	par rapport aux précédentes.
	L'étoile placée en début de c ne sert qu'à avoir
	des indices de 1 à n correspondant à une 
	numérotation 'naturelle' des colonnes de 1 à n.
	"""
	n=len(c)-1 # nb de reines
	rr=c[-1] # ligne de la reine à tester
	for i, r in enumerate(c) :
		if 0<i<n :
			if r==rr : return False
			elif i+int(r)==n+int(rr) : return False
			elif i-int(r)==n-int(rr) : return False
	return True
	

def LesSolutions(n) :
	""" Retourne la liste des solutions
	pour un échiquier n*n."""	
	def solut(n,r) :
		""" 
		n : echiquier n*n.
		r : numéro de la colonne où l'on cherche à placer une reine.
		retourne la liste des emplacements possibles pour la 
		colonne r.
		"""
		if r==1 : return [str(i) for i in range(1,n+1)]
		else :
			S=[]
			for j in solut(n, r-1) :
				for k in range(1,n+1) :
					if ok('*'+j+str(k)) :
						S.append(j+str(k))
			return S
	return solut(n,n)
	
	
		
def afficher(solu, n) :
	""" 
	Affichage d'une solution
	pour un échiquier n*n.
	La solution solu donnée en argument est sous la forme '*235...'
	"""
	print(' ',end=' ')
	for k in range(1,n+1) : print(k,end='|')
	print()
	for l in range(1,n+1) :
		print(l,end='|')
		for c in range(1,n+1) :
			if solu[c]==str(l) :
				print('R',end='|')
			else :
				print(' ',end='|')
		print()
		 
		
	



n=8 # taille de l échiquier
S=LesSolutions(n)  # liste des solutions
print("Le nombre de solutions : ", len(S), "\n") # nombre de solutions
print(S,"\n") # affichage des solutions sous la forme chaînes
afficher('*'+S[0],n) # affichage de la première solution
                     # de la liste sous la forme dessin de grille

On obtient pour S[0] :

  1|2|3|4|5|6|7|8|
1|R| | | | | | | |
2| | | | | | |R| |
3| | | | |R| | | |
4| | | | | | | |R|
5| |R| | | | | | |
6| | | |R| | | | |
7| | | | | |R| | |
8| | |R| | | | | |

et pour la liste S (92 solutions) :

['15863724', '16837425', '17468253', '17582463',
 '24683175', '25713864', '25741863', '26174835', '26831475', '27368514', 
 '27581463', '28613574', '31758246', '35281746', '35286471', '35714286', 
 '35841726', '36258174', '36271485', '36275184', '36418572', '36428571',
 '36814752', '36815724', '36824175', '37285146', '37286415', '38471625',
 '41582736', '41586372', '42586137', '42736815', '42736851', '42751863', 
 '42857136', '42861357', '46152837', '46827135', '46831752', '47185263', 
 '47382516', '47526138', '47531682', '48136275', '48157263', '48531726',
  '51468273', '51842736', '51863724', '52468317', '52473861', '52617483',
 '52814736', '53168247', '53172864', '53847162', '57138642', '57142863', 
 '57248136', '57263148', '57263184', '57413862', '58413627', '58417263',
 '61528374', '62713584', '62714853', '63175824', '63184275', '63185247',
 '63571428', '63581427', '63724815', '63728514', '63741825', '64158273',
 '64285713', '64713528', '64718253', '68241753', '71386425', '72418536',
  '72631485', '73168524',
 '73825164', '74258136', '74286135', '75316824', '82417536', '82531746',
  '83162574', '84136275']

Remarque

On peut facilement écrire ici une version non récursive de l'algorithme décrit précédemment.


def ok(c) :
    """ c='*254' signifie 
    reine colonne 1, ligne 2;
    reine colonne 2, ligne 5; 
    reine colonne 3, ligne 4.
    Retourne True si reines non en prise.
    On teste seulement la dernière reine par rapport aux précédentes.
    L'étoile placée en début de c ne sert qu'à avoir
    des indices de 1 à n correspondant à une numérotation 'naturelle' des colonnes de 1 à n.
    """
    n=len(c)-1 # nb de reines
    for i in range(1,n) :
            if c[i]==c[n] : return False
            elif i+int(c[i])==n+int(c[n]) : return False
            elif i-int(c[i])==n-int(c[n]) : return False
    return True
    
def resolution(n) :
    """ Retourne la liste des solutions pour un échiquier n*n.""" 
    solu=['*'+str(i) for i in range(1,n+1)]
    for i in range(2,n+1) :
        solut=solu[:]
        solu=[]
        for j in solut :
            for k in range(1,n+1) :
                if ok(j+str(k)) : solu.append(j+str(k))
    return solu
    
    
def afficher(solu, n) :
    """ Affichage d'une solution pour un échiquier n*n.
    La solution solu donnée en argument est sous la forme '*235...'  """
    print(' ',end=' ')
    for k in range(1,n+1) : print(k,end='|')
    print()
    for l in range(1,n+1) :
        print(l,end='|')
        for c in range(1,n+1) :
            if solu[c]==str(l) :
                print('R',end='|')
            else :
                print(' ',end='|')
        print()
        
        
n=8 # taille de l échiquier
S=resolution(n)  # liste des solutions
print("Le nombre de solutions : ", len(S), "\n") # nombre de solutions
print(S,"\n") # affichage des solutions sous la forme chaînes
afficher('*'+S[0],n) # affichage de la première solution
                     # de la liste sous la forme dessin de grille