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

 

Aux échecs, le cavalier est une pièce atypique. Alors que les autres pièces se déplacent horizontalement, verticalement ou obliquement, le cavalier progresse de façon asymétrique. C’est le trouble-fête du jeu d’échecs. Il est un peu comme le méchant dans un roman. Il est permis de penser que le jeu d’échecs n’aurait pas connu autant de succès sans la présence de cet être redoutable. Il s’introduit de façon sournoise sur des cases en passant par-dessus d’autres pièces.

 

Le cavalier se déplace en forme de L, soit d’une case horizontalement (ou verticalement) et de deux cases verticalement (ou horizontalement). Sur le tablier du jeu d’échecs, il progresse dans tous les sens, d’une case noire à une blanche ou inversement. Il se déplace à la fois comme la tour et comme le fou. À partir du centre d’une grille 5 × 5, il peut atteindre huit cases au plus. Dans la grille ci-dessous, le B indique la case d’arrivée quand le départ se fait en A.

 

 

B

 

B

 

B

 

 

 

B

 

 

A

 

 

B

 

 

 

B

 

B

 

B

 

 

Les problèmes de cavalier sont fort nombreux. L’un des plus connus est celui qui consiste à faire en sorte qu’un cavalier parcoure toutes les cases d’une grille donnée.

 

Cet article est constitué de trois volets. Dans le premier volet, on étudie comment se comporte le cavalier dans des grilles carrées et rectangulaires. Dans le second, on décrit brièvement 12 stratégies pour que le cavalier puisse occuper toutes les cases d’une grille carrée. Dans le troisième, on dévoile le secret d’un tour de magie.

 

Volet A. Le cavalier dans des grilles carrées et rectangulaires

Notre étude se fait dans des grilles de petite taille.

 

Une grille 3 × 3

Dans une grille 3 × 3, le problème a peu d’intérêt. On ne peut pas placer le cavalier dans la case centrale. Si on le place dans une autre case, il ne peut pas atteindre le centre. Lorsqu’il part d’une case périphérique, il peut atteindre deux cases au plus dans un premier pas. Voici un exemple de parcours en partant de la case 1 :

 

1

6

3

4

 

8

7

2

5

 

Si le cavalier est autorisé à visiter de nouveau les mêmes cases, il n’arrêtera jamais. En mathématiques, on dit qu’il forme un circuit ou un parcours fermé parce que son chemin est complet.

 

Une grille 4 × 4

Dans une grille 4 × 4, il existe trois groupes de cases équivalentes, soit celles marquées A, B et C.

 

A

B

B

A

B

C

C

B

B

C

C

B

A

B

B

A

 

Si on part d’une case A, par exemple, et si on trouve une configuration, celle-ci vaut pour les trois autres cases A parce qu’on peut faire des rotations.

 

Dans une grille 4 × 4, peu importe la case de départ, le cavalier peut parcourir au plus 15 cases.  C’est le cas lorsque le départ se fait dans un coin. Voici un exemple :

 

1

8

15

 

14

11

4

7

5

2

9

12

10

13

6

3

 

Lorsque le cavalier part d’une case autre que celles des coins, il ne peut parcourir que 14 cases. Voici une configuration :

 

 

4

13

2

12

1

10

7

5

8

3

14

 

11

6

9

 

Ce sont toujours les cases des coins qui causent des problèmes parce que, si on les atteint, il faut avoir une case libre pour en ressortir.

 

Une grille 5 × 5

On commence par colorer les cases en deux teintes comme sur l’échiquier.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


On remarque que la grille contient 13 cases noires et 12 cases pâles. Or, d’un saut à l’autre, le cavalier passe d’une case noire à une pâle ou d’une pâle à une noire. S’il part d’une case pâle, la deuxième case est noire, la troisième est pâle, la quatrième est noire, etc. En conséquence, la 24
e case est noire. Il reste alors une seule case qui est noire. Le cavalier ne peut pas l’atteindre. Aussi, lorsque le cavalier part d’une case pâle, il peut parcourir 24 cases au plus. Voici un exemple où le cavalier part d’une case pâle :

 

14

1

16

7

12

17

6

13

2

21

24

15

20

11

8

5

18

9

22

3

 

23

4

19

10

 

Le cavalier a atteint 24 cases, alors que la case inférieure gauche est noire. À partir de la case 24, le cavalier pourrait atteindre la case 1.

 

À partir de cet exemple, on peut montrer que, peu importe la case pâle de départ, une configuration existe pour toute case de départ de cette teinte. En effet, comme on a obtenu un circuit, le cavalier peut parcourir 24 cases. Par exemple, si la case de départ est celle marquée 5 dans le cas précédent, la case 6 deviendra 2, la 7 deviendra 3, …, la 24 deviendra 20, la 1 deviendra 21, la 2 deviendra 22, etc. Voici la nouvelle configuration issue de ce même parcours :

 

10

21

12

3

8

13

2

9

22

17

20

11

16

7

4

1

14

5

18

23

 

19

24

15

6

 

En mathématiques, on dit que cette démonstration est élégante. Elle est simple, relativement courte et utilise un moyen détourné, les couleurs. En plus, elle est visuelle.

 

