Bonjour,

J'essaie de créer un programme qui calcule les 92 solutions du problème des huit dames: https://fr.wikipedia.org/wiki/Probl%...des_huit_dames

L'idée de base de mon code est simple:
  • Les dames sont représentées par des "1" (pour le moment).
  • je fais deux checks, un pour lignes et colonnes et l'autre pour les diagonales
  • j'assigne la valeur 0 à toutes les positions de mon tableau de tableau
  • je cherche de placer les huit (valeurs "1") dames.

Je sais ça fait beaucoup de lignes mais je débute dans la programmation.

Mon problème c'est que l'algorithme calcule uniquement une solution et même si j'essaie de placer des dames en avance, me retourne toujours la même solution.

Est-ce que quelqu'un peut m'aider à trouver un algorithme de backtracking qui me permettrait de calculer les 92 combinaisons?

Voici mon code:
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>
#include <stdlib.h>
 
 
int check_lin_col(int **c, int li, int co)
{
    int l;
    int k;
 
    l = li;
    k = 0;
    while(k <= 6)
    {
        if((c[l][k] + c[l][k + 1]) > 0)
            return(0);
        k++;
    } 
    l = 0;
    k = co;
    while(l <= 6)
    {
        if((c[l][k] + c[l + 1][k]) > 0)
            return(0);
        l++;
    } 
    return(1);
} 
 
int check_diagonal(int **c, int li, int co)
{
    int l;
    int k;
 
    l = 0;
    k = 0;
    if(li >= co)
        l = li - co;
    else
        k = co - li;
    while(l <= 6 && k <= 6)
    {
        if((c[l][k] + c[l + 1][k + 1]) > 0)
            return(0);
        l++;
        k++;
    }
    l = 0;
    k = 7;
    if ((co + li) <= 7)
        k = co + li;
    else
        l = (co + li) - 7;
    while(l <= 6 && k >= 1)
    {
        if((c[l][k] + c[l + 1][k - 1]) > 0)
            return(0);
        l++;
        k--;
    } 
    return(1);
}
 
int **zerobase(int **c)
{
    int i;
    int j;
 
    c = malloc(sizeof(int *) * 8);
    i = 0;
    while(i < 8)
    {
        j = 0;
        c[i] = malloc(sizeof(int) * 8);
        while(j < 8)
        {
            c[i][j] = 0;
            j++;
        }
        i++;
    }
    return(c);
}
 
int backtrackplacement(int **c, int li, int co)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int s = 0;
 
    while (j <= 7)
    {	
        k = 0;
        while(k <= 6)
        {
            s = s + (c[j][k] + c[j][k + 1]);
            k++;
            k++;
        } 
        j++;
    }
    if(s == 8)
        return(1);
//La solution est valide seulement s'il y a huit dames de placées.
 
    while(i < 8)
    {
        if((check_diagonal(c, i, co) == 1) && (check_lin_col(c, i, co)) == 1)
        {
            c[i][co] = 1;
            if(backtrackplacement(c, i, co + 1) == 1)
                return(1);
            c[i][co] = 0;
        }
        i++;
    }
    return(0); 
}
 
int main(void)
{
    int li;
    int co;
    int **a;
 
    a = zerobase(a);
    li = 0;
    co = 0;
    backtrackplacement(a, li, co);
    // ____________________________________	
    int line = 0;
    while(line < 8)
    {
        int column = 0;
        while(column < 8)
        {
            printf("%d ", a[line][column]);
            column++;
        }
        printf("%c", '\n');
        line++;
    }
    // ____________________________________	
 
    return(0);
}
Merci d'avance!