Euler et le cavalier sur l' echiquier

Soyez le premier à donner votre avis sur cette source.

Snippet vu 8 288 fois - Téléchargée 29 fois


Contenu du snippet

Un problème posé par le mathématicien EULER, sans réponse à ce jour.
Sur un échiquier un cavalier doit passer une seule fois par toute les cases.
Question : combien de solutions existe-t-il ?

La source est écrite en Visual Basic pour EXCEL.
Pour la mettre en oeuvre, il suffit de copier la macro dans un classeur EXCEL, puis de lancer son exécution dans la première feuille.

L' algorithme permet dans son principe de trouver toutes les solutions.
Quelques résultats:
87 solutions en 87secondes
1 594 solutions en 901 secondes
2 051 solutions en 4 617 secondes (1.283 heures)
4 158 solutions en 12 381 secondes (3.429 heures)
11 100 solutions en 63 875 secondes (4.784 heures)

Source / Exemple :


Sub Macro1()
  
'<<<<< La promenade d'un cavalier sur un échiquier >>>>
' version 2  

'numérotation des cases : de gauche à droite et de bas en haut
  
' _57_58_59_60_61_62_63_64
' _49_50_51_52_53_54_55_56
' _41_42_43_44_45_46_47_48
' _33_34_35_36_37_38_39_40
' _25_26_27_28_29_30_31_32
' _17_18_19_20_21_22_23_24
' __9_10_11_12_13_14_15_16
' __1__2__3__4__5__6__7__8
  
' Pour le coup suivant,l'algorithme de progression du cavalier passe par le balayage des cases de sortie permises : de gauche à droite et de bas en haut
' La numérotation est la suivante:
  
'  ¤7¤8¤
'  5¤¤¤6
'  ¤¤X¤¤
'  3¤¤¤4
'  ¤1¤2¤
  
' Cinq tableaux sont définis:
  
' Tableau D : D(5)=4 signifie que pour la case 5, le cavalier dispose au maximum de 4 cases de sorties (en l'occurence : 11, 15, 20, 22)
' Tableau T : T(1,5)=11 signifie que pour la case 5, la première case (1) de sortie possible est la case 11
' Le tableau A mémorise la suite des numéros des cases parcourues, et donc les solutions quand il en a
' Le tableau B mémorise la suite des numéros de sortie
' Le tableau C mémorise la suite des rangs des cases parcourues
' Le tableau E mémorise cette suite
     
Dim T(1 To 8, 1 To 64) As Integer, A(1 To 64) As Integer, B(1 To 64) As Integer, C(1 To 64) As Integer, D(1 To 64) As Integer, E(1 To 64) As Integer
Dim N As Integer, I As Integer, P As Integer, x As Integer, µ As Integer,L As Integer,k As Integer
     
D(1) = 2: D(2) = 3: D(3) = 4: D(4) = 4: D(5) = 4: D(6) = 4: D(7) = 3: D(8) = 2: D(9) = 3: D(10) = 4: D(11) = 6: D(12) = 6: D(13) = 6: D(14) = 6: D(15) = 4: D(16) = 3: D(17) = 4: D(18) = 6: D(19) = 8: D(20) = 8: D(21) = 8: D(22) = 8: D(23) = 6: D(24) = 4: D(25) = 4: D(26) = 6: D(27) = 8: D(28) = 8: D(29) = 8: D(30) = 8: D(31) = 6: D(32) = 4: D(33) = 4: D(34) = 6: D(35) = 8: D(36) = 8: D(37) = 8: D(38) = 8: D(39) = 6: D(40) = 4: D(41) = 4: D(42) = 6: D(43) = 8: D(44) = 8: D(45) = 8: D(46) = 8: D(47) = 6: D(48) = 4: D(49) = 3: D(50) = 4: D(51) = 6: D(52) = 6: D(53) = 6: D(54) = 6: D(55) = 4: D(56) = 3: D(57) = 2: D(58) = 3: D(59) = 4: D(60) = 4: D(61) = 4: D(62) = 4: D(63) = 3: D(64) = 2
  
