une ptite aide :s - Page 1

bonjour, j'ai un projet en C, je doit programmer un Sudoku, et j'ai vraiment besoin le plus vite possible, svp.
j'ai besoin de faire un tableau de 2 dimensions, contenant 9 ligne, et 9 colonnes.
je doit remplir ce tableau par des nombres aléatoires, en condition qu'un chiffre ne soit pas présent 2 fois dans la meme ligne, ni dans la meme colonne, ni dans un sous carré.
Est possible de m'aider ??
merci d'avance

probablement que oui, si tu précises un peu sur quoi tu veux de l'aide; pour l'instant ton post laisse supposer que tu veux que quelqun fasse tout à ta place et... enfin voilà quoi

si c possible ...
sa fait plus de 2 semaine que j'essai et pas de résultats. je doit termnier ce soir, et je n'est pas réussi.

Explique ce que tu as fait, alors. Ça n'est pas grave si ça ne ressemble pas à grand chose

ce que j'ai fait, c'est une fonction qui vérifie si le chiffre x est possible pour une case X. x ne doit pas etre présent 2 fois dans la meme ligne ni la meme colonne, ni dans le meme sous carré.
cette fonction va construire un tablea de possibilités de 2 dimensions, 81 lignes, et 9 colonnes. les colonnes sont de 1 jusq'à 9. la ligne du tableau vau le numero de la case du jeu initial, par exemple la case (0,0) de la grille du jeu possède le numero de ligne 0 dans le tableau de possibilté. case (0,1) correspond à 1 et inci de suite.
les cases du tableau de possibilités vont 0 si l'indice de colonne n'est pas valide pour la case de la grille ayant l'indice de ligne de possibilté, et 1 s'il est valide.
maintenant ce que je veut, c'est de faire une grille complète, remplie aléatoirement, de 1 jusq'à 9, suivant les conditions de validité du chiffre bien sur. et à partir de cette grille je vais générer une grille "masquée" pour jouer.
comme ca j'ai la solution, et le jeu.

Oui, en gros, tu veux qu'on te fasse tout.

Tiens, voilà pour commencer :

Yoshi Noir: tu fais vraiment chier en fait, toujours a rembarrer tout le monde. tu te crois meilleurs ? c'est pour ca que tu prends le droit de faire ca ?

dark_angelo: Beh pkoi tu essayes pas tant que tes contraintes ne sont pas satisfaites ?
somme des chiffres dans les blocs = somme des chiffres dans une ligne = somme des chiffres dans une colonne = 45

ca me parrait excellent. merci bien nEUrOO.

Hum... c'est pas excellent, pke c'est basiquement du brute force.
Tu peux trouver des trucs bien moins cons que ca...

nEUrOO (./7) :
dark_angelo: Beh pkoi tu essayes pas tant que tes contraintes ne sont pas satisfaites ?
somme des chiffres dans les blocs = somme des chiffres dans une ligne = somme des chiffres dans une colonne = 45

attention, c'est une condition nécessaire, mais il faut bien voir que ça ne suffit pas : 1 2 3 4 5 6 7 8 9 et 5 5 5 5 5 5 5 5 5 ont tous deux pour somme 45

nEUrOO (./9) :
Hum... c'est pas excellent, pke c'est basiquement du brute force.
Tu peux trouver des trucs bien moins cons que ca...

ah oui le brute force ça risque pas de marcher très bien, 9^81 ça fait un peu bcp
ce qu'on peut faire, c'est pas regénérer TOUTE la grille à chaque fois, c'est générer un début de grille, essayer de rajouter un chiffre, si ça marche pas le changer et sinon continuer -- si ça marche qd on continue, tant mieux, sinon ben on change le chiffre qu'on avait rajouté et ainsi de suite ^^

Yoshi Noir: même remarque, et même en rouge si tu trouves que c'est plus parlant...

sinon y'a une autre solution, c'est de commencer avec une grille valide (tu en choisis une quelconque, peu importe), et d'inverser deux à deux des lignes et/ou des colonnes, un certain nombre de fois, puisque ça ne rendra pas la grille invalide mais que ça mélangera quand même les chiffres.

