Petite erreur dans le C et mesure réelle de difficulté

[arnaudhl]

Bonjour,

1) Dans le programme C publié il y a un blanc en trop :
/* option d'affichage dans la fontion resolve */
g_flag_affiche = ((argc >= 2) && (parametre_affichage(argv[1]))); //au lieu de > = 2 !!!
Le programme en C est astucieux par 'force brutale" (3 boucles imbriquées) mais pas moins bon qu'une approche 'branch and bound' plus structurée.

2) La véritable mesure de la difficulté n'est pas le nombre d'"itérations" (appel à resolve) mais la profondeur de l'exploration (le nombre d'appels de resolve empilés)
Quelqu'un est-il intéressé par le programme C avec cet affichage ajouté? Permet de mieux comprendre comment ça marche.

3) il y a > 40 ans que je fais de la programmation linéaire en nombres entiers: c'est un cas particulier où il n'y a aucun critère permettant de limiter la profondeur du Branch and Bound par un majorant simple à obtenir d'une fonctionnelle.
Pour les Profs...

4) Le jeu de Sudoku est sans intéret, et fait perdre du temps puisqu'un programme combinatoire le résoud aisément. Je vais mettre en ligne (pas nouveau) un programme de résolution avec saisie graphique pour que les gens lisent ou fassent des maths au lieu de perdre du temps et puisse l'utilser avec un 'browser" à partir d'un mobile. Et aussi faire une application USSD pour les gens qui n'ont pas de connexion GPRS.

Arnaud

[Cédric67]

On a l'impression que tu veux juste exposer le fait que tu sais faire un résolveur en C, waou c'est génial bravo, mais là on s'en fout quoi, surtout que tu dis simplement que tu vas en faire un pour les gens, tu fais ce que tu veux. Puis t'en fais depuis 40 ans, c'est cool, la petite erreur dans le code, je pense ne necessitait pas qu'on fasse un topic la dessus

Puis surtout quand tu dis qu'on perd notre temps à faire des sudoku oO, je veux dire si on veut faire des sudoku c'est qu'on aime bien, donc on en fait, si t'aime pas et tu penses perdre ton temps n'en fait pas et laisse nous ! oO Tout le monde n'est pas comme toi, et heureusement !

Tu trouves que c'est débile de faire des sudoku parce qu'il y a des résolveur... ça n'a aucun sens, les sudoku c'est fait pour réfléchir c'est un petit jeu, à quoi ça sert d'avoir la solution directement ! Après c'est sur c'est toujours intéressé de voir s'il est juste, mais il faut d'abord le faire !

[Julie]

Bonjour,

Il me semble que Cédric "tape" juste, très juste même...

Petits commentaires purement techniques de ma part :

1) Dans la ligne de code du programme pré-cité ( http://www.top-sudoku.com/sudoku/fr/exemple-backtracking-c.php ) :

Code: Tout sélectionner

g_flag_affiche = ((argc>= 2) && (parametre_affichage(argv[1])));

Il n'y a pas un caractère de trop mais un caractère de moins !
Voici la syntaxe d'écriture strictement conventionnelle !

Code: Tout sélectionner

g_flag_affiche = ((argc >= 2) && (parametre_affichage(argv[1])));

Dans les deux cas cela passe sans erreur ou message d'avertissement lors de la compilation, même la plus stricte, avec par exemple l'option -pedantic .

2) Dans le code proposé "le nombre d'appels de resolve empilés" ne peut dépasser 81, c'est à dire le nombre total de cases. La "profondeur de l'exploration" est-elle donc importante, celle-ci étant limitée srtictement par la taille même de la grille ?

3) Personnellement je serais très intéressée par un code en C expliquant la P.L.N.E. "Programmation Linéaire en Nombres Entiers" et résolvant les sudokus.
Si Arnaud veux bien nous envoyer cette étude nous pourrions en faire un article.
Dans ce contexte faudra-t-il tenir compte des inégalités de Gomory ?
Merci Arnaud.

Cordialement,
Julie