Probleme des huit dames avec backtracking

**Balario** · 07/10/2018, 12h52

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!

**Sve@r** · 07/10/2018, 18h33

Envoyé par Balario

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

Bonjour

Il ne faut pas que ton algorithme s'arrête quand il a trouvé une position mais qu'il examine chacune des positions possibles.
Ca serait un truc de ce style: une fonction se charge de placer une dame sur une ligne L => elle boucle donc sur les 8 colonnes de cette ligne et place alors la dame sur la première colonne possible. Puis elle s'appelle elle-même en récursif pour la ligne L+1. Et dès que la 8° dame est placée tu affiches la position. MAIS tu ne t'arrêtes pas. Ainsi la 8° instance continue à évaluer les 8 colonnes possibles. Puis ça remonte à la 7° qui est toujours dans sa boucle et passe alors à la colonne C+1 de sa 7° ligne et si c'est bon, réappelle alors la 8° instance pour tester cette nouvelle position. Et etc etc etc jusqu'à ce que la fonction de premier niveau ait traité elle-aussi les 8 colonnes possibles.

Un truc de ce genre

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
void placeReine(lig, echiquier) {
	for (col=0; col < 8; col++) {
		echiquier[lig][col]=1;
		if (validePosition(echiquier)) {
			if (lig < 7)
				placeReine(lig+1, echiquier);
			else
				afficheEchiquier(echiquier);
		}
		echiquier[lig][col]=0;
	}
}

Eventuellement, si l'échiquier est affiché, ça veut dire que la 8° reine est sur la seule et unique position possible donc dans ce cas précis on peut interrompre la boucle par un break mais ça fait gagner au mieux 7 évaluations et dans ce cas, il ne faut pas oublier de rajouter echiquier[lig][col]=0 pour enlever la reine de sa case.

**Balario** · 09/10/2018, 21h58

Envoyé par Sve@r

Bonjour

Il ne faut pas que ton algorithme s'arrête quand il a trouvé une position mais qu'il examine chacune des positions possibles.
Ca serait un truc de ce style: une fonction se charge de placer une dame sur une ligne L => elle boucle donc sur les 8 colonnes de cette ligne et place alors la dame sur la première colonne possible. Puis elle s'appelle elle-même en récursif pour la ligne L+1. Et dès que la 8° dame est placée tu affiches la position. MAIS tu ne t'arrêtes pas. Ainsi la 8° instance continue à évaluer les 8 colonnes possibles. Puis ça remonte à la 7° qui est toujours dans sa boucle et passe alors à la colonne C+1 de sa 7° ligne et si c'est bon, réappelle alors la 8° instance pour tester cette nouvelle position. Et etc etc etc jusqu'à ce que la fonction de premier niveau ait traité elle-aussi les 8 colonnes possibles.

Eventuellement, si l'échiquier est affiché, ça veut dire que la 8° reine est sur la seule et unique position possible donc dans ce cas précis on peut interrompre la boucle par un break mais ça fait gagner au mieux 7 évaluations et dans ce cas, il ne faut pas oublier de rajouter echiquier[lig][col]=0 pour enlever la reine de sa case.

Merci beaucoup!!!

J'ai juste modifié ton code en passant le "echiquier[lig][col]=1;" dans le "if" et ça a marché!

Voici le bout de code final (j'ai séparé les controles pour lignes et colonnes) :

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
int backtrackplacement(int **c, int li, int co)
{
    int kk = 0;
    while(kk < 8)
    {
        if((check_diagonal(c, li, kk) == 1) && (check_line(c, li, kk) == 1 && check_column(c, li, kk) == 1))
        {
           c[li][kk] = 1;
           if(li < 7)
           {
          	  backtrackplacement(c, li + 1, kk);
           }
           else
           {
              print(c);
           }   
           c[li][kk] = 0;
        }
        kk++;
    }
    return(0); 
}

J'aimerais aussi compter les résultats mais avec un compteur classique ("count++" dans l'else) j'ai du mal car la fonction est récursive.
Est-ce que t'as un conseil à me donner pour cela aussi?

**Sve@r** · 10/10/2018, 07h02

Envoyé par Balario

J'ai juste modifié ton code en passant le "echiquier[lig][col]=1;" dans le "if" et ça a marché!

C'est bizarre car cette ligne est la ligne qui place la reine sur sa case. Or il faut la placer avant de vérifier que la position est valide car cette vérification implique qu'on teste la reine en cours...

[edit]Je viens de coder le truc à mon idée et non, il faut bien placer cette ligne comme je l'avais écrit avant le "if"

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
62
63
64
65
#include <stdio.h>

