Journal Deplacement du cheval

Posté par doublehp (site web personnel) le 01 mai 2003 à 20:14.

Étiquettes : aucune

mai

2003

Puis que c est le jour de programmer, je vais vous demander votre avis sur un "deplacement du cavalier " : le but est simple : faire deplacer un cheval sur un plateau 8*8 , le faire passer une unique fois, sur toutes les cases consecutivement.
J arrive a avoir 63 cases en 3minutes45, mais pour 64 cases, ... meme en >4h il trouve pas ...
NB : dans le damier, un 0 signifie case libre, sinon les numeros induquent les ordres du deplacement. ...

code source a http://www.ece.fr/~demaine/main.c

Merci de vos conseils.

# Re: Deplacement du cheval

Posté par tanguy_k (site web personnel) le 01 mai 2003 à 22:28. Évalué à 2.

Ca me fait furieusement penser a la programmation par contrainte.
cf http://kti.mff.cuni.cz/~bartak/CP.PDF(...) et l'exemple classique des 8 reines (regarde bien backtracking/forward checking sur l'exemple des 8 reines).

Le probleme c'est que la programmation par contraintes c'est souvent des trucs proprios en Prolog comme SciTUS. Mais rien n'empeche de le programmer toi meme dans le langage que tu veux surtout pour un exemple simple.
- [^] # Re: Deplacement du cheval
  
  Posté par Kriek le 01 mai 2003 à 22:47. Évalué à 1.
  
  >> SciTUS
  Sicstus plutôt non?
  
  Sinon GNU Prolog (le "meilleur" à mon avis de la liste que je donne), SWi et YAP Prolog sont tous les trois libres et suffiront pour le problème ci-dessus
- [^] # Programmation par contraintes
  
  Posté par Polaris le 02 mai 2003 à 10:51. Évalué à 1.
  
  Si vous êtes intéressés par la programmtion par contraintes, il y a un solveur libre (GPL) développé par Bouygues E-Lab, qui s'appelle Choco. Il se base sur Claire, un langage de haut niveau un peu ésotérique, mais il offre plein de fonctionnalités rigolotes, et il paraît que maintenant, chez Bouygues, ils font toute leut planif' avec ça -- et des bibliothèques proprios qu'ils ont développé en interne ;-)
  
  http://www.choco-constraints.net/downloads.html(...)
