Projet résolution de Sudoku !

Version imprimable

02/12/2009, 16h50
Lenou

1 pièce(s) jointe(s)

Projet résolution de Sudoku !

Bonjour,
Voila le sujet de mon projet.

Le jeu prend la forme d’une grille de taille 9×9 composee de 9 sous-grilles de 3×3, appelees « regions ». Quelques cases contiennent des chiffres, elles sont dites ”devoilees”. Le but est de remplir les cases vides (c’est a dire de les ”devoiler”). La contrainte `a satisfaire est la suivante : chaque case doit contenir un chiffre, de telle sorte que chaque ligne, chaque colonne et chaque
region contiennent chacune un seul chiffre allant de 1 a 9. Un sudoku n’admet qu’une seule solution.
Exemple :
0 8 7 0 0 0 5 2 0
9 1 0 5 0 2 0 4 6
2 0 0 0 0 0 0 0 7
0 9 0 0 2 0 0 1 0
0 0 0 1 0 6 0 0 0
0 4 0 0 9 0 0 8 0
6 0 0 0 0 0 0 0 3
5 7 0 3 0 1 0 6 8
0 3 8 0 0 0 9 5 0
Les cases non devoilees sont `a 0. Les lignes, colonnes et regions sont numerotees de 0 `a 8.

Methode de resolution : implementation de diverses regles
Pour chaque case non devoilee les candidats sont les chiffres 1, 2, 3, 4, 5, 6, 7, 8, 9.

Certaines regles permettent une determination directe du contenu d’une case non devoilee (R2 candidats seuls, R3 candidats uniques) tandis que d’autres permettent seulement de diminuer le nombre de candidats de certaines cases (R1, R4 considerations interregions).

Regle R1
Une seule occurrence de chaque chiffre dans chaque groupe : Un candidat
à une case ne peut etre qu’un chiffre non encore placé dans un groupe (ligne, colonne et region) qui contient cette case.

Regle R2Candidats seuls
S’il n’y a qu’un candidat `a une case, alors c’est cette valeur qu’il
faut placer dans la case.

L’application de ces deux seules regles est suffisante pour resoudre des sudokus faciles mais, en general, elles ne suffisent pas. Il peut intervenir d'autres regles

R3 Candidats uniques
Un candidat n’apparaissant que pour une seule case d’un groupe peut etre place dans la case correspondante.

(CF Sujet en piece jointe pour plus d'info.
02/12/2009, 16h54
SofEvans

Ce sujet est proposé mainte fois, les source sur "votre contribution" en C ne manque pas.

De plus, il s'agit d'un forum d'entraide : il n'est pas question de nous balancer ton sujet dans l'espoir que l'un de nous le fasse.

Voici mon code pour le début de projet, J'ai fait les règles 1 et 2 et je pense que ça marche. Par contre mon problème se pose sur 2points:
- Comment je dois faire pour initialiser ma grille
- Je ne sais pas du tout comment faire pour la regle R3.

Je souhaiterai, si éventuellement c'est possible, que l'on m'aide et que l'on m'explique !

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
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
145
146
147
148
149
150
151
152
153
154
155
 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define TAILLE 9
 
/* Definition d'un nouveau type cellule */
typedef struct
{
    int valeur ;
    int candidat[TAILLE];
}T_Cellule;
 
/* Remplir une grille manuellement */
void saisirGrille(T_Cellule grille[TAILLE][TAILLE])
{
    int i,j;
    for (i=0;i<TAILLE;i++)
    {
	    for (j=0;j<TAILLE;j++)
	    {
	      printf("Saisissez une valeur comprise entre 0 et 9 :\n");
	      scanf("%d",&(grille[i][j].valeur));
   	    }
    }
}
 
/* Afficher la grille saisie avec mise en page */
void afficherGrille(T_Cellule grille[TAILLE][TAILLE])
{
    int i,j;
    for (i=0;i<TAILLE;i++)
    {
	for (j=0;j<TAILLE;j++)
	{
	  printf("%d ",(grille[i][j].valeur));
	    if (j==(TAILLE-1))
		printf("\n");
	}
    }
}
 
/* Recherche d'une valeur v dans un tableau t de n entiers 
   AI 0<=I<N -> (AJ (0<=I<N and J!=I)-> T[I]!=T[J])
   recherche(T,N,V,i)
   ((EI (0<=I<N) and T[I]=V)-> i=I) and ((AI (0<=I<N)->T[I]!=V)->i=N) */
int recherche(int t[TAILLE], int n, int v)
{
    int i;
    for(i=0 ; i<n ; i++)
    {
        if(t[i] == v) 
           return i;
    }    
    return n;
}
 
/* Initialisation d'une cellule c 
void initialiserCellule(T_Cellule c)
{
  int i;
  for (i=0;i<TAILLE;i++)
  {
    c.valeur=0;
  }
} */
 
/* Cherche le chiffre x dans la ligne l de la grille, retourne vrai si prÃ©sent */
bool NumLigne(T_Cellule grille[TAILLE][TAILLE], int x, int l)
{
  int i;
  bool resultat=false;
  for (i=0;i<TAILLE;i++)
  {
    if(grille[l][i].valeur==x)
    {
      resultat=true;
      break;
    }
  }
  return resultat;
}
 
/* Cherche le chiffre x dans la colonne c de la grille, retourne vrai si present */
bool NumColonne(T_Cellule grille[TAILLE][TAILLE], int x, int c)
{
  int j;
  bool resultat=false;
  for (j=0;j<TAILLE;j++)
  {
    if(grille[j][c].valeur==x)
    {
      resultat=true;
      break;
    }
  }
  return resultat;
}
 
/* Cherche le chiffre x dans la rÃ©gion de coordonnÃ©es(c1,c2) de la grille, retourne vrai si prÃ©sent */
bool NumRegion(T_Cellule grille[TAILLE][TAILLE],int x, int l,int c)
{
    int i,j,c1,c2;
    bool resultat=false;
    c1=3*(l/3);
    c2=3*(l/3);
    for(i=c1;i<(c1+3);i++)
    {
        for(j=c2;j<(c2+3);j++)
        {
            if(grille[i][j].valeur==x)
            {
                resultat=true;
                break;
            }
        }
    }
    return resultat;
}
 
/* Attribue a*une case de la grille, la valeur du seul candidat possible dans celle-ci */    
void CandidatSeul(T_Cellule grille[TAILLE][TAILLE])
{
    int i,j,x;
    for(i=0;i<TAILLE;i++)
    {
        for(j=0;j<TAILLE;j++)
        {
            for(x=1;x<10;x++)
            {
                if(NumLigne(grille,x,i) || NumColonne(grille,x,j) || NumRegion(grille,x,i,j))
                {
                    grille[i][j].candidat[x-1] = 0;
                }
            }
        }
    }
}
 
/* R3 */
 
 
 
int main ()
{
    T_Cellule grille[TAILLE][TAILLE];
    saisirGrille(grille);
    afficherGrille(grille);
 
    printf("Cherche la valeur 9 dans la ligne 3 : %d\n",NumLigne(grille,9,3));
    //printf("Cherche la valeur 7 dans la colonne 4 : %d\n",NumColonne(grille,7,4));
    printf("Cherche la valeur 5 dans la region (7,1) ": %d\n",NumRegion(grille,5,7,1));
    return 0;
}