Faire un sudoku

Salut a tous. Je me présente : lauri ^^

Si je me permets de venir vous ennuyer aujourd'hui, c'est que j'ai un gros problème…

Étant une bille en C, à vrai dire une néophite, J'ai ete selectionner pour faire la piscine d'aout de l'ecole 42 sur paris.
Je me rend compte que c'est tres dur, que je n'arrive plus a suivre. Quand d'autre avance a grand pas, moi, j'en suis toujours au jour 03, c'est a dire le debut du C..
Pour ce soir nous devons rendre un sujet concernant un sudoku. Pour dire la verite je m'en sent incapable.. j'ai essayer de trouver les reponses sur le net, mais rien ne collais a la norme imposer par l'ecole 42.
Je cumule les sales notes, poutant j'ai envie d'etre prise, je m'en remet donc a vous.
Sauriez vous m'aider svp?
Sacahnt que leurs norme ne tolere pas les bol, les for, les raz etc. En gros il faut des if, des write, des while etc..
Je vous laisse mon skype si ca vous arrange pour me joindre: atiriya_kiyox



le sujet :
Chapitre III
Sujet
Exercice : 00
colle-1
Dossier de rendu : ex00/
Fichiers à rendre : Tous les fichiers necessaires
Fonctions Autorisées : write, malloc, free
Remarques : n/a
• Votre code source sera compilé par la commande : gcc -Wall -Wextra -Werror
-o colle-1 *.c
• Votre dossier de rendu devra contenir tout ce qui sera nécessaire à la compilation
de votre programme.
• Vous devez réaliser un programme qui résout un sudoku.
• Un sudoku valide posséde une seule solution unique.
• Ce programme aura pour synopsis :
> ./colle-1 ligne0 ligne1 ligne2 ligne3 ligne4 ligne5 ligne6 ligne7 ligne8
• LigneN est une suite de caractere qui peuvent prendre une valeur entre ’1’ et ’9’ ou
’.’ si la case est vide.
• Vous devrez afficher en sortie le sudoku résolut comme suit
>./sudoku "9...7...." "2...9..53" ".6..124.." "84...1.9." "5.....8.." ".31..4..." "..37..68."
".9..5.741" "47......." | cat -e
9 1 4 3 7 5 2 6 8$
2 8 7 4 9 6 1 5 3$
3 6 5 8 1 2 4 7 9$
8 4 6 5 2 1 3 9 7$
5 2 9 6 3 7 8 1 4$
7 3 1 9 8 4 5 2 6$
1 5 3 7 4 9 6 8 2$
6 9 8 2 5 3 7 4 1$
4 7 2 1 6 8 9 3 5$
>

• En cas d’erreur vous écrirez seulement "Erreur" suivi d’un retour à la ligne.

Salut,

Je ne savais pas qu'il y avait une sorte de "sélection" en août pour 42. Honnêtement, si tu es débutante en programmation (que tu n'en as jamais fait auparavant), écrire un programme résolvant un sudoku (le 3ème jour en plus ??) est à la limite de l'impossible.

J'avais regardé leur programme et ça me semble vraiment trop optimiste, il y a des cours a 3 ects qui couvrent énormément de notions. Alors soit ils vont revoir leur prétentions à la baisse, soit ils ne vont couvrir les sujets qu'en superficie.

Ceci étant dit, je veux bien t'aider à écrire ce programme mais je ne le ferai pas à ta place (sachant que ça n'a jamais aidé personne). À mon avis, le mieux est que tu décomposes le problème en plusieurs étapes, tout d'abord écrit simplement un programme qui écrit le sudoku tel quelle sur la sortie standard (après l'avoir lu).

Je t'ajoute sur skype si jamais tu as des questions "à chaud" mais n'hésite pas à aller demander de l'aide sur le chat et à répondre ici pour que d'autres personnes puissent te corriger et voir ton avancement.

Tu peu aussi te former gratuitement avec les tutoriels et cours de formation au langage C : http://c.developpez.com/cours/

