begin process at 2012 05 27 19:04:54
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > RÉSOLUTION DU PROBLÈME DES 8 DAMES

RÉSOLUTION DU PROBLÈME DES 8 DAMES


 Information sur la source

Note :
5 / 10 - par 2 personnes
5,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Classé sous :algorithme, dames, recursif, reines Niveau :Débutant Date de création :24/12/2006 Date de mise à jour :26/12/2006 21:14:16 Vu / téléchargé :11 440 / 1 694
Auteur : The_Void

Ecrire un message privé
Commentaire sur cette source (5)
Ajouter un commentaire et/ou une note

 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

  • #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;
  • } 
#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;
}


 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

24 décembre 2006 22:35:40 :
Executable un peu gros :) (d'ailleurs toujours un peu trop...)
25 décembre 2006 23:37:05 :
Joyeux noël ^^
26 décembre 2006 21:14:16 :
2-3 modifs

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture RÉSOLUTION SUDOKU (9X9) PAR BACKTRACKING RÉCURSIF INTELLIGEN... par Gallien69
GÉRER UN COMBAT DANS UN JEU 2D / ALGORITHME PRIMAIRE D'UNE I... par Chiheb2010
Source avec Zip BELLMAN:LA VALEUR DU PLUS COURT CHEMIN ET LE PLUS COURT CHEM... par Perace
Source avec Zip COMPRESSION / DECOMPRESSION SELON L'ALGORITHME LEMPELZIV 78V par th1man

Commentaires et avis

Commentaire de Arnaud16022 le 26/12/2006 16:19:12

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 )
++

Commentaire de The_Void le 26/12/2006 21:20:24

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

Commentaire de cobol60 le 27/02/2008 16:16:26

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 ...

Commentaire de rim1302 le 08/04/2008 22:07:56

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

Commentaire de amineagzid le 23/04/2011 18:31:22

Svp j'ai besoin de plus d'explication concernant le code source et Merci .

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Algorithme d'un jeu de dames simplifié [ par PRUNE87 ] Bonjour, Je recherche l'algorithme (programme principal + fonction/procédure d'un jeu de dames simplifié dont voici la règle: "L'ordinateur demande algorithme de Huffman [ par amazyo ] Bonjour, SVP je cherche depuis une semaine 'Algorithme de HUFFMAN mais pour l'instant j'ai rien trouvé, s ke vous pouvez m'aider. je vous remercie d' Triangle de Pascal [ par choucroutes ] bonjour je débute en algorithme serait t il possible de m apporter quelque information sur cet exercice merci.< je cherche un algorithme de l'indexation d'un texte [ par baster200x ] bonjour tout le monde, ben je cherche un algorithme qui fait l'indexation d'un texte par la méthode de "sac de mots".c-à-d : l'algorithme doit fournir algorithme et morphologie [ par dadou846 ] bonçoir à tous :j'ai une image en niveau de gris et je dois appliquer les opérateurs de la morphologie mais j'arrive pas a commencer,j'ai pas trouvé s a propos d'algorithme de booth [ par zakaryaej8 ] zakaryaej8   bonjour monsieurs,j'ai besoin de votre aide, j'aimrais bien si vous pouvez m'informer sur les étepes l'algorithme aprori de generation des itemes frequents [ par arab10 ] salut, je cherche le code source de l'algorithme apriori, si quelqu'un peut m'aidre je serai tres reconnaissant.merci d'avance. aidééé moiii svp [ par zakaryaej8 ] zakaryaej8salut tout le monde; qui peut m'aidé  à écrire cet algorithme en langague C svp , je vous jure que c'est important pour moi. merçi algorithm code c , c++ en algorithme genetique pour optimiser une fonction non lineaire [ par dandee2 ] bonjour ,  ou  est ce que je peux trouver en language c++ un code source en algorithme genetique pour optimiser la fonction  :F(x,y,z)=x4.y4.z4-y4.z+e


Nos sponsors


Sondage...

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,515 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)