Cavalier d'euler - règle de warnsdorff

Soyez le premier à donner votre avis sur cette source.

Vue 15 277 fois - Téléchargée 1 087 fois

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.

Source / Exemple :


'Dans le zip...

Conclusion :


Tout commentaire est le bienvenu.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
20
Date d'inscription
jeudi 17 février 2011
Statut
Membre
Dernière intervention
11 mai 2012

Bonjour,
Je vais peut-être passé ^pour un débile mais comment est-ce que l'on fait marcher ce programme ?? Car aucun des fichiers est éxécutable.
Merci d'avance New-disco1
Messages postés
31
Date d'inscription
jeudi 2 août 2007
Statut
Membre
Dernière intervention
19 avril 2009

Salut à tous !
Bravo à Cacophrene,c'est une superbe source !
interface et code parfait !:)
10/10

@+
Messages postés
263
Date d'inscription
lundi 29 mars 2004
Statut
Membre
Dernière intervention
4 mars 2008
1
Re !

Correction effectuée.

A bientôt,
Cacophrène
Messages postés
263
Date d'inscription
lundi 29 mars 2004
Statut
Membre
Dernière intervention
4 mars 2008
1
Salut !

En effet oui... il y a quelque chose qui ne va pas. Je corrigerai ça bientôt, selon mon temps libre.

Cordialement,
Cacophrène
Messages postés
12
Date d'inscription
mercredi 16 juin 2004
Statut
Membre
Dernière intervention
3 mai 2010

Bonjour Cacophrene

ce programme a l'air interressant et commenté.

Je viens juste de l'essayer et avant d'aller plus loin, j'ai voulu le tester un peu.

Si je prends la taille a 8:8 et point de depart 4:4 on obtient certaines cases n'ont pas été parcourues.

Si je prends la taille a 8:8 et point de depart 5:4 on obtient j'ai trouvé un chemin complet.

Or il me semble que par rotation de l'echiquier de +90° le point de depart 5:4 devient 4:4 donc il semble que l'algorithme de calcul de ton programme ait une petite faille.

D'ailleurs si le point de depart est 5:5 on obtient j'ai trouvé un chemin complet. or 5:5=4:4 par symetrie centrale

Sinon l'interface est bien faite.

Bon courage
Afficher les 6 commentaires

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.