Le backtraking pour une grosse grille de 8 reines

**Dev 37C** · 13/03/2015, 13h01

Bonjour, je viens de finir de coder un jeu des 8 reines en console.

Pour placer ces reines, j'utilise la backtraking.

Mon code fonctionne, je voudrai juste vos avis pour voir ou je peux l'améliorer

Si vous connaissez d'autres algo pour solder de grosse grille, je veux bien, car 136 seg pour trouver une grille de 30*30 cest beaucoup

.

Merci de votre aide

Au passage, j'aime beaucoup ce site, il est tres complet

Voici mon code, bonne lecture

main.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
************************************************************************************************
Base des 8 reines :
    Positionne 1 reine par ligne, colonne et diagonale.
 
Version 1.0
 
Méthode utilisée :
    Méthode du backTraking (retour sur trace en FR)
 
Crée par Florian P
Le 08/03/2015
************************************************************************************************/
 
#include<stdio.h>
#include<stdlib.h>
#include"grille.h"
#include"placeReine.h"
#include<unistd.h>
 
int main(int argc, char* argv[])
{
	int** grille;
 
	if((grille = creGrille((const unsigned int)TAILLE)) == NULL)
	{
		char erreur[] = "Erreur dans creation grille.\n";
		write(STDERR_FILENO, erreur, sizeof(erreur));
		return EXIT_FAILURE;
	}
 
	placeReine(grille, 0);
 
	afficherGrille((const int**) grille);
 
	freeGrille(grille, TAILLE);
 
	return EXIT_SUCCESS;
}

grille.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include"grille.h"
 
static void		initGrille(int** grille, const unsigned int taille)
{
	int y;
	int x;
 
	y = 0;
 
	while(y < taille)
	{
		x = 0;
 
		while(x < taille)
			grille[y][x++] = INIT;
 
		y++;
	}
 
}
 
int**			creGrille(const unsigned int taille)
{
	int** grille;
 
	grille = NULL;
 
	if((grille = malloc(taille * sizeof(*grille))) == NULL)
		return NULL;
 
	int i;
 
	i = 0;
 
	while(i < taille)
	{
		if((grille[i] = malloc(taille * sizeof(**grille))) == NULL)
		{
			freeGrille(grille, i - 1);
			return NULL;
		}
 
		i++;
	}
 
	initGrille(grille, taille);
 
	return grille;
}
 
void			afficherGrille(const int** grille)
{
	if(grille == NULL)
	{
		char erreur[] = "Grille dans la fonction affichageGrille == NULL";
		write(STDERR_FILENO, erreur, sizeof(erreur));
		exit(EXIT_FAILURE);
	}
 
	int x;
	int y;
	char c;
	char esp;
	char entree;
 
	entree = '\n';
	y = 0;
	esp = ' ';
 
	while(y < TAILLE)
	{
		x = 0;
 
		while(x < TAILLE)
		{
			c = (char) grille[y][x];
			write(STDOUT_FILENO, &c, sizeof(char));
			write(STDOUT_FILENO, &esp, sizeof(char));
 
			x++;
		}
 
		write(STDOUT_FILENO, &entree, sizeof(char));
		y++;
	}
}
 
void			freeGrille(int** grille, unsigned int taille)
{
	while(--taille <= 0)
	{
		free(grille[taille]);
		grille[taille++] = NULL;
	}
 
	free(grille);
	grille = NULL;
}

grille.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef GRILLE
 
#define GRILLE
 
#include<stdlib.h>
#include<unistd.h>
 
#define TAILLE 10
 
#define INIT '.'
 
int**			creGrille(const unsigned int taille);
void			afficherGrille(const int** grille);
void			freeGrille(int** grille, unsigned int taille);
 
#endif

placeReine.c

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include"placeReine.h"
#include"grille.h"
 
static int nbReine = 0;
 
static int      valDroiteBas(const int position)
{
    int droiteBas;
 
    if(TAILLE % 2 == 1)// Taille impaire
    {
        droiteBas = ((position - (position % TAILLE) + TAILLE - 1) - position) * TAILLE + position + 1 * (position - (position % TAILLE) + TAILLE - 1) - position;
        if(droiteBas > TAILLE * TAILLE)
            droiteBas = TAILLE * TAILLE - 1 - ((position - (position % TAILLE)) / TAILLE) + (position % TAILLE);
    }
    else
    {
        droiteBas = ((position - position % TAILLE) + TAILLE - 1) + (((position - position % TAILLE + TAILLE - 1) - position) * TAILLE);
        if(droiteBas >= TAILLE * TAILLE)
            droiteBas = ((TAILLE * (TAILLE - 1) - (position - position % TAILLE)) / TAILLE) + position + (((TAILLE * (TAILLE - 1) -(position - position % TAILLE)) / TAILLE) * TAILLE);
    }
 
    return droiteBas;
}
 
