Accueil

Banque de problèmes récréatifs

Défis

Détente

Jeux de société

Quiz

Récréations cryptarithmiques

Récréations géométriques

Récréations logiques

Récréations magiques

Récréations numériques

Banque d'outils mathématiques

Aide-mémoire

Articles

Dictionnaire de mathématiques récréatives

Lexique de résolution de problèmes

Livres édités

Références

Contactez-nous


 Articles

Ceci est le 27e article publié par Récréomath


Parcours du cavalier

Par Charles-É. Jean

 

Le cavalier aux échecs est une pièce atypique. Il passe d’une case noire à une case blanche et vice versa en se déplaçant sous forme d’un L. Dans une grille 3 × 3, il peut se mouvoir en suivant les numéros suivants.

 

6

1

4

3

 

7

8

5

2

 

Un des problèmes principaux concernant le cavalier consiste à déterminer s’il peut parcourir toutes les cases d’une grille donnée. Par exemple, on sait que, dans une grille 4 × 4, le cavalier ne peut parcourir que 14 ou 15 cases sur 16, la difficulté étant créée par l’entrée et la sortie des cases des coins.

 

Dans cet article, nous allons donner brièvement 12 stratégies lorsque le cavalier se déplace dans une grille carrée. La case de départ portera le numéro 1 et chaque autre case visitée sera numérotée dans l’ordre.

 

1. Repli stratégique

Dans une grille de grandeur donnée, on commence par écrire 1, 2, 3, 4, … en respectant le saut du cavalier. Quand le cavalier est bloqué, on retourne en arrière d’un ou de plusieurs pas. On reprend le chemin en visitant une autre case que la dernière. On continue ainsi jusqu’on soit obligé de refaire la même opération.

 

 

2. Comptage de cases

Le mathématicien allemand Warnsdorff a décrit une stratégie. On compte les cases possibles d’accès et on choisit toujours de visiter la case qui en possède le plus petit nombre. On réserve certaines cases sur lesquelles le cavalier pourrait passer. Dans la grille suivante, le nombre indique les possibilités d’atteindre toute case. Ainsi, quand une case est marquée 3, cela veut dire que le cavalier peut partir de trois cases pour l’atteindre. Le cavalier peut partir des trois cases grises pour atteindre la case 3 en rouge.

 

2

3

4

3

2

3

4

6

4

3

4

6

8

6

4

3

4

6

4

3

2

3

4

3

2

 

Par exemple, pour visiter les cases des coins, on peut entrer par une case marquée 6 et sortir pour atteindre l’autre case marquée 6.

 

 

3. Parcours entier de couronnes

On partage la grille de façon à avoir au moins une couronne comportant deux rangées de cases. Le cavalier visite toutes les cases de la couronne avant de passer à une autre couronne. Voici une grille où le cavalier se déplace dans le sens des aiguilles d’une montre :

 

1

14

9

20

3

24

19

2

15

10

13

8

25

4

21

18

23

6

11

16

7

12

17

22

5

 

Une grille 9 × 9 qui comporte une couronne est donnée. Les cases jaunes indiquent le passage d’une couronne à l’autre.

 

1

56

29

42

15

54

27

40

13

30

43

16

55

28

41

14

53

26

17

2

57

80

69

74

63

12

39

44

31

70

75

64

79

68

25

52

3

18

65

58

81

62

73

38

11

32

45

76

71

60

67

78

51

24

19

4

59

66

77

72

61

10

37

46

33

6

21

48

35

8

23

50

5

20

47

34

7

22

49

36

9

 

Une grille 13 × 13 qui comporte deux couronnes est donnée. Les cases jaunes indiquent le passage d’une couronne à l’autre.

 

1

88

45

66

23

86

43

64

21

84

41

62

19

46

67

24

87

44

65

22

85

42

63

20

83

40

25

2

89

144

117

130

103

142

115

128

101

18

61

68

47

118

131

104

143

116

129

102

141

114

39

82

3

26

105

90

145

168

157

162

151

100

127

60

17

48

69

132

119

158

163

152

169

156

113

140

81

38

27

4

91

106

153

146

167

150

161

126

99

16

59

70

49

120

133

164

159

148

155

166

139

112

37

80

5

28

107

92

147

154

165

160

149

98

125

58

15

50

71

134

121

94

109

136

123

96

111

138

79

36

29

6

93

108

135

122

95

110

137

124

97

14

57

72

51

8

31

74

53

10

33

76

55

12

35

78

7

30

73

52

9

32

75

54

11

34

77

56

13

 

Dans un tel cas, la grille centrale doit être au moins 5 × 5, car il n’y a pas de solution dans une grille 3 × 3.

 

 

4. Parcours partiels de couronnes

Quand on le veut, on peut quitter la couronne ou changer de direction. Dans la grille suivante, au départ, le cavalier se déplace dans les sens des aiguilles d’une montre. Il rejoint le centre au pas 17 et revient dans la couronne tout en changeant de direction :

 

1

14

9

22

3

18

23

2

15

10

13

8

17

4

21

24

19

6

11

16

7

12

25

20

5

 

 

5. Les quatre coins

Dans une grille 5 × 5, on conserve libres les cases colorées dont celles des coins pour les visiter à la fin. En cours de route, on peut changer de sens si on le veut.

 

25

12

17

2

23

6

1

24

11

16

13

18

7

22

3

8

5

20

15

10

19

14

9

4

21

 

 

6. Un quadrant à la fois

On partage une grille 10 × 10 en quatre carrés de même grandeur. Le cavalier passe par toutes les cases d’un premier quadrant, rejoint un deuxième, un troisième et un quatrième quadrant où il fait de même. Voici un exemple où le cavalier parcourt 100 cases dans une grille 10 × 10 partagée en quatre quadrants 5 × 5 :

 

