TP4 : Récursivité

Ce TP s’étendra sur deux séances.

Documentation

TP4 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

• Date : mercredi 18-11 et jeudi 19-11, puis jeudi 03-11 et 17-11 (2015),
• Auteur : Lilian Besson, pour le cours d’informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
• Licence : MIT Licence (http://lbesson.mit-license.org).

TP4.suite_u(n)

Suite \({(u_n)}_n\) définie par récurrence \(u_0 = 1.0, u_n+1 = u_n + 1 / (2^{u_n})\).

TP4.exponentiation_rapide(x, n)

Calcule \(x^n\) en ne faisant que \(O(\log n)\) multiplications (flottantes ou entières, selon x).

TP4.naive_fibonacci(n)

Fibonacci(n) \(F_n\) en \(O(2^n)\) opérations (et une pile d’appel de taille \(O(2^n)\)).

Avertissement

C’est très inefficace.

naive_fibonacci(40) prend de l’ordre de \(O(2^{40})\) operations élémentaires :

• Soit au moins 15 minutes, si on dit qu’un CPU à 3.1 GHz fait \(10^9\) opérations par seconde,
• ou plutôt de l’ordre d’une journée de calcul avec Python... Beaucoup trop quoi !

TP4.puissMat(A, n)

Calcule la matrice \(A^n\) en ne faisant que \(O(\log n)\) multiplications de matrices

Note : chaque multiplication de matrice est en \(O(k^3)\) si \(A\) est de taille \(k \times k\).

TP4.fibo(n)

Fibonacci(n) \(F_n\) en \(O(\log n)\) opérations (additions et multiplications de matrices d’entiers 64 bits, de tailles \(2 \times 2\)).

Note

• Utiliser des matrices numpy demande d’utiliser un type de données accepté par numpy, comme np.int32 (entiers 32 bits) ou np.int64, et qui sont limités en taille (jusqu’à \(2^{31}\) ou \(2^{63}\) respectivement).
• Donc cette implémentation est exacte tant que \(F_n\) ne dépasse pas cette capacité maximale.
• On peut corriger soit en réimplémentant nous même le produit matriciel (et ne plus utiliser np.dot()).

TP4.fibo2(n)

Fibonacci(n) \(F_n\) en \(O(1)\) opérations (additions et exponentiations flottantes).

\[F_n = \frac{1}{\sqrt{5}} \Big( {\left( \frac{1 + \sqrt{2}}{2} \right)}^n - {\left( \frac{1 - \sqrt{2}}{2} \right)}^n \Big)\]

Note

• utiliser des flottants entraîne des erreurs de calcul dues aux arrondis (fibo2(n) n’est presque jamais exacte)
• on pourrait utiliser le module decimal pour pouvoir fixer la précision (à 100 chiffres après la virgule au lieu de 14), ou sympy.mpmath.

TP4.rechercheDichoRecopiages(t, x)

(Mauvaise) recherche dichotomique de la valeur x dans le tableau (liste) trié t.

• entrée : un tableau d’entiers t trié en ordre croissant et un entier x,
• sortie : un indice i tel que t[i]=x ou -1 si x n’est pas dans t.

Cette première implémentation était fausse (il faut ajouter k+1 si on recherche à droite), et inefficace car le recopiage d’un sous-tableau (t[:k] ou t[k+1:]) prend un temps non-négligeable (\(O(n/2)\) en l’occurrence), donc la recherche n’était pas logarithmique en n (la longueur du tableau) mais linéaire en n (\(n/2 + n/4 + \dots + 1\))...

TP4.rechercheDichoRec(t, x, g, d)

Recherche dichotomique récursive de la valeur x dans le tableau (liste) trié t.

• entrée : un tableau d’entiers t trié en ordre croissant et un entier x, ainsi que g et d deux entiers (on recherche dans t[g:d+1] = t[g], .., t[d]),
• sortie : un indice i tel que t[i]=x ou -1 si x n’est pas dans t.

TP4.rechercheDicho(t, x)

Bonne recherche dichotomique de la valeur x dans le tableau (liste) trié t.

• entrée : un tableau d’entiers t trié en ordre croissant et un entier x,
• sortie : un indice i tel que t[i]=x ou -1 si x n’est pas dans t.

TP4.inverse(t)

Renvoie le tableau “inverse” de t (renverse puis change les signes).

TP4.listeRec(n)

Implémentation récursive de cette liste \(L_n\) (de taille \(2^{(n+1)} - 1\)).

TP4.dragon(n, sauvegarde=False)

Trace la courbe (récursive) du dragon à l’ordre n (< 22 sinon illisible).

TP4.hanoi(n, i, j)

Affiche les instructions nécessaires pour effectuer le déplacement d’une pyramide de n rondelles du piquet i vers le piquet j.

• Affiche \(O(2^n)\) lignes (c’est grand !)
• On peut en fait montrer que ce nombre d’opérations est minimal.

Une légende...

Note

Dans le grand temple de Bénarès, au-dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle d’airain, hautes d’une coudée et grosses comme le corps d’une abeille. Sur une de ces aiguilles, Dieu enfila au commencement des siècles, 64 disques d’or pur, le plus large reposant sur l’airain, et les autres, de plus en plus étroits, superposés jusqu’au sommet. C’est la tour sacrée du Brahmâ. Nuit et jour, les prêtres se succèdent sur les marches de l’autel, occupés à transporter la tour de la première aiguille sur la troisième, sans s’écarter des règles fixes que nous venons d’indiquer, et qui ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la fin des mondes ! (Ce texte vient de cette page Wikipédia)

Note

Une borne sur la durée nécessaire pour déplacer tous les disques ?

Un jeu à 64 disques requiert un minimum de \(2^{64}-1\) déplacements. En admettant qu’il faille 1 seconde pour déplacer un disque, ce qui fait 86 400 déplacements par jour, la fin du jeu aurait lieu au bout d’environ 213 000 milliards de jours, ce qui équivaut à peu près à 584,5 milliards d’années, soit 43 fois l’âge estimé de l’univers (13,7 milliards d’années selon certaines sources).

TP4.pgcd_rec(a, b)

Calcule le PGCD de a et b récursivement.

Note : elle a un temps logarithmique mais une pile d’appels logarithmique aussi (la version itérative est meilleure, car sans pile d’appel).

TP4.pgcd_rec_verbeux(a, b)

Calcule le PGCD de a et b récursivement, et affiche les quotiens et restes successifs.

TP4.euclideEtendu(a, b)

Utilse l’algorithme d’Euclide étendu pour renvoyer un triplet (d, u, v) solution du problème :

• \(d = \mathrm{PGCD}(a, b) \,\text{et}\, d = u a + v b\)
• Effectue \(O( \ln(\min(a, b)) )\) divisions entières, et le même nombre de multiplications et soustractions.

TP4.int_factorial(n)

Factorielle de n, obtenue par math.factorial().

TP4.inserer(li, x)

Insère l’élément x dans la liste li à toutes les positions possibles (renvoie une liste de listes).

TP4.permutations(n)

Renvoie la liste des \(n!\) permutations de l’ensemble \(\{1, 2, \dots, n\}\).

TP4.estSolution(v)

Vérifie si la liste des neuf valeurs v[0], .., v[8] (permutation de [1..9]) est solution du “problème Vietnamien”.

TP4.compteSolutions()

Compte le nombre de solutions de ce “problème Vietnamien” en utilisant notre fonction permutations().

J’en ai compté exactement 136 : 128 où le calcul numérique donne 66.0, et 8 où ça donne 65.999999999.

(sur 362880 permutations de {1..9} différentes, soit un taux de 0.035% solution).

TP4.coefficientBinomial(k, n)

Compute n factorial by a direct multiplicative method: (\(C^n_k = {k \choose n}\)).

• Complexity: O(1) in memory, O(n) in time.
• From https://en.wikipedia.org/wiki/Binomial_coefficient#Binomial_coefficient_in_programming_languages
• From: http://userpages.umbc.edu/~rcampbel/Computers/Python/probstat.html#ProbStat-Combin-Combinations

TP4.parmi(k, n)

Calcule k parmi n avec la factorielle (\(C^n_k = {k \choose n} = \frac{n!}{k!(n-k)!})\).

TP4.verifierDames(positions)

Vérifie que les dames présentes aux positions (positions[k] = i,j)_k soient valides sur un équiquier de taille n x n.

• Voir https://fr.wikipedia.org/wiki/Problème_des_huit_dames pour une présentation du problème.

On vérifie qu’aucun conflit n’arrive :

• d’abord sur une ligne (nb d’indices de lignes est exactement n),
• puis aucun conflit sur une colonne (nb indices colonnes = n),
• puis sur les diagonales (montantes et descendantes, nb de i+j différents et de i-j différents est exemple n).

TP4.afficheEchiquier(positions)

Affiche une version très simple d’un équiquier.

TP4.enumererDames(n=8)

Résolution du problème des n=8 dames, par énumération (presque) force brute.

Pour énumerer la liste des positions potentiellement valide, on se restreint à celles qui n’ont aucune reine sur une même ligne (\(i \neq i'\)) ou colonne (\(j \neq j'\)). On utilise donc notre énumération des permutations (exercice 7) sur \(\{1,\dots,n\}\), ce qui est grand (pour \(n = 8, 8! = 40320\)) mais vraiment petit face à \({n^2}^n\) (qui vaut \(64^8 \simeq 2 \times 10^{14}\) pour 8 reines).

Numériquement, ça prend environ 350 ms pour \(n=8\) et 3.3 s pour \(n=9\) :

>>> %timeit enumererDames(n=8)
1 loop, best of 3: 350 ms per loop
>>> %timeit enumererDames(n=9)
1 loop, best of 3: 3.32 s per loop

Avertissement

Numériquement, c’est déjà trop lourd pour \(n=10\) (environ 40 secondes)...

Pour n = 8, il y a 92 solutions, mais seulement 12 uniques en tenant compte de transformations telles que des rotations ou des réflexions (via le lemme de Burnside, tient c’était un de mes développements pour les oraux d’agrégation).

Voici une illustration, un peu dense, de ces 12 solutions :

TP4.backtrackingDames(n, afficherSolutions=True)

Enrobage pour l’initialisation, partant d’une liste p vide.

• Utilise la function backtrackingDames_rec().

TP4.backtrackingDames_rec(n, p, afficherSolutions=True)

Résolution du problème des n dames, par backtracking.

Idée : on construit la permutation p peu à peu. Explications de l’algorithme :

• Notation : p = [a1, ..., a(i)],
• on calcule le nb de sol possibles obtenues en complétant p,
• principe : on cherche à placer une reine sur la ligne i+1,
• on doit éviter un certain nombre d’emplacements,
• pour chaque emplacement licite, on poursuit la complétion récursivement.

Note

Ça marche bien jusqu’à \(n=12\); pour \(n=13\) ça galère un peu...:

- n = 1 -> 1
- n = 2 -> 0  (réfléchissez-y)
- n = 3 -> 0  (réfléchissez-y)
- n = 4 -> 2
- n = 5 -> 10
- n = 6 -> 4
- n = 7 -> 40
- n = 8 -> 92   (pb d'origine)
- n = 9 -> 352
- n = 10 -> 724
- n = 11 -> 2680
- n = 12 -> 14200
- n = 13 -> 73712

Numériquement, c’est bien plus rapide que l’énumération exhaustive, ça prend environ 9.5 ms pour \(n=8\) :

>>> %timeit backtrackingDames(n=8, afficherSolutions=False)
100 loops, best of 3: 9.48 ms per loop
>>> %timeit backtrackingDames(n=9, afficherSolutions=False)
100 loops, best of 3: 41.8 ms per loop

Numériquement, pour \(n=10\) ou \(n=12\), c’est encore pas trop lent, même si ça prend déjà 198 ms :

>>> %timeit backtrackingDames(n=10, afficherSolutions=False)
100 loops, best of 3: 198 ms per loop
>>> %timeit backtrackingDames(n=11, afficherSolutions=False)
100 loops, best of 3: 1 s per loop
>>> %timeit backtrackingDames(n=12, afficherSolutions=False)
100 loops, best of 3: 5.52 s ms per loop

Avertissement

Ça commence à galérer pour \(n \geq 13\) (40 secondes !).

Soyez rassurés : d’autres techniques encore plus malines permettent de résoudre ce problème des n dames pour des valeurs de n plus grandes.

Références :

• Voir sur Wikipédia pour plus de détails (sur la partie backtracking).
• Voir sur RosettaCode.org pour d’autres résolutions du problème des N-reines en Python.

Note

Message de fin : bonnes vacances et joyeux Noël !! Meilleurs voeux de réussite et de bonheur pour l’année 2016 !

---

Sortie du script

$ python TP4.py


Exercice 1 : Suite definie par recurrence
Premier terme u_0   = 1.0
10  eme terme u_10  = 3.24939558513
100 eme terme u_100 = 6.1819962093 (= 6.18199... OK)
101 eme terme u_101 = 6.19576937296


Exercice 2 : Exponentiation rapide
Exemples avec l'exponentiation rapide :
0 ** 0 = 1
0 ** 1 = 0
0 ** 2 = 0
0 ** 3 = 0
0 ** 10 = 0
1 ** 0 = 1
1 ** 1 = 1
1 ** 2 = 1
1 ** 3 = 1
1 ** 10 = 1
2 ** 0 = 1
2 ** 1 = 2
2 ** 2 = 4
2 ** 3 = 8
2 ** 10 = 1024
4 ** 0 = 1
4 ** 1 = 4
4 ** 2 = 16
4 ** 3 = 64
4 ** 10 = 1048576
100 ** 0 = 1
100 ** 1 = 100
100 ** 2 = 10000
100 ** 3 = 1000000
100 ** 10 = 100000000000000000000
3.1415 ** 0 = 1
3.1415 ** 1 = 3.1415
3.1415 ** 2 = 9.86902225
3.1415 ** 3 = 31.0035333984
3.1415 ** 10 = 93620.4319407
Exemples avec Fibonacci naif :
Fibo 0 = 0
Fibo 1 = 1
Fibo 2 = 1
Fibo 3 = 2
Fibo 4 = 3
Fibo 5 = 5
Fibo 10 = 55
Fibo 20 = 6765
Fibo 25 = 75025
Exemples avec Fibonacci matriciel (fibo) :
Fibo 0 = 0
Fibo 1 = 1
Fibo 2 = 1
Fibo 3 = 2
Fibo 4 = 3
Fibo 5 = 5
Fibo 10 = 55
Fibo 20 = 6765
Fibo 25 = 75025
Fibo 30 = 832040
Fibo 35 = 9227465
Fibo 45 = 1134903170
Pour de grande valeurs, ça foire :
Fibo 100 = 3736710778780434371
Fibo 200 = -1123705814761610347
Fibo 1000 = 817770325994397771
Exemples avec Fibonacci flottant via sa formule exacte (fibo2) :
Fibo 0 = 0
Fibo 1 = 1
Fibo 2 = 1
Fibo 3 = 2
Fibo 4 = 3
Fibo 5 = 5
Fibo 10 = 55
Fibo 20 = 6765
Fibo 25 = 75025
Fibo 30 = 832040
Fibo 35 = 9227465
Fibo 45 = 1134903170
Comparons ces deux fibo et fibo2 pour n = 78 et n = 95 :
Pour n = 78 fibo(n) = 8944394323791464 et fibo2(n) = 8944394323791488
Pour n = 95 fibo(n) = -4953053512429003327 et fibo2(n) = 31940434634990198784


Exercice 3 : Version recursive de la recherche dichotomique
Exemple de t et x :
t = [-100005, -451, -78, -54, -6, 0, 7, 9, 10, 25, 67, 31, 78, 911, 5000, 10000, 746154879] 
x = 911
rechercheDichoRecopiages(t, x) = 13
Cette implementation etait fausse, et mauvaise car utilise des recopiages inutiles.
Meilleure implementation, effectivement en O(log len(t)) :
rechercheDicho(t, x) = 13


Exercice 4 - Courbe du dragon
Inverse d'un tableau :
Pour t = [1, 1, -1], inverse(t) = [1, -1, -1] (comme voulu).
listeRec 0 =  [1]
listeRec 1 =  [1, 1, -1]
listeRec 2 =  [1, 1, -1, 1, 1, -1, -1]
listeRec 3 =  [1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1]
Demonstration de la courbe du dragon pour n = 3, 4, 5, 15 : (voir graphiques plus bas)


Exercice 5 : Les tours de Hanoï
Exemple, hanoi(2, 1, 2) :
1 -> 3
1 -> 2
3 -> 2
Exemple, hanoi(4, 1, 3) :
1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2
1 -> 3
2 -> 3
2 -> 1
3 -> 1
2 -> 3
1 -> 2
1 -> 3
2 -> 3


Exercice 6 : Programmation recursive de l'algorithme d'Euclide

Quelques essais de pgcd_rec(a, b) :
pgcd_rec de 10 et 0 = 10
pgcd_rec de 10 et 1 = 1
pgcd_rec de 10 et 2 = 2
pgcd_rec de 10 et 5 = 5
pgcd_rec de 10 et 10 = 10
pgcd_rec de 20 et 0 = 20
pgcd_rec de 20 et 1 = 1
pgcd_rec de 20 et 2 = 2
pgcd_rec de 20 et 5 = 5
pgcd_rec de 20 et 10 = 10
pgcd_rec de 30 et 0 = 30
pgcd_rec de 30 et 1 = 1
pgcd_rec de 30 et 2 = 2
pgcd_rec de 30 et 5 = 5
pgcd_rec de 30 et 10 = 10
pgcd_rec de 200 et 0 = 200
pgcd_rec de 200 et 1 = 1
pgcd_rec de 200 et 2 = 2
pgcd_rec de 200 et 5 = 5
pgcd_rec de 200 et 10 = 10
pgcd_rec de 400 et 0 = 400
pgcd_rec de 400 et 1 = 1
pgcd_rec de 400 et 2 = 2
pgcd_rec de 400 et 5 = 5
pgcd_rec de 400 et 10 = 10

Quelques essais de pgcd_rec_verbeux(a, b) :
    a = 10 et b = 2 donne a = bq + r : q = 5 et r = 0
        --> pgcd_rec( 2 , 0 )
    b = 0, on finit avec a = 2
  => pgcd_rec_verbeux de 10 et 2 = 2
    a = 10 et b = 3 donne a = bq + r : q = 3 et r = 1
        --> pgcd_rec( 3 , 1 )
    a = 3 et b = 1 donne a = bq + r : q = 3 et r = 0
        --> pgcd_rec( 1 , 0 )
    b = 0, on finit avec a = 1
  => pgcd_rec_verbeux de 10 et 3 = 1
    a = 10 et b = 7 donne a = bq + r : q = 1 et r = 3
        --> pgcd_rec( 7 , 3 )
    a = 7 et b = 3 donne a = bq + r : q = 2 et r = 1
        --> pgcd_rec( 3 , 1 )
    a = 3 et b = 1 donne a = bq + r : q = 3 et r = 0
        --> pgcd_rec( 1 , 0 )
    b = 0, on finit avec a = 1
  => pgcd_rec_verbeux de 10 et 7 = 1
    a = 20 et b = 2 donne a = bq + r : q = 10 et r = 0
        --> pgcd_rec( 2 , 0 )
    b = 0, on finit avec a = 2
  => pgcd_rec_verbeux de 20 et 2 = 2
    a = 20 et b = 3 donne a = bq + r : q = 6 et r = 2
        --> pgcd_rec( 3 , 2 )
    a = 3 et b = 2 donne a = bq + r : q = 1 et r = 1
        --> pgcd_rec( 2 , 1 )
    a = 2 et b = 1 donne a = bq + r : q = 2 et r = 0
        --> pgcd_rec( 1 , 0 )
    b = 0, on finit avec a = 1
  => pgcd_rec_verbeux de 20 et 3 = 1
    a = 20 et b = 7 donne a = bq + r : q = 2 et r = 6
        --> pgcd_rec( 7 , 6 )
    a = 7 et b = 6 donne a = bq + r : q = 1 et r = 1
        --> pgcd_rec( 6 , 1 )
    a = 6 et b = 1 donne a = bq + r : q = 6 et r = 0
        --> pgcd_rec( 1 , 0 )
    b = 0, on finit avec a = 1
  => pgcd_rec_verbeux de 20 et 7 = 1
u = v1, et v = u1 - q1 v1 est la relation demandee.

Quelques essais de euclideEtendu(a, b) :
euclideEtendu de 10 et 2 donne d = 2 u = 0 et v = 1
euclideEtendu de 10 et 3 donne d = 1 u = 1 et v = -3
euclideEtendu de 10 et 7 donne d = 1 u = -2 et v = 3
euclideEtendu de 20 et 2 donne d = 2 u = 0 et v = 1
euclideEtendu de 20 et 3 donne d = 1 u = -1 et v = 7
euclideEtendu de 20 et 7 donne d = 1 u = -1 et v = 3


Exercice 7 : Énumeration recursive de permutations
Exemple d'inserer : inserer([1, 2], 3) = [[3, 1, 2], [1, 3, 2], [1, 2, 3]]
Exemple de permutations :

Pour n = 0 permutations(n) =
	 [[]]

Pour n = 1 permutations(n) =
	 [[1]]

Pour n = 2 permutations(n) =
	 [[2, 1], [1, 2]]

Pour n = 3 permutations(n) =
	 [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

Pour n = 5 permutations(n) =
	 [[5, 4, 3, 2, 1], [4, 5, 3, 2, 1], [4, 3, 5, 2, 1], [4, 3, 2, 5, 1], [4, 3, 2, 1, 5], [5, 3, 4, 2, 1], [3, 5, 4, 2, 1], [3, 4, 5, 2, 1], [3, 4, 2, 5, 1], [3, 4, 2, 1, 5], [5, 3, 2, 4, 1], [3, 5, 2, 4, 1], [3, 2, 5, 4, 1], [3, 2, 4, 5, 1], [3, 2, 4, 1, 5], [5, 3, 2, 1, 4], [3, 5, 2, 1, 4], [3, 2, 5, 1, 4], [3, 2, 1, 5, 4], [3, 2, 1, 4, 5], [5, 4, 2, 3, 1], [4, 5, 2, 3, 1], [4, 2, 5, 3, 1], [4, 2, 3, 5, 1], [4, 2, 3, 1, 5], [5, 2, 4, 3, 1], [2, 5, 4, 3, 1], [2, 4, 5, 3, 1], [2, 4, 3, 5, 1], [2, 4, 3, 1, 5], [5, 2, 3, 4, 1], [2, 5, 3, 4, 1], [2, 3, 5, 4, 1], [2, 3, 4, 5, 1], [2, 3, 4, 1, 5], [5, 2, 3, 1, 4], [2, 5, 3, 1, 4], [2, 3, 5, 1, 4], [2, 3, 1, 5, 4], [2, 3, 1, 4, 5], [5, 4, 2, 1, 3], [4, 5, 2, 1, 3], [4, 2, 5, 1, 3], [4, 2, 1, 5, 3], [4, 2, 1, 3, 5], [5, 2, 4, 1, 3], [2, 5, 4, 1, 3], [2, 4, 5, 1, 3], [2, 4, 1, 5, 3], [2, 4, 1, 3, 5], [5, 2, 1, 4, 3], [2, 5, 1, 4, 3], [2, 1, 5, 4, 3], [2, 1, 4, 5, 3], [2, 1, 4, 3, 5], [5, 2, 1, 3, 4], [2, 5, 1, 3, 4], [2, 1, 5, 3, 4], [2, 1, 3, 5, 4], [2, 1, 3, 4, 5], [5, 4, 3, 1, 2], [4, 5, 3, 1, 2], [4, 3, 5, 1, 2], [4, 3, 1, 5, 2], [4, 3, 1, 2, 5], [5, 3, 4, 1, 2], [3, 5, 4, 1, 2], [3, 4, 5, 1, 2], [3, 4, 1, 5, 2], [3, 4, 1, 2, 5], [5, 3, 1, 4, 2], [3, 5, 1, 4, 2], [3, 1, 5, 4, 2], [3, 1, 4, 5, 2], [3, 1, 4, 2, 5], [5, 3, 1, 2, 4], [3, 5, 1, 2, 4], [3, 1, 5, 2, 4], [3, 1, 2, 5, 4], [3, 1, 2, 4, 5], [5, 4, 1, 3, 2], [4, 5, 1, 3, 2], [4, 1, 5, 3, 2], [4, 1, 3, 5, 2], [4, 1, 3, 2, 5], [5, 1, 4, 3, 2], [1, 5, 4, 3, 2], [1, 4, 5, 3, 2], [1, 4, 3, 5, 2], [1, 4, 3, 2, 5], [5, 1, 3, 4, 2], [1, 5, 3, 4, 2], [1, 3, 5, 4, 2], [1, 3, 4, 5, 2], [1, 3, 4, 2, 5], [5, 1, 3, 2, 4], [1, 5, 3, 2, 4], [1, 3, 5, 2, 4], [1, 3, 2, 5, 4], [1, 3, 2, 4, 5], [5, 4, 1, 2, 3], [4, 5, 1, 2, 3], [4, 1, 5, 2, 3], [4, 1, 2, 5, 3], [4, 1, 2, 3, 5], [5, 1, 4, 2, 3], [1, 5, 4, 2, 3], [1, 4, 5, 2, 3], [1, 4, 2, 5, 3], [1, 4, 2, 3, 5], [5, 1, 2, 4, 3], [1, 5, 2, 4, 3], [1, 2, 5, 4, 3], [1, 2, 4, 5, 3], [1, 2, 4, 3, 5], [5, 1, 2, 3, 4], [1, 5, 2, 3, 4], [1, 2, 5, 3, 4], [1, 2, 3, 5, 4], [1, 2, 3, 4, 5]]

Denombrons les solutions de ce "probleme Vietnamien" :
	  Pour v = [4, 3, 2, 1, 5, 8, 9, 7, 6] resultat = 66.0 est bonne.
	La 1 eme solution est [4, 3, 2, 1, 5, 8, 9, 7, 6]
	  Pour v = [4, 3, 2, 1, 5, 8, 7, 9, 6] resultat = 66.0 est bonne.
	La 2 eme solution est [4, 3, 2, 1, 5, 8, 7, 9, 6]
	  Pour v = [3, 2, 4, 8, 5, 1, 9, 7, 6] resultat = 66.0 est bonne.
	La 3 eme solution est [3, 2, 4, 8, 5, 1, 9, 7, 6]
	  Pour v = [3, 2, 4, 8, 5, 1, 7, 9, 6] resultat = 66.0 est bonne.
	La 4 eme solution est [3, 2, 4, 8, 5, 1, 7, 9, 6]
	  Pour v = [5, 9, 3, 6, 2, 1, 8, 7, 4] resultat = 66.0 est bonne.
	La 5 eme solution est [5, 9, 3, 6, 2, 1, 8, 7, 4]
	  Pour v = [5, 9, 3, 6, 2, 1, 7, 8, 4] resultat = 66.0 est bonne.
	La 6 eme solution est [5, 9, 3, 6, 2, 1, 7, 8, 4]
	  Pour v = [6, 9, 3, 5, 2, 1, 8, 7, 4] resultat = 66.0 est bonne.
	La 7 eme solution est [6, 9, 3, 5, 2, 1, 8, 7, 4]
	  Pour v = [6, 9, 3, 5, 2, 1, 7, 8, 4] resultat = 66.0 est bonne.
	La 8 eme solution est [6, 9, 3, 5, 2, 1, 7, 8, 4]
	  Pour v = [3, 5, 2, 1, 4, 8, 9, 7, 6] resultat = 66.0 est bonne.
	La 9 eme solution est [3, 5, 2, 1, 4, 8, 9, 7, 6]
	  Pour v = [3, 5, 2, 1, 4, 8, 7, 9, 6] resultat = 66.0 est bonne.
	La 10 eme solution est [3, 5, 2, 1, 4, 8, 7, 9, 6]
	  Pour v = [3, 9, 6, 2, 5, 1, 7, 4, 8] resultat = 66.0 est bonne.
	La 11 eme solution est [3, 9, 6, 2, 5, 1, 7, 4, 8]
	  Pour v = [3, 9, 6, 2, 5, 1, 4, 7, 8] resultat = 66.0 est bonne.
	La 12 eme solution est [3, 9, 6, 2, 5, 1, 4, 7, 8]
	  Pour v = [3, 2, 8, 6, 5, 1, 9, 7, 4] resultat = 66.0 est bonne.
	La 13 eme solution est [3, 2, 8, 6, 5, 1, 9, 7, 4]
	  Pour v = [3, 2, 8, 6, 5, 1, 7, 9, 4] resultat = 66.0 est bonne.
	La 14 eme solution est [3, 2, 8, 6, 5, 1, 7, 9, 4]
	  Pour v = [7, 3, 2, 8, 5, 9, 6, 1, 4] resultat = 66.0 est bonne.
	La 15 eme solution est [7, 3, 2, 8, 5, 9, 6, 1, 4]
	  Pour v = [8, 3, 2, 7, 5, 9, 6, 1, 4] resultat = 66.0 est bonne.
	La 16 eme solution est [8, 3, 2, 7, 5, 9, 6, 1, 4]
	  Pour v = [7, 3, 2, 8, 5, 9, 1, 6, 4] resultat = 66.0 est bonne.
	La 17 eme solution est [7, 3, 2, 8, 5, 9, 1, 6, 4]
	  Pour v = [8, 3, 2, 7, 5, 9, 1, 6, 4] resultat = 66.0 est bonne.
	La 18 eme solution est [8, 3, 2, 7, 5, 9, 1, 6, 4]
	  Pour v = [3, 9, 2, 8, 1, 5, 7, 6, 4] resultat = 66.0 est bonne.
	La 19 eme solution est [3, 9, 2, 8, 1, 5, 7, 6, 4]
	  Pour v = [3, 9, 2, 8, 1, 5, 6, 7, 4] resultat = 66.0 est bonne.
	La 20 eme solution est [3, 9, 2, 8, 1, 5, 6, 7, 4]
	  Pour v = [9, 3, 2, 1, 5, 6, 7, 4, 8] resultat = 66.0 est bonne.
	La 21 eme solution est [9, 3, 2, 1, 5, 6, 7, 4, 8]
	  Pour v = [9, 3, 2, 1, 5, 6, 4, 7, 8] resultat = 66.0 est bonne.
	La 22 eme solution est [9, 3, 2, 1, 5, 6, 4, 7, 8]
	  Pour v = [3, 2, 1, 5, 4, 7, 9, 8, 6] resultat = 66.0 est bonne.
	La 23 eme solution est [3, 2, 1, 5, 4, 7, 9, 8, 6]
	  Pour v = [3, 2, 1, 5, 4, 7, 8, 9, 6] resultat = 66.0 est bonne.
	La 24 eme solution est [3, 2, 1, 5, 4, 7, 8, 9, 6]
	  Pour v = [7, 5, 2, 8, 4, 9, 3, 1, 6] resultat = 66.0 est bonne.
	La 25 eme solution est [7, 5, 2, 8, 4, 9, 3, 1, 6]
	  Pour v = [8, 5, 2, 7, 4, 9, 3, 1, 6] resultat = 66.0 est bonne.
	La 26 eme solution est [8, 5, 2, 7, 4, 9, 3, 1, 6]
	  Pour v = [8, 2, 4, 3, 5, 1, 9, 7, 6] resultat = 66.0 est bonne.
	La 27 eme solution est [8, 2, 4, 3, 5, 1, 9, 7, 6]
	  Pour v = [8, 2, 4, 3, 5, 1, 7, 9, 6] resultat = 66.0 est bonne.
	La 28 eme solution est [8, 2, 4, 3, 5, 1, 7, 9, 6]
	  Pour v = [5, 7, 2, 8, 3, 9, 6, 1, 4] resultat = 66.0 est bonne.
	La 29 eme solution est [5, 7, 2, 8, 3, 9, 6, 1, 4]
	  Pour v = [5, 7, 2, 8, 3, 9, 1, 6, 4] resultat = 66.0 est bonne.
	La 30 eme solution est [5, 7, 2, 8, 3, 9, 1, 6, 4]
	  Pour v = [7, 2, 8, 9, 6, 5, 3, 1, 4] resultat = 66.0 est bonne.
	La 31 eme solution est [7, 2, 8, 9, 6, 5, 3, 1, 4]
	  Pour v = [9, 2, 8, 7, 6, 5, 3, 1, 4] resultat = 66.0 est bonne.
	La 32 eme solution est [9, 2, 8, 7, 6, 5, 3, 1, 4]
	  Pour v = [8, 7, 2, 5, 3, 9, 6, 1, 4] resultat = 66.0 est bonne.
	La 33 eme solution est [8, 7, 2, 5, 3, 9, 6, 1, 4]
	  Pour v = [8, 7, 2, 5, 3, 9, 1, 6, 4] resultat = 66.0 est bonne.
	La 34 eme solution est [8, 7, 2, 5, 3, 9, 1, 6, 4]
	  Pour v = [6, 2, 8, 3, 5, 1, 9, 7, 4] resultat = 66.0 est bonne.
	La 35 eme solution est [6, 2, 8, 3, 5, 1, 9, 7, 4]
	  Pour v = [6, 2, 8, 3, 5, 1, 7, 9, 4] resultat = 66.0 est bonne.
	La 36 eme solution est [6, 2, 8, 3, 5, 1, 7, 9, 4]
	  Pour v = [2, 9, 6, 3, 5, 1, 7, 4, 8] resultat = 66.0 est bonne.
	La 37 eme solution est [2, 9, 6, 3, 5, 1, 7, 4, 8]
	  Pour v = [2, 9, 6, 3, 5, 1, 4, 7, 8] resultat = 66.0 est bonne.
	La 38 eme solution est [2, 9, 6, 3, 5, 1, 4, 7, 8]
	  Pour v = [2, 3, 6, 1, 7, 9, 5, 4, 8] resultat = 66.0 est bonne.
	La 39 eme solution est [2, 3, 6, 1, 7, 9, 5, 4, 8]
	  Pour v = [8, 9, 2, 3, 1, 5, 7, 6, 4] resultat = 66.0 est bonne.
	La 40 eme solution est [8, 9, 2, 3, 1, 5, 7, 6, 4]
	  Pour v = [8, 9, 2, 3, 1, 5, 6, 7, 4] resultat = 66.0 est bonne.
	La 41 eme solution est [8, 9, 2, 3, 1, 5, 6, 7, 4]
	  Pour v = [2, 3, 6, 1, 7, 9, 4, 5, 8] resultat = 66.0 est bonne.
	La 42 eme solution est [2, 3, 6, 1, 7, 9, 4, 5, 8]
	  Pour v = [4, 2, 6, 1, 7, 8, 5, 3, 9] resultat = 66.0 est bonne.
	La 43 eme solution est [4, 2, 6, 1, 7, 8, 5, 3, 9]
	  Pour v = [4, 2, 6, 1, 7, 8, 3, 5, 9] resultat = 66.0 est bonne.
	La 44 eme solution est [4, 2, 6, 1, 7, 8, 3, 5, 9]
	  Pour v = [7, 5, 2, 8, 4, 9, 1, 3, 6] resultat = 66.0 est bonne.
	La 45 eme solution est [7, 5, 2, 8, 4, 9, 1, 3, 6]
	  Pour v = [8, 5, 2, 7, 4, 9, 1, 3, 6] resultat = 66.0 est bonne.
	La 46 eme solution est [8, 5, 2, 7, 4, 9, 1, 3, 6]
	  Pour v = [9, 8, 6, 2, 4, 1, 7, 5, 3] resultat = 66.0 est bonne.
	La 47 eme solution est [9, 8, 6, 2, 4, 1, 7, 5, 3]
	  Pour v = [9, 8, 6, 2, 4, 1, 5, 7, 3] resultat = 66.0 est bonne.
	La 48 eme solution est [9, 8, 6, 2, 4, 1, 5, 7, 3]
	  Pour v = [2, 8, 6, 9, 4, 1, 7, 5, 3] resultat = 66.0 est bonne.
	La 49 eme solution est [2, 8, 6, 9, 4, 1, 7, 5, 3]
	  Pour v = [2, 8, 6, 9, 4, 1, 5, 7, 3] resultat = 66.0 est bonne.
	La 50 eme solution est [2, 8, 6, 9, 4, 1, 5, 7, 3]
	  Pour v = [2, 4, 8, 1, 7, 9, 5, 3, 6] resultat = 66.0 est bonne.
	La 51 eme solution est [2, 4, 8, 1, 7, 9, 5, 3, 6]
	  Pour v = [2, 4, 8, 1, 7, 9, 3, 5, 6] resultat = 66.0 est bonne.
	La 52 eme solution est [2, 4, 8, 1, 7, 9, 3, 5, 6]
	  Pour v = [8, 5, 2, 1, 4, 7, 9, 3, 6] resultat = 66.0 est bonne.
	La 53 eme solution est [8, 5, 2, 1, 4, 7, 9, 3, 6]
	  Pour v = [8, 5, 2, 1, 4, 7, 3, 9, 6] resultat = 66.0 est bonne.
	La 54 eme solution est [8, 5, 2, 1, 4, 7, 3, 9, 6]
	  Pour v = [8, 6, 9, 2, 5, 1, 7, 4, 3] resultat = 66.0 est bonne.
	La 55 eme solution est [8, 6, 9, 2, 5, 1, 7, 4, 3]
	  Pour v = [8, 6, 9, 2, 5, 1, 4, 7, 3] resultat = 66.0 est bonne.
	La 56 eme solution est [8, 6, 9, 2, 5, 1, 4, 7, 3]
	  Pour v = [2, 6, 9, 8, 5, 1, 7, 4, 3] resultat = 66.0 est bonne.
	La 57 eme solution est [2, 6, 9, 8, 5, 1, 7, 4, 3]
	  Pour v = [2, 6, 9, 8, 5, 1, 4, 7, 3] resultat = 66.0 est bonne.
	La 58 eme solution est [2, 6, 9, 8, 5, 1, 4, 7, 3]
	  Pour v = [2, 1, 4, 3, 7, 9, 6, 5, 8] resultat = 66.0 est bonne.
	La 59 eme solution est [2, 1, 4, 3, 7, 9, 6, 5, 8]
	  Pour v = [2, 1, 4, 3, 7, 9, 5, 6, 8] resultat = 66.0 est bonne.
	La 60 eme solution est [2, 1, 4, 3, 7, 9, 5, 6, 8]
	  Pour v = [5, 2, 1, 3, 4, 7, 9, 8, 6] resultat = 66.0 est bonne.
	La 61 eme solution est [5, 2, 1, 3, 4, 7, 9, 8, 6]
	  Pour v = [5, 2, 1, 3, 4, 7, 8, 9, 6] resultat = 66.0 est bonne.
	La 62 eme solution est [5, 2, 1, 3, 4, 7, 8, 9, 6]
	  Pour v = [7, 2, 8, 9, 6, 5, 1, 3, 4] resultat = 66.0 est bonne.
	La 63 eme solution est [7, 2, 8, 9, 6, 5, 1, 3, 4]
	  Pour v = [9, 2, 8, 7, 6, 5, 1, 3, 4] resultat = 66.0 est bonne.
	La 64 eme solution est [9, 2, 8, 7, 6, 5, 1, 3, 4]
	  Pour v = [5, 4, 8, 9, 6, 7, 3, 1, 2] resultat = 66.0 est bonne.
	La 65 eme solution est [5, 4, 8, 9, 6, 7, 3, 1, 2]
	  Pour v = [7, 6, 4, 8, 5, 9, 3, 1, 2] resultat = 66.0 est bonne.
	La 66 eme solution est [7, 6, 4, 8, 5, 9, 3, 1, 2]
	  Pour v = [8, 6, 4, 7, 5, 9, 3, 1, 2] resultat = 66.0 est bonne.
	La 67 eme solution est [8, 6, 4, 7, 5, 9, 3, 1, 2]
	  Pour v = [9, 4, 8, 5, 6, 7, 3, 1, 2] resultat = 66.0 est bonne.
	La 68 eme solution est [9, 4, 8, 5, 6, 7, 3, 1, 2]
	  Pour v = [9, 6, 4, 3, 5, 8, 7, 1, 2] resultat = 66.0 est bonne.
	La 69 eme solution est [9, 6, 4, 3, 5, 8, 7, 1, 2]
	  Pour v = [9, 6, 4, 3, 5, 8, 1, 7, 2] resultat = 66.0 est bonne.
	La 70 eme solution est [9, 6, 4, 3, 5, 8, 1, 7, 2]
	  Pour v = [4, 3, 9, 1, 7, 8, 5, 2, 6] resultat = 66.0 est bonne.
	La 71 eme solution est [4, 3, 9, 1, 7, 8, 5, 2, 6]
	  Pour v = [4, 3, 9, 1, 7, 8, 2, 5, 6] resultat = 66.0 est bonne.
	La 72 eme solution est [4, 3, 9, 1, 7, 8, 2, 5, 6]
	  Pour v = [3, 6, 4, 9, 5, 8, 7, 1, 2] resultat = 66.0 est bonne.
	La 73 eme solution est [3, 6, 4, 9, 5, 8, 7, 1, 2]
	  Pour v = [3, 6, 4, 9, 5, 8, 1, 7, 2] resultat = 66.0 est bonne.
	La 74 eme solution est [3, 6, 4, 9, 5, 8, 1, 7, 2]
	  Pour v = [7, 3, 4, 1, 6, 5, 9, 2, 8] resultat = 66.0 est bonne.
	La 75 eme solution est [7, 3, 4, 1, 6, 5, 9, 2, 8]
	  Pour v = [7, 3, 4, 1, 6, 5, 2, 9, 8] resultat = 66.0 est bonne.
	La 76 eme solution est [7, 3, 4, 1, 6, 5, 2, 9, 8]
	  Pour v = [9, 5, 3, 1, 4, 2, 8, 7, 6] resultat = 66.0 est bonne.
	La 77 eme solution est [9, 5, 3, 1, 4, 2, 8, 7, 6]
	  Pour v = [9, 5, 3, 1, 4, 2, 7, 8, 6] resultat = 66.0 est bonne.
	La 78 eme solution est [9, 5, 3, 1, 4, 2, 7, 8, 6]
	  Pour v = [7, 8, 3, 1, 4, 5, 6, 2, 9] resultat = 66.0 est bonne.
	La 79 eme solution est [7, 8, 3, 1, 4, 5, 6, 2, 9]
	  Pour v = [7, 8, 3, 1, 4, 5, 2, 6, 9] resultat = 66.0 est bonne.
	La 80 eme solution est [7, 8, 3, 1, 4, 5, 2, 6, 9]
	  Pour v = [3, 1, 4, 2, 7, 9, 6, 5, 8] resultat = 66.0 est bonne.
	La 81 eme solution est [3, 1, 4, 2, 7, 9, 6, 5, 8]
	  Pour v = [3, 1, 4, 2, 7, 9, 5, 6, 8] resultat = 66.0 est bonne.
	La 82 eme solution est [3, 1, 4, 2, 7, 9, 5, 6, 8]
	  Pour v = [5, 3, 1, 7, 2, 6, 9, 8, 4] resultat = 66.0 est bonne.
	La 83 eme solution est [5, 3, 1, 7, 2, 6, 9, 8, 4]
	  Pour v = [5, 3, 1, 7, 2, 6, 8, 9, 4] resultat = 66.0 est bonne.
	La 84 eme solution est [5, 3, 1, 7, 2, 6, 8, 9, 4]
	  Pour v = [7, 3, 1, 5, 2, 6, 9, 8, 4] resultat = 66.0 est bonne.
	La 85 eme solution est [7, 3, 1, 5, 2, 6, 9, 8, 4]
	  Pour v = [7, 3, 1, 5, 2, 6, 8, 9, 4] resultat = 66.0 est bonne.
	La 86 eme solution est [7, 3, 1, 5, 2, 6, 8, 9, 4]
	  Pour v = [6, 3, 1, 9, 2, 5, 8, 7, 4] resultat = 66.0 est bonne.
	La 87 eme solution est [6, 3, 1, 9, 2, 5, 8, 7, 4]
	  Pour v = [6, 3, 1, 9, 2, 5, 7, 8, 4] resultat = 66.0 est bonne.
	La 88 eme solution est [6, 3, 1, 9, 2, 5, 7, 8, 4]
	  Pour v = [9, 3, 1, 6, 2, 5, 8, 7, 4] resultat = 66.0 est bonne.
	La 89 eme solution est [9, 3, 1, 6, 2, 5, 8, 7, 4]
	  Pour v = [9, 3, 1, 6, 2, 5, 7, 8, 4] resultat = 66.0 est bonne.
	La 90 eme solution est [9, 3, 1, 6, 2, 5, 7, 8, 4]
	  Pour v = [5, 4, 8, 9, 6, 7, 1, 3, 2] resultat = 66.0 est bonne.
	La 91 eme solution est [5, 4, 8, 9, 6, 7, 1, 3, 2]
	  Pour v = [7, 6, 4, 8, 5, 9, 1, 3, 2] resultat = 66.0 est bonne.
	La 92 eme solution est [7, 6, 4, 8, 5, 9, 1, 3, 2]
	  Pour v = [8, 6, 4, 7, 5, 9, 1, 3, 2] resultat = 66.0 est bonne.
	La 93 eme solution est [8, 6, 4, 7, 5, 9, 1, 3, 2]
	  Pour v = [9, 4, 8, 5, 6, 7, 1, 3, 2] resultat = 66.0 est bonne.
	La 94 eme solution est [9, 4, 8, 5, 6, 7, 1, 3, 2]
	  Pour v = [4, 9, 6, 1, 5, 8, 7, 3, 2] resultat = 66.0 est bonne.
	La 95 eme solution est [4, 9, 6, 1, 5, 8, 7, 3, 2]
	  Pour v = [4, 9, 6, 1, 5, 8, 3, 7, 2] resultat = 66.0 est bonne.
	La 96 eme solution est [4, 9, 6, 1, 5, 8, 3, 7, 2]
	  Pour v = [1, 9, 6, 4, 5, 8, 7, 3, 2] resultat = 66.0 est bonne.
	La 97 eme solution est [1, 9, 6, 4, 5, 8, 7, 3, 2]
	  Pour v = [1, 9, 6, 4, 5, 8, 3, 7, 2] resultat = 66.0 est bonne.
	La 98 eme solution est [1, 9, 6, 4, 5, 8, 3, 7, 2]
	  Pour v = [7, 1, 4, 9, 6, 5, 3, 2, 8] resultat = 66.0 est bonne.
	La 99 eme solution est [7, 1, 4, 9, 6, 5, 3, 2, 8]
	  Pour v = [9, 1, 4, 7, 6, 5, 3, 2, 8] resultat = 66.0 est bonne.
	La 100 eme solution est [9, 1, 4, 7, 6, 5, 3, 2, 8]
	  Pour v = [1, 5, 3, 9, 4, 2, 8, 7, 6] resultat = 66.0 est bonne.
	La 101 eme solution est [1, 5, 3, 9, 4, 2, 8, 7, 6]
	  Pour v = [1, 5, 3, 9, 4, 2, 7, 8, 6] resultat = 66.0 est bonne.
	La 102 eme solution est [1, 5, 3, 9, 4, 2, 7, 8, 6]
	  Pour v = [1, 3, 4, 7, 6, 5, 9, 2, 8] resultat = 66.0 est bonne.
	La 103 eme solution est [1, 3, 4, 7, 6, 5, 9, 2, 8]
	  Pour v = [1, 3, 4, 7, 6, 5, 2, 9, 8] resultat = 66.0 est bonne.
	La 104 eme solution est [1, 3, 4, 7, 6, 5, 2, 9, 8]
	  Pour v = [1, 8, 3, 7, 4, 5, 6, 2, 9] resultat = 66.0 est bonne.
	La 105 eme solution est [1, 8, 3, 7, 4, 5, 6, 2, 9]
	  Pour v = [1, 8, 3, 7, 4, 5, 2, 6, 9] resultat = 66.0 est bonne.
	La 106 eme solution est [1, 8, 3, 7, 4, 5, 2, 6, 9]
	  Pour v = [1, 3, 9, 4, 7, 8, 5, 2, 6] resultat = 66.0 est bonne.
	La 107 eme solution est [1, 3, 9, 4, 7, 8, 5, 2, 6]
	  Pour v = [1, 3, 9, 4, 7, 8, 2, 5, 6] resultat = 66.0 est bonne.
	La 108 eme solution est [1, 3, 9, 4, 7, 8, 2, 5, 6]
	  Pour v = [1, 3, 6, 2, 7, 9, 5, 4, 8] resultat = 66.0 est bonne.
	La 109 eme solution est [1, 3, 6, 2, 7, 9, 5, 4, 8]
	  Pour v = [1, 3, 2, 9, 5, 6, 7, 4, 8] resultat = 66.0 est bonne.
	La 110 eme solution est [1, 3, 2, 9, 5, 6, 7, 4, 8]
	  Pour v = [1, 3, 2, 9, 5, 6, 4, 7, 8] resultat = 66.0 est bonne.
	La 111 eme solution est [1, 3, 2, 9, 5, 6, 4, 7, 8]
	  Pour v = [1, 3, 6, 2, 7, 9, 4, 5, 8] resultat = 66.0 est bonne.
	La 112 eme solution est [1, 3, 6, 2, 7, 9, 4, 5, 8]
	  Pour v = [1, 3, 2, 4, 5, 8, 9, 7, 6] resultat = 66.0 est bonne.
	La 113 eme solution est [1, 3, 2, 4, 5, 8, 9, 7, 6]
	  Pour v = [1, 3, 2, 4, 5, 8, 7, 9, 6] resultat = 66.0 est bonne.
	La 114 eme solution est [1, 3, 2, 4, 5, 8, 7, 9, 6]
	  Pour v = [5, 4, 1, 9, 2, 7, 8, 3, 6] resultat = 66.0 est bonne.
	La 115 eme solution est [5, 4, 1, 9, 2, 7, 8, 3, 6]
	  Pour v = [5, 4, 1, 9, 2, 7, 3, 8, 6] resultat = 66.0 est bonne.
	La 116 eme solution est [5, 4, 1, 9, 2, 7, 3, 8, 6]
	  Pour v = [9, 4, 1, 5, 2, 7, 8, 3, 6] resultat = 66.0 est bonne.
	La 117 eme solution est [9, 4, 1, 5, 2, 7, 8, 3, 6]
	  Pour v = [9, 4, 1, 5, 2, 7, 3, 8, 6] resultat = 66.0 est bonne.
	La 118 eme solution est [9, 4, 1, 5, 2, 7, 3, 8, 6]
	  Pour v = [7, 1, 4, 9, 6, 5, 2, 3, 8] resultat = 66.0 est bonne.
	La 119 eme solution est [7, 1, 4, 9, 6, 5, 2, 3, 8]
	  Pour v = [9, 1, 4, 7, 6, 5, 2, 3, 8] resultat = 66.0 est bonne.
	La 120 eme solution est [9, 1, 4, 7, 6, 5, 2, 3, 8]
	  Pour v = [1, 4, 8, 2, 7, 9, 5, 3, 6] resultat = 66.0 est bonne.
	La 121 eme solution est [1, 4, 8, 2, 7, 9, 5, 3, 6]
	  Pour v = [1, 4, 8, 2, 7, 9, 3, 5, 6] resultat = 66.0 est bonne.
	La 122 eme solution est [1, 4, 8, 2, 7, 9, 3, 5, 6]
	  Pour v = [5, 1, 2, 9, 6, 7, 4, 3, 8] resultat = 66.0 est bonne.
	La 123 eme solution est [5, 1, 2, 9, 6, 7, 4, 3, 8]
	  Pour v = [7, 9, 6, 1, 5, 2, 4, 3, 8] resultat = 66.0 est bonne.
	La 124 eme solution est [7, 9, 6, 1, 5, 2, 4, 3, 8]
	  Pour v = [1, 9, 6, 7, 5, 2, 4, 3, 8] resultat = 66.0 est bonne.
	La 125 eme solution est [1, 9, 6, 7, 5, 2, 4, 3, 8]
	  Pour v = [1, 5, 2, 8, 4, 7, 9, 3, 6] resultat = 66.0 est bonne.
	La 126 eme solution est [1, 5, 2, 8, 4, 7, 9, 3, 6]
	  Pour v = [1, 5, 2, 8, 4, 7, 3, 9, 6] resultat = 66.0 est bonne.
	La 127 eme solution est [1, 5, 2, 8, 4, 7, 3, 9, 6]
	  Pour v = [9, 1, 2, 5, 6, 7, 4, 3, 8] resultat = 66.0 est bonne.
	La 128 eme solution est [9, 1, 2, 5, 6, 7, 4, 3, 8]
	  Pour v = [1, 2, 6, 4, 7, 8, 5, 3, 9] resultat = 66.0 est bonne.
	La 129 eme solution est [1, 2, 6, 4, 7, 8, 5, 3, 9]
	  Pour v = [1, 2, 6, 4, 7, 8, 3, 5, 9] resultat = 66.0 est bonne.
	La 130 eme solution est [1, 2, 6, 4, 7, 8, 3, 5, 9]
	  Pour v = [5, 1, 2, 9, 6, 7, 3, 4, 8] resultat = 66.0 est bonne.
	La 131 eme solution est [5, 1, 2, 9, 6, 7, 3, 4, 8]
	  Pour v = [7, 9, 6, 1, 5, 2, 3, 4, 8] resultat = 66.0 est bonne.
	La 132 eme solution est [7, 9, 6, 1, 5, 2, 3, 4, 8]
	  Pour v = [1, 9, 6, 7, 5, 2, 3, 4, 8] resultat = 66.0 est bonne.
	La 133 eme solution est [1, 9, 6, 7, 5, 2, 3, 4, 8]
	  Pour v = [1, 5, 2, 3, 4, 8, 9, 7, 6] resultat = 66.0 est bonne.
	La 134 eme solution est [1, 5, 2, 3, 4, 8, 9, 7, 6]
	  Pour v = [1, 5, 2, 3, 4, 8, 7, 9, 6] resultat = 66.0 est bonne.
	La 135 eme solution est [1, 5, 2, 3, 4, 8, 7, 9, 6]
	  Pour v = [9, 1, 2, 5, 6, 7, 3, 4, 8] resultat = 66.0 est bonne.
	La 136 eme solution est [9, 1, 2, 5, 6, 7, 3, 4, 8]
==> Finalement, il y a exactement 136 solutions (et on a teste 362880 differentes combinaisons).
(Soit un taux de solutions de 0.037% ...)


Exercice 8 : Le probleme des huit dames
Il y a en tout 8 parmi 64 facon de poser 8 reines sur un echiquier, ce qui fait 4426165368 (environ 4.4e+09).
Pour les dames aux positions suivantes : [(0, 1), (1, 3), (2, 5), (3, 7), (4, 2), (5, 0), (6, 6), (7, 1)]
Est-ce une solution valide ? Non.
Pour les dames aux positions suivantes : [(0, 1), (0, 3), (2, 5), (3, 7), (4, 2), (5, 0), (6, 6), (7, 1)]
Est-ce une solution valide ? Non.
Pour les dames aux positions suivantes : [(0, 0), (7, 7)]
Est-ce une solution valide ? Non.
Pour les dames aux positions suivantes : [(0, 7), (5, 2)]
Est-ce une solution valide ? Non.
Pour les dames aux positions suivantes : [(0, 1), (1, 3), (2, 5), (3, 7), (4, 2), (5, 0), (6, 6), (7, 4)]
Est-ce une solution valide ? Oui

================
_ Q _ _ _ _ _ _ 
_ _ _ Q _ _ _ _ 
_ _ _ _ _ Q _ _ 
_ _ _ _ _ _ _ Q 
_ _ Q _ _ _ _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ _ _ _ Q _ _ _ 
================



8.1 : Enumeration complete.
Pour n = 1, il y a 1 solution(s) :  (par énumération)
	 [(0, 0)]

==
Q 
==

Pour n = 2, il y a 0 solution(s) :  (par énumération)

==
Q 
==

Pour n = 3, il y a 0 solution(s) :  (par énumération)

==
Q 
==

Pour n = 4, il y a 2 solution(s) :  (par énumération)
	 [(0, 1), (1, 3), (2, 0), (3, 2)]
	 [(0, 2), (1, 0), (2, 3), (3, 1)]

========
_ _ Q _ 
Q _ _ _ 
_ _ _ Q 
_ Q _ _ 
========

Pour n = 5, il y a 10 solution(s) :  (par énumération)
	 [(0, 2), (1, 4), (2, 1), (3, 3), (4, 0)]
	 [(0, 3), (1, 1), (2, 4), (3, 2), (4, 0)]
	 [(0, 1), (1, 4), (2, 2), (3, 0), (4, 3)]
	 [(0, 4), (1, 1), (2, 3), (3, 0), (4, 2)]
	 [(0, 1), (1, 3), (2, 0), (3, 2), (4, 4)]
	 [(0, 4), (1, 2), (2, 0), (3, 3), (4, 1)]
	 [(0, 2), (1, 0), (2, 3), (3, 1), (4, 4)]
	 [(0, 3), (1, 0), (2, 2), (3, 4), (4, 1)]
	 [(0, 0), (1, 2), (2, 4), (3, 1), (4, 3)]
	 [(0, 0), (1, 3), (2, 1), (3, 4), (4, 2)]

==========
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 
==========

Pour n = 8, il y a 92 solution(s) :  (par énumération)
	 [(0, 3), (1, 6), (2, 2), (3, 7), (4, 1), (5, 4), (6, 0), (7, 5)]
	 [(0, 2), (1, 5), (2, 3), (3, 1), (4, 7), (5, 4), (6, 6), (7, 0)]
	 [(0, 2), (1, 4), (2, 1), (3, 7), (4, 5), (5, 3), (6, 6), (7, 0)]
	 [(0, 5), (1, 2), (2, 6), (3, 1), (4, 3), (5, 7), (6, 0), (7, 4)]
	 [(0, 2), (1, 5), (2, 7), (3, 1), (4, 3), (5, 0), (6, 6), (7, 4)]
	 [(0, 2), (1, 6), (2, 1), (3, 7), (4, 5), (5, 3), (6, 0), (7, 4)]
	 [(0, 2), (1, 4), (2, 1), (3, 7), (4, 0), (5, 6), (6, 3), (7, 5)]
	 [(0, 5), (1, 2), (2, 6), (3, 1), (4, 7), (5, 4), (6, 0), (7, 3)]
	 [(0, 2), (1, 5), (2, 1), (3, 6), (4, 4), (5, 0), (6, 7), (7, 3)]
	 [(0, 2), (1, 5), (2, 1), (3, 4), (4, 7), (5, 0), (6, 6), (7, 3)]
	 [(0, 6), (1, 2), (2, 7), (3, 1), (4, 4), (5, 0), (6, 5), (7, 3)]
	 [(0, 2), (1, 6), (2, 1), (3, 7), (4, 4), (5, 0), (6, 3), (7, 5)]
	 [(0, 2), (1, 5), (2, 1), (3, 6), (4, 0), (5, 3), (6, 7), (7, 4)]
	 [(0, 3), (1, 1), (2, 6), (3, 2), (4, 5), (5, 7), (6, 4), (7, 0)]
	 [(0, 3), (1, 1), (2, 6), (3, 2), (4, 5), (5, 7), (6, 0), (7, 4)]
	 [(0, 4), (1, 1), (2, 3), (3, 5), (4, 7), (5, 2), (6, 0), (7, 6)]
	 [(0, 4), (1, 1), (2, 3), (3, 6), (4, 2), (5, 7), (6, 5), (7, 0)]
	 [(0, 1), (1, 3), (2, 5), (3, 7), (4, 2), (5, 0), (6, 6), (7, 4)]
	 [(0, 4), (1, 6), (2, 1), (3, 5), (4, 2), (5, 0), (6, 7), (7, 3)]
	 [(0, 4), (1, 6), (2, 1), (3, 5), (4, 2), (5, 0), (6, 3), (7, 7)]
	 [(0, 7), (1, 1), (2, 4), (3, 2), (4, 0), (5, 6), (6, 3), (7, 5)]
	 [(0, 1), (1, 6), (2, 2), (3, 5), (4, 7), (5, 4), (6, 0), (7, 3)]
	 [(0, 6), (1, 1), (2, 5), (3, 2), (4, 0), (5, 3), (6, 7), (7, 4)]
	 [(0, 1), (1, 5), (2, 7), (3, 2), (4, 0), (5, 3), (6, 6), (7, 4)]
	 [(0, 3), (1, 6), (2, 4), (3, 1), (4, 5), (5, 0), (6, 2), (7, 7)]
	 [(0, 5), (1, 3), (2, 1), (3, 7), (4, 4), (5, 6), (6, 0), (7, 2)]
	 [(0, 3), (1, 1), (2, 4), (3, 7), (4, 5), (5, 0), (6, 2), (7, 6)]
	 [(0, 3), (1, 1), (2, 6), (3, 4), (4, 0), (5, 7), (6, 5), (7, 2)]
	 [(0, 6), (1, 3), (2, 1), (3, 4), (4, 7), (5, 0), (6, 2), (7, 5)]
	 [(0, 3), (1, 1), (2, 7), (3, 4), (4, 6), (5, 0), (6, 2), (7, 5)]
	 [(0, 3), (1, 5), (2, 7), (3, 1), (4, 6), (5, 0), (6, 2), (7, 4)]
	 [(0, 6), (1, 3), (2, 1), (3, 7), (4, 5), (5, 0), (6, 2), (7, 4)]
	 [(0, 3), (1, 1), (2, 7), (3, 5), (4, 0), (5, 2), (6, 4), (7, 6)]
	 [(0, 4), (1, 6), (2, 1), (3, 3), (4, 7), (5, 0), (6, 2), (7, 5)]
	 [(0, 1), (1, 4), (2, 6), (3, 3), (4, 0), (5, 7), (6, 5), (7, 2)]
	 [(0, 5), (1, 7), (2, 1), (3, 3), (4, 0), (5, 6), (6, 4), (7, 2)]
	 [(0, 6), (1, 1), (2, 3), (3, 0), (4, 7), (5, 4), (6, 2), (7, 5)]
	 [(0, 7), (1, 1), (2, 3), (3, 0), (4, 6), (5, 4), (6, 2), (7, 5)]
	 [(0, 4), (1, 1), (2, 5), (3, 0), (4, 6), (5, 3), (6, 7), (7, 2)]
	 [(0, 4), (1, 1), (2, 7), (3, 0), (4, 3), (5, 6), (6, 2), (7, 5)]
	 [(0, 1), (1, 6), (2, 4), (3, 7), (4, 0), (5, 3), (6, 5), (7, 2)]
	 [(0, 5), (1, 1), (2, 6), (3, 0), (4, 3), (5, 7), (6, 4), (7, 2)]
	 [(0, 1), (1, 5), (2, 0), (3, 6), (4, 3), (5, 7), (6, 2), (7, 4)]
	 [(0, 1), (1, 4), (2, 6), (3, 0), (4, 2), (5, 7), (6, 5), (7, 3)]
	 [(0, 5), (1, 1), (2, 6), (3, 0), (4, 2), (5, 4), (6, 7), (7, 3)]
	 [(0, 1), (1, 7), (2, 5), (3, 0), (4, 2), (5, 4), (6, 6), (7, 3)]
	 [(0, 3), (1, 6), (2, 4), (3, 2), (4, 0), (5, 5), (6, 7), (7, 1)]
	 [(0, 3), (1, 7), (2, 4), (3, 2), (4, 0), (5, 6), (6, 1), (7, 5)]
	 [(0, 3), (1, 5), (2, 7), (3, 2), (4, 0), (5, 6), (6, 4), (7, 1)]
	 [(0, 4), (1, 2), (2, 7), (3, 3), (4, 6), (5, 0), (6, 5), (7, 1)]
	 [(0, 2), (1, 4), (2, 7), (3, 3), (4, 0), (5, 6), (6, 1), (7, 5)]
	 [(0, 2), (1, 5), (2, 3), (3, 0), (4, 7), (5, 4), (6, 6), (7, 1)]
	 [(0, 5), (1, 2), (2, 6), (3, 3), (4, 0), (5, 7), (6, 1), (7, 4)]
	 [(0, 2), (1, 7), (2, 3), (3, 6), (4, 0), (5, 5), (6, 1), (7, 4)]
	 [(0, 5), (1, 2), (2, 4), (3, 6), (4, 0), (5, 3), (6, 1), (7, 7)]
	 [(0, 5), (1, 2), (2, 4), (3, 7), (4, 0), (5, 3), (6, 1), (7, 6)]
	 [(0, 2), (1, 4), (2, 6), (3, 0), (4, 3), (5, 1), (6, 7), (7, 5)]
	 [(0, 2), (1, 5), (2, 7), (3, 0), (4, 3), (5, 6), (6, 4), (7, 1)]
	 [(0, 5), (1, 2), (2, 0), (3, 7), (4, 3), (5, 1), (6, 6), (7, 4)]
	 [(0, 6), (1, 4), (2, 2), (3, 0), (4, 5), (5, 7), (6, 1), (7, 3)]
	 [(0, 4), (1, 2), (2, 0), (3, 5), (4, 7), (5, 1), (6, 3), (7, 6)]
	 [(0, 4), (1, 2), (2, 0), (3, 6), (4, 1), (5, 7), (6, 5), (7, 3)]
	 [(0, 5), (1, 2), (2, 0), (3, 6), (4, 4), (5, 7), (6, 1), (7, 3)]
	 [(0, 5), (1, 2), (2, 0), (3, 7), (4, 4), (5, 1), (6, 3), (7, 6)]
	 [(0, 2), (1, 5), (2, 7), (3, 0), (4, 4), (5, 6), (6, 1), (7, 3)]
	 [(0, 6), (1, 2), (2, 0), (3, 5), (4, 7), (5, 4), (6, 1), (7, 3)]
	 [(0, 2), (1, 0), (2, 6), (3, 4), (4, 7), (5, 1), (6, 3), (7, 5)]
	 [(0, 7), (1, 2), (2, 0), (3, 5), (4, 1), (5, 4), (6, 6), (7, 3)]
	 [(0, 4), (1, 6), (2, 3), (3, 0), (4, 2), (5, 7), (6, 5), (7, 1)]
	 [(0, 4), (1, 7), (2, 3), (3, 0), (4, 2), (5, 5), (6, 1), (7, 6)]
	 [(0, 3), (1, 0), (2, 4), (3, 7), (4, 5), (5, 2), (6, 6), (7, 1)]
	 [(0, 5), (1, 3), (2, 6), (3, 0), (4, 2), (5, 4), (6, 1), (7, 7)]
	 [(0, 7), (1, 3), (2, 0), (3, 2), (4, 5), (5, 1), (6, 6), (7, 4)]
	 [(0, 3), (1, 7), (2, 0), (3, 2), (4, 5), (5, 1), (6, 6), (7, 4)]
	 [(0, 4), (1, 6), (2, 0), (3, 2), (4, 7), (5, 5), (6, 3), (7, 1)]
	 [(0, 0), (1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4)]
	 [(0, 6), (1, 0), (2, 2), (3, 7), (4, 5), (5, 3), (6, 1), (7, 4)]
	 [(0, 4), (1, 0), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3)]
	 [(0, 0), (1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3)]
	 [(0, 4), (1, 7), (2, 3), (3, 0), (4, 6), (5, 1), (6, 5), (7, 2)]
	 [(0, 5), (1, 3), (2, 0), (3, 4), (4, 7), (5, 1), (6, 6), (7, 2)]
	 [(0, 3), (1, 5), (2, 0), (3, 4), (4, 1), (5, 7), (6, 2), (7, 6)]
	 [(0, 3), (1, 6), (2, 0), (3, 7), (4, 4), (5, 1), (6, 5), (7, 2)]
	 [(0, 3), (1, 7), (2, 0), (3, 4), (4, 6), (5, 1), (6, 5), (7, 2)]
	 [(0, 3), (1, 0), (2, 4), (3, 7), (4, 1), (5, 6), (6, 2), (7, 5)]
	 [(0, 5), (1, 3), (2, 6), (3, 0), (4, 7), (5, 1), (6, 4), (7, 2)]
	 [(0, 4), (1, 0), (2, 3), (3, 5), (4, 7), (5, 1), (6, 6), (7, 2)]
	 [(0, 4), (1, 6), (2, 0), (3, 3), (4, 1), (5, 7), (6, 5), (7, 2)]
	 [(0, 4), (1, 0), (2, 7), (3, 3), (4, 1), (5, 6), (6, 2), (7, 5)]
	 [(0, 0), (1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7, 2)]
	 [(0, 0), (1, 6), (2, 4), (3, 7), (4, 1), (5, 3), (6, 5), (7, 2)]
	 [(0, 5), (1, 0), (2, 4), (3, 1), (4, 7), (5, 2), (6, 6), (7, 3)]

================
_ _ _ _ _ Q _ _ 
Q _ _ _ _ _ _ _ 
_ _ _ _ Q _ _ _ 
_ Q _ _ _ _ _ _ 
_ _ _ _ _ _ _ Q 
_ _ Q _ _ _ _ _ 
_ _ _ _ _ _ Q _ 
_ _ _ Q _ _ _ _ 
================



8.2 : par backtracking !
Pour n = 1, affichons toutes les solutions :  (par backtracking)

==
Q 
==


 ==> Pour n = 1, il y a 1 solution(s) :  (par backtracking)
Pour n = 2, affichons toutes les solutions :  (par backtracking)

 ==> Pour n = 2, il y a 0 solution(s) :  (par backtracking)
Pour n = 3, affichons toutes les solutions :  (par backtracking)

 ==> Pour n = 3, il y a 0 solution(s) :  (par backtracking)
Pour n = 4, affichons toutes les solutions :  (par backtracking)

========
_ Q _ _ 
_ _ _ Q 
Q _ _ _ 
_ _ Q _ 
========


========
_ _ Q _ 
Q _ _ _ 
_ _ _ Q 
_ Q _ _ 
========


 ==> Pour n = 4, il y a 2 solution(s) :  (par backtracking)
Pour n = 5, affichons toutes les solutions :  (par backtracking)

==========
Q _ _ _ _ 
_ _ Q _ _ 
_ _ _ _ Q 
_ Q _ _ _ 
_ _ _ Q _ 
==========


==========
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 
==========


==========
_ Q _ _ _ 
_ _ _ Q _ 
Q _ _ _ _ 
_ _ Q _ _ 
_ _ _ _ Q 
==========


==========
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 
Q _ _ _ _ 
_ _ _ Q _ 
==========


==========
_ _ Q _ _ 
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 
==========


==========
_ _ Q _ _ 
_ _ _ _ Q 
_ Q _ _ _ 
_ _ _ Q _ 
Q _ _ _ _ 
==========


==========
_ _ _ Q _ 
Q _ _ _ _ 
_ _ Q _ _ 
_ _ _ _ Q 
_ Q _ _ _ 
==========


==========
_ _ _ Q _ 
_ Q _ _ _ 
_ _ _ _ Q 
_ _ Q _ _ 
Q _ _ _ _ 
==========


==========
_ _ _ _ Q 
_ Q _ _ _ 
_ _ _ Q _ 
Q _ _ _ _ 
_ _ Q _ _ 
==========


==========
_ _ _ _ Q 
_ _ Q _ _ 
Q _ _ _ _ 
_ _ _ Q _ 
_ Q _ _ _ 
==========


 ==> Pour n = 5, il y a 10 solution(s) :  (par backtracking)

 ==> Pour n = 6, il y a 4 solution(s) :  (par backtracking)

 ==> Pour n = 7, il y a 40 solution(s) :  (par backtracking)

 ==> Pour n = 8, il y a 92 solution(s) :  (par backtracking)

 ==> Pour n = 9, il y a 352 solution(s) :  (par backtracking)

 ==> Pour n = 10, il y a 724 solution(s) :  (par backtracking)

 ==> Pour n = 11, il y a 2680 solution(s) :  (par backtracking)

 ==> Pour n = 12, il y a 14200 solution(s) :  (par backtracking)

Le fichier Python se trouve ici : TP4.py.

---

Courbes du dragon