Euler et le cavalier sur l' echiquier


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

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.