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 :
Mes fonctions absentLigne, absentColonne et absentRegion :
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 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; }
Si quelqu'un y voit une erreur, merci de la signaler
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 // 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; }
Partager