Cavalier, jeux d'échec.

cs_Tanaka24
Messages postés
14
Date d'inscription
vendredi 23 juin 2006
Statut
Membre
Dernière intervention
1 août 2006
- 30 juil. 2006 à 22:38
super_toinou
Messages postés
764
Date d'inscription
mardi 25 mai 2004
Statut
Membre
Dernière intervention
8 mars 2011
- 1 août 2006 à 15:14
Bonjour,

J'ai tenté de résoudre un problème vieux de plus de 300 ans qui consite tout simplement à déplacer un cavalier sur un jeux d'échec et ce sans jamais passer par une case par laquel on est déjà passé et en passant par les 64 cases.

J'ai développé avec succès un cavalier qui bouge aléatoirement sur le plateau sans jamais sortir et sans jamais passer par une case qu'il a déjà visiter mais voila lorsuque je tente de faire une boucle récursive pour lui faire trouver la solution par la force en essayant toute les combinaisons possible aléatoirement... il plante et me lance une OverFlowError.

Voici le programme qui fonctionne sans la récucivité:

/**
 * Write a description of class tableau here.
 *
 * @author (Samuel)
 * @version (a version number or a date)
 */
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.ArrayList;


public class cavalier extends JApplet {
int tab[][] = new int [8][8];
int horizontal[] = new int [8];
int vertical [] = new int [8];
int ligneActuelle = 0;
int colonneActuelle = 0;


int compteur = 0;


String sortie;


JTextArea zoneSortie;


public void init ()
 {


//crée un JTextArea et le lie à l'applet.
zoneSortie = new JTextArea();
Container conteneur = getContentPane();
conteneur.add(zoneSortie);


//construire la chaîne de sortie
sortie = "Tour du cavalier: \n";




//Changer la police d'affichage de ZoneSortie
zoneSortie.setFont(new Font("Courier", Font.PLAIN, 12));


//Placer la chaiîne de sortie dans zoneSortie.
zoneSortie.setText(sortie);


deplaceCavalier() ;


}


//construire la chaîne de sortie
public void construireString(){
sortie += "    "; //sert à alliger les en-têtes des colonnes


//crée les en-têtes de colonnes
for( int compteur= 0 ; compteur< 8 ; compteur++){
sortie += "[" + compteur + "] ";


}
for (int ligne = 0; ligne <8 ; ligne ++){
sortie += "\n\n[" + ligne + "]   ";


  for (int colonne = 0; colonne<8; colonne++)
  sortie += tab[ligne][colonne] + "  " ;


}




}




private class Position {


    private int horizontal ;
    private int vertical ;


    public Position(int myHorizontal, int myVertical) {
      horizontal = myHorizontal ;
      vertical = myVertical ;
    }


    public Position(Position mypos) {
      horizontal = mypos.getHorizon() ;
      vertical = mypos.getVert() ;
    }


    int getHorizon() {return horizontal;}


    int getVert() {return vertical;}


    public Position clone() {
      return new Position(horizontal, vertical) ;
    }
  }


 


 


 


 


 


Position Mouvementacceptable (int row, int col)
{
    ArrayList  positionlist = new ArrayList();


    positionlist.add(new Position(2,-1));
    positionlist.add(new Position(1,-2));
    positionlist.add(new Position(-1,-2));
    positionlist.add(new Position(-2,-1));
    positionlist.add(new Position(-2,1));
    positionlist.add(new Position(-1,2));
    positionlist.add(new Position(1,2));
    positionlist.add(new Position(2,1));


     while( !positionlist.isEmpty())
      {


          int typeMouvement =(int)(Math.random()*positionlist.size());


          Position mouvementChoisi;
          mouvementChoisi = positionlist.get(typeMouvement);


          int rowFutur= mouvementChoisi.getHorizon()+row;
          int colFutur= mouvementChoisi.getVert()+col;


          if(rowFutur<8&&rowFutur>-1&&colFutur<8&&colFutur>-1&&tab[rowFutur][colFutur]==0)
          return mouvementChoisi.clone();
          else
          positionlist.remove(typeMouvement);
       }
      return null;
}




public void deplaceCavalier()
  {
  int rowCourent=0;
  int colCourent=0;
   for(int i=0;i<64;i++)
      {
       Position mouvementPris= Mouvementacceptable(rowCourent,colCourent);
       if(mouvementPris==null)
          {
           break;
          }
       else
          {
           tab[rowCourent+mouvementPris.getHorizon()][colCourent+mouvementPris.getVert()]= i+1;
           rowCourent += mouvementPris.getHorizon();
           colCourent += mouvementPris.getVert();
           }
      }


   construireString() ;
   zoneSortie.setText(sortie);


  }


}


 


 


 




Et voici le programme avec la récursitivté mais il foire la pluspart du temps sauf quand j'ai de la chance et qu'il trouve rapidement.

/**
 * Write a description of class tableau here.
 *
 * @author (Samuel)
 * @version (a version number or a date)
 */
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.ArrayList;


