Résolution du problème des 8 dames

5/5 (6 avis)

Vue 26 293 fois - Téléchargée 2 507 fois

Description

Le problème des 8 dames est un bon prétexte pour présenter le principe des algorithmes récursifs ;)

Pour ceux qui ne connaissent pas, le problème est de trouver toutes les solutions différentes de facon à mettre 8 dames sur un jeu d'échequier sans qu'aucune ne puisse se prendre entre elles.

Le principe est le suivant: on appelle une fonction qui place une dame dans chacune des positions libres de la ligne 0, qui s'appelle elle même en se positionnant sur la ligne suivante... jusqu'à ce qu'il n'y ai plus de place libre ou qu'on arrive à la dernière ligne.

Compilation réalisée sous dev-cpp.

Source / Exemple :


#include <conio.h>
#include <stdio.h>

int posDames[8]={0}; // index du tableau=y, valeur=x
int solution=0;

int abs(int n)
{
    return n<0 ? -n : n;
}

void recursive(int nDames) // nDames=ligne en cours et dames restantes
{
    if(nDames==8)
    {
                 for(int i=0; i<8; ++i)
                 {
                 for(int j=0; j<8; ++j)
                 if(j==posDames[i]) printf("1 ");
                 else printf("0 ");
                 printf("\n");
                 }
                 printf("\n\n");
                 ++solution;
                 }
    for(int i=0; i<8; ++i)
    {
    for(int j=0; j<nDames; ++j)
    if(posDames[j]==i || ( abs(posDames[j]-i) == abs(j-nDames)))
    // Si il y a déjà une dame dans la colonne OU 
    // Si il faut se "déplacer" d'autant (en valeur absolue) de cases en x et y pour aller d'une dame 
    // à une autre c'est à dire que les pieces peuvent se prendre en diagonale
    goto next;
    posDames[nDames]=i;
    recursive (nDames+1); // On parcourt la ligne suivante dans l'echequier
    next: continue;
    }
    return;
}
         
    
int main(int argc, char *argv[])
{
        recursive(0);
        printf("\nNombre de solutions: %d\n",solution);
        _getch();
        return 0;
}

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Arnaud16022 Messages postés 1329 Date d'inscription vendredi 15 août 2003 Statut Membre Dernière intervention 16 juin 2010 2
26 déc. 2006 à 16:19
Alors:
pour la taille de l'exec, l'idée est d'enlever les symboles de débug lors de la compilation, tu utilises quel IDE ?
Clock est peu précis, mais bon vu l'utilisation que tu en fais on va dire que c'est pas bein grave :)
Ne pas utiliser system c'est pas portable
Tu devrais expliquer un peu plus le if(posDames[j]==i || ( abs(posDames[j]-i) == abs(j-nDames))) j'ai mis un peu de temps à comprendre ^^

7/10, je pense :) (surtout pour une 1ère source )
++
The_Void Messages postés 4 Date d'inscription dimanche 24 décembre 2006 Statut Membre Dernière intervention 14 janvier 2007
26 déc. 2006 à 21:20
Merci pour ton commentaire :)
J'utilise dev-c++, et aparament j'ai mis toutes les options susceptibles de diminuer la taille...
J'ai essayé de viré l'en tête iostream pour mettre stdio.h et la comme par magie mon exe passe de 260 ko à... 5,5ko!
C'est pas très normal ça, si? ^^

Sinon pour le system tu as raison faut vraiment que je perde l'habitude de l'utiliser lol
cs_cobol60 Messages postés 2 Date d'inscription jeudi 20 septembre 2007 Statut Membre Dernière intervention 27 février 2008
27 févr. 2008 à 16:16
Bonjour, si cela intéresse quelqu'un j'ai écrit un algorithme qui trouve une solution pour n=100 en une dizaine de seconde. L'algorithme n'utilise pas la méthode décrite dans wikipedia :
Il existe un algorithme simple retournant une solution simple pour n dames si n 1 ou n 4:

Diviser n par 12. Se rappeler du reste (c'est 8 pour le problème des huit dames).
Écrire dans l'ordre la liste des nombres pairs de 2 à n.
Si le reste est 3 ou 9, mettre 2 à la fin de la liste.
Écrire dans l'ordre les nombres impairs de 1 à n, mais, si le reste est 8, permuter les deux à deux (ie 3, 1, 7, 5, 11, 9, …).
Si le reste est 2, permuter les places de 1 et 3, puis mettre 5 à la fin de la liste.
Si le reste est 3 ou 9, mettre 1 et 3 à la fin de la liste.
Placer la reine de la première colonne dans la ligne avec le premier nombre de la liste, placer la reine de la seconde colonne dans la ligne avec le deuxième nombre de la liste, etc.

car cet algorithme est trop simple et suppose que l'on connaisse la solution avant d'écrire l'algorithme
De plus il ne fonctionne pas si l'on change légèrement les règles échiquéenne ...
rim1302 Messages postés 1 Date d'inscription vendredi 4 avril 2008 Statut Membre Dernière intervention 8 avril 2008
8 avril 2008 à 22:07
Explique moi stp cette ligne, je n'ai rien compris, et je dois savoir le plus vite possible merci bcp pour votre aide

if(posDames[j]==i || ( abs(posDames[j]-i) == abs(j-nDames)))
amineagzid Messages postés 1 Date d'inscription samedi 23 avril 2011 Statut Membre Dernière intervention 23 avril 2011
23 avril 2011 à 18:31
Svp j'ai besoin de plus d'explication concernant le code source et Merci .

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.