- [^] # Arc Consistency
  
  Posté par Polaris le 02 mai 2003 à 11:01. Évalué à 1.
  
  Si le problème est vraiment difficile (je ne pense pas qu'il le soit), maintenir la cohérence d'arc pendant la recherche peut être payant. En gros, ça consiste à supprimer du backtrack toutes les valeurs qui ne peuvent pas s'étendre à une solution locale --par exemple, les cases qui n'ont plus de voisins libres-- et donc a fortiori à une solution tout court. Si de cette manière on vide un domaine, on sait que la dernière valeur instanciée est inconsistante, donc on peut la supprimer (et propager cette suppression).
  
  L'intérêt de supprimer des valeurs, c'est qu'ensuite on évite de les explorer de manière répétitive.
  - [^] # Re: Arc Consistency
    
    Posté par JereMe le 30 avril 2004 à 16:53. Évalué à 1.
    
    En Chip : http://www.enseirb.fr/~gloess/chipdir/clp/solutions/nqueens.pl(...)
    Je sais, chip n'est pas libre, mais ca donne un exemple de résolution en programation par contrainte ... à adapter !
    
    Y a pas de licence sur le fichier à ma connaissance, sinon je peux toujours fournir un fichier à moi qui traine quelque part si ca interresse quelqu'un.
# Re: Deplacement du cheval

Posté par ced le 01 mai 2003 à 22:32. Évalué à 0.

Es-tu sur que ce soit possible ?
- [^] # Re: Deplacement du cheval
  
  Posté par Foxy (site web personnel) le 02 mai 2003 à 01:43. Évalué à 2.
  
  Ignare : c'est un grand problème classique de l'informatique et de la résolution de problème complexe.
  - [^] # Re: Deplacement du cheval
    
    Posté par doublehp (site web personnel) le 02 mai 2003 à 01:55. Évalué à 1.
    
    j etais quasi sure que oui, mais je n ai jamais rien lu la dessus, juste entendu parler quand j avais 7 ou 8 ans ... et la a 22 ans, je reprend des vieux conceptes de ma jeunesse ...
# Re: Deplacement du cheval

Posté par Barbapapa le 02 mai 2003 à 01:05. Évalué à 2.
Facile :)
Mais il faut bien choisir son point de départ. En partant du point 0,0 je ne trouve rien par contre en partant du point 5,5 je trouve une solution en 2s !
```
15 18 05 10 13 40 27 64 

04 09 14 17 06 11 42 39 

19 16 07 12 41 26 63 28 

08 03 20 25 62 29 38 43 

21 24 33 02 37 44 61 30 

34 49 22 53 32 01 58 45 

23 54 51 36 47 56 31 60 

50 35 48 55 52 59 46 57 
```
- [^] # Re: Deplacement du cheval
  
  Posté par doublehp (site web personnel) le 02 mai 2003 à 01:54. Évalué à 1.
  
  avec mon soft ?
  et dire que j ai pense a inverser le chemin ( cf les commentaires ) mais pas l origine ... ARG ...
  - [^] # Re: Deplacement du cheval
    
    Posté par doublehp (site web personnel) le 02 mai 2003 à 02:20. Évalué à 1.
    
    heu j ai meme ete jusqu a :
    
    #define ENDD 64
    [...]
    if(!recur(plip,x-2,y+1)) /* try y-1 and then y+1, or y+1 and then y-1 */
    return(0); /* and see the change in time and steps */
    if(!recur(plip,x-2,y-1))
    return(0);
    if(!recur(plip,x+2,y-1))
    return(0);
    if(!recur(plip,x+2,y+1))
    [...]
    if(recur(&plip,5, 5))
    
    avec bogomips : 897.84 il ne trouve pas dans les 5 minutes ...
  - [^] # Re: Deplacement du cheval
    
    Posté par Barbapapa le 02 mai 2003 à 05:56. Évalué à 1.
    
    non non avec un petit prog que j'ai écrit.
    bogomips: 399
    time: 0m1.608s
    - [^] # Re: Deplacement du cheval
      
      Posté par doublehp (site web personnel) le 02 mai 2003 à 13:05. Évalué à 1.
      
      On peut voire TON source ?
      - [^] # Re: Deplacement du cheval
        
        Posté par Barbapapa le 02 mai 2003 à 13:29. Évalué à 1.
        
        http://empire.free.fr/cheval2.c(...)
        
        [^] # Re: Deplacement du cheval
        
        Posté par doublehp (site web personnel) le 02 mai 2003 à 18:10. Évalué à 1.
        
        Ouai, j ai mis le meme ordre de deplacement, et il trouve en
        user 0m1.360s
        depuis (5,5) ...
        
        [^] # Re: Deplacement du cheval
        
        Posté par doublehp (site web personnel) le 02 mai 2003 à 18:13. Évalué à 1.
        
        Je vais faire le teste une semaine, de lui donner "le temps" de trouver depuis 5,5 puis depuis 0,0 avec l ordre initiale ... parceque ton 64e coup est dans un coin ... donc il y a forcement un chemin inverse qui part d un coin (0,0 ou 7,0) pour finire en 5,5 ou en 2,5 ... c est la loi du chemin inverse ...
        
        [^] # Symétrie
        
        Posté par Polaris le 02 mai 2003 à 20:24. Évalué à 1.
        
        Comme tu le fais remarquer, il y a une grosse symétrie dans ton problème: toute solution partant d'un coin a une solution symétrique qui part des autres coins, et pareil pour les cases à 1, 2 ou 3 déplacements d'un coin. Donc, pour ta première valeur, tu peux limiter les cases explorées à 1/4 du damier, s'il n'y a pas de solution dans un quart (complet), il n'y en a pas ailleurs. En fait, tu peux même limiter à 1/8 du damier, parce que chaque quart est symétrique par rapport à la diagonale...
        
        [^] # Re: Deplacement du cheval
        
        Posté par ced le 02 mai 2003 à 21:23. Évalué à 1.
        
        bash-2.05a$ ./caval2 0 0
        Found a solution.
        Step 64
        01 04 07 12 27 30 25 64
        08 11 02 05 24 13 28 31
        03 06 09 14 29 26 63 60
        10 15 18 23 62 59 32 35
        19 22 47 16 33 36 61 58
        48 17 20 43 46 53 34 37
        21 44 51 54 41 38 57 56
        50 49 42 45 52 55 40 39
        
        cf en bas a doite : 40 39
        c'est pas très régulier comme déplacement de cavalier..
        
        [^] # Re: Deplacement du cheval
        
        Posté par Barbapapa le 02 mai 2003 à 23:04. Évalué à 1.
        
        Hum effectivement il y a un petit bug :)
        
        ligne 64: remplacer
        
        while (i < 8) {
        
        par
        
        while (i < 7) {
        
        par ailleurs le temps mis pour trouver une solution dépend beaucoup de l'ordre d'analyse (l'ordre des tableaux dx et dy). Y'a sûrement un truc à optimiser de ce côté...
        
        [^] # Re: Deplacement du cheval
        
        Posté par ced le 03 mai 2003 à 13:44. Évalué à 1.
        
        en effet ca va mieux :)
        
        bash-2.05a$ time caval2 7 0
        Found a solution.
        Step 64
        22 19 08 03 24 27 30 01
        07 04 23 20 09 02 25 28
        18 21 10 05 26 29 60 31
        11 06 17 38 33 58 53 62
        48 37 12 57 52 61 32 59
        13 16 47 34 39 42 63 54
        36 49 14 45 56 51 40 43
        15 46 35 50 41 44 55 64
        
        real 0m1.204s
        
        C'est quand meme étrange qu'il ne trouve rien en 0,0 : une simple "rotation" du tableau nous la donne..
        
        [^] # Re: Deplacement du cheval
        
        Posté par doublehp (site web personnel) le 06 mai 2003 à 18:26. Évalué à 1.
        
        j ai dis ( plus haut ) que la loie du chemin inverse implique qu une solution existe ... reste a trouver la bonne matruce des dx/dy pour trouver la solution en temps raisonnable ... je vais laisse tourner le truc sur un server qui sert a personne ... et dont l uptime peut toucher 10 mois ... je pense qu il devrait trouver une solution un de ces jours ... peut etre meme pas exactement le chemin inverse mais justement ce serait encore + drole :=)
- [^] # Re: Deplacement du cheval
  
  Posté par doublehp (site web personnel) le 02 mai 2003 à 02:05. Évalué à 1.
  
  tu peut me faire un
  time cheval
  et un
  cat /proc/cpuinfo | grep bogomips
  ?

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.