Akuma84
Messages postés1Date d'inscriptionmardi 5 mai 2009StatutMembreDernière intervention19 mai 2009
-
19 mai 2009 à 23:17
TychoBrahe
Messages postés1309Date d'inscriptionsamedi 31 janvier 2009StatutMembreDernière intervention 5 juin 2013
-
20 mai 2009 à 00:37
Bonjour à tous,
Dans le cadre des mes études, je dois réaliser un projet en c.
Je dois écrire un programme capable de résoudre un sudoku par élimination c'est-à-dire qu'un nombre n'est placé qu'à condition qu'il ne soit pas présent dans le carré, la ligne ou la colonne.
J'ai du mal a établir l'algorithme. Pourriez vous m'aider et m'indiquer quelles bibliothèques utiliser.
TychoBrahe
Messages postés1309Date d'inscriptionsamedi 31 janvier 2009StatutMembreDernière intervention 5 juin 201312 20 mai 2009 à 00:37
Salut,
«J'ai du mal a établir l'algorithme.»
Il y a plein de renseignements a ce sujet sur wikipedia ainsi que sur pas mal d'autres sites web.
En fait ton algo devrais implémenter plusieurs méthodes pour déterminer si une case ne peux contenir qu'un seul élément. Une méthode simple consiste a regarder si sur la ligne, ta case est la seule manquante (idem pour les colones et régions). Bien entendu ceci ne suffis pas, il te faudras en implémenter d'autres pour être efficace.
«Pourriez vous m'aider et m'indiquer quelles bibliothèques utiliser.»
Tu n'as besoin que de la lib standard si tu reste en console.
Quelques petits conseils :
- Tu peux stocker ta grille dans un tableau de char fini (de 81 éléments).
- Code donc des fonctions retournant la valeur des cases voisines (attention a ne pas segfaulter sur les bords).
- Pense a une condition d'arrêt empêchant de partir en boucle infinie dans le cas ou les déterminations que tu effectue ne permettent pas de résoudre la grille intégralement (ou mieux, intégrer un algo de "brute force" qui prend temporairement le relais).