Besoin d'aide pour solveur de Sudoku en Backtracking
Bonjour à tous !
Je cherche à créer un jeu de sudoku pour mon projet de fin d'année.
J'ai déjà trois méthodes de résolution à savoir :
- Par inclusion
- Par exclusion
- Par paires exclusives
Je cherche a réaliser ma dernière méthode, celle à choix multiple.
(utilisation d'hypothèse)
On cherche une case avec peu de possibilités, on teste une des possibilité,
on essaye de résoudre la grille
=> ca marche, c'est cool !
=> ca marche pas, on recommence depuis le début.
Ma grille est une grille de [11][10]
1ere ligne : compteurs de colonnes
1ere colonne : compteurs de lignes
11eme ligne : compteurs de régions (bloc 3x3)
La case [0][0] stocke le compteurs de cases remplies.
Un tableau a 3 dimensions me sert pour les possibilités de chaque cases :
plan 1 : chiffre 1 (pour la case x,y => 1 si possible; 0 sinon)
etc...
Le plan 0 comptent le nombre de possibilités par case.
Mon cube : [11][10][10]
Les 1ere ligne et colonne ainsi que la derniere ligne fonctionne comme
pour la grille. Elles ne sont pas utilisées pour le plan 0
et la case [0][0] est aussi inutile.
Si quelqu'un pouvait me mettre sur la voie, je lui en serait très reconnaissant...
Je travaille depuis un nombre d'heure assez impressionnant d'heures dessus.
Mes tests n'ont pas été très concluants.
J'ai aussi essayé avec un tutoriel sur le backtracking mais ça n'a pas marché...
voila mon code :
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
|
int methode5(Grille grille, int position)
{ int k;
if (position == 9*9)
return VRAI;
int i = position/9+1, j = position%9+1;
if (grille[i][j] != 0)
return methode5(grille, position+1);
for (k=1; k <= 9; k++)
{
if (absentLigne(k,grille,i) && absentColonne(k,grille,j) && absentRegion(k,grille,i,j))
{
grille[i][j] = k;
if ( methode5(grille, position+1) )
return VRAI;
}
}
grille[i][j] = 0;
return FAUX;
} |
Mes fonctions absentLigne, absentColonne et absentRegion :
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
|
// VERIFIE SI UN NOMBRE EXISTE DANS UNE LIGNE
int absentLigne(int k, Grille g, int i)
{ int j;
for(j=1;j<=MAX;j++)
{ if(g[i][j]==k)
{ return FAUX; }
}
return VRAI;
}
// VERIFIE SI UN NOMBRE EXISTE DANS UNE COLONNE
int absentColonne(int k, Grille g, int j)
{ int i;
for(i=1;i<=MAX;i++)
{ if(g[i][j]==k)
{ return FAUX; }
}
return VRAI;
}
// VERIFIE SI UN NOMBRE EXISTE DANS UNE REGION
int absentRegion(int k, Grille g, int i, int j)
{
int ideb = i-(i%3)+1, jdeb = j-(j%3)+1;
for (i=ideb; i < ideb+3; i++)
{ for (j=jdeb; j < jdeb+3; j++)
{ if (g[i][j] == k)
{ return FAUX; }
}
}
return VRAI;
} |
Si quelqu'un y voit une erreur, merci de la signaler :(
