Cavalier d'euler - règle de warnsdorff
Description
Bonjour à tous !
Il existe déjà des sources sur ce site qui proposent de jouer à ce jeu bien connu : le cavalier d'Euler. Ce casse-tête consiste à faire parcourir une et une seule fois toutes les cases d'un échiquier par un cavalier. Ce que je vous propose ici est bien sûr en rapport avec ce jeu, si ce n'est que :
1. On recherche une solution pour des échiquiers classiques (carrés) ou rectangulaires.
2. On n'emploie pas le backtracking mais une règle heuristique appelée "règle de Warnsdorff" du nom de son inventeur (un mathématicien allemand).
3. Important : On n'est cependant pas sûr de trouver un chemin complet, et ce n'est pas parce qu'on n'en trouve pas qu'il n'y en a pas !
Le principe de la règle de Warnsdorff est largement décrit dans le programme. En voici cependant les deux grandes idées :
a) Affecter un "poids" à toutes les cases de l'échiquier. Le poids d'une case n'est autre que le nombre de cases accessibles à un cavalier à partir de celle-ci. Par exemple, la case située en haut à gauche d'un échiquier ne permet à un cavalier que deux déplacements. Son poids est donc 2.
b) Toujours privilégier les cases qui ont le poids le plus faible (c'est-à-dire parcourir d'abord les cases situées en périphérie, puis se rapprocher progressivement du centre).
Tous les tracés utilisent les fonctions de VB (Line et Circle), sans graphisme poussé.
Voilà tout !
Amusez-vous bien.
Tout commentaire est le bienvenu.
Il existe déjà des sources sur ce site qui proposent de jouer à ce jeu bien connu : le cavalier d'Euler. Ce casse-tête consiste à faire parcourir une et une seule fois toutes les cases d'un échiquier par un cavalier. Ce que je vous propose ici est bien sûr en rapport avec ce jeu, si ce n'est que :
1. On recherche une solution pour des échiquiers classiques (carrés) ou rectangulaires.
2. On n'emploie pas le backtracking mais une règle heuristique appelée "règle de Warnsdorff" du nom de son inventeur (un mathématicien allemand).
3. Important : On n'est cependant pas sûr de trouver un chemin complet, et ce n'est pas parce qu'on n'en trouve pas qu'il n'y en a pas !
Le principe de la règle de Warnsdorff est largement décrit dans le programme. En voici cependant les deux grandes idées :
a) Affecter un "poids" à toutes les cases de l'échiquier. Le poids d'une case n'est autre que le nombre de cases accessibles à un cavalier à partir de celle-ci. Par exemple, la case située en haut à gauche d'un échiquier ne permet à un cavalier que deux déplacements. Son poids est donc 2.
b) Toujours privilégier les cases qui ont le poids le plus faible (c'est-à-dire parcourir d'abord les cases situées en périphérie, puis se rapprocher progressivement du centre).
Tous les tracés utilisent les fonctions de VB (Line et Circle), sans graphisme poussé.
Voilà tout !
Amusez-vous bien.
Source / Exemple :
'Dans le zip...
Conclusion :
Tout commentaire est le bienvenu.
Codes Sources
A voir également
- Cavalier d'euler - règle de warnsdorff
- Dame chinoise regle du jeu - Forum C# / .NET
- Boggle regle - Forum VBA Office (Excel, Word ...)
- Deplacement cavalier echec - Forum Java
- Dame chinoise règle ✓ - Forum Java
- Dessin règle graduée ✓ - Forum VB.NET
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.