T(1, 1) = 11: T(1, 2) = 12: T(1, 3) = 9: T(1, 4) = 10: T(1, 5) = 11: T(1, 6) = 12: T(1, 7) = 13: T(1, 8) = 14: T(1, 9) = 3: T(1, 10) = 4: T(1, 11) = 1: T(1, 12) = 2: T(1, 13) = 3: T(1, 14) = 4: T(1, 15) = 5: T(1, 16) = 6: T(1, 17) = 2: T(1, 18) = 1: T(1, 19) = 2: T(1, 20) = 3: T(1, 21) = 4: T(1, 22) = 5: T(1, 23) = 6: T(1, 24) = 7: T(1, 25) = 10: T(1, 26) = 9: T(1, 27) = 10: T(1, 28) = 11: T(1, 29) = 12: T(1, 30) = 13: T(1, 31) = 14: T(1, 32) = 15: T(1, 33) = 18: T(1, 34) = 17: T(1, 35) = 18: T(1, 36) = 19: T(1, 37) = 20: T(1, 38) = 21: T(1, 39) = 22: T(1, 40) = 23: T(1, 41) = 26: T(1, 42) = 25: T(1, 43) = 26: T(1, 44) = 27: T(1, 45) = 28: T(1, 46) = 29: T(1, 47) = 30: T(1, 48) = 31: T(1, 49) = 34: T(1, 50) = 33: T(1, 51) = 34: T(1, 52) = 35: T(1, 53) = 36: T(1, 54) = 37: T(1, 55) = 38: T(1, 56) = 39: T(1, 57) = 42: T(1, 58) = 41: T(1, 59) = 42: T(1, 60) = 43: T(1, 61) = 44: T(1, 62) = 45: T(1, 63) = 46: T(1, 64) = 47
T(2, 1) = 18: T(2, 2) = 17: T(2, 3) = 13: T(2, 4) = 14: T(2, 5) = 15: T(2, 6) = 16: T(2, 7) = 22: T(2, 8) = 23: T(2, 9) = 19: T(2, 10) = 20: T(2, 11) = 5: T(2, 12) = 6: T(2, 13) = 7: T(2, 14) = 8: T(2, 15) = 21: T(2, 16) = 22: T(2, 17) = 11: T(2, 18) = 3: T(2, 19) = 4: T(2, 20) = 5: T(2, 21) = 6: T(2, 22) = 7: T(2, 23) = 8: T(2, 24) = 14: T(2, 25) = 19: T(2, 26) = 11: T(2, 27) = 12: T(2, 28) = 13: T(2, 29) = 14: T(2, 30) = 15: T(2, 31) = 16: T(2, 32) = 22: T(2, 33) = 27: T(2, 34) = 19: T(2, 35) = 20: T(2, 36) = 21: T(2, 37) = 22: T(2, 38) = 23: T(2, 39) = 24: T(2, 40) = 30: T(2, 41) = 35: T(2, 42) = 27: T(2, 43) = 28: T(2, 44) = 29: T(2, 45) = 30: T(2, 46) = 31: T(2, 47) = 32: T(2, 48) = 38: T(2, 49) = 43: T(2, 50) = 35: T(2, 51) = 36: T(2, 52) = 37: T(2, 53) = 38: T(2, 54) = 39: T(2, 55) = 40: T(2, 56) = 46: T(2, 57) = 51: T(2, 58) = 43: T(2, 59) = 44: T(2, 60) = 45: T(2, 61) = 46: T(2, 62) = 47: T(2, 63) = 48: T(2, 64) = 54
T(3, 2) = 19: T(3, 3) = 18: T(3, 4) = 19: T(3, 5) = 20: T(3, 6) = 21: T(3, 7) = 24: T(3, 9) = 26: T(3, 10) = 25: T(3, 11) = 17: T(3, 12) = 18: T(3, 13) = 19: T(3, 14) = 20: T(3, 15) = 30: T(3, 16) = 31: T(3, 17) = 27: T(3, 18) = 12: T(3, 19) = 9: T(3, 20) = 10: T(3, 21) = 11: T(3, 22) = 12: T(3, 23) = 13: T(3, 24) = 30: T(3, 25) = 35: T(3, 26) = 20: T(3, 27) = 17: T(3, 28) = 18: T(3, 29) = 19: T(3, 30) = 20: T(3, 31) = 21: T(3, 32) = 38: T(3, 33) = 43: T(3, 34) = 28: T(3, 35) = 25: T(3, 36) = 26: T(3, 37) = 27: T(3, 38) = 28: T(3, 39) = 29: T(3, 40) = 46: T(3, 41) = 51: T(3, 42) = 36: T(3, 43) = 33: T(3, 44) = 34: T(3, 45) = 35: T(3, 46) = 36: T(3, 47) = 37: T(3, 48) = 54: T(3, 49) = 59: T(3, 50) = 44: T(3, 51) = 41: T(3, 52) = 42: T(3, 53) = 43: T(3, 54) = 44: T(3, 55) = 45: T(3, 56) = 62: T(3, 58) = 52: T(3, 59) = 49: T(3, 60) = 50: T(3, 61) = 51: T(3, 62) = 52: T(3, 63) = 53
T(4, 3) = 20: T(4, 4) = 21: T(4, 5) = 22: T(4, 6) = 23: T(4, 10) = 27: T(4, 11) = 21: T(4, 12) = 22: T(4, 13) = 23: T(4, 14) = 24: T(4, 15) = 32: T(4, 17) = 34: T(4, 18) = 28: T(4, 19) = 13: T(4, 20) = 14: T(4, 21) = 15: T(4, 22) = 16: T(4, 23) = 29: T(4, 24) = 39: T(4, 25) = 42: T(4, 26) = 36: T(4, 27) = 21: T(4, 28) = 22: T(4, 29) = 23: T(4, 30) = 24: T(4, 31) = 37: T(4, 32) = 47: T(4, 33) = 50: T(4, 34) = 44: T(4, 35) = 29: T(4, 36) = 30: T(4, 37) = 31: T(4, 38) = 32: T(4, 39) = 45: T(4, 40) = 55: T(4, 41) = 58: T(4, 42) = 52: T(4, 43) = 37: T(4, 44) = 38: T(4, 45) = 39: T(4, 46) = 40: T(4, 47) = 53: T(4, 48) = 63: T(4, 50) = 60: T(4, 51) = 45: T(4, 52) = 46: T(4, 53) = 47: T(4, 54) = 48: T(4, 55) = 61: T(4, 59) = 53: T(4, 60) = 54: T(4, 61) = 55: T(4, 62) = 56
T(5, 11) = 26: T(5, 12) = 27: T(5, 13) = 28: T(5, 14) = 29: T(5, 18) = 33: T(5, 19) = 25: T(5, 20) = 26: T(5, 21) = 27: T(5, 22) = 28: T(5, 23) = 38: T(5, 26) = 41: T(5, 27) = 33: T(5, 28) = 34: T(5, 29) = 35: T(5, 30) = 36: T(5, 31) = 46: T(5, 34) = 49: T(5, 35) = 41: T(5, 36) = 42: T(5, 37) = 43: T(5, 38) = 44: T(5, 39) = 54: T(5, 42) = 57: T(5, 43) = 49: T(5, 44) = 50: T(5, 45) = 51: T(5, 46) = 52: T(5, 47) = 62: T(5, 51) = 57: T(5, 52) = 58: T(5, 53) = 59: T(5, 54) = 60
T(6, 11) = 28: T(6, 12) = 29: T(6, 13) = 30: T(6, 14) = 31: T(6, 18) = 35: T(6, 19) = 29: T(6, 20) = 30: T(6, 21) = 31: T(6, 22) = 32: T(6, 23) = 40: T(6, 26) = 43: T(6, 27) = 37: T(6, 28) = 38: T(6, 29) = 39: T(6, 30) = 40: T(6, 31) = 48: T(6, 34) = 51: T(6, 35) = 45: T(6, 36) = 46: T(6, 37) = 47: T(6, 38) = 48: T(6, 39) = 56: T(6, 42) = 59: T(6, 43) = 53: T(6, 44) = 54: T(6, 45) = 55: T(6, 46) = 56: T(6, 47) = 64: T(6, 51) = 61: T(6, 52) = 62: T(6, 53) = 63: T(6, 54) = 64
T(7, 19) = 34: T(7, 20) = 35: T(7, 21) = 36: T(7, 22) = 37: T(7, 27) = 42: T(7, 28) = 43: T(7, 29) = 44: T(7, 30) = 45: T(7, 35) = 50: T(7, 36) = 51: T(7, 37) = 52: T(7, 38) = 53: T(7, 43) = 58: T(7, 44) = 59: T(7, 45) = 60: T(7, 46) = 61
T(8, 19) = 36: T(8, 20) = 37: T(8, 21) = 38: T(8, 22) = 39: T(8, 27) = 44: T(8, 28) = 45: T(8, 29) = 46: T(8, 30) = 47: T(8, 35) = 52: T(8, 36) = 53: T(8, 37) = 54: T(8, 38) = 55: T(8, 43) = 60: T(8, 44) = 61: T(8, 45) = 62: T(8, 46) = 63
  
