Résolution du problème des 8 dames

Télécharger le projet
Commenter

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;
}
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.