Cavalier, jeux d'échec.

Question

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: "; //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 += " [" + 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: "; //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 += " [" + 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é...

cs_Tanaka24 · Answer

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...

cs_Tanaka24 · Answer

Personne ne sais comment faire une boucle jusqu'a ce qu'il trouve?

super_toinou · Answer

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

Cavalier, jeux d'échec.

3 réponses

Votre réponse

Discussions similaires