Sudoku - le programme !

par **Flodelarab** » 28 Déc 2007, 01:23

comment un programme peut il te sortir instantanément la solution avec le nombre de possibilités a tester ?

On est justement dans un problème d'optimisation (pour une fois).

Souvent, on donne des conseils de codages alors que c'est inutile. Quelle importance de mettre 10ms ou 15ms pour faire afficher "bonjour toto"?
Mais quand tu répètes des milliards de fois une opération, tout gain sur 1 tour, te fait gagner beaucoup sur l'ensemble car c'est multiplié énormément.

L'opération charnière, ici, est la vérification. Il faut donc un accès direct à cette information. J'ai donc 3 tableaux qui disent directement si un nombre est présent dans la colonne, la ligne, la région. L'élimination est immédiate. Il ne faut pas attendre qu'une fooooooonctiooooooon paaaaarcouuuuuurt toooooon taaaaableauuuuuuuuuu pour découvrir que le dernier chiffre que tu as inséré (et le seul que tu aies inséré!!!!) soit non valide.

Entre des appels à fonctions, des additions, des recopies de données, etc .... et une simple lecture en mémoire, j'ai choisi. Je prends la seconde.

Avec un ordi qui fait plus d'un milliard et demi de cycles à la seconde, et un temps d'exécution de 0,06s, il a mis 90 millions de cycles pour résoudre le sudoku: ça laisse de la place pour faire des choses... et notamment des lectures en mémoire.
J'ajoute que la solution n'est pas forcément la grille la plus lointaine. Quoiqu'ici, il prolonge 1 à 3 dixièmes de secondes quand on fait toutes les grilles possibles. Non significatif.

par **lapras** » 28 Déc 2007, 11:11

J'ai modifié pour la fonction isValid : elle ne vérifie que une ligne et une colonne en faisant quelques petites boucles.
c'est toujours "lent" ! (0.5 sec seconde je pense, mais j'ai pas chronométré)
sinon, qu'appelles tu la "région" ?

par **Flodelarab** » 28 Déc 2007, 21:01

Ben le carré de 9 cases dans lequel il ne faut qu'une occurrence de chaque chiffre.
Je les numérote ainsi:
1 2 3
4 5 6
7 8 9

Une fois que la ligne et la colonne sont fixées, la région est obligatoire. J'ai donc juste fait une fonction qui donne la région en fonction des coordonnées de la case.

par **Dominique Lefebvre** » 29 Déc 2007, 13:28

Bonjour à tous,

Je viens de parcourir ce fil intéressant. Constat : cela n'a rien à voir avec un énigme logique, mathématique ou shadock...
Je déplace la discussion en informatique, messieurs les fous du C++.
Au fait, lapras, en programmation évite donc la récursivité: ça fait bien mais ce n'est pas très efficace!

par **lapras** » 29 Déc 2007, 13:34

Ok c'est mieux en informatique.
Dominique, franchement le sudoku mon ordinateur le fait instantanément avec la récursivité. Pourquoi changer le programme?
Aussi, quelqun peut il m'expliquer les désavantages de la récursivité ?

par **Dominique Lefebvre** » 29 Déc 2007, 14:38

lapras a écrit:Ok c'est mieux en informatique.
Dominique, franchement le sudoku mon ordinateur le fait instantanément avec la récursivité. Pourquoi changer le programme?
Aussi, quelqun peut il m'expliquer les désavantages de la récursivité ?

A propos de la récursion (la récursivité est la propriété, la récursion le concept), je lui trouve un inconvénient gravissime: c'est quasi-impossible à debugger simplement !
Notons tout d'abord que les compilateurs ne travaillent jamais de manière récursive mais de manière itérative.... La suppression de la récursion est d'ailleurs un élément de base des cours d'algo (voir par exemple le cours de R. Sedgewick, il y en a d'autres mais c'est celui que j'ai sous la main...)
Sur le plan technique, les architectures d'ordinateurs ne sont pas conçues pour traiter des fonctions récursives. Les compilateurs sont obligés de faire des pieds et des mains pour traduire ceci en un assembleur jouable sur les processeurs. Et le code généré est bien moins efficace que celui produit à partir d'un algo non récursif. Regarde donc la gestion de la mémoire que requière un algo récursif!