unsigned short valideDroite(unsigned short e[8][8], unsigned short l, unsigned short c, char sens) {
	unsigned short i;
	for (i=0; i < 8; i++) {
		switch (sens) {
			case 'c': // Colonne
				if (i == c) continue;
				if (e[l][i] != 0) return 0;
				break;
			case 'l': // Ligne
				if (i == l) continue;
				if (e[i][c] != 0) return 0;
				break;
			case 'd': // Diagonale
				if (i == 0) continue;
				if ((short)(l - i) >= 0 && (short)(c - i) >= 0 && e[l-i][c-i] != 0) return 0;
				if ((short)(l - i) >= 0 && (short)(c + i) <= 7 && e[l-i][c+i] != 0) return 0;
				if ((short)(l + i) <= 7 && (short)(c - i) >= 0 && e[l+i][c-i] != 0) return 0;
				if ((short)(l + i) <= 7 && (short)(c + i) <= 7 && e[l+i][c+i] != 0) return 0;
				break;
			default:
				return 0;
		}
	}
	return 1;
}

unsigned short validePosition(unsigned short e[8][8], unsigned short l, unsigned short c) {
	if (valideDroite(e, l, c, 'l') == 0) return 0;
	if (valideDroite(e, l, c, 'c') == 0) return 0;
	if (valideDroite(e, l, c, 'd') == 0) return 0;
	return 1;
}

void afficheEchiquier(unsigned short e[8][8]) {
	unsigned short l;
	unsigned short c;
	for (l=0; l < 8; l++) {
		for (c=0; c < 8; c++) {
			printf("%c", e[l][c] == 0 ?'.' :'D');
		}
		fputc('\n', stdout);
	}
	fputc('\n', stdout);
}

void placeDame(unsigned short e[8][8], unsigned short l) {
	unsigned short c;
	for (c=0; c < 8; c++) {
		e[l][c]=1;				// Avant le "if" !!!
		if (validePosition(e, l, c) != 0) {
			if (l < 7)
				placeDame(e, l+1);
			else
				afficheEchiquier(e);
		}
		e[l][c]=0;
	}
}

int main() {
	unsigned short e[8][8]={};
	placeDame(e, 0);
}

Envoyé par Balario

J'aimerais aussi compter les résultats mais avec un compteur classique ("count++" dans l'else) j'ai du mal car la fonction est récursive.
Est-ce que t'as un conseil à me donner pour cela aussi?

En terme de variables, la récursivité équivaut à une autre fonction. Or si tu veux passer un compteur à une autre fonction pour qu'elle le modifie tu passes alors l'adresse du compteur pour que l'autre fonction puisse taper dans la bonne variable.

Donc ça devrait être un truc ressemblant à ceci

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
void backtrackplacement(int **c, int li, int co, int *cpt)
{
    int kk = 0;
    while(kk < 8)
    {
        if((check_diagonal(c, li, kk) == 1) && (check_line(c, li, kk) == 1 && check_column(c, li, kk) == 1))
        {
           c[li][kk] = 1;
           if(li < 7)
           {
          	  backtrackplacement(c, li + 1, kk, cpt);
           }
           else
           {
              print(c);
              (*cpt)++;
           }   
           c[li][kk] = 0;
        }
        kk++;
    }
}

Et dans le main, tu définis un "int" à 0 et tu passes son adresse au premier appel de backtrackplacement(). Et au retour tu affiches sa valeur (j'ai essayé sur mon propre code et j'obtiens bien 92).

Autre possibilité: le compteur est passé à l'instance récursive (pour qu'elle le connaisse et s'en serve) et en même temps récupéré depuis cette même instance (pour qu'il remonte jusqu'au main)

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
int backtrackplacement(int **c, int li, int co, int cpt)
{
    int kk = 0;
    while(kk < 8)
    {
        if((check_diagonal(c, li, kk) == 1) && (check_line(c, li, kk) == 1 && check_column(c, li, kk) == 1))
        {
           c[li][kk] = 1;
           if(li < 7)
           {
          	  cpt=backtrackplacement(c, li + 1, kk, cpt);
           }
           else
           {
              print(c);
              cpt++;
           }   
           c[li][kk] = 0;
        }
        kk++;
    }
    return cpt;
}

Et dans le main tu écris cpt=backtrackplacement(c, 0, 0, 0).

**Balario** · 14/10/2018, 11h44

Envoyé par Sve@r

C'est bizarre car cette ligne est la ligne qui place la reine sur sa case. Or il faut la placer avant de vérifier que la position est valide car cette vérification implique qu'on teste la reine en cours...

[edit]Je viens de coder le truc à mon idée et non, il faut bien placer cette ligne comme je l'avais écrit avant le "if"

Je crois que la différence est dans mes contrôles.
Dans mon code si je place un "1" au préalable, les conditions dans le "if" (check_line et check_column) ne sont jamais vraies et la fonction n'est jamais appelée en récursif.

Envoyé par Sve@r

En terme de variables, la récursivité équivaut à une autre fonction. Or si tu veux passer un compteur à une autre fonction pour qu'elle le modifie tu passes alors l'adresse du compteur pour que l'autre fonction puisse taper dans la bonne variable.

Et dans le main, tu définis un "int" à 0 et tu passes son adresse au premier appel de backtrackplacement(). Et au retour tu affiches sa valeur (j'ai essayé sur mon propre code et j'obtiens bien 92).

Merci beaucoup pour ton aide! ça a marché et j'ai bien 92 comme résultat final!
C'est vraiment une approche intéressante de passer l'adresse du compteur pour que la variable ne son pas "clonée".

