Un grand classique ici : comment placer N dames sur un echiquier de NxN cases, sans qu'il soit possible pour une dame de capturer une autre dame. ( on rappelle qu'un dame peut prendre une autre piece en se deplacant sur un ligne, une colonne ou une diagonale )
Analyse
En C on fait bourrin, mas ca n'empêche pas d'être un peu malin. On voit quand même qu'il faut mettre une seule dame par ligne et une seule par colonne. Ce qui revient une fois de plus à trouver les permutations de N chiffres parmi N. Pour savoir si 2 dames sont sur une même
diagonale, c'est trés simple, la différence entre les lignes et les colonnes
respectives est la même. Et au final, on essaye de montrer le resultat de facon
presque lisible.
Programme
#define N 4
#define CASES "# D"
char r[N];
void dame(int c, int u, int j) {
int i;
if ( c < N ) {
for (i=0; i<c && c-i + (r[i]>j?j-r[i]:r[i]-j) ;i++ );
if ( !(u & (1<<j)) && c==i) r[c] = j, dame(c+1, u| (1<<j), 0);
if ( j != N-1 ) dame(c, u, j+1);
} else {
char p[N+1]; i=0;
while(i<=N) p[i++]=CASES[i%2]; i=0;
while(i<N)
p[r[i]+i%2]=CASES[2],
printf("%0.*s\n",N,p+i%2),
p[r[i++]+i%2]=CASES[(r[i]+i%2)%2];
putchar('\n');
}
}
int main ( void ) { dame(0,0,0); }
Conclusion
Disposer vos dames sur un echequier
n'est pas un drame en langage C
comme d'habitude, la recursion
est avec certitude notre decision.
Voici la solution proposée par Yoshi ( c'est plus long mais plus rapide )
ici
Problème
Analyse
Programme
Conclusion