Il n'y a pratiquement aucun problème qui implique obligatoirement l'usage de la récursion. La seule fonction dans laquelle elle est nécessaire c'est le calcul des factorielles, et encore...

A noter aussi, qu'elle est impraticable lorsque tu fais de la programmation parallèle, c'est qui est presque toujours la règle en calcul scientifique.

par **Flodelarab** » 29 Déc 2007, 16:29

Chaque fois que tu appelles une fonction, le point de retour est chargé dans la pile système.

Sans vouloir jouer les vieux combattants, ya 20 ans, j'avais fait un programme récursif (à l'époque je ne savais même pas que c'en était) qui marchait pour des petits tests et quand je faisais tourner le programme entier normalement, BOOM! Dépassement de pile système! La technologie a évolué et avant de dépasser la pile système de nos jours, tu peux y aller ... c'est pour cela que beaucoup ne comprennent pas l'inconvénient aujourd'hui.

Mais c'est vrai que tu monopolises beaucoup de ressources pour faire la même chose qu'une boucle. Entre un pauvre compteur avec un jnz et un appel à fonction récursif, il est clair que le rapport qualité/prix est meilleur pour la boucle en temps(execution)/complexité(debuggage)/ressources(système)

Il faut penser "boucle" et non "récursion".

par **lapras** » 29 Déc 2007, 22:10

Ok dommage j'aimais bien le principe de récursion !
Figure toi que dans un de mes programme récursifs j'ai atteint laprofondeur maximale supportée par mon ordi.
C'est bizarre, mais vers 70 000 de profondeur dans la récursivité mon programme plante...
Bref, je vais essayer de penser "boucle"

par **Dominique Lefebvre** » 29 Déc 2007, 22:18

lapras a écrit:Ok dommage j'aimais bien le principe de récursion !
Figure toi que dans un de mes programme récursifs j'ai atteint laprofondeur maximale supportée par mon ordi.
C'est bizarre, mais vers 70 000 de profondeur dans la récursivité mon programme plante...
Bref, je vais essayer de penser "boucle"

ça n'a rien de bizarre : tu te plantes sur un débordement de pile! Chaque process possède un espace mémoire limité appelé "pile" ou "tas". Il utilise cet espace pour stocker ses données dynamiques en cours d'exécution.
Comme Flodelarab l'a expliqué, l'usage de la récursion est fortement consommateur de mémoire en pile (stockage de pointeurs et de données diverses). Lorsque la pile déborde, ton process se plante, àmoins que tu ais géré l'exception de débordement de pile, mais j'ai des doutes...
Il y a longtemps, du même temps que Flo, la pile était limitée à 1024 octets au plus. Et on se débrouillait souvent avec bien moins! Voilà pourquoi les anciens programmeurs (les vrais!) évitent les codes récursifs...
Sais-tu qu'en 1980 la RAM d'un PC faisait 16 Ko ou 32 Ko... Le calculateur de mission de l'Atlantique 2 fonctionnait sur MC68000 et tenait dans 60 Ko de RAM...

par **lapras** » 29 Déc 2007, 22:21

Ok.
Vous devez être émerveillés devant les ordis actuels, vous, anciens programmeurs :we:
C'est dommage mon programme devait aller jusqu'a la profondeur 100 000 , il n'y arrivera pas , je vais devoir tout reprogrammer ! :(
(même mon nouvel ordi plante a 75 000 !)

par **Flodelarab** » 29 Déc 2007, 22:24

Dominique Lefebvre a écrit:Le calculateur de mission de l'Atlantique 2 fonctionnait sur MC68000 et tenait dans 60 Ko de RAM...

60 kilo de rames pour traverser l'Atlantique ?
Le fibre de carbone a du bon....

par **Dominique Lefebvre** » 29 Déc 2007, 22:35

Flodelarab a écrit:60 kilo de rames pour traverser l'Atlantique ?
Le fibre de carbone a du bon....