@Trademark : nonon ils ne changeront rien du programme ET couvriront tout... :P

@eaglegeek : c'est très difficile, et leur but est "en effet" de ne sélectionner que les strictement "meilleurs" des meilleurs.

C'est justement le "but" de 42.... mais ça n'est pas le sujet


Pour ton problème :
Arrives-tu à parser la ligne en entrée ?
Pour te permettre d'avancer, fais des essais avec printf pour voir le contenu des variables (et n'oublie surtout pas de les retirer quand ça fonctionne !).
1) Pour commencer, essaye de lire le tableau "argv" jusqu'à sa taille max qui est "argc".
2) Une fois que tu arrives à lire ces valeurs, elles sont sous formes de "char", il te suffira d'une toute petite fonction pour en faire des int (utile pour les opérations si tu veux en faire).
3) Représente chaque ligne par un tableau de 9 int ! De 1 à 9, tu auras tes valeurs, 0 représentera un point.
4) fais un tableau de 9 "tableaux d'int".
Tu peux maintenant travailler avec !
5) Commence déjà la fonction qui "imprime" ton tableau de tableaux d'int.

La norme que 42 t'impose est déjà en place dans 2 autres écoles, et je t'assure que tout est réalisable.
Pour la norme avec les espacements, emacs fournit de base une indentation pas mal (TAB alignera correctement, Alt + i fera les tabulations importantes entre les noms des fonctions et variables).
Pour les mots réservés, c'est facile : dès qu'emacs t'affiche un mot en bleu clair, tu dois faire un espace après.
Bon... ça c'est la norme Epita/tech, mais au vue de l'historique de l'école, ça n'a pas dû trop varier sur ces points.

C'est tout à fait faisable, et non il ouvrerons tous le programme, après tout Sadirac est l'ancien directeur d'épitech...

Alors, pour ma part, je conseillerait l’approche suivante (bon, pour l'algorithme, je pense qu'on est d'accord que le plus simple, c'est du "brut force", et les optimisation par la suite si il lui reste du temps.)

1) Je conseillerais de stoquer le tableau sous la forme d'un char**, ou la première coordonnée est une ligne, et la seconde une colonne, et où l'on stocke pas des nombre mais des caractères. (Attention à bien faire la différence entre le nombre char c = 42; et le caractère '*'. Donc ne pas confondre 0 (= '\0') et '0' (= 48). Cf "man ascii").


L'avantage, c'est que tu n'a rien a faire, car &argv[1] est déjà ce tableau :D

Ensuite, fait une fonction d'affichage qui prend un char** et affiche le
tableau (tu peux afficher chaque ligne en fesant un printf de tableau[i]).

2) Bon, maintenant il te faux absolument une fonction qui prend ton tableau, et renvoi 1 si le tableau est un sudoku valide, 0 sinon.
Un sudoku est valide si :
Chaque ligne ne contient qu'un seul '1', qu'un seul '2', etc...
Chaque colonne ne contient qu'un seul '1', qu'un seul '2', etc..
Chaque block 3*3 ne contient qu'un seul '1', qu'un seul '2', etc...

N'hésite pas à appeler ton programme avec des sudoku déjà remplis, qui soit valide et non valide, histoire de vérifier que ta fonction fonctionne.

3) Bien, une fois ton afficheur de sudoku en main, il est temps de le résoudre.

Voici, en français un trais mauvais algorithme, mais facile à implémenter, sur le quel tu pourras peut-être ajouter des optimisations :

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

