Dictionnaire de mathématiques récréatives Circuit du cavalier

Cavalier

° Circuit du cavalier. – Problème ancien retrouvé dans de vieux manuscrits consacrés aux échecs : Déterminez le trajet parcouru par un cavalier qui part d'une case quelconque de l'échiquier, qui visite toutes les cases une et une seule fois et qui revient au point de départ.

Cela revient à trouver le circuit hamiltonien du graphe représentant l'échiquier, en considérant toute case comme un point-sommet et en traçant les arêtes qui correspondent au déplacement du cavalier d'une case à l'autre.

Voici une solution où chaque nombre indique le rang d'un saut :

47	50	31	28	37	52	33	56
30	27	48	51	32	55	10	53
49	46	29	38	11	36	57	34
26	3	40	7	44	13	54	9
41	22	45	12	39	8	35	58
2	25	4	43	6	61	14	17
21	42	23	64	19	16	59	62
24	1	20	5	60	63	18	15

Des variantes de ce problème sont appliquées à des grilles carrées ou rectangulaires de mesures variées ou même à des grilles de différentes formes. Sur certaines figures, comme la grille carrée d'ordre n où n est impair, il est impossible de former un circuit, même si le cavalier peut visiter toutes les cases.

Euler (1707-1783) réalisa un circuit en partageant l'échiquier en deux rectangles. Les 32 premiers nombres se trouvent dans la moitié inférieure et les 32 suivants dans la partie supérieure.

37	62	43	56	35	60	41	50
44	55	36	61	42	49	34	59
63	38	53	46	57	40	51	48
54	45	64	39	52	47	58	33
1	26	15	20	7	32	13	22
16	19	8	25	14	21	6	31
27	2	17	10	29	4	23	12
18	9	28	3	24	11	30	5

Emmanuel Laquière (1855-1920) a donné en 1881 une façon pour le cavalier de parcourir les 64 cases d’un échiquier. Il a partagé l’échiquier en quatre quadrants :

Dans les deux grilles de gauche, la trace des mouvements forme des losanges reliés ; dans les deux autres, ce sont des carrés. Quand on dispose ces traces sur un échiquier, on obtient un circuit :

2	19	64	47	6	21	50	35
63	46	3	20	49	34	7	22
18	1	48	61	24	5	36	51
45	62	17	4	33	52	23	8
16	31	60	41	12	25	54	37
59	44	13	32	53	40	9	26
30	15	42	57	28	11	38	55
43	58	29	14	39	56	27	10

Index : C

Voir :

Cavalier d'Euler

Coins du cavalier

Échange de cavaliers

Parcours du cavalier