28

37

42

47

26

1

22

11

16

3

43

46

27

36

41

12

17

2

21

10

38

29

44

33

48

25

8

23

4

15

45

50

31

40

35

18

13

6

9

20

30

39

34

49

32

7

24

19

14

5

51

56

67

62

73

100

79

90

85

98

66

61

72

57

68

89

84

99

80

91

55

52

69

74

63

76

93

78

97

86

60

65

54

71

58

83

88

95

92

81

53

70

59

64

75

94

77

82

87

96

 

 

7. Sauts de quadrants

On partage la grille 8 × 8 en quatre carrés de même grandeur. Le cavalier passe par quatre cases d’un premier quadrant, d'un deuxième, d'un troisième et d'un quatrième quadrant. Après 16 cases, le cavalier peut changer de sens. Pour une même séquence, on respecte les mêmes dispositions dans les quatre quadrants. Voici un premier exemple où le cavalier change de sens après le pas 16 :  

6

23

54

37

10

19

50

35

55

38

7

22

51

36

11

18

24

5

40

53

20

9

34

49

39

56

21

8

33

52

17

12

58

25

4

41

64

13

48

31

3

42

57

28

45

32

63

16

26

59

44

1

14

61

30

47

43

2

27

60

29

46

15

62

 

Fait intéressant. Le cavalier suit un parcours fermé. Il peut passer de la case 1 à la case 64.

 

Voici un deuxième exemple où le cavalier change de sens après le pas 32 :  

1

58

41

20

5

56

39

22

18

43

4

57

40

21

6

55

59

2

19

42

53

8

23

38

44

17

60

3

24

37

54

7

15

62

29

48

9

52

25

36

30

45

16

61

28

33

10

51

63

14

47

32

49

12

35

26

46

31

64

13

34

27

50

11

 

8. Partage en rectangles

On peut partager la grille en deux rectangles, résoudre le premier rectangle et passer au second. Voici un exemple où le deuxième rectangle montre un parcours similaire au premier :

 

1

30

15

20

7

22

13

26

16

19

8

29

14

25

6

23

31

2

17

10

21

4

27

12

18

9

32

3

28

11

24

5

33

62

47

52

39

54

45

58

48

51

40

61

46

57

38

55

63

34

49

42

53

36

59

44

50

41

64

35

60

43

56

37

 

 

9. Parcours complémentaire

Pour trouver le parcours complémentaire dans une grille n × n, de (n2 + 1), on soustrait chaque élément qui correspond au pas du cavalier. En d’autres mots, on part de la case d’arrivée et on remonte jusqu’à la case de départ, soit dans l’ordre inverse. Voici deux grilles complémentaires l’une de l’autre :

 

1

10

21

16

3

25

16

5

10

23

20

15

2

9

22

6

11

24

17

4

25

8

11

4

17

1

18

15

22

9

14

19

6

23

12

12

7

20

3

14

7

24

13

18

5

19

2

13

8

21

 

 

10. Circuit fermé

Lorsque le parcours du cavalier est fermé, c’est-à-dire qu’il est possible de passer de la dernière case visitée à la première dans une même grille, le départ du cavalier peut se faire sur n’importe laquelle case. Dans cette grille 6 × 6, on peut passer de la case 36 à la case 1.

 

26

13

28

9

24

11

29

2

25

12

31

8

14

27

30

1

10

23

3

36

21

18

7

32

20

15

34

5

22

17

35

4

19

16

33

6

 

Pour trouver une seconde grille, on part de la case 26 de la première grille. On passe par 27, 28, 29, etc. Après 36, on saute à 1 et on continue.

 

1

24

3

20

35

22

4

13

36

23

6

19

25

2

5

12

21

34

14

11

32

29

18

7

31

26

9

16

33

28

10

15

30

27

8

17

 

 

11. Chemin séquentiel

À partir d’une grille dûment parcourue par le cavalier, on peut choisir une séquence et modifier son chemin, tout en préservant l’accès au reste du parcours. Dans l’exemple suivant, on a modifié le parcours dans les cases jaunes. Cela donne une autre solution.

 

26

13

28

9

24

11

26

13

28

9

24

11

29

2

25

12

31

8

29

8

25

12

31

2

14

27

30

1

10

23

14

27

30

1

10

23

3

36

21

18

7

32

7

36

21

18

3

32

20

15

34

5

22

17

20

15

34

5

22

17

35

4

19

16

33

6

35

6

19

16

33

4

 

 

12. Corrections

Lorsque le cavalier ne peut plus avancer et qu’il reste quelques cases libres, on peut tenter de faire des corrections en modifiant ou en ajoutant des séquences.

 

Dans la grille suivante de gauche, deux cases sont libres. Elles sont reliées entre elles par le saut du cavalier. On doit viser à atteindre l’une des deux. On place 10 sous le 3, 11 sous le 4, 24 sous le 1 et 25 sous le 2. Seules les cases jaunes sont modifiées.

 

1

14

9

20

3

1

14

9

20

3

10

19

2

15

 

24

19

2

15

10

13

8

11

4

21

13

8

25

4

21

18

23

6

 

16

18

23

6

11

16

7

12

17

22

5

7

12

17

22

5

 

 

En guise de conclusion
Certaines stratégies peuvent être combinées à une ou plusieurs autres stratégies : ce qui enrichit davantage la boîte à outils.

 

Par ailleurs, il serait intéressant de voir si ces stratégies peuvent s’appliquer à une grille rectangulaire.

 

FIN