public class cavalier1 extends JApplet {
int tab[][] = new int [8][8];
int horizontal[] = new int [8];
int vertical [] = new int [8];
int ligneActuelle = 0;
int colonneActuelle = 0;


int compteur = 0;


String sortie;


JTextArea zoneSortie;


public void init ()
 {


//crée un JTextArea et le lie à l'applet.
zoneSortie = new JTextArea();
Container conteneur = getContentPane();
conteneur.add(zoneSortie);


//construire la chaîne de sortie
sortie = "Tour du cavalier: \n";




//Changer la police d'affichage de ZoneSortie
zoneSortie.setFont(new Font("Courier", Font.PLAIN, 12));


//Placer la chaiîne de sortie dans zoneSortie.
zoneSortie.setText(sortie);


deplaceCavalier() ;


}


//construire la chaîne de sortie
public void construireString(){
sortie += "    "; //sert à alliger les en-têtes des colonnes


//crée les en-têtes de colonnes
for( int compteur= 0 ; compteur< 8 ; compteur++){
sortie += "[" + compteur + "] ";


}
for (int ligne = 0; ligne <8 ; ligne ++){
sortie += "\n\n[" + ligne + "]   ";


  for (int colonne = 0; colonne<8; colonne++)
  sortie += tab[ligne][colonne] + "  " ;


}




}




private class Position {


    private int horizontal ;
    private int vertical ;


    public Position(int myHorizontal, int myVertical) {
      horizontal = myHorizontal ;
      vertical = myVertical ;
    }


    public Position(Position mypos) {
      horizontal = mypos.getHorizon() ;
      vertical = mypos.getVert() ;
    }


    int getHorizon() {return horizontal;}


    int getVert() {return vertical;}


    public Position clone() {
      return new Position(horizontal, vertical) ;
    }
  }


 


 


Position Mouvementacceptable (int row, int col)
{
    ArrayList  positionlist = new ArrayList();


    positionlist.add(new Position(2,-1));
    positionlist.add(new Position(1,-2));
    positionlist.add(new Position(-1,-2));
    positionlist.add(new Position(-2,-1));
    positionlist.add(new Position(-2,1));
    positionlist.add(new Position(-1,2));
    positionlist.add(new Position(1,2));
    positionlist.add(new Position(2,1));


     while( !positionlist.isEmpty())
      {


          int typeMouvement =(int)(Math.random()*positionlist.size());


          Position mouvementChoisi;
          mouvementChoisi = positionlist.get(typeMouvement);


          int rowFutur= mouvementChoisi.getHorizon()+row;
          int colFutur= mouvementChoisi.getVert()+col;


          if(rowFutur<8&&rowFutur>-1&&colFutur<8&&colFutur>-1&&tab[rowFutur][colFutur]==0)
          return mouvementChoisi.clone();
          else
          positionlist.remove(typeMouvement);
       }
      return null;
}




public void deplaceCavalier()
  {
  int rowCourent=0;
  int colCourent=0;
   for(int i=0;i<64;i++)
      {
       Position mouvementPris= Mouvementacceptable(rowCourent,colCourent);
       if(mouvementPris==null)
          {
              if(i<50){
                  try{
                  recommecer();
                }
                catch(Throwable throwable ){
                 System.err.println(throwable.getMessage());  
                }
               
                }
             
              break;
          
          
          }
       else
          {
           tab[rowCourent+mouvementPris.getHorizon()][colCourent+mouvementPris.getVert()]= i+1;
           rowCourent += mouvementPris.getHorizon();
           colCourent += mouvementPris.getVert();
           }
      }


   construireString() ;
   zoneSortie.setText(sortie);


  }


public void recommecer()
    {
       
     deplaceCavalier();  
       
       
    }
 
}


 


 


 




Merci à tous ceux qui pourrait m'aider sur cette histoire de récurcivité...

3 réponses

cs_Tanaka24
Messages postés
14
Date d'inscription
vendredi 23 juin 2006
Statut
Membre
Dernière intervention
1 août 2006

30 juil. 2006 à 22:39
remplacer naturellement le 50 par 63 pour qu'il passe partout. Mais dans un premier temps j'ai essayer avec 50 et ca marche parfois...
0
cs_Tanaka24
Messages postés
14
Date d'inscription
vendredi 23 juin 2006
Statut
Membre
Dernière intervention
1 août 2006

1 août 2006 à 13:00
Personne ne sais comment faire une boucle jusqu'a ce qu'il trouve?
0
super_toinou
Messages postés
764
Date d'inscription
mardi 25 mai 2004
Statut
Membre
Dernière intervention
8 mars 2011
8
1 août 2006 à 15:14
j ai pas regardé ton code c trop long mais a mon avis ton approche n est pas top, vu que tu teste aléatoirement t es jamais garanti d aller au bout.
Ton probleme relève d'un algorithme de backtracking, j t encourage a aller faire un tour dans cette direction, t apprendra + que trouver un stackoverfloow error (a mon avis tu dois avoir une histoire genre tu sors pas de ta récursivité et ta liste des déplacements doit péter)
+++ Toinou
0