Communauté Clubic

Problème des N Reines Java

Bonsoir,

je dois programmer une classe qui affiche n reines sur un échiquier de taille n * n sans qu’elles soient prises l’une avec l’autre. Je dois afficher toutes les solutions possibles. Avec mon code j’arrive à afficher qu’une seule solution et je n’arrive pas à trouver l’astuce pour pouvoir afficher toutes les possibilités. Je vous mets mon code dans la suite.

public class Echiquier {
	
	private int[] echiquier;
	private int[] memoireColonne;
	private int taille;
	public static int nombreReinePosee = 0;

	public Echiquier(int taille){
		this.taille = taille;
		echiquier = new int[taille];
		memoireColonne = new int[1];
		initialisation();		
	}
	
	private void initialisation(){
		for(int i=0;i<taille;i++){
			echiquier[i] = -1;
		}
	}
		
	public void poserReine(int posLigne, int posColonne){
		echiquier[posLigne] = posColonne;
	}
	
	public boolean colonnePrise(int colonne){
		for(int i=0;i<taille;i++){
			if(echiquier[i] == colonne) return true;
		}
		return false;
	}

	public boolean diagonalePrise(int ligne, int colonne){
		boolean bool = false;
		
		for(int i =0;i<taille && bool == false;i++){
			if(echiquier[i] != -1){
				int tmp_ligne = ligne -i;
				int tmp_colonne = colonne - echiquier[i];
				if(Math.abs(tmp_ligne) == Math.abs(tmp_colonne)) bool = true;
			}
		}
		return bool;
	}
	
	public boolean peutJouer(int ligne, int colonne){
		return (!colonnePrise(colonne) && !diagonalePrise(ligne, colonne));
	}
	
	public void jouer(int ligne, int colonne){
		int tmp_ligne = 0;
		int tmp_colonne = 0;
		
		/* Si on peut poser la reine alors on la pose */
		if(peutJouer(ligne, colonne)){
			poserReine(ligne, colonne);
			nombreReinePosee++;
			/* Si la taille n'est pas atteinte, on continue a appeler la même fonction */
			if(ligne+1<taille) jouer(ligne+1,0);
			else return;
		}
		else{
			/* Si l'indice de la colonne est inférieure à la taille alors on ajoute la reine
			 * sur la dernière colonne
			 */
			if(colonne+1<taille) jouer(ligne,colonne+1);
			/* On ne peut plus mettre de reine sur les lignes*/
			else{
				/* Si la reine de la ligne du dessus n'est pas sur l'avant dernière colonne, alors on l'enlève 
				 * et on la met sur la première colonne suivante disponible */

				if((echiquier[ligne-1]+1)<taille){
					tmp_colonne = echiquier[ligne-1]+1;
					echiquier[ligne-1] = -1;
					jouer(ligne-1,tmp_colonne);	
				}else{
					/* Sinon on recule d'une ligne et on enlève la dernière reine posée*/
					tmp_colonne = echiquier[ligne-1];
					tmp_ligne = ligne - 1;
					echiquier[ligne-1] = -1;
					
					if(tmp_colonne+1<=taille) jouer(tmp_ligne-1,echiquier[tmp_ligne-1]+1);
					/* Sinon on reprend à la premiere colonne */
					else jouer(ligne-1,0);					
				}
			}			
		}
	}		
	
	public String toString(){
		
		String var="";
		
		for(int i=0;i<taille;i++){
			for(int j=0;j<taille;j++){
				if(echiquier[i]!=-1 && echiquier[i] == j) var+="[R]";
				else var+="[*]";
			}
			var+="\n";
		}
		return var;
	}
	
	public static void main(String args[]){
		Echiquier echiquier = new Echiquier(6);
		echiquier.jouer(0,0);
		System.out.println(echiquier);
	}	
}

Concrètement j’obtiens ça :

[][R][][][][]
[
][][][R][][]
[][][][][][R]
[R][
][][][][]
[][][R][][][]
[
][][][][R][]

Je ne vous demande pas la solution, si possible de me guider. Merci beaucoup

Faut que d’une façon ou d’une autre tu sauvegarde ta ou tes solutions de telle sorte à ne pas les revisiter. Bon je dis ça, je ne saurais pas trop comment faire à moins de tester le programme de bout en bout :slight_smile:

C est ton prof qui te demande d’ écrire des commentaires ? J ai pas trop saisi le problème. Je ne rentre pas facilement dans ta classe. Et pourquoi d’ après toi ? Probablement pour les raisons qui t amènent a nous.