N = 1: I = 2: C(I) = N: A(N) = I: P = 0: x = 1

Cells(1, 69) = Time

1:
' L balaie le tableau D en commençant par la valeur x
For L = x To D(I)
' k est le numéro de la case de sortie possible
    k = T(L, I)
' si cette case n'a pas déjà été parcourue
    If C(k) = 0 Then
' mémorisation de la case et coup suivant
        B(N) = L
        N = N + 1
        I = k
        C(I) = N
        A(N) = I
        If N = 64 Then
' P compte le nombre de solutions trouvées
            P = P + 1
' affichage du nombre de solutions et d'itérations
            Cells(5, 67) = P
            Cells(5, 69) = Time

' affichage des solutions ( retirer les apostrophes ' placées au début des trois lignes suivantes)
'            For µ = 1 To 64
'                Cells(P, µ) = A(µ)
'            Next µ
            GoTo 2
            Else
                x = 1
                GoTo 1
            End If
    End If
Next L
2:
' si cette case a déjà été parcourue : retour d'une case en arrière
A(N) = 0
C(I) = 0
N = N - 1
E(N) = N
I = A(N)
L = B(N) + 1
If L > D(I) Then
    GoTo 2
    Else
        x = L
        GoTo 1
End If
End Sub

Conclusion :