fonction resoudre_tableau (tableau) :   Tant que tu peux trouver une case du tableau qui contient un '.' (a la position (i, j) ) : Tu remplace la valeur en i,j par un '1', et tu appelle resoudre_tableau sur le tableau modifier. Si resoudre_tableau(tableau) renvoi 1 Tu fait un return 1 pour sortir de cette fonction, et informer que tu a réussi à remplir le tableau. Tu remplace la valeur en i,j par un '2', et tu appelle resoudre_tableau sur le tableau modifier. Si resoudre_tableau(tableau) renvoi 1 Tu fait un return 1 pour sortir de cette fonction, et informer que tu a . . . . Tu remplace la valeur en i,j par un '9', et tu appelle resoudre_tableau sur le tableau modifier. Si resoudre_tableau(tableau) renvoi 1 Tu fait un return 1 pour sortir de cette fonction, et informer que tu a     //Si tu arrive ici, c'est que tout le tableau est remplis. Si le tableau est valide, renvoi 1. Sinon, renvoi 0.

---

Cette algo teste TOUTES les combinaisons possibles. C'est long, très long.
Une première optimisation très simple consiste à "élaguer l'arbre des possibilités" en virant tout les tableau partiellement remplis que tu sais invalide. Je te laisse chercher comment faire. Il n'y a besoin que d'ajouter une seul ligne de code ;)

Je sais que c'est difficile, mais il faux garder courage. Essaye de te faire aider par des gens autour de toi, et surtout, ne te laisse pas avoir par la faciliter de copier/coler un code sans le comprendre, c'est la meilleur façon de perdre pied.

Courage, beaucoup d'autres sont passé par là, et on fini par bien s'en sortir ;)

@Zenol, Metalman : Je vais pas lancer un débat sur 42, mais si tu prends l'exemple de eaglegeek, elle n'avait jamais codé de sa vie et 1 semaine après qu'elle ait commencé à coder on lui demande de faire un résolveur de sudoku. Faut pas rêver c'est impossible.

Je prend un cours au hasard dans leur plaquette : "Administration de base de données II", un petit cours de 3 ECTs (en 3ème année). Ils vont soit-disant apprendre :

- DataMining
- Datawarehouse
- SGBD parallèle et répartie

Et encore plein d'autres chose comme le noSQL, les bdd objets, ... Pour les trois que j'ai cité avant, à l'univ il y a un cours pour chaque de 3 ECTs. Alors je veux bien que parfois 3 ECTs ne représente pas la même difficulté partout mais il faut pas pousser. C'est impossible qu'ils voient ces sujets en profondeur ! C'est pour ça que je disais qu'ils étaient optimiste, en plus me parler pas d'Epitech ou quoi, ça fait des années qu'ils ont eu le temps de calibrer leur programme, faut pas oublier qu'ici c'est la première année.

Nicolas Sadirac est l'ancien directeur d'épitech. Quand au programme, il n'est pas apparue par magie, si tu vois ce que je veux dire ;)

Et si, comparé au jeu des "8 reines" de la piscine C, ou la bistromatix, c'est du même acabit.

Je suis d'accord avec Trademark. Suite à vos messages, je suis allé voir le programme de 42 et il me semble impossible de couvrir tout cela proprement. Tout est dans le "proprement", évidemment... Il est possible de survoler brièvement chaque point du programme mais pas de faire un bon cours.

Je suis enseignant-chercheur à l'université et le principe est "1 ECTS = 10h de cours/TD/TP". Bref, 3 ECTS valent à peu près une trentaine d'heures d'enseignement (hors travail personnel). Pour reprendre l'exemple de Trademark, les points du programme du cours "Administration de base de données II" nécessitent presque chacun une trentaine d'heures... Honnêtement, prenez le "Data Mining", personne ne pourra assimiler le principe de l'analyse en composantes principales, l'analyse factorielle, l'analyse des correspondances, la classification, ... en 3 ou 4 heures seulement.

Je ne sais pas comment l'école 42 va mettre en place ses théories pédagogiques mais je crois qu'ils vont devoir réduire les ambitions du programme annoncé car nombreux sont les points importants. Après, je vais attendre de lire les premiers retours des élèves pour me faire une meilleure idée de cette école.

Pour ma part je devais faire un sudoku a la fin de ma première année , et ceci en utilisant la récursivité :aie:
Je pourrai pas conseillé a un débutant de commencé par la, mais c'est la meilleur solution pour résoudre un sudoku a mon avis.