22 décembre 2024
Depuis toujours, j’adore me faire des nœuds avec le malheureux neurone qui traine dans mon crâne. Dernièrement, en regardant mon échiquier, je me suis souvenu que j’avais écrit un bout de code pour résoudre le problème des huit reines sur un échiquier. Un autre problème m’a alors sauté à la figure : existe-t-il une solution pour qu’un cavalier puisse parcourir la totalité de l’échiquier sans repasser deux fois par la même case.
Since always, I love to make knots with the unfortunate neuron that lingers in my skull. Recently, looking at my chessboard, I remembered that I had written a piece of code to solve the problem of eight Queens on a chessboard. Another problem jumped to me: is there a solution so that a Knight can walk the entire board without going through the same square twice.
Le problème semblait simple, une solution de type “Labyrinthe” devait pouvoir répondre à ce type de problème. En fait, ce choix conduisait à une impasse, j’ai donc opté pour une solution de force brute et, miracle, après trois jours d’écriture et tests, en près 400 lignes de code, j’ai trouvé un moyen d’y parvenir. Dans l’insert, ci-dessous, deux solutions au problème.
The problem seemed simple, a solution of type “Labyrinth” should be able to answer this type of problem. In fact, this choice led to a dead end, so I opted for a brute force solution and, miracle, after three days of writing and testing, in almost 400 lines of code, I found a way to achieve it. In the insert, below, two solutions to the problem.
Le programme utilise un dé à de 1 à 8 faces pour choisir le coup suivant. Cette méthode conduit naturellement vers des impasses, elle impose de nombreux retours en arrière. Donc, il va de soi que le nombre de coups conduisant à la solution est important et variable.
Pour le curieux, vous trouverez dans l’insert ci-dessous, en mode texte, les 64 déplacements.
The program uses a dice from 1 to 8 sides to choose the next move. This method leads naturally to dead ends, it imposes many backtracking. So, it goes without saying that the number of shots leading to the solution is important and variable.
For the curious, you will find in the insert below, in text mode, the 64 moves.
Première Solution DEFHFHGECABCDFHGEDFGEDBACBACDBABACABDCEGHFHGHFGHGECABABDCEGFEDFH
4687657878686568754213243576875312312454234687531212468754313121
Deuxième Solution
DFHGHFECABACEDBACEGHGEDBDECABCABABDEGHFDCDFHFDBACABCEFHGHGEFGHFG
4346875653121342121356876878687531243121356787865424312468757542
Il existe de nombreuses solutions, l’exemple ci-dessus n’en propose que deux.
Enfin, comme je suis de la vieille école, le programme a été écrit en FORTRAN sans avoir, et c’est une erreur, consulté au préalable Google et ChatGPT qui, tous deux, m’auraient fait gagner un temps précieux.
There are many solutions, the example above only offers two.
Finally, as I am old school, the program was written in FORTRAN without having, and this is a mistake, consulted beforehand Google and ChatGPT which, both, would have saved me a precious time.