Bonjour à tous,

dans le cadre d'un projet, j'ai réalisé un programme permettant de résoudre le problème des cavaliers.
Pour ceux qui ne le connaissent pas voici le résumé de Wikipédia :

Le problème du cavalier est un problème mathématico-logique fondé sur les déplacements du cavalier du jeu d'échecs. Un cavalier posé sur une case quelconque d'un échiquier doit en visiter toutes les cases sans passer deux fois sur la même.
Afin de résoudre ce problème je me suis lancé dans un programme en python qui réglerais récursivement ce problème.
Le voici:

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
# -*-coding:utf-8-*-
 
"""
    
    INITIALISATION DE L'ECHIQUIER
    
"""
 
# On crée un échiquier remplit de 0 (de taille m x m)
# Le programme marche avec m=5 en quelque seconde, mais même après plusieurs minutes ne trouve rien avec m=8
 
m = 5
Echiquier = [[0 for i in range(m)] for j in range(m)]
 
 
"""
 
    DÉFINITION DE LA CLASSE
    
"""
 
class Vecteur():
 
    """ Permet de retrouver x et y entré en argument avec pos.x et pos.y """
    # Classe inutile, permet juste la simplification de la lecture du code
 
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
 
"""
   
   DÉFINITION DES DIFFÉRENTES FONCTIONS
    
"""
 
def Afficher(grille):
 
    """ On affiche la grille pour plus de lisibilité """
 
    print '\n'
 
    # On écrit les lignes une par avec indication du numéro la ligne
    for i,g in enumerate(grille): print i,g
 
 
def cases_accessibles(pos):
 
    """ Fonction retournant les cases accesible par le cavalier en position pos sur l'Echiquier """
    # Tous les mouvements possible par le cavalier
    Mouvements = [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]]
 
    # On initialise la liste CA qui contiendra toutes les cases accessibles par le cavalier
    CA = []
 
    # Pour chaque mouvement contenu dans les mouvements possibles
    for mouvement in Mouvements:
        # On creer un vecteur pour que la suite soit plus lisible
        m = Vecteur(mouvement[0],mouvement[1])
 
        # new est la case que l'on atteint en effectuant le mouvement m
        new = [pos.x + m.x, pos.y + m.y]
 
        # On verifie que la case ne se trouve pas en dehors de l'echiquier
        if new[0] >= 0 and new[0]<len(Echiquier[0]) and new[1] >= 0 and new[1]<len(Echiquier):
            # On regarde si cette case n'a pas deja ete utilisee
            if Echiquier[new[0]][new[1]] == 0 :
                # On ajoute la case new aux cases accessibles par le cavalier
                CA.append(new)
 
    # On retourne toutes les cases accessibles par le cavalier
    return CA
 
 
 
def cases_restantes():
 
    """ Retourne le nombre de cases restante (=0) dans l'Echiquier """
    cases = 0
    # On parcours l'échiquier et incrémente 1 à chaque fois qu'on recontre 0 (Case libre)
    for i in range(len(Echiquier)):
        for j in range(len(Echiquier[0])):
            if Echiquier[i][j] == 0: cases +=1
 
    # On retourne le nombre de cases restante (=0) sur l'échiquier
    return cases
 
 
 
def parcours(pos, n = 0):
 
    """ Fonction récursive retournant Vrai ou Faux sur la validité du parcours et le complétant """
    # On ajoute 1 au numéro de case à chercher
    n+=1
 
    # Inutile, permet juste de suivre son fonctionnement
    print '\n---------------------------'
    print 'On met le cavalier n°%d à la case (%d, %d)' % (n, pos.x, pos.y)
    print cases_accessibles(pos)
 
    # On met le cavalier à la position entré en argument.
    Echiquier[pos.x][pos.y] = n
    Afficher(Echiquier)
 
    # S'il ne reste aucune case libre, ça veut dire que le problème est résolu !
    if cases_restantes() == 0:
        Afficher(Echiquier)
        return True
 
    # Sinon pour chaques cases accessibles par le cavalier on vérifie si la case suivante permet d'aboutir à une solution
    for c in cases_accessibles(pos):
        case = Vecteur(c[0],c[1])
        print 'On est à la position (%d, %d) se dirige vers la case (%d, %d)' % (pos.x, pos.y, case.x, case.y)
        if parcours(case,n):
            return True
 
    # Si on a testé toutes les possibilités de cette case on la remet à 0 et on passe à la case suivante
    print 'On remet à 0 la case (%d, %d)' % (pos.x, pos.y)
    Echiquier[pos.x][pos.y] = 0
    return False
 
 
def main(x,y):
    """ Programme principale appelant tous les autres et initialisation de params """
    # On cree un Vecteur position pour que ce soit plus lisible
    pos = Vecteur(x,y)
    # On appelle le programme permettant la résolution du problème
    parcours(pos)
 
# Le cavalier aura pour position de départ la case (0,0)
main(0,0)
... Oui je sais j'ai mis beaucoup de code inutile, mais c'était pour mieux comprendre le fonctionnement.

Lors des nombreux test sur ce code, j'ai remarqué qu'en quelques secondes il m'affichait une réponse exacte pour une grille 5x5. Alors comme n'importe qui j'ai essayé de faire de même avec une grille 8x8 (Grille habituelle utilisée dans un jeu d'échec). Mais là le programme met plusieurs minute et ne trouve ... RIEN !

Je me demande donc quel est le problème avec ce programme. Voyant qu'il fonctionne pour une grille 5x5, je suppose qu'il est correct (mais je peux me tromper !). Si ce dernier n'en a pas, ce que je doute fort, comment faire pour l'améliorer ? Et pour finir (oui je sais que j'en demande beaucoup ) comment faire pour afficher non seulement la première solution trouvé, mais aussi les autre sans pour autant attendre que toutes les solutions soient trouvées avant de les afficher.

Bon, j'espère que j'aurais été clair, si ce n'est pas le cas dite le moi !
Dans tous les cas merci d'avance pour votre aide

PS : Ceci est mon premier post, désolé si je n'ai pas respecté toutes les normes... Et je ne suis pas non plus un pro de python (voire même un débutant ) . Merci de votre indulgence !