Formation ISN - cavalier

Le problème du cavalier consiste à partir d'une case de l'échiquier et à parcourir tout l'échiquier, en passant une fois et une seule sur chaque case, en respectant le déplacement autorisé pour un cavalier au jeu d'échec.
mouvement du cavalier

Écrire une version récursive de cette recherche. Le programme partira d'une case au hasard et cherchera une solution (une seule) si elle existe en partant de cette case.

principe
un choix de représentation
un code

Le cavalier est sur une case. On marque cette case comme étant visitée.
- Si le cavalier a déjà visité toutes les cases : c'est fini.
- Sinon
  - Si depuis sa case, il peut atteindre des cases non encore visitées : il en choisit une au hasard et s'y déplace.
  - Sinon il remonte jusqu'à la précédente case ayant encore des voisins non visités et les cases ainsi remontées doivent être marquées comme non visitées.
Retour au point 1.

Dans le programme proposé dans l'onglet suivant en solution, on a associé un graphe à cette situation : chaque case (de 0 à 63) est un sommet du graphe et deux sommets sont reliés par une arête lorsque le cavalier peut passer d'une case à l'autre.

On a ensuite choisi de représenter ce graphe par un dictionnaire python.


def graphe(n) :
  
    E = dict()
    for k in range(n*n) :
        i = k//n # ligne de la case k
        j = k%n # colonne de la case k

        E[k] = [] # E[k]  : liste des voisins de la case k
        if  0 <= i-2 < n and  0 <= j-1 < n : E[k].append((i-2)*n+(j-1))
        if  0 <= i-2 < n and  0 <= j+1 < n : E[k].append((i-2)*n+(j+1))
        if  0 <= i+2 < n and  0 <= j-1 < n : E[k].append((i+2)*n+(j-1))
        if  0 <= i+2 < n and  0 <= j+1 < n : E[k].append((i+2)*n+(j+1))

        if  0 <= i-1 < n and  0 <= j-2 < n : E[k].append((i-1)*n+(j-2))
        if  0 <= i-1 < n and  0 <= j+2 < n : E[k].append((i-1)*n+(j+2))
        if  0 <= i+1 < n and  0 <= j-2 < n : E[k].append((i+1)*n+(j-2))
        if  0 <= i+1 < n and  0 <= j+2 < n : E[k].append((i+1)*n+(j+2))
    return E
    
    
E =  graphe(4)
print(E)

On obtient :

{0: [9, 6], 
1: [8, 10, 7], 
2: [9, 11, 4], 
3: [10, 5], 
4: [13, 2, 10], 
5: [12, 14, 3, 11], 
6: [13, 15, 0, 8], 
7: [14, 1, 9], 
8: [1, 6, 14], 
9: [0, 2, 7, 15], 
10: [1, 3, 4, 12], 
11: [2, 5, 13], 
12: [5, 10], 
13: [4, 6, 11], 
14: [5, 7, 8], 
15: [6, 9]}

Interprétation :

A la clef 10, le dictionnaire associe [1, 3, 4, 12]. Cela signifie que dans l'échiquier 4×4 ci-dessous, le cavalier peut, depuis la case 10, atteindre les cases 1, 3, 4, 12.

00	01	02	03
04	05	06	07
08	09	10	11
12	13	14	15


import random

def graphe(n) :
  
    E = dict()
    for k in range(n*n) :
        i = k//n # ligne de la case k
        j = k%n # colonne de la case k

        E[k] = [] # E[k]  : liste des voisins de la case k
        if  0 <= i-2 < n and  0 <= j-1 < n : E[k].append((i-2)*n+(j-1))
        if  0 <= i-2 < n and  0 <= j+1 < n : E[k].append((i-2)*n+(j+1))
        if  0 <= i+2 < n and  0 <= j-1 < n : E[k].append((i+2)*n+(j-1))
        if  0 <= i+2 < n and  0 <= j+1 < n : E[k].append((i+2)*n+(j+1))

        if  0 <= i-1 < n and  0 <= j-2 < n : E[k].append((i-1)*n+(j-2))
        if  0 <= i-1 < n and  0 <= j+2 < n : E[k].append((i-1)*n+(j+2))
        if  0 <= i+1 < n and  0 <= j-2 < n : E[k].append((i+1)*n+(j-2))
        if  0 <= i+1 < n and  0 <= j+2 < n : E[k].append((i+1)*n+(j+2))
    return E
    
    
def cavalierHamilton(n) :
    """ recherche d'un chemin hamiltonien dans le graphe du cavalier."""
    E = graphe(n)
    chemin = [] # contiendra les cases dans leur ordre de visite
    
    
    def parcours( case ) :
        """ 
            case : case actuelle du cavalier.
        """
        chemin.append(case) # case est ajoutée au chemin, ce qui la marque comme visitée également
         
        if len(chemin) == n*n :
            gagne = True
        
        else :
            gagne = False
            voisins = [ u for u in E[case] if u not in chemin ] # voisins non visités de case
            for v in voisins :
                if gagne : break
                else : gagne = parcours( v )
            if not gagne :
                chemin.pop() #  case est supprimée de chemin si elle a mené à une impasse
                
                
        return gagne
        
    # départ d'une case prise au hasard :
    parcours(  random.randint(0,n*n-1)  )
    return chemin



