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) |
Problème du cavalier : Amélioration d'un code récursif
) 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.
) . Merci de votre indulgence !
Répondre avec citation
Envoyé par jbafraisse
Partager