Discussion :

[Balario]

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]

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]

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]

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);
}

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]

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.

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]

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

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

[Balario]

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.

Wow t'as fait un sacré boulot là, je t'admire! J'ai un peu regardé ton code mais je crois de n'avoir pas encore le niveau pour tout comprendre
Pour l'instant je suis passé rapidement sur les structures, il faut que j'approfondisse l'argument...

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

ahahahahha tu me diras si t’arrives à avoir le résultat?
Là j'ai trouvé quelqu'un qui est allé jusqu'à 21: http://www.ic-net.or.jp/home/takaken/e/queen/

[Sve@r]

Wow t'as fait un sacré boulot là, je t'admire! J'ai un peu regardé ton code mais je crois de n'avoir pas encore le niveau pour tout comprendre

La fonction la plus compliquée c'est "valideDroite()" qui valide si une dame est la seule sur sa droite (droite à prendre au sens large c'est à dire aussi bien ligne que colonne que diagonale).
Donc pour vérifier si une ligne ou une colonne est valide je boucle de 0 à 8 et je regarde si aucune autre case de cette ligne/colonne vaut 1. Et pour une diagonale je regarde si aucune des 4 cases qui sont sur les 4 directions diagonales en partant de la dame testée vaut 1 en incrémentant à chaque tour de boucle la distance entre la dame et les 4 cases testées des diagonales.

ahahahahha tu me diras si t’arrives à avoir le résultat?

Ca tourne toujours. Mais vu qu'il y a 39 milliards de solutions je comprends pourquoi. Peut-être que si je modifie ma fonction "valideDroite()" en inversant le switch et la boucle ça ira plus vite (un seul test au lieu de 8). Toutefois vu que je travaille en unsigned long mon compteur ne pourra pas dépasser les 4 milliards.

[edit]C'est fait. j'ai changé ma fonction "valideDroite()" par celle-ci (c'est l'avantage de la programmation modulaire => si un module ne convient pas, on peut le changer facilement sans mettre en péril le fonctionnement du programme).

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
unsigned short valideDroite(t_echiquier *e, unsigned short l, unsigned short c, char sens) {
	unsigned short i;
	switch (sens) {
		case 'c': // Colonne
			for (i=0; i < e->cote; i++)
				if (e->plateau[l*e->cote + i] != 0 && i != c) return 0;
			break;
		case 'l': // Ligne
			for (i=0; i < e->cote; i++)
				if (e->plateau[i*e->cote + c] != 0 && i != l) return 0;
			break;
		case 'd': // Diagonale
			for (i=1; i < e->cote; i++) {
				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;
}

Et je gagne approximativement 20% en temps de résolution (l'optimisation des tests y est sûrement aussi pour quelque chose => au lieu de regarder à chaque tour si je me trouve sur la case de la dame en cours d'évaluation, je ne regarde cet état que si la case contient une dame). Mais ça ne changera rien pour la taille de mon compteur.

Là j'ai trouvé quelqu'un qui est allé jusqu'à 21: http://www.ic-net.or.jp/home/takaken/e/queen/

Hum, lui il utilise une autre approche. Au lieu de tester toutes les positions, il ne teste que les positions valides qu'il permute ou inverse. De plus il gère les cases en utilisant les bits (un bit par case donc 16 cases par int). Evidemment son algo est clairement plus rapide que le mien. C'est peut-être pour ça que lui il a la solution. En tout cas j'obtiens les mêmes chiffres que lui jusqu'à 14.

[Balario]

Je m'incline à ton code et tes skills !

J'ai vraiment apprécié le fait que t'as continué à partager avec moi tes progrès et essais.

Merci encore pour tout !