Un problème à résoudre

Le problème des N-reines

Nous allons réaliser un code destiner à résoudre le problème des N-Reines. Ce dernier consiste à placer N reines sur un échiquier NxN en évitant les conflits sur une ligne, une colonne ou une diagonale. Voila une solution pour six reines :

+---+---+---+---+---+---+
|   | R |   |   |   |   |
+---+---+---+---+---+---+
|   |   |   | R |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   | R |
+---+---+---+---+---+---+
| R |   |   |   |   |   |
+---+---+---+---+---+---+
|   |   | R |   |   |   |
+---+---+---+---+---+---+
|   |   |   |   | R |   |
+---+---+---+---+---+---+

Une première solution

• Préparer une classe Queens.
• Prévoir une variable d'instance nb non modifiable et affectée par le constructeur.
• Prévoir un tableau d'entiers pour la position de chaque reine.
• Prévoir un méthode noConflict(int r) qui vérifie que la reine r n'est pas en conflit avec les reines précédemment posées (de 0 à r-1).
• Prévoir un méthode solve(int r) qui va résoudre le problème en essayant les positions possibles pour la reine r. En l'absence de conflit, la méthode solve est appelée récursivement sur la reine suivante.
• Le constructeur va lancer la recherche.

(N)        Total Solutions
--------------------------
1                        1
2                        0
3                        0
4                        2
5                       10
6                        4
7                       40
8                       92
9                      352
10                     724
11                   2,680
12                  14,200
13                  73,712
14                 365,596
15               2,279,184
16              14,772,512
17              95,815,104
18             666,090,624
19           4,968,057,848
20          39,029,188,884

Une deuxième solution

Dans cette solution, nous allons utiliser les trois tableaux ci-dessous afin de savoir si une colonne ou une diagonale est libre. Nous n'avons donc plus besoin de comparer la dernière reine avec les précédentes.

boolean[] columns;
boolean[] diagonals1;
boolean[] diagonals2;

Une troisième solution

Dans cette solution, nous allons utiliser les trois ensembles ci-dessous pour mémoriser les colonnes et les diagonales occupées.

Set<Integer> columns = new HashSet<>();
Set<Integer> diagonals1 = new HashSet<>();
Set<Integer> diagonals2 = new HashSet<>();

Prévoir une interface

Prévoir une interface qui va unifier le fonctionnement de ces trois solutions afin de pouvoir facilement passer d'une solution à une autre.