BDD IA Web services Architecture Info. Ubi.

M1

TD n°3

Code pour la résolution des N-Reines (pas complet):

/*
 * Problème des N-Reines.
 *
 * N reines posées sur 1 échiquier de n x n.
 * => Aucune reine ne doit être attaquée
 *
 * Une reine se déplace en ligne, colonne, diagonale de n-1 cases max
 *
 * On fixe une reine par colonne
 *
 * => Définir les contraintes entre a reine i (ième colonne, ligne i)
 * et la reine j (jème colonne, ligne j)
 */
class NReines {
  static class Echiquier {
    private int[][] echiquier;
    private int[] queens;
    private int n;

    public Echiquier(int n) {
      this.echiquier = new int[n][n];
      this.queens    = new int[n];
      this.n = n;

      for (int i = 0; i < n; i++)
        this.queens[i] = 1;
    }

    public void arrayFill(int[] conflicts) {
      for (int i = 0; i < n-1; i++) {
        int ligne_i = queens[i];

        for (int j = 0; j < n; j++) {
          if (ligne_i == queens[j]) {
            conflicts[i]++;
            conflicts[j]++;
            continue;
          }

          if (i-ligne_i == j-queens[j]) {
            conflicts[i]++;
            conflicts[j]++;
            continue;
          }

          if (i+ligne_i == j+queens[j]) {
            conflicts[i]++;
            conflicts[j]++;
            continue;
          }
        }
      }
    }

    public void afficher() {
      for (int i = 0; i < n; i++) {
        System.out.print("| ");

        for (int j = 0; j < n; j++) {
          System.out.print(this.echiquier[i][j]);
          System.out.print(" | ");
        }

        System.out.println("");
      }
    }
  }

  public static void main(String args[]) {
    System.out.println("Eh bien le bonjour !");

    Echiquier e = new Echiquier(4);

    e.afficher();
  }
}

Choco solver pour la réalisation d'un solver de N-Reines en Java.

int n = 200;

Model model = new Model("Pb des " + n + " reines");

IntVar[] queens = new IntVar[n];

for (int i = 0; i < n; i++)
  queens[i] = model.intVar("Q"+i, 1, n);

for (int i = 0; i < n; j++) {
  for (int j = i+1; j < n; j++) {
    model.arithm(queens[i], "!=", queens[j]).post();
    model.arithm(queens[i], "!=", queens[j], "-", (j-i)).post();
    model.arithm(queens[i], "!=", queens[j], "+", (j-i)).post();
  }
}

Solver solver = model.getSolver();
Solution s = solver.FindSolution();
System.out.println(s.toString());

// Petits plus

solver.showStatistics();

TD Backtracking:

Soit E = {n₁, ..., n_n} avec n_i ∈ N.

A = {a₁, ..., a_n} <- action a_i ∈ {0, 1}

But ∑ a_i × m_i = C

Initialement E = {5, 12, 6, 9}, A = {0, 0, 0, 0}

On a donc :

                 Ø
                 |
        +-----+-----+-----+
        |     |     |     |
        5     12    6     9

Objectif, obtenir 26 en additionnant les nombres et en ne changeant qu'un a_i par étape.

Effectuer la recherche:

• En largeur
• En profondeur
• En profondeur limité à 3 niveaux

Parcours en largeur:

1. Première itération :
   • Noeuds libres = 5, 12, 6, 9
   • Noeuds clos = Ø
2. Deuxième itération (combinaisons avec 5 et les autres noeuds) :
   • Noeuds libres = 12, 6, 9, 17, 11, 14
   • Noeuds clos = Ø, 5
3. Troisième itération (combinaisons avec 12 et les autres noeuds) :
   • Noeuds libres = 9, 17, 11, 14, 18, 21
   • Noeuds clos = Ø, 5, 12
4. Quatrième itération (combinaisons avec 6 et les autres noeuds) :
   • Noeuds libres = 9,17,11,14,18,21,15
   • Noeuds clos = Ø, 5, 12, 6

Les combinaisons avec 9 vont redonner les mêmes résultats, on peut donc arrêter le parcours de l'arbre.