On se propose de programmer et visualiser (en Python, avec le package turtle) le parcours d’un cavalier sur un échiquier.
À partir d’une position initiale du cavalier, on s’attachera à décrire des trajectoires explorant la totalité de l’échiquier en passant une fois et une seule sur chaque case (voir l’article de Wikipedia).
On verra aussi comment généraliser à des échiquiers de tailles différentes et/ou modifiés pour rendre certaines de leurs cases inaccessibles.
Une idée classique est que le cavalier doit toujours viser, parmi les cases libres autour de lui, celle qui a elle-même le plus de voisins libres à ce moment-là (de façon à minimiser le risque de finir par isoler des cases et les rendre ainsi totalement inaccessibles).
Je donne ici une implémentation personnelle de cette idée. C’est sans doute perfectible (notamment parce que j’utilise trop de variables globales), et tout ça devrait sans doute être réécrit en programmation-objet, mais en l’état ça fonctionne bien quand même :-)
On trouvera une archive du programme ici.
On commence par importer les modules utiles :
|
1 2 3 4 5 6 7 8 9 |
from tkinter import * from turtle import * # importe le package turtle import turtle ts = turtle.getscreen() import sys from time import sleep import numpy as np from PIL import Image import io |
On définit quelques objets globaux :
|
1 2 3 4 5 6 7 8 |
compteur = 0 ### liste des déplacements relatifs du cavalier''' Deps = [(2,-1),(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2)] ### Un objet écran EC = Screen() EC.clear() ### Un objet Turtle CA = Turtle() |
La fonction suivante est chargée de dessiner une case de l’échiquier :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def case(x, y, long, coul): '''dessin d'une case''' '''Remplit un carré d'arête longueur à partir du sommet (x, y). Le premier coté est tracé dans la direction initiale de la tortue. Le contour du carré est dessiné dans le sens horaire. À la sortie, la tortue est en (x,y), dans la direction initiale''' CA.up(); # lève le crayon CA.goto(x, y); # se déplace au point (x,y) CA.down() # baisse le crayon CA.color(coul) # règle couleur de remplissage CA.begin_fill() # on va remplir le carré for k in range(4): # quatre fois de suite CA.forward(long) # trace un coté CA.left(90) # tourne de 90° vers la gauche CA.end_fill() # retour au départ et remplit |
Chaque case de l’échiquier est colorée alternativement en jaune ou en marron (mais les cases inaccessibles sont colorées en blanc) :
|
1 2 3 4 |
def couleur(i,j): '''renvoie la couleur d'une case''' if Board[j,i]<0: return "white" else: return ["brown","yellow"][(i+j)%2] |
La fonction suivante sera chargée de dessiner et d’initialiser l’échiquier, ainsi que le cavalier.
On utilise ici une image gif pour représenter le cavalier. Cette image doit figurer dans le répertoire de travail du programme Python. On peut remplacer l’instructione CA.shape(« knight.gif ») par CA.shape(« circle »)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
def Init(board, i0, j0): '''Initialise les objets échiquier et cavalier''' global NL, NC, CL, AR, CA NL, NC = np.shape(board) # nb lignes/colonnes du plateau CL = NL*NC - np.count_nonzero(board) # nb cases libres size = 600 # taille fenêtre carrée, en pixels AR = size//max(NL,NC) # taille arête d'une case # initialisation de l'objet échiquier EC = turtle.Screen() EC.register_shape("knight.gif") EC.setworldcoordinates(0,size,size,0) # fenêtre 600*600 EC.tracer(0) for i in range(NL): for j in range(NC): case(i*AR, j*AR, AR, couleur(i,j)) EC.tracer(1) # initialisation de l'objet cavalier CA = turtle.Turtle() CA.shape("knight.gif") # CA.shape("circle") CA.speed(0) CA.up(); CA.goto(centre(i0,j0)); CA.down() CA.color("blue"); CA.pensize(3) |
On a besoin de connaître les coordonnées du centre d’une case :
|
1 2 3 |
def centre(i,j): '''coordonnées du centre d'une case''' return j*AR+AR/2, i*AR+AR/2 |
La fonction suivante sauvegarde une image de l’échiquier (en l’état actuel des déplacements).
Le nom du fichier est sur le modèle « parcours00k.eps » où k est un compteur d’image.
Par sécurité, le programme s’arrête au-delà de 500 déplacements.
|
1 2 3 4 5 6 7 8 9 10 |
def savefig(): '''sauvegarde l'image de l'échiquier''' global compteur compteur +=1 if compteur > 500: sys.exit("Trop d'étapes!") nom = "parcours"+str(1000+compteur)[1:] screen = turtle.getscreen() canvas = screen.getcanvas() postscript = canvas.postscript(file=nom+'.eps') |
La fonction suivante place le cavalier sur la case (i,j). Elle écrit également le numéro du déplacement au centre de la case. Enfin elle sauvegarde l’image de l’échiquier.
|
1 2 3 4 5 6 7 |
def pose(i, j, k): '''place le cavalier et attend la pause''' Board[i,j] = k CA.goto(centre(i,j)) CA.write(k,False, align="center",font=("Arial", AR//2, "normal")) savefig() sleep(Poz) |
La fonction suivante retire le cavalier de la case (i,j) (c’est le premier CA.undo) puis efface le déplacement (c’est le deuxième CA.undo). Enfin elle sauvegarde l’image de l’échiquier.
|
1 2 3 4 5 6 |
def retire(i,j,k): '''retire le cavalier et attend la pause''' Board[i, j] = 0 sleep(Poz) CA.undo(); CA.undo() savefig() |
Cette fonction permet de savoir si (à un moment donné du parcours) la case (i,j) est encore disponible.
|
1 2 3 |
def libre(i, j): ''' dit si la case 'i,j) est libre''' return (0 <= i < NL) and (0 <= j < NC) and Board[i, j] == 0 |
Cette fonction donne la liste des cases libres voisines de la case (i,j) :
|
1 2 3 |
def voisins(i, j): '''renvoie la liste des cases libres voisines de (i,j)''' return [(i+di,j+dj) for (di,dj) in Deps if libre(i+di,j+dj)] |
Cette fonction donne le nombre de cases libres autour de (i,j) :
|
1 2 3 4 5 6 7 |
def liens(pos): '''nombre de voisins libres de (i,j)''' v = 0 for dep in Deps: if libre(pos[0] + dep[0], pos[1] + dep[1]): v += 1 return v |
La fonction suivante pose récursivement le cavalier en (i,j). Quand une solution est trouvée, cette fonction affiche dans la console une image texte de l’état de l’échiquier (on peut y lire les numéros de déplacements; les cases indisponibles éventuelles sont marquées par la valeur -1).
À chaque solution complète, l’utilisateur a la possibilité de continuer ou d’arrêter.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def cavalier(i, j, k): '''pose récursivement le cavalier en (i,j) k est le numéro du déplacement''' global Board pose(i, j, k) if k < CL: for (ni, nj) in sorted(voisins(i,j), key=liens): cavalier(ni, nj, k+1) else: print(Board,'\n') if input('Bravo!!! On continue (O/N) ? : ') in ['n','N']: sys.exit("C'est fini!") # après l'avoir posé en (i,j) # viendra le temps de le retirer retire(i,j,k) |
Voici la fonction principale. Le premier argument facultatif choix permet de choisir un type d’échiquier (par défaut, c’est l’échiquier 8×8 traditionnel). Plusieurs exemples sont fournis ici (et on peut facilement en ajouter). L’argument facultatif « pause » (par défaut 0) oblige le cavalier à marquer une pause (exprimée en secondes) entre deux déplacements. Les deux arguments facultatifs i_0,j_0 (nuls par défaut) donnent la position de départ du cavalier.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
def go(choix=0, pause=0, i0=0, j0=0): '''fonction principale. départ en (i0,j0) avec pause éventuelle entre deux mouvements et choix de l'échiquier''' global Board, Poz, compteur compteur = 0 Poz = pause if choix==0: # échiquier 8x8 usuel Board = np.zeros((8, 8),'int') elif choix==1: # échiquier 10x10 Board = np.zeros((10, 10),'int') # on interdit 16 cases centrales Board[3:7,3:7]=-1 elif choix==2: # échiquier 5x5 Board = np.zeros((5, 5),'int') # on interdit la case centrale Board[2,2]=-1 elif choix==3: # échiquier 9x9 Board = np.zeros((9, 9),'int') # on interdit quelques cases Board[2:7,2:7]=-1 Board[3:6,3:6]=0 Board[4,4]=-1 elif choix==4: # échiquier 12x12 Board = np.zeros((12, 12),'int') # on interdit certaines cases Board[3:5,3:5]=-1 Board[5:7,5:7]=-1 Board[7:9,7:9]=-1 Board[10:12,0:2]=-1 Board[0:2,10:12]=-1 elif choix==5: # échiquier 8x8 Board = np.zeros((9, 9),'int') # on interdit certaines cases Board[2:6,2:6]=-1 Board[3:5,3:5]=0 # initialise l'échiquier Init(Board, i0, j0) # lance le parcours du cavalier cavalier(i0, j0, 1) |
Passons maintenant à quelques exemples, tout d’abord avec l’échiquier classique. On constate que le cavalier parcourt les 64 cases de l’échiquier sans le moindre retour en arrière.
|
1 2 3 4 5 6 7 8 9 10 11 |
go() [[ 1 26 15 24 29 42 13 32] [16 23 28 43 14 31 38 41] [27 2 25 30 51 40 33 12] [22 17 60 57 44 37 52 39] [ 3 64 21 50 59 56 11 34] [18 49 58 61 36 45 8 53] [63 4 47 20 55 6 35 10] [48 19 62 5 46 9 54 7]] Bravo!!! On continue (O/N) ? : n |
Et voici l’animation correspondante!
Voici une autre possibilité (c’est le choix 5). Cette fois le cavalier doit effectuer pas mal de retours en arrière avant de trouver une première solution :
|
1 2 3 4 5 6 7 8 9 10 11 12 |
go(choix=5) [[ 1 68 17 48 29 54 15 50 31] [18 47 28 67 16 49 30 53 14] [69 2 -1 -1 -1 -1 55 32 51] [46 19 -1 27 66 -1 52 13 56] [ 3 26 -1 24 59 -1 65 38 33] [20 45 -1 -1 -1 -1 34 57 12] [ 7 4 25 60 23 58 39 64 37] [44 21 6 9 42 35 62 11 40] [ 5 8 43 22 61 10 41 36 63]] Bravo!!! On continue (O/N) ? : n |
Et voici l’animation correspondante!
