valettearnaud
Le problème du cavalier
Le problème du cavalier (ou encore polygraphie ou algorithme du cavalier ou cavalier d'Euler) est un problème mathématico-logique fondé sur les déplacements du cavalier du jeu d'échecs : un cavalier partant d'une case quelconque doit visiter chaque case sans y repasser.
La résolution algorithmique du problème du cavalier sur un échiquier est une entrée captivante et exigeante dans l'univers de la théorie des graphes, des heuristiques, et de l'algorithmique elle-même. Ce problème, bien que formulé de manière simple - faire parcourir à un cavalier toutes les cases d'un échiquier sans jamais repasser deux fois par la même case - cache en réalité une complexité combinatoire qui le rend particulièrement intéressant à étudier.
La dimension amusante du problème se situe dans la proposition de considérer le lieu de l'échiquier selon le comportement d'un seul objet du jeu d'échec - le cavalier. En limitant le nombre d'acteurs possibles sur le plateau nous mettons en évidence la nature graphée de l'échiquier : un ensemble de noeuds (les cases), relié par le mouvement caractéristique d'un acteur (la pièce d'échec).
Préliminaires
Avant de résoudre le problème, il nous faut modéliser le graphe des déplacements
possibles du cavalier d'une manière qui nous sera utile.
À partir d'un ensemble de cases
\(E=\{11,..,18,21,..,28,...,88\}\)
On construit une hashmap \(X\) dont les indices \(i \in E\) et dont
les éléments \(X_{i} \subset \mathcal{P}(E)\).
La condition que l'on utilise:
(Math.abs(a[0] - b[0]) == 1 && Math.abs(a[1] - b[1]) == 2) || (Math.abs(a[0] - b[0]) == 2 && Math.abs(a[1] - b[1]) == 1)
nous permet de savoir si les sommets \(a\) et \(b\) sont adjacents (\(a \sim b\)), c'est à dire si
un cavalier peut aller de l'un à l'autre en un mouvement.
\(a \sim b \implies b \in X_{a} \implies a \in X_{b}\)
const board = {}
const l = "12345678".split("")
const f = () => l.flatMap((x) => l.map((y) => `${x}${y}`))
const nodes = f()
const cond = (a, b) =>
(Math.abs(a[0] - b[0]) == 1 && Math.abs(a[1] - b[1]) == 2) ||
(Math.abs(a[0] - b[0]) == 2 && Math.abs(a[1] - b[1]) == 1)
nodes.forEach((x) => {
board[x] = []
})
nodes.forEach((x) => {
nodes.forEach((y) => {
if (cond(x, y)) {
if (!board[x].includes(y)) {
board[x].push(y)
}
if (!board[y].includes(x)) {
board[y].push(x)
}
}
})
})
Solution
Approche naïve
Si l'on considère l'ensemble de l'échiquier comme un graphe, chacun de nos mouvements élimine un sommet et les arêtes qui lui sont incidentes. L'algorithme constitue une recherche en profondeur (depth-first search), il visite un à un les différents sommets qu'il est possible d'atteindre à partir de la position actuelle jusqu'à ce qu'aucun mouvement ne soit possible. Une solution est trouvée lorsque, une fois bloqué, le cavalier a parcouru un chemin contenant 64 entrées. À chaque fois que cette deuxième condition échoue il doit revenir en arrière et essayer d'autres cheminements à travers le graphe (backtracking).
function solve(current, board, path, visited) {
if (path.length == 64) {
return path
}
let possibles = [...board[current]]
for (let x of possibles) {
if (!visited.has(x)) {
visited.add(x)
let res = solve(x, board, path.concat(x), visited)
if (res) {
return res
}
visited.delete(x)
}
}
return null
}
function solver(position) {
let visited = new Set()
visited.add(position)
// board : {cellule:[cellules atteignables]}
return solve(position, board, [position], visited)
}
solver("E8")
Cette approche est valide et mène inévitablement à une solution dans le cas ou une solution
existe (et c'est toujours le cas, au moins sur un échiquier de 8x8).
Sur un ordinateur équipé d'un Intel(R) Core(TM) i5-8350U CPU @ 1.70GHz l'algorithme
met entre 3 et 7 minutes pour trouver une solution à partir d'une position donnée.
Une fois lancé, l'algorithme explore un grand nombre de possibilités
qui ne peuvent pas mener à une solution, bien souvent cela est dû au fait qu'il existe
un sommet isolé.
Règle de Warnsdorff
Il existe un moyen de garantir que l'algorithme évite de laisser derrière lui des sommets isolés.
Si l'on considère une position \(P_{i}\), alors on connaît le degré de chacun
des sommets \(e \in Xi\). L'algorithme précédent, en ignorant cette information,
permet par exemple d'explorer de nombreux chemins nécessairement faux:
\(X_{k} = \{i\}\)
Avec \(j \neq k \neq i\), si on part de \(P_{i}\) pour aller vers \(P_{j}\),
alors \(\deg(k)=0\); toutes les explorations subséquentes mèneront à un parcours incomplet.
Voici un exemple de comment se comporte l'algorithme naíf sans backtracking:
Afin d'éviter ce comportement, on peut implémenter la règle de Warnsdorff: privilégier en priorité les déplacements vers les sommets dont le degré est moindre.
function solve(current, board, path, visited) {
if (path.length == 64) {
return path
}
/* règle de Warnsdorff: on trie les sommets
selon leur degré, de manière croissante
*/
let possibles = [...board[current]].sort(
(a, b) => board[a].length - board[b].length,
)
for (let x of possibles) {
if (!visited.has(x)) {
visited.add(x)
let res = solve(x, board, path.concat(x), visited)
if (res) {
return res
}
visited.delete(x)
}
}
return null
}
function solver(position) {
let visited = new Set()
visited.add(position)
// board : {cellule:[cellules atteignables]}
return solve(position, board, [position], visited)
}
solver("A1")
Voilà comment se comporte l'algorithme amélioré avec backtracking: