Afficher toutes les solutions au problème des N-Reines

Bonjour PatrickNice,

Avec des balises (#), c'est plus propre.

Code

Avec des balises de code (bouton #), c'est plus propre.

def dames(N = 8, n = 0, x = , a = None): # n = profondeur de recherche, a = "échiquier"

if a is None :
if N < 4 or N > 12: N = 8
a = * N

if n >= N: # affichage d'une solution
x += 1 # et comptage du nombre de solution
#return # pour ne faire que compter les solutions

print(f"\n N°{x} - {''.join(map(str,a))}")
print('┌', '───┬'*(N-1), '───┐', sep='')
for u in range(N): # lignes
for z in range(N): # colonnes
if a == z:
b=['│ ']*N
b='│ * '
print(*b, sep='', end='│\n')
if u < N-1: print('├', '───┼'*(N-1), '───┤', sep='')
# ou b=['·']*N; b='*'; print(*b)
break
print('└', '───┴'*(N-1),'───┘',sep='')
return

for a in range(N): # colonnes
if not any(a == a or abs(a - a) == n - z for z in range(n)):
dames(N, n+1, x, a) # c'est ok, on poursuit
"""
valid = True # validité par défaut
for z in range(n): # lignes
if a == a or abs(a - a) == n - z:
valid = False # invalide
break
if valid: dames(N, n+1, x, a) # c'est ok, on poursuit
"""
return x

print('\n',dames(8),'solutions')

ou en c++ :

#include

extern "C" int SetConsoleOutputCP(unsigned);
extern "C" int _getch();

using namespace std;

#define N 8 // N de 4 à 12
int x = 0; // Compteur de solutions
int a; // ligne d'échiquier

void afficher_solution() {
cout << "\nN°" << x << " - "; // return ici si on ne veut que le nombre de solution
for (int i = 0; i < N; i++) cout << a;

// Ligne du haut
cout << "\n┌";
for (int i = 0; i < N - 1; i++) cout << "───┬";
cout << "───┐\n";

for (int u = 0; u < N; u++) {
for (int i = 0; i < N; i++) cout << (i == a ? "│ * " : "│ ");
cout << "│\n"; // Affichage de la fin de ligne

// Ligne de séparation (sauf pour la dernière ligne)
if (u < N - 1) {
cout << "├";
for (int i = 0; i < N - 1; i++) cout << "───┼";
cout << "───┤\n";
}
}

// Ligne du bas
cout << "└";
for (int i = 0; i < N - 1; i++) cout << "───┴";
cout << "───┘\n";
}

bool valide(int n) {
for (int z = 0; z < n; z++)
if (a == a || abs(a - a) == n - z) return false;
return true;
}

void dames(int n = 0) {
if (n >= N) {++x; return afficher_solution();}
for (a = 0; a < N; a++)
if (valide(n)) dames(n + 1);
}

int main() {
SetConsoleOutputCP(65001);
dames();
printf("\n%d solutions\n", x);
_getch();
return 0;
}


Comme souvent en informatique, il est possible d'échanger de l'espace contre du temps. Si au lieu de valider ou non une nouvelle position, on choisit une propagtion des interdits on gagne beaucoup de temps au prix d'un maximum de 288 octets (12 matrices de 12*2 octets soit 288 octets - 2 octets gérant jusqu'à 16 positions dont 4 inutilisées). Si l'initialisation est à N bits à 1 ((1 << N) - 1) la disparition de toute possibilité se traduit juste par un word (uint16_t) à 0. En toute rigueur, on pourrait diminuer cet espace car chaque ligne i (0 à N-1) n'altère que N -1 - i lignes. Mais la place n'est pas si critique me semble-t-il.
On pourrait aussi utiliser les symétries pour diviser le volume d'analyse.

Salut