Si le cavalier part d’une case noire, les cases de rang impair seront noires. Aussi, la 25e case sera de cette couleur. Voici un exemple de parcours où le cavalier part d’une case noire :

 

1

24

19

14

3

18

13

2

9

20

23

8

25

4

15

12

17

6

21

10

7

22

11

16

5

 

Si le cavalier partait de la case marquée 25, on pourrait suivre le chemin à rebours et on aurait une autre configuration où le cavalier atteint 25 cases. L’arrivée se ferait alors sur la case marquée 1. Voici une configuration où le cavalier tourne dans le même sens jusqu’à la case marquée 15, sans toutefois réaliser un circuit :

 

23

12

7

2

25

6

1

24

13

8

11

22

15

18

3

16

5

20

9

14

20

10

17

4

19

 

Voici un exemple où le cavalier se déplace en tournant toujours dans le même sens et qui finit sa course au centre, ne pouvant atteindre la case 1 :

 

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 3 × 4

Le cavalier peut parcourir toutes les cases d’une telle grille. Par exemple, on place le cavalier dans la case centrale de la première colonne et on se déplace dans le sens contraire des aiguilles d’une montre. On obtient cette configuration.

 

12

9

6

3

1

4

11

8

10

7

2

5

 

De 13, on soustrait chaque élément du rectangle précédent. On obtient un chemin qui débute dans le coin supérieur gauche. C’est une seconde configuration.

 

1

4

7

10

12

9

2

5

3

6

11

8

 

On intervertit la première et la troisième ligne. On obtient une configuration équivalente.

 

3

6

11

8

12

9

2

5

1

4

7

10

 

Une grille 3 × 5

Le cavalier ne peut pas parcourir toutes les cases de cette grille. Au maximum, il peut en atteindre 14. Voici une configuration :

 

1

4

13

10

7

14

9

6

3

12

5

2

11

8

 

 

Une grille 3 × 6

Dans cette grille, le cavalier peut parcourir 17 cases sur 18. Voici un exemple :

 

7

2

5

14

9

12

4

15

8

11

 

17

1

6

3

16

13

10

 

Une grille 3 × 7

Dans cette grille, le cavalier peut parcourir toutes les cases. Une façon de procéder peut être de remplir le contour de la grille 3 × 3 de gauche et de faire de même dans la grille 3 × 3 de droite.

 

1

4

7

18

15

10

13

6

19

2

9

12

21

16

3

8

5

20

17

14

11

 

Il est possible de trouver des configurations pour les grilles dont un côté contient quatre cases à partir de 4 × 5. Voici un exemple dans trois cas :

 

Une grille 4 × 5

 

1

14

5

18

9

6

19

10

15

4

13

2

17

8

11

20

7

12

3

16

 

Une grille 4 × 6

 

1

24

7

16

3

20

8

15

2

19

12

17

23

6

13

10

21

4

14

9

22

5

18

11

 

Une grille 4 × 7

 

1

24

11

28

7

20

5

12

27

14

21

4

17

8

23

2

25

10

15

6

19

26

13

22

3

18

9

16

 

Une grille 5 × 6

Il est possible de trouver des configurations pour les grilles dont un côté contient cinq cases. Voici un exemple dans une grille 5 × 6 :

 

1

14

21

28

3

12

22

27

2

13

20

29

15

8

17

24

11

4

26

23

6

9

30

19

7

16

25

18

5

10

 

 

Volet B. Stratégies pour remplir des grilles carrées

Nous donnons brièvement 12 stratégies pour que le cavalier atteigne toutes les cases dans une grille carrée.

 

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 configuration 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 le 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 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 configuration.

 

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

 

Volet C. Tour de magie

Il y a quelques années, un jeune garçon de huit ans a épaté ses proches. Il demandait à une personne de lui indiquer une case de départ sur un échiquier, soit une grille 8 × 8. Il plaçait son cavalier sur cette case et disait qu’il pouvait remplir la grille assez rapidement. En soi, c’était un tour de magie remarquable parce que, si on tente l’expérience sans modèle, on peut y passer plusieurs heures à vouloir atteindre toutes les cases.

 

Quel était son truc ? Il s’inspirait d’une grille 8 × 8 dans laquelle le cavalier formait un circuit. Il avait appris par cœur le parcours : ce qui est quand même tout à son honneur. Ainsi, il pouvait remplir la grille en suivant le chemin.

 

Par exemple, on prend la grille de gauche comme modèle. Si on place le cavalier dans le coin supérieur gauche de la grille de droite, on aura le parcours suivant :

 

18

31

16

35

20

33

 

1

14

35

18

3

16

15

2

19

32

9

36

 

34

21

2

15

28

19

30

17

8

1

34

21

 

13

36

27

20

17

4

3

14

23

26

7

10

 

22

33

6

9

26

29

24

29

12

5

22

27

 

7

12

31

24

5

10

13

4

25

28

11

6

 

32

23

8

11

30

25

 

Si vous avez un enfant ou un petit-enfant particulièrement futé et ayant une bonne mémoire visuelle, apprenez-lui ce tour de magie. Il pourra épater ses amis.