static int      valGaucheBas(const int position)
{
    int  gaucheBas;
 
    if(TAILLE % 2 == 1)// Taille impaire
    {
        gaucheBas = (position - (position - position % TAILLE)) * TAILLE + (position - position % TAILLE);
        if(gaucheBas > TAILLE * TAILLE - TAILLE)
            gaucheBas = TAILLE * TAILLE - position - (TAILLE * TAILLE - position) % TAILLE + position - ((TAILLE * TAILLE - position - (TAILLE * TAILLE - position) % TAILLE) / TAILLE);
    }
    else
    {
        gaucheBas = ((TAILLE * (TAILLE - 1) - (position - position % TAILLE)) / TAILLE) * TAILLE + position - ((TAILLE * (TAILLE - 1) - (position - position % TAILLE)) / TAILLE);
        if(gaucheBas < TAILLE * TAILLE - TAILLE)
            gaucheBas = (position - position % TAILLE) + (position - (position - position % TAILLE)) * TAILLE;
    }
 
    return gaucheBas;
}
 
/*static bool		absLigne(const int** grille, const int y)
{
	int x;
 
	x = 0;
 
	while(x < TAILLE)
		if(grille[y][x++] == REINE)
			return 0;
 
	return 1;
}*/
 
static bool		absColonne(const int** grille, const int x)
{
	int y;
 
	y = 0;
 
	while(y < TAILLE)
		if(grille[y++][x] == REINE)
			return 0;
 
	return 1;
}
 
static bool		absD_GaucheBasDroiteHaut(const int** grille, int y, int x)
{
	while(y >= 0 && x < TAILLE)
        	if(grille[y--][x++] == REINE)
           		 return 0;
 
	return 1;
}
 
static bool		absD_DroiteBasGaucheHaut(const int** grille, int y, int x)
{
	while(y >= 0 && x >= 0)
		if(grille[y--][x--] == REINE)
			return 0;
	return 1;
}
 
static bool     absDiagonale(const int** grille, const int position)
{
	int droiteBas;
	int gaucheBas;
 
	gaucheBas = valGaucheBas(position);
	droiteBas = valDroiteBas(position);
 
	if(!(absD_GaucheBasDroiteHaut((const int**)grille, gaucheBas / TAILLE, gaucheBas % TAILLE)))
		return 0;
	if(!(absD_DroiteBasGaucheHaut((const int**)grille, droiteBas / TAILLE, droiteBas % TAILLE)))
		return 0;
 
	return 1;
}
 
bool			placeReine(int** grille, const unsigned int position)
// fonction récursive pour placer les reines dans grille
{
	int y;
	int x;
 
 
	if(nbReine >= TAILLE)										            //si les reines ont été placées
		return 1;
	if(position >= TAILLE * TAILLE)								            //si position est en dehors du tableau
		return 0;
 
	y = position / TAILLE;
	x = position % TAILLE;
 
	while(x < TAILLE)				 						                //teste la ligne y : y0, y1, y2 > yTAILLE-1
	{
        if(absColonne((const int**) grille, x) && absDiagonale((const int**) grille, y * TAILLE + x))
	       	{
			grille[y][x] = REINE;								            //si une reine est placée, on passe a la ligne d'en dessous
			nbReine++;
 
			if(placeReine(grille,(y + 1) * TAILLE) == 1)		            //si la grille après est bonne
				return 1;
 
			grille[y][x] = INIT;
			nbReine--;
		}
 
		x++;
	}
 
	if(y == 0 && x >= TAILLE)
	{
		char erreur[] = "Impossible de placer les rennes\n\n"; 				//si toutes les positions de la ligne on été testées
		write(STDERR_FILENO, erreur, sizeof(erreur));						//c'est fini
	}
 
	return 0;
}

placeReine.h

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#ifndef PLACE_REINE
 
#define PLACE_REINE
 
#include<stdbool.h>
#include<unistd.h>
#include<stdlib.h>
#include<stdio.h>
 
#include"grille.h"
 
#define REINE '0'
 
bool			placeReine(int** grille, const unsigned int position);
 
#endif

Merci

**ternel** · 13/03/2015, 13h25

Premièrement, merci pour le sourire du jour.
Un renne, c'est un caribou, la monarque, c'est une reine

Concrètement, et si au lieu de faire des grilles, tu stockais uniquement les positions des N reines?

Ainsi, au lieu de stocker N² cases par étapes, tu stockes 2N indices, voire N, si tu considères que tu peux numéroter les cases de 0 à N²-1.
En plus, ca te fera un liste chainée de reine, qu'il suffira d'empiler/depiler pour naviguer.

Tu n'auras besoin de ta grille que pour la vérification actuelle, et encore.
deux reines se genent si:

elles sont sur la même ligne,
elles sont sur la même colonne,
le décalage entre leurs colonnes est le même que celui de leurs lignes (une diagonale),
le décalage entre leurs colonnes est l'opposé de celui de leurs lignes (l'autre diagonale)

Il te suffit donc bien d'avoir une structure représentant ces deux coordonnées, ou au moins, permettant de les trouver.
Les cases vides ne t'intéressent pas du tout.

**Dev 37C** · 13/03/2015, 14h19

La honte

je changerai ca correctement ce soir

Le backtraking pour une grosse grille de 8 reines

C

Discussions similaires

Partager

Partager