Elle est bonne... T'as du connaitre le MC68000 non?

par **anima** » 29 Déc 2007, 22:38

lapras a écrit:Ok.
Vous devez être émerveillés devant les ordis actuels, vous, anciens programmeurs :we:
C'est dommage mon programme devait aller jusqu'a la profondeur 100 000 , il n'y arrivera pas , je vais devoir tout reprogrammer !
(même mon nouvel ordi plante a 75 000 !)

Et pourquoi pas le threader, ton programme? Ca peut peut-etre résoudre la chose. Un thread va en profondeur 50 000, puis passe le relai au second thread, ou mieux, les 2 coexistent et marchent chacuns en boucle.

par **Dominique Lefebvre** » 29 Déc 2007, 22:40

lapras a écrit:Ok.
Vous devez être émerveillés devant les ordis actuels, vous, anciens programmeurs :we:
C'est dommage mon programme devait aller jusqu'a la profondeur 100 000 , il n'y arrivera pas , je vais devoir tout reprogrammer !
(même mon nouvel ordi plante a 75 000 !)

pour être honnête, je ne classerais pas dans la catégorie "ancien programmeur"...
La limite de pile n'a rien à voir avec ton PC, qui j'imagine possède un quantité de mémoire très supérieure à la taille de la pile. Cette dernière est définie par le compilateur et le système d'exploitation.
Et oui, lorsque je programme, j'ai toujours les vieux réflexes d'économie de mémoire. Alors que j'ai entre 2 et 4 Go de mémoire sur mes stations (16 Go sur les serveurs) ... Je suis plus impressionné par les fréquences CPU et les architectures hyper-pipeline...

par **Dominique Lefebvre** » 29 Déc 2007, 22:42

anima a écrit:Et pourquoi pas le threader, ton programme? Ca peut peut-etre résoudre la chose. Un thread va en profondeur 50 000, puis passe le relai au second thread, ou mieux, les 2 coexistent et marchent chacuns en boucle.

En boucle, oui. Mais faire du multithread avec un algo récursif, il va falloir que tu me montres ça :-)

)

par **Joker62** » 29 Déc 2007, 23:09

D'un point de vue machine, comme humain, la récursion est quelque chose de très dur à suivre. C'est à peu près, comme les programmeurs accros au goto, label

J'en ai connu un qui était un vrai génie, mais d'un point de vue lisibilité, c'est à peine s'il me fallait une semaine pour voir ce qu'il voulait y faire !
Sacré Brunews pour ceux qui connaissent lol ! Cppfrance :)
ça me manque ce temps où je touchais à la prog..

par **Flodelarab** » 30 Déc 2007, 00:13

Le premier ordi était

avec un 6502A à 2 Mhz

Le second était

i8086 à 8 MHz (oui, celui du dépassement de pile en pleine face)

par **Joker62** » 30 Déc 2007, 00:35

J'aime le logo LCD sur le moniteur lol

Edit : Oui je sais, c'est écrit ICD

par **anima** » 30 Déc 2007, 00:58

Dominique Lefebvre a écrit:En boucle, oui. Mais faire du multithread avec un algo récursif, il va falloir que tu me montres ça )

Pas du vrai multithread; juste couper la boucle en 2.

par **anima** » 30 Déc 2007, 01:00

Joker62 a écrit:D'un point de vue machine, comme humain, la récursion est quelque chose de très dur à suivre. C'est à peu près, comme les programmeurs accros au goto, label

Pas d'accord; une récursion est dans beaucoup de cas (Expérience perso) logique et assez simple a suivre. Sauf, bien entendu, quand ca se complique.

J'en ai connu un qui était un vrai génie, mais d'un point de vue lisibilité, c'est à peine s'il me fallait une semaine pour voir ce qu'il voulait y faire !
Sacré Brunews pour ceux qui connaissent lol ! Cppfrance
ça me manque ce temps où je touchais à la prog..

Y'en a un qui m'a bien bloqué pendant un moment, un algorithme du jeu de la vie en BASIC. Tu parles d'un cauchemar...

Sudoku - le programme !

Qui est en ligne