Vos commentaires et vos notations seront les bienvenus.

A voir également

Ajouter un commentaire

Commentaires

Messages postés
86
Date d'inscription
jeudi 18 août 2005
Statut
Membre
Dernière intervention
20 février 2007

_DoOmy_

Merci : ce site est en effet très intéressant
Messages postés
15
Date d'inscription
samedi 19 novembre 2005
Statut
Membre
Dernière intervention
17 septembre 2006

pour des généralités sur le cavalier d'euler
http://www.recreomath.qc.ca/dict_cavalier.htm
Messages postés
86
Date d'inscription
jeudi 18 août 2005
Statut
Membre
Dernière intervention
20 février 2007

Merci WARNY pour ta réponse.
Je vais rechercher l'article en question dans ce magazine.
Messages postés
473
Date d'inscription
mercredi 7 août 2002
Statut
Membre
Dernière intervention
10 juin 2015

C'etait dans l'excelent mais oh combien complexe hebdomadaire "la recherche", et je dois avouer que c'était assez chaud.
Le principe était de rajouter 2 dimensions (pour arriver à 4 dimensions) à la représentation de l'échiquier ce qui permettait d'éliminer certains tests récurrents.
Ceci dit, je dois avouer que l'explication complète était hors de portée et de ma comprehension et de ma mémoire.

Tout ce que j'ai retenu de l'article, c'est que pratiquement tous les problèmes d'echecs pouvaient être interprétés dans un espace fini à 4 dimensions.
Messages postés
86
Date d'inscription
jeudi 18 août 2005
Statut
Membre
Dernière intervention
20 février 2007

A l'attention de WARNY
Merci pour ton conseil, mais comme je l'ai dit le 18/08, j'ai pris finalement le parti de supprimer le compteur J.
Je serais très intéressé d'en savoir plus sur la solution du circuit fermé que tu évoques.
Afficher les 14 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.