Discussion :

[pottiez]

Bonjour, Je vous propose un nouvel élément à utiliser : Afficher toutes les solutions au problème des N-Reines



Programme qui permet de résoudre et afficher toutes les solutions au problème des N-Reines (ou N-Dames).



Le problème des N-Reines consiste à placer N reines sur un échiquier NxN sans que l'une d'elles puisse en manger une autre (avec les règles des échecs : une reine peut « manger » toute pièce située sur sa ligne, sur sa colonne ou sur l'une de ses deux diagonales).



Pour plus d'informations sur le problème des N-Reines, vous pouvez consulter cet article sur la résolution du problème des Huit Dames (http://fr.wikipedia.org/wiki/Probl%C3%A8me_des_huit_dames)



Qu'en pensez-vous ?

[PatrickNice]

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def dames(N = 8, n = 0, x = [0], a = None): # n = profondeur de recherche, a = "échiquier"
 
    if a is None :
        if N < 4 or N > 12: N = 8
        a = [0] * N
 
    if n >= N: # affichage d'une solution
        x[0] += 1 # et comptage du nombre de solution
        #return # pour ne faire que compter les solutions
 
        print(f"\n N°{x[0]} - {''.join(map(str,a))}")
        print('┌', '───┬'*(N-1), '───┐', sep='')
        for u in range(N): # lignes
            for z in range(N): # colonnes
                if a[u] == z:
                    b=['│   ']*N
                    b[z]='│ * '
                    print(*b, sep='', end='│\n')
                    if u < N-1: print('├', '───┼'*(N-1), '───┤', sep='')
                    # ou b=['·']*N; b[z]='*'; print(*b)
                    break
        print('└', '───┴'*(N-1),'───┘',sep='')
        return
 
    for a[n] in range(N): # colonnes
        if not any(a[n] == a[z] or abs(a[n] - a[z]) == 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[n] == a[z] or abs(a[n] - a[z]) == n - z:
                valid = False # invalide
                break
        if valid: dames(N, n+1, x, a) # c'est ok, on poursuit
        """
    return x[0]
 
print('\n',dames(8),'solutions')

ou en c++ :

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
 
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[N]; // 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[i];
 
    // 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[u] ? "│ * " : "│   ");
        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[n] == a[z] || abs(a[n] - a[z]) == n - z)
            return false;
    return true;
}
 
void dames(int n = 0) {
    if (n >= N) {++x; return afficher_solution();}
    for (a[n] = 0; a[n] < N; a[n]++)
        if (valide(n)) dames(n + 1);
}
 
int main() {
 
	SetConsoleOutputCP(65001);
 
	dames();
	printf("\n%d solutions\n", x);
 
	_getch();
	return 0;
}

[Guesset]

Bonjour PatrickNice,

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

Code

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

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def dames(N = 8, n = 0, x = [0], a = None): # n = profondeur de recherche, a = "échiquier"
 
    if a is None :
        if N < 4 or N > 12: N = 8
        a = [0] * N
 
    if n >= N: # affichage d'une solution
        x[0] += 1 # et comptage du nombre de solution
        #return # pour ne faire que compter les solutions
 
        print(f"\n N°{x[0]} - {''.join(map(str,a))}")
        print('┌', '───┬'*(N-1), '───┐', sep='')
        for u in range(N): # lignes
            for z in range(N): # colonnes
                if a[u] == z:
                    b=['│   ']*N
                    b[z]='│ * '
                    print(*b, sep='', end='│\n')
                    if u < N-1: print('├', '───┼'*(N-1), '───┤', sep='')
                    # ou b=['·']*N; b[z]='*'; print(*b)
                    break
        print('└', '───┴'*(N-1),'───┘',sep='')
        return
 
    for a[n] in range(N): # colonnes
        if not any(a[n] == a[z] or abs(a[n] - a[z]) == 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[n] == a[z] or abs(a[n] - a[z]) == n - z:
                valid = False # invalide
                break
        if valid: dames(N, n+1, x, a) # c'est ok, on poursuit
        """
    return x[0]
 
print('\n',dames(8),'solutions')

ou en c++ :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
 
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[N]; // 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[i];
 
    // 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[u] ? "│ * " : "│   ");
        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[n] == a[z] || abs(a[n] - a[z]) == n - z)  return false;
    return true;
}
 
void dames(int n = 0) {
    if (n >= N) {++x; return afficher_solution();}
    for (a[n] = 0; a[n] < N; a[n]++)
        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