Tu as un besoin complexe. Suffisamment complexe pour ne pas pouvoir l aborder d’ une traite. Je pense qu il
faudrait que tu organises tes programmes pour diminuer les responsabilités de chaque sous partie. Ensuite tu les testes les uns après les autres.

Il te faut savoir pourquoi tu ne piges pas pourquoi ça ne fait pas l attendu, et ensuite ou se passe le bins

Pour les commentaires pas spécialement mais ils nous les conseillent. Tu veux dire qu’il faut que j’éxécute pas à pas la méthode jouer() ?

Avis perso :

  • tu enleves tes commentaires, et tu essaies d’ écrire clairement. Introduis des méthodes, nommage simple et précis, évite la compression d’instructions, etc . Tu veux un exemple ?
  • ensuite tu crées des méthodes qui vont tester chaque méthode. Les méthodes privées peuvent passer proteges pour l occaz. C est ce qu on peut appeler couvrir son code
  • l exécution pas a pas est utile lorsque le périmètre du code a explorer est faible. Si tu le fais sur tout ton programme, en plus de prendre du temps, alors on peut facilement conclure que tu n as pas confiance en la qualité de ton code. Ce a quoi il faut remédier.

Ce que je te suggères n est pas une solution professionnelle. Mais c le principe qui est important

Je ne vois pas en quoi retirer les commentaires aidera quoi que ce soit…

C est parce qu il faut bien lire toute la phrase, et ensuite te poser la question suivante “pourquoi ?”

Le code simple et propre avec variables et procédures bien nommées n’empêche pas de commenter son code :neutre:
Edité le 13/10/2009 à 18:31

Bon fait chier, j’avais écrit un exemple mais j’ai fait une erreur de manip …

Bref, pour résumer :

  • Ecrire et du code simple & propre, et des commentaires et un non sens. A quoi bon commenter un code source bien écrit ? A faire beau ? A faire de la paraphrase ? A faire parce qu’on dit que c’est bien de le faire ?
  • La justification typique du commentaire -de ce qui ne peut pas etre compris quand on lit- est la présence de limitation technique ou de bug.
  • Ce que je dis s’applique généralement, parce que les développeurs sont la plupart du temps impliqués dans des projets. Les commentaires sont bien entendu évidents lorsque le code produit est celui d’un framework, pour lequel il n’existe pas de code collective ownership.

Ouais. C’est clair qu’une méthode non commentée, avec des paramètres non commentés, c’est plus utile que quand c’est commenté…

Puis bon, la doc ultime de tout projet c’est le mode debug, c’est bien connu :slight_smile:

Bref, j’ironise, mais le plus important c’est de commenter les méthodes publiques et protégées histoire qu’on sache ce qu’elle fait, on n’a pas vocation d’aller comprendre par cœur le code des autres, hein :slight_smile:
Edité le 13/10/2009 à 19:50

On m’avait fait coder le même problème du temps où j’étais étudiant :slight_smile:

Mon approche a été la suivante :

D’abord une fonction qui vérifie qu’une position est valide (s’assure qu’aucune dame ne peut prendre une autre).
A partir de là, tu fais une fonction récursive qui prend en paramètre un échiquier et le numéro de la ligne, et qui va se charger de peupler l’échiquier :

  • Si tu es à la dernière ligne (et que la position est valide), tu as trouvé une solution
  • Sinon, tu boucles sur le nombre de cases de la ligne, et à chaque itération :
    … - Tu ajoutes une dame sur la n-ème case de la ligne
    … - Si la position est valide, tu rappelle la fonction récursive en lui passant le nouvel échiquier et le numéro de ligne suivant

(et je suis fervent partisan des commentaires dans le code dans la limite du raisonnable, mais c’est un autre débat)
Edité le 13/10/2009 à 20:20

Je vous remercie. Je vais essayer ça demain et je vous tiendrais au courant de mon avancée.

Ne serait ce pas plus simple de passer par une classe Static ?

Vu que tu ne manipules qu’une seule instance de la classe, je ne vois pas ce que ça changerais :slight_smile:

Voilà j’ai réussi à résoudre le problème. J’ai commencé par réécrire chaque méthode en essayant de voir où je pouvais gagner en exécution et pour ma compréhension. Je suis d’abord parti d’une classe en static, je trouvais ça plus facil, et j’en ai fais une deuxième version plus normale.

Merci beaucoup :wink: