Problème des n-reines

Commenter

Contenu du snippet

Le problème des N-Reines consiste à disposer N Reines sur un échiquier de N x N cases sans qu'aucune d'elles ne soit attaquée par une autre.

Trouver une solution est très facile et rapide. Trouver toutes les solutions est plus compliqué.
À cette date (07/07/11), le problème est résolu pour 26 reines.

Je propose 2 méthodes permettant de résoudre le problème pour 15 reines dans un temps raisonnable.

Source / Exemple : 


/**


     
  •  algorithme court mais peu efficace

    •  
  •  

    •  
  •  @author guehenneux

    •  
  • /

public class NReines1 {

	/**


    	 
  •  @param arguments

    • 	 
  • /

	public static void main(String... arguments) {
		new NReines1(14);
	}

	private final int n;
	private int nombreSolutions;

	/**


    	 
  •  @param n

    • 	 
  • /

	public NReines1(int n) {

		this.n = n;

		System.out.println(n + " reines");
		nombreSolutions = 0;

		long t0 = System.currentTimeMillis();
		placerReines(0, 0, 0, 0);
		long t1 = System.currentTimeMillis();

		System.out.println("solution(s) : " + nombreSolutions);
		System.out.println("duree de la recherche : " + (t1 - t0) + "ms");

	}

	/**


    	 
  •  methode recursive permettant de placer n reines

    • 	 
  •  

    • 	 
  •  @param x

    • 	 
  •             index de la colonne ou placer la reine suivant

    • 	 
  •  @param bH

    • 	 
  •             bits indiquant quelles lignes horizontales sont occupees

    • 	 
  •  @param bD

    • 	 
  •             bits indiquant quelles lignes diagonales \ sont occupees

    • 	 
  •  @param bA

    • 	 
  •             bits indiquant quelles lignes diagonales / sont occupees

    • 	 
  • /

	private final void placerReines(int x, int bH, long bD, long bA) {

		int xSuivant = x + 1;

		int mH = 1;
		long mD = 1 << x;
		long mA = 1 << n - xSuivant;

		for (int y = 0; y < n; y++, mH <<= 1, mD <<= 1, mA <<= 1) {

			/*


    			 
  •  on verifie que les lignes horizontales et diagonales passant par

    • 			 
  •  la case sont vides

    • 			 
  • /


			if ((bH & mH) == 0 && (bD & mD) == 0 && (bA & mA) == 0) {

				if (xSuivant == n) {
					nombreSolutions++;
				} else {
					placerReines(xSuivant, bH + mH, bD + mD, bA + mA);
				}

			}

		}

	}

}

/**


     
  •  algorithme relativement efficace (reste a le paralleliser et a tirer profit

    •  
  •  des symetries)

    •  
  •  

    •  
  •  @author guehenneux

    •  
  • /

public class NReines2 {

	/**


    	 
  •  @param arguments

    • 	 
  • /

	public static void main(String... arguments) {
		new NReines2(14);
	}

	private final int n;
	private final int limiteMasque;
	private int nombreSolutions;
	private int[][] echiquiers;

	/**


    	 
  •  @param n

    • 	 
  •             largeur et hauteur, au moins 1

    • 	 
  • /

	public NReines2(int n) {

		this.n = n;

		/*


    		 
  •  chaque colonne est representee par un entier

    • 		 
  •  

    • 		 
  •  si une case est libre, le bit correspondant est a 1, sinon il est a 0

    • 		 
  •  

    • 		 
  •  par exemple pour n = 8, la colonne 10011101 (1 + 4 + 8 + 16 + 128 =

    • 		 
  •  157) signifie que seules les cases 0, 2, 3, 4 et 7 sont libres)

    • 		 
  • /


		/*


    		 
  •  un echiquier est represente par un tableau de colonnes

    • 		 
  • /


		/*


    		 
  •  pour la solution iterative, on utilise un tableau d'echiquiers (un

    • 		 
  •  echiquier par niveau de recursivite)

    • 		 
  •  

    • 		 
  •  par exemple, au niveau 2 de la recursivite, on travaille sur

    • 		 
  •  l'echiquier echiquiers[2]

    • 		 
  • /


		echiquiers = new int[n][n];

		/*


    		 
  •  ce masque est un '1' suivi de n '0' (purement utilitaire)

    • 		 
  • /


		limiteMasque = 1 << n;

		System.out.println(n + " reines");
		nombreSolutions = 0;

		/*


    		 
  •  on initialise l'echiquier pour la profondeur 0, toutes les positions

    • 		 
  •  sont possibles donc chaque colonne est valorisee avec n bits a 1

    • 		 
  • /


		int colonneLibre = limiteMasque - 1;

		for (int x = 0; x < n; x++) {
			echiquiers[0][x] = colonneLibre;
		}

		long t0 = System.currentTimeMillis();
		placerReines(0);
		long t1 = System.currentTimeMillis();

		System.out.println("solution(s) : " + nombreSolutions);
		System.out.println("duree de la recherche : " + (t1 - t0) + "ms");

	}

	/**


    	 
  •  methode recursive permettant de placer n reines

    • 	 
  •  

    • 	 
  •  @param x

    • 	 
  •             index de la colonne ou placer la reine suivant

    • 	 
  • /

	private final void placerReines(int x) {

		/*


    		 
  •  on recupere l'echiquier correspondant a la profondeur courante

    • 		 
  • /


		int[] echiquier = echiquiers[x];

		/*


    		 
  •  on recupere la colonne ou placer la reine

    • 		 
  • /


		int colonne = echiquier[x];

		/*


    		 
  •  index de la colonne suivante

    • 		 
  • /


		int xSuivant = x + 1;

		if (xSuivant == n) {

			/*


    			 
  •  DERNIER COLONNE

    • 			 
  • /


			/*


    			 
  •  s'il y a une case libre, on a une solution

    • 			 
  • /


			if (colonne != 0) {
				nombreSolutions++;
			}

		} else {

			/*


    			 
  •  PAS ENCORE LA DERNIERE COLONNE

    • 			 
  • /


			int[] echiquierSuivant = echiquiers[xSuivant];

			int masqueColonne, masqueCase;
			int i;

			/*


    			 
  •  on boucle sur la colonne tant qu'il y a des cases libres

    • 			 
  • /


			while (colonne != 0) {

				/*


    				 
  •  on prend la prochaine case libre

    • 				 
  • /


				masqueCase = colonne ^ (colonne & (colonne - 1));

				/*


    				 
  •  on y place une reine

    • 				 
  • /


				colonne &= ~masqueCase;

				/*


    				 
  •  on marque les cases sur la meme horizontale

    • 				 
  • /


				i = x;

				while (++i != n) {
					echiquierSuivant[i] = echiquier[i] & ~masqueCase;
				}

				/*


    				 
  •  on marque les cases sur la meme antidiagonale

    • 				 
  • /


				masqueColonne = masqueCase;
				i = x;

				while (++i != n && (masqueColonne >>= 1) != 0) {
					echiquierSuivant[i] &= ~masqueColonne;
				}

				/*


    				 
  •  on marque les cases sur la meme diagonale

    • 				 
  • /


				masqueColonne = masqueCase;
				i = x;

				while (++i != n && (masqueColonne <<= 1) != limiteMasque) {
					echiquierSuivant[i] &= ~masqueColonne;
				}

				/*


    				 
  •  on tente de placer une reine sur la colonne suivante

    • 				 
  • /


				placerReines(xSuivant);

			}

		}

	}

}

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_jojolemariole)