Pollux (./10) :
attention, c'est une condition nécessaire, mais il faut bien voir que ça ne suffit pas : 1 2 3 4 5 6 7 8 9 et 5 5 5 5 5 5 5 5 5 ont tous deux pour somme 45

Jamais dit que ct une solution suffisante
Je pensais d'ailleurs rajouter ca et le fait que le sudoku doit etre faisable (je sias plus trop comment ca s'appelle ca par contre, tu dois pas avoir de choix possible en fait)

Zephyr>
ça par contre c'est Mal : tu n'auras qu'un type très très spécifique de grille, elle ne sera pas du tout aléatoire... menfin qqun qui jettera un coup d'oeil vite fait à ton programme n'y verra sans doute que du feu

vi je sais bien que c'est Mal (par contre c'est aléatoire, l'univers est juste plus réduit ^^), mais bon il a qu'une journée... ça peut être une solution ^^

nEUrOO (./13) :
Jamais dit que ct une solution suffisante

j'ai jamais dit que tu l'avais dit, je précise juste pour que ça soit clair ^^

Je pensais d'ailleurs rajouter ca et le fait que le sudoku doit etre faisable (je sias plus trop comment ca s'appelle ca par contre, tu dois pas avoir de choix possible en fait)

unicité de la solution ? ça c'est pour la 2è phase, qd tu commences à masquer les cases, mais on en est p-ê pas encore là...

mais la je parlais d'une condition suffisante pour avoir un vrai sudoku ^^
j'ai pas dit qu'on etait dans cette phase la

mais j'ai pas dit que t'avais dit qu'on était dans cette phase-là

En meme temps générer une grille avec un bruteforce, c'est pas plus simple ? (a coder je parle^^)

generalement si, mais il peut y avoir des bien meilleures solutions qui ne sont pas specialement plus difficiles a programmer...
#HS#de toute facon, le plus important c la structure de donnees#HS#

Hum une autre solution "originale" ;
Je fais ça n fois (n=nombre de lignes) :

Je fais une liste contenant 1;2;3;4;5;6;7;8;9 à l'aide de pointeurs,

Tant que tant que liste != Null
Je tire aléatoirement un nombre entre 0 et sizeof(liste)
Je parcours la liste et retire l'élément obtenu (en réaffectant le pointeur [suivant] de l'élément principal à la valeur du [suivant] courant)


Bon question optimisation, c'est pas terrible je pense, mais ça a le mérite d'être original et pas brute force

en gros tu veux faire du bruteforce sur une grille dont les lignes sont des permutations au lieu d'une grille totalement quelconque ? c'est déjà une première optimisation, mais ça doit rester pas mal coûteux qd même...

moi ce que je propose c'est vraiment tout simple : j'ai pas envie d'écrire le code parce que ma religion me l'interdit, mais conceptuellement on prend l'arbre des grilles partielles remplies dans un certain ordre (avec feuille = grille entièrement remplie), et on fait un parcours en profondeur en zappant les sous-arbres où on détecte une collision, jusqu'à atteindre une feuille

Pollux > tu parles à Yoshi Rose, j'imagine ? (non parce que moi je ne fais pas de permutations, juste de l'éjection ^^)

non je parle à toi ^^ (bouh, yoshi jaune est déjà pris )

j'ai p-ê mal compris, mais pour moi

Tant que tant que liste != Null
Je tire aléatoirement un nombre entre 0 et sizeof(liste) Je parcours la liste et retire l'élément obtenu (en réaffectant le pointeur [suivant] de l'élément principal à la valeur du [suivant] courant)

ça génère bien une permutation non ?

Dans un certain sens oui, mais non
En fait je tire au hasard parmi l'ensemble des chiffres que je n'ai pas encore tiré, donc c'est un tirage aléatoire sans remise en jeu de ce qui a déjà été tiré au rang précédent.

Pollux > j'échange contre le violet stu veux

@Boo, Yoshi Bleu, Yoshi Noir, Yoshi Vert, @Yoshi Jaune + 3 inconnu(s)

Yoshi Bleu (./26) :
Dans un certain sens oui, mais non
En fait je tire au hasard parmi l'ensemble des chiffres que je n'ai pas encore tiré, donc c'est un tirage aléatoire sans remise en jeu de ce qui a déjà été tiré au rang précédent.

et ? c'est pas une méthode pour générer une permutation ?