**Sve@r** · 14/10/2018, 12h19

Envoyé par Balario

Je crois que la différence est dans mes contrôles.

Oui, c'est possible. Si t'as envisagé une approche différente de la mienne ça peut amener à cet écart. Heureusement l'écart est minime.
De mon côté j'ai modifié mon code pour pouvoir lui demander de trouver la solution sur un échiquier de taille variable (la taille étant alors passée comme argument lors de l'appel).
Seul souci: transformer l'échiquier 2D en échiquier 1D (c'est en effet plus facile d'allouer d'un coup n*n cases que d'allouer en deux étapes n pointeurs puis, pour chaque pointeur, allouer n cases). Et en mémoire c'est la même chose. Simplement ensuite, faut remplacer toute référence de type case[x][y] en référence de type case[x * cote + y].
Ensuite j'ai associé l'échiquier et sa taille dans une structure pour que toute fonction qui reçoive l'échiquier sache aussi comment il est fait => ne jamais négliger l'avantage inégalable d'une structure et chaque fois qu'on doit associer deux éléments ensembles, toujours se forcer à les mettre dans une structure. Je sais, c'est chiant car il faut réfléchir au nom de la structure et des éléments mais quand c'est fait, c'est un soulagement à coder car on se fait plus chier à se dire "oh là là je dois passer ceci et cela à ma fonction". On passe la structure et basta.

Voici le code

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <stdlib.h>
 
typedef struct {
	unsigned short *plateau;
	size_t cote;
} t_echiquier;
 
unsigned short valideDroite(t_echiquier *e, unsigned short l, unsigned short c, char sens) {
	unsigned short i;
	for (i=0; i < e->cote; i++) {
		switch (sens) {
			case 'c': // Colonne
				if (i == c) continue;
				if (e->plateau[l*e->cote + i] != 0) return 0;
				break;
			case 'l': // Ligne
				if (i == l) continue;
				if (e->plateau[i*e->cote + c] != 0) return 0;
				break;
			case 'd': // Diagonale
				if (i == 0) continue;
				if ((short)(l - i) >= 0 && (short)(c - i) >= 0 && e->plateau[(l-i)*e->cote + (c-i)] != 0) return 0;
				if ((short)(l - i) >= 0 && (short)(c + i) < e->cote && e->plateau[(l-i)*e->cote + (c+i)] != 0) return 0;
				if ((short)(l + i) < e->cote && (short)(c - i) >= 0 && e->plateau[(l+i)*e->cote + (c-i)] != 0) return 0;
				if ((short)(l + i) < e->cote && (short)(c + i) < e->cote && e->plateau[(l+i)*e->cote + (c+i)] != 0) return 0;
				break;
			default:
				return 0;
		}
	}
	return 1;
}
 
unsigned short validePosition(t_echiquier *e, unsigned short l, unsigned short c) {
	if (valideDroite(e, l, c, 'l') == 0) return 0;
	if (valideDroite(e, l, c, 'c') == 0) return 0;
	if (valideDroite(e, l, c, 'd') == 0) return 0;
	return 1;
}
 
void afficheEchiquier(t_echiquier *e) {
	unsigned short l;
	unsigned short c;
	for (l=0; l < e->cote; l++) {
		for (c=0; c < e->cote; c++) {
			printf("%c", e->plateau[l*e->cote + c] == 0 ?'.' :'D');
		}
		fputc('\n', stdout);
	}
	fputc('\n', stdout);
}
 
unsigned long placeDame(t_echiquier *e, unsigned short l, unsigned long cpt) {
	unsigned short c;
	for (c=0; c < e->cote; c++) {
		e->plateau[l*e->cote + c]=1;
		if (validePosition(e, l, c) != 0) {
			if (l < (e->cote-1))
				cpt=placeDame(e, l+1, cpt);
			else {
				afficheEchiquier(e);
				cpt++;
			}
		}
		e->plateau[l*e->cote + c]=0;
	}
	return cpt;
}
 
int main(int argc, char *argv[]) {
	t_echiquier e;
	e.cote=atoi(argv[1]);
	e.plateau=calloc(e.cote * e.cote, sizeof(*e.plateau));
	printf("%hu => %lu\n", e.cote, placeDame(&e, 0, 0));
	free(e.plateau);
}

Une fois fait, ça a fonctionné et je me suis amusé à lancer le problème pour 4 cases (la plus petite taille ayant au-moins une solution) jusqu'à 12 cases. Ensuite, j'ai désactivé l'affichage de l'échiquier et ai continué à regarder juste le nombre de solutions. Pour une taille de 14x14 il y en a 365596. Mais ensuite j'ai lancé le truc pour un échiquier de 20x20 et ça fait plus de 3 jours qu'il tourne et j'ai toujours pas le résultat

Envoyé par Balario

C'est vraiment une approche intéressante de passer l'adresse du compteur pour que la variable ne son pas "clonée".

Ben... la variable n'est peut-être pas clonée mais le pointeur qui reçoit son adresse lui il l'est !!!

Moi j'ai préféré l'autre solution qui évite donc d'avoir à créer une variable