transformer de l'itératif en récursif

Version imprimable

salu, j'ai un problème avec un programme je fais donc appelle a vos conseils, merci d'avance.

l'éxo:
le but est de placer 8 reines sur un échiquier sans qu'elles ne puissent s'atteindre en un seul coup (l'échiquier est un damier de 8*8 cases) (une reine peut ce deplacer en ligne / colone / diagonale)

voici le code en itératif qui realise cette exercice poru 4 reines sur un damier de 4*4 cases:

Code:

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
 
#include <stdio.h>
 
int jeu_des_reines()
{
    int tab[9];
    tab[1] = 1;    
 
    while (tab[1] < 5)
    {
          tab[2] = 1;
          while (tab[2] < 5)
          {
                if ((tab[2] != tab[1]) && (tab[2] != tab[1]+1) && (tab[2] != tab[1]-1))
                {
                       tab[3] = 1;
                       while (tab[3] < 5)
                       {
                             if ((tab[3] != tab[1]) && (tab[3] != tab[2]) && (tab[3] != tab[1]+2) && (tab[3] != tab[1]-2) && (tab[3] != tab[2]+1) && (tab[3] != tab[2]-1))
                             {
                                     tab[4] = 1;
                                     while (tab[4] < 5)
                                     {
                                           if ((tab[4] != tab[1]) && (tab[4] != tab[2]) && (tab[4] != tab[3]) && (tab[4] != tab[1]+3) && (tab[4] != tab[1]-3) && (tab[4] != tab[2]+2) && (tab[4] != tab[2]-2) && (tab[4] != tab[3]+1) && (tab[4] != tab[3]-1))
                                           {
                                                       printf("%d", tab[1]);
                                                       printf("%d", tab[2]);
                                                       printf("%d", tab[3]);
                                                       printf("%d", tab[4]);
                                                       printf("\n");
                                           }
                                           tab[4]++;
                                     }
                             }
                             tab[3]++;
                       }
                }
                tab[2]++;
          }
          tab[1]++;
    }
}
 
int main()
{
    jeu_des_reines();
    return (0);
}

comme vous le voyez les conditions des if sont assez monstrueuses :( comment est il possible de transformer ce code pour utiliser la recursivitée svp

27/11/2005, 18h24
sorry60

Tu devrais plutot aller voir du coté du forum d'algo :?
27/11/2005, 18h59
hiina

j'ai été voir en section algo (notament le poste persistant sur la recursivité), mais étant débutant en programmation je m'embrouille en lisant les codes en algo.
le seul langage que je comprend un peu c'est le C c'est pourquoi j'ai poster ici :roll:
27/11/2005, 19h52
semaj_james
Citation:

l'éxo:
le but est de placer 8 reines sur un échiquier sans qu'elles ne puissent s'atteindre en un seul coup (l'échiquier est un damier de 8*8 cases) (une reine peut ce deplacer en ligne / colone / diagonale)

voici le code en itératif qui realise cette exercice poru 4 reines sur un damier de 4*4 cases:

ton programme donne çà:
Code:

1 2 2 4 1 3 3 1 4 2
çà represente quoi ? la 1ere reine se trouve sur 2 3 ou sur 2 4 ?
27/11/2005, 20h01
hiina
Code:

1 2 3 2 4 1 3 3 1 4 2
représente les position des reines il y a 2 lignes donc 2 solution:

0: emplacement vide
X: reine

pour: 2 4 1 3

0 0 X 0
X 0 0 0
0 0 0 X
0 X 0 0

pour: 3 1 4 2

0 X 0 0
0 0 0 X
X 0 0 0
0 0 X 0

L'exo des 8 reines est un des exos d'algo les plus repandus sur le net....

Il y a 92 solutions differentes... Comme ca deja tu pourras savoir si c'est juste ou pas.

Le principe de l'algo recursif est le suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int 8_reines(int nb_de_solutions, echiquier, numero de ligne) { pour (chacune des 8 cases de la ligne): si (tu peux placer une reine sur une case) { tu la places; nb_de_solutions += (la meme fonction, une ligne plus bas) } si (tu es a la derniere ligne et que tu reussi a placer une reine) retourne (1); si (tu n'as pu placer aucune reine sur ta ligne) retourne (0); }
dans ton main():

tu crees un tableau de 64 ou de 8*8 (plus facile a comprendre) ou meme un tableau de 8 ou le contenu de la case indique le numero de la colonne ou est situee la reine.

tu appelles : 8_reines(0, echiquier, 0)

Ce n'est peut etre pas la meilleure solution, mais elle marche.
Bonne chance !

27/11/2005, 21h03
granquet

a ta place je ferait:

stocker la position de chaque reine dans une structure de 2 entiers pos{int x, int y}
ou x et y representent les lignes//colonnes.
tu declare un tableau de struct de 8 elements - 1 position par reine.
ensuite, tu n'as plus qu'a jouer avec tes boucles pour tester si 2 reines sont sur la meme ligne ou la meme colonne (if reine[i].x == reine[j].x alors les reines i et j sont sur la meme ligne)
pour la diagonale, il faut un peu reflechir ...
27/11/2005, 21h08
semaj_james

Pour des explications sur le recursif tu peux aller voir ici

il y a ton probleme en exemple
27/11/2005, 21h16
hiina

merci a tout le monde pour ces reponses :)