Placer N reines sur un échiquier N×N tel qu'aucune reine ne peut attaquer une autre.
Règles d'attaque des reines aux échecs:
- Une reine attaque horizontalement (même ligne)
- Une reine attaque verticalement (même colonne)
- Une reine attaque en diagonale (dans les 4 directions diagonales)
Exemple visuel pour N=4:
Solution valide: Solution INVALIDE:
. Q . . Q . . .
. . . Q . . Q . ← Reines sur même diagonale!
Q . . . . Q . .
. . Q . . . . Q
Décision: Où placer chaque reine?
Approche choisie: Une variable par colonne
queens[0]= position ligne de la reine dans colonne 0queens[1]= position ligne de la reine dans colonne 1- ...
queens[N-1]= position ligne de la reine dans colonne N-1
Pourquoi cette modélisation? ✓ Garantit automatiquement: 1 reine par colonne ✓ Réduit l'espace de recherche ✓ N variables au lieu de N×N
Exemple N=4:
queens[0] = 1 signifie:
Colonne 0, Ligne 1 → . Q . .
Domaine = valeurs possibles pour chaque variable
Pour chaque queens[i]:
- Domaine: {0, 1, 2, ..., N-1}
- Signification: La reine peut être placée sur n'importe quelle ligne
Exemple N=4:
queens[0] ∈ {0, 1, 2, 3} ← peut être ligne 0, 1, 2 ou 3
queens[1] ∈ {0, 1, 2, 3}
queens[2] ∈ {0, 1, 2, 3}
queens[3] ∈ {0, 1, 2, 3}
Espace de recherche initial: N^N solutions possibles
- N=4: 256 possibilités
- N=8: 16,777,216 possibilités!
model.allDifferent(queens).post();Signification: queens[i] ≠ queens[j] pour tout i ≠ j
Exemple:
queens[0] = 1, queens[1] = 1 ❌ INVALIDE (même ligne)
queens[0] = 1, queens[1] = 3 ✓ OK (lignes différentes)
Les reines sont sur la même diagonale montante si:
queens[i] + i = queens[j] + j
Pourquoi? Sur une diagonale ↗, quand on avance d'une colonne (+1), on monte d'une ligne (+1)
Exemple N=4:
Position (col=1, row=2): 2 + 1 = 3
Position (col=2, row=3): 3 + 2 = 5 ← Différent, OK
Position (col=3, row=4): 4 + 3 = 7 ← Différent, OK
Code:
IntVar[] diag1 = new IntVar[n];
for (int i = 0; i < n; i++) {
diag1[i] = queens[i] + i; // Diagonale montante
}
model.allDifferent(diag1).post(); // Toutes différentes!Les reines sont sur la même diagonale descendante si:
queens[i] - i = queens[j] - j
Pourquoi? Sur une diagonale ↘, quand on avance d'une colonne (+1), on descend d'une ligne (-1)
Exemple N=4:
Position (col=1, row=3): 3 - 1 = 2
Position (col=2, row=2): 2 - 2 = 0 ← Différent, OK
Position (col=3, row=1): 1 - 3 = -2 ← Différent, OK
Code:
IntVar[] diag2 = new IntVar[n];
for (int i = 0; i < n; i++) {
diag2[i] = queens[i] - i; // Diagonale descendante
}
model.allDifferent(diag2).post(); // Toutes différentes!Problème N=4, Solution: queens = [1, 3, 0, 2]
Échiquier: Vérification:
0 1 2 3 (colonnes)
0 . . Q . Col 2, Row 0
1 Q . . . Col 0, Row 1
2 . . . Q Col 3, Row 2
3 . Q . . Col 1, Row 3
Lignes: {1,3,0,2} ✓ Toutes différentes
Diag ↗: {1,4,2,5} ✓ Toutes différentes
Diag ↘: {1,2,-2,-1} ✓ Toutes différentes
C'est l'algorithme utilisé automatiquement par Choco.
Comment ça marche:
1. Choisir une variable non assignée (ex: queens[0])
2. Choisir une valeur du domaine (ex: 0)
3. PROPAGATION: Éliminer les valeurs incompatibles des autres variables
4. Si domaine vide → BACKTRACK (revenir en arrière)
5. Sinon → continuer avec la variable suivante
6. Si toutes assignées → SOLUTION!
Techniques de propagation:
- Arc-Consistency (AC): Élimine les valeurs incohérentes
- Forward Checking: Vérifie les contraintes avant d'assigner
Vous pouvez améliorer les performances en spécifiant:
a) Quelle variable choisir?
// Choisir la variable avec le plus petit domaine (Most Constrained)
solver.setSearch(Search.minDomLBSearch(queens));
// Choisir par ordre (First-Fail)
solver.setSearch(Search.inputOrderLBSearch(queens));b) Quelle valeur essayer en premier?
// Essayer la plus petite valeur d'abord
solver.setSearch(Search.minDomLBSearch(queens));
// Essayer la valeur médiane
solver.setSearch(Search.minDomMidSearch(queens));Pour N > 100, utilisez une recherche locale:
solver.setLNS(INeighborFactory.random(queens));// Dans ProblemSolver.java, ajoutez dans le constructeur:
if (n <= 20) {
// Recherche complète pour petits N
solver.setSearch(Search.minDomLBSearch(queens));
} else if (n <= 100) {
// Heuristique Domain-over-Weighted-Degree
solver.setSearch(Search.domOverWDegSearch(queens));
} else {
// Large Neighborhood Search pour très grands N
solver.setLNS(INeighborFactory.random(queens));
solver.limitTime(60000); // 60 secondes max
}Sans contraintes: N^N possibilités Avec contraintes: Réduit drastiquement!
| N | Solutions Possibles | Solutions Valides |
|---|---|---|
| 4 | 256 | 2 |
| 8 | 16,777,216 | 92 |
| 12 | 8.9×10^12 | 14,200 |
Temps de résolution:
- N=8: < 1ms
- N=100: quelques secondes
- N=1000: quelques minutes (avec LNS)
choco-nqueens/
│── pom.xml # Maven dependencies
│── README.md # This file
│── .gitignore # Git ignore rules
└── src/main/java/com/yourname/ppc/
├── Main.java # Application entry point
├── data/
│ └── ProblemData.java # Problem parameters (N)
├── model/
│ └── ProblemModel.java # Variables & constraints
└── solver/
└── ProblemSolver.java # Solving logic & output
queens[i]: Row position of queen in column i- Domain: [0, N-1] for each variable
- All-different on rows: No two queens in same row
- All-different on ascending diagonals: queens[i] + i ≠ queens[j] + j
- All-different on descending diagonals: queens[i] - i ≠ queens[j] - j
The solver finds valid queen placements satisfying all constraints.
- Java 11 or higher
- Maven 3.6+
mvn clean compilemvn exec:java -Dexec.mainClass="com.yourname.ppc.Main"mvn package
java -jar target/choco-nqueens-1.0-SNAPSHOT.jarChange the value of n in Main.java to solve for different board sizes:
- n=4: First non-trivial case
- n=8: Classic chess problem (92 solutions)
- n=12+: Computationally intensive
=== Solving N-Queens Problem: n = 8 ===
✓ Solution found!
Queen positions (column -> row):
Column 0 -> Row 0
Column 1 -> Row 4
Column 2 -> Row 7
...
Chessboard visualization:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
...