def affichage(n) :
	""" affichage simple de l'échiquier avec indication de l'ordre de parcours des cellules réalisé."""

	t = [[0 for j in range(n) ] for k in range(n)]
	chemin = cavalierHamilton(n)

	rg = 1
	for x in chemin :
		if rg > 9 : t[x//n][x%n] = str(rg)
		else : t[x//n][x%n] = '0' + str(rg)
		rg += 1

	for ligne in t :
		for c in ligne :
			print(c, end=" ")
		print() 
    
    
    
affichage(6)

Exemple d'affichage obtenu :

25 18 15 34 31 36 
16 03 24 05 14 33 
19 26 17 32 35 30 
02 09 04 23 06 13 
27 20 11 08 29 22 
10 01 28 21 12 07

La recherche devient rapidement très longue.

Une heuristique permet d'améliorer le temps de recherche d'une solution : choisir, parmi les voisins disponibles de la case en cours, celui qui a le moins de voisins disponibles.

Programmer une telle version.

heuristique
un code

Définition du mot heuristique.

Qui sert à la découverte.

Hypothèse heuristique : hypothèse adoptée provisoirement comme idée directrice indépendamment de sa vérité absolue.


import random

def graphe(n) :
  
	E = dict()
	for k in range(n*n) :
		i = k//n # ligne de la case k
		j = k%n # colonne de la case k

		E[k] = [] # E[k]  : liste des voisins de la case k
		if  0 <= i-2 < n and  0 <= j-1 < n : E[k].append((i-2)*n+(j-1))
		if  0 <= i-2 < n and  0 <= j+1 < n : E[k].append((i-2)*n+(j+1))
		if  0 <= i+2 < n and  0 <= j-1 < n : E[k].append((i+2)*n+(j-1))
		if  0 <= i+2 < n and  0 <= j+1 < n : E[k].append((i+2)*n+(j+1))

		if  0 <= i-1 < n and  0 <= j-2 < n : E[k].append((i-1)*n+(j-2))
		if  0 <= i-1 < n and  0 <= j+2 < n : E[k].append((i-1)*n+(j+2))
		if  0 <= i+1 < n and  0 <= j-2 < n : E[k].append((i+1)*n+(j-2))
		if  0 <= i+1 < n and  0 <= j+2 < n : E[k].append((i+1)*n+(j+2))
	return E
    
    
def cavalierHamiltonHeuristique(n) :
	""" recherche d'un chemin hamiltonien dans le graphe du cavalier."""
	E = graphe(n)
	chemin = [] # contiendra les cases dans leur ordre de visite


	def parcours( case ) :
		""" 
			case : case actuelle du cavalier.
		"""
		chemin.append(case) # case est ajoutée au chemin, ce qui la marque comme visitée également
		 
		if len(chemin) == n*n :
			gagne = True
		
		else :
			gagne = False
			voisins = [ u for u in E[case] if u not in chemin ] # voisins non visités de case
			
			voisinsNbPossibles = []
			for u in voisins :
				nb = len( [v for v in E[u] if v not in chemin]) # nb de possibles à partir de u
				voisinsNbPossibles.append([u,nb])
			voisinsNbPossibles.sort(key= lambda x:x[1])# tri croissant suivant le nombre de possibles
			voisins = [ x[0] for x in voisinsNbPossibles ] # on récupère uniquement les voisins
				
			for v in voisins :
				if gagne : break
				else : gagne = parcours( v )
			if not gagne :
				chemin.pop() #  case est supprimée de chemin si elle a mené à une impasse
				
				
		return gagne
		
		
	parcours(  random.randint(0,n*n-1)  )
	return chemin
    

def affichage(n) :
	""" affichage simple de l'échiquier avec ordre de parcours des cellules indiqué."""

	t = [[0 for j in range(n) ] for k in range(n)]
	chemin = cavalierHamiltonHeuristique(n)

	rg = 1
	for x in chemin :
		if rg > 9 : t[x//n][x%n] = str(rg)
		else : t[x//n][x%n] = '0'+str(rg)
		rg += 1

	 
	for ligne in t :
		for c in ligne :
			print(c, end=" ")
		print() 
    
    
    
affichage(8)

Exemple d'affichage obtenu :

21 38 17 02 27 50 15 54 
18 03 20 49 16 53 28 51 
39 22 37 26 01 46 55 14 
04 19 48 45 62 35 52 29 
23 40 25 36 47 58 13 56 
08 05 44 63 34 61 30 59 
41 24 07 10 43 32 57 12 
06 09 42 33 64 11 60 31

Formation I.S.N.

le problème du cavalier

une heuristique