Discussion :

[bisthebis]

Bonjour à tous,
Ca faisait longtemps que je n'avais plus programmé (et à l'époque je n'étais pas très bon ) et pour me remettre dans le bain j'ai décidé de coder un jeu de Sudoku (en console pour l'instant).
Entre les points virgules oubliés et les pointeurs ratés (quand je dis que je suis rouillé ^^) J'ai réussi à obtenir quelques maigres résultats, avec un problème assez surprenant.
En ce moment, je planche sur la génération d'une grille 9x9 complète et correcte (donc : injouable car déjà complétée, mais qui respecte les contraintes du jeu : pas de doublons dans les lignes, colonnes et carrés).
Comme j'avance par étapes, je me contente d'abord des lignes et colonnes : les deux marchent à merveille individuellement, mais je n'arrive pas à les combiner.
Le raisonnement de base consiste à avoir une grille (un tableau 9x9) qui commence avec 0 partout (pour l'initialisation), ensuite, pour chaque case, j'utilise une fonction "mettre n'importe quelle valeur tant que ca fonctionne" : la première case a donc une valeur purement aléatoire, mais la suivante en a une autre, et ainsi de suite. Pour chaque case, on prend une valeur test aléatoire : si elle respecte les contraintes on la prend, sinon on réessaye, jusqu'à ce que ça marche.
Donc, pour vérifier que les contraintes sont respectées, je regarde toute la ligne ou colonne et regarde si cette valeur est déjà prise.
Voici la méthode telle que je l'ai implémentée.
Elle prend à paramètre les coordonnées de la case à remplir, et se termine par le remplissage de la case. (Le tableau de cases étant un attribut de l'objet représentant la grille)

Il y a une boucle pour la vérification de la ligne, et une pour la colonne. Si je commente une des deux boucles et n'utilise qu'une seule des deux vérifications, celle-ci marche crème. Peu importe si je garde la 1ere ou la 2e. Mais si les deux sont actifs, le programme freeze (boucle infinie je présume).

Je voudrais savoir si j'ai fait une bourde de syntaxe quelque part ou si mon algorithme est mauvais. (Peut-être que, statistiquement, mon algorithme bloquera forcément à la fin ?)
Dois-je changer une ligne, ou bien trouver un autre raisonnement ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void Sudoku_grille::PutRandomPossibleValue(int x, int y)
{
    bool done = false;
    int valeurtest = 0;
    int i = 0;
     bool lineOK = true;
     bool columnOK = true;
    while (!done)
    {
        valeurtest = (rand()%9)+1;  // Choisir une valeur à tester
 
        for (i =0; i<9; i++)  // Vérification de la colonne
        {
            columnOK = true;
            if (cases[x][i]->get_correct_value() == valeurtest && i != y)  //Si déjà pris... Ou si se vérifie lui-meme
            {
                columnOK = false;
                break;
            }
 
 
        } 
 
 
       for (i =0; i<9; i++)  // vérif ligne
        {
            lineOK = true;
            if (cases[i][y]->get_correct_value() == valeurtest && i != x)  //Si déjà pris... Ou si se vérifie lui-meme
            {
                lineOK = false;
                break;
            }
 
 
        } 
    if (lineOK && columnOK)
    {
        cases[x][y]->set_correct_value(valeurtest);
        done = true;
    }
 
 
 
    }
 
}

Merci d'avance
(PS : Je suis nouveau ici; j'hésitais entre poster ici ou sur la section débuter; que me conseillez vous à l'avenir ?)

[Capitaine Kirk]

Bonjour,

Je ne suis pas programmeur c++ donc il y a certaines petites choses qui m'echaperont surement, mais au niveau de l'algorithme je ne sais pas si c'est une bonne idee de proceder ainsi parce que j'ai l'impression le probleme se situe dans le fait que tu peux avoir 10 fois de suite le meme chiffre aleatoire genere, donc tu vas verifier 10 fois le meme chiffre c'est surement pour cette raison que ton programme prend enormement de temps et donne l'impression de bloquer, il faudrait je pense trouver un moyen de stocker les chiffres deja present et eviter a ton generateur de les generer.

Cordialement.

[ternel]

En général, les algorithmes utilisent une grille des nombres encore possible pour chaque case.
Chaque fois que tu choisis un nombre, tu le retire des possibles de chaque case de sa ligne, de sa colonne et de son bloc.
Si tu as une case qui n'a plus de possible mais n'est pas rempli, c'est que le nombre généré n'était pas possible.

A ce moment là, tu remarques que les grilles sont générées par parcours (éventuellement avec embranchement).
Il pourrait être intéressant de créer un arbre de dépendance entre les cases, et de générer les premières cases aléatoirement.

C'est triste à dire, mais la génération d'une grille en un temps rapide requiert de savoir résoudre une grille.
En effet, ce sont les techniques de résolution qui permette de lier les nombres.
Il "suffit" de générer dans l'autre sens pour savoir comment l'initialiser.

[kajtp]

Oui il y a bien un problème d'algo, voir le message précédent pour la solution, avec le tient on peut tomber sur cette grille par exemple
<code>
2 8 1 6 4 7 5 9 3
6 5 3 4 2 9 1 7 8
4 3 7 8 9 6 2 1 5
7 1 5 3 8 4 6 2 9
3 4 6 2 7 5 8 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
<\code>
où l'on voit bien que pour remplir la case (4,7) aucune de tes conditions n'est satisfaite (tout les nombre sont déjà pris par la colonne et la ligne qui entoure la case), done est toujours false, et boucle infinie (pourtant, toutes les cases précédentes ont vérifient tes conditions).

[ternel]

Une idée, empruntée à un ami: générer des blocs de 3 sur 3, et chercher 9 blocs compatibles.

Une autre, lire les mathématiques du sudoku sur wikipedia.

[bisthebis]

Merci à tous pour les réponses
Effectivement le cas présenté par kajtp est insolvable, bien vu !

C'est triste à dire, mais la génération d'une grille en un temps rapide requiert de savoir résoudre une grille.
En effet, ce sont les techniques de résolution qui permette de lier les nombres.
Il "suffit" de générer dans l'autre sens pour savoir comment l'initialiser.

Peux-tu développer ? Je n'arrive pas vraiment à saisir le concept... Est-il question de placer quelques nombres aléatoires de façon à faire une grille solvable, puis de la résoudre pour avoir une grille complète ?
Quant aux concepts de dépendance et d'arbres, je ne les maitrise absolument pas. J'ajoute ça à ma liste de choses à voir.

Je pense que je vais lire la page wikipedia (j'avais cherché en vitesse sur la page des sudokus mais je n'avais pas trouvé de page dédiée à l'aspect mathématique) et évenutellement tenter le coup des blocs compatibles.

Encore merci !

[ternel]

Pour résoudre une grille il y a plusieurs techniques applicables.
Savoir les reconnaitre permet de définir les chaines de raisonnement qui servent à résoudre la grille.

Une des techniques:

Par exemple, si N cases d'un même bloc/ligne/colonne ne peuvent contenir que les mêmes N valeurs, les autres cases de ce bloc/ligne/colonne ne peuvent pas contenir l'une de ces N valeurs.
Par exemple (avec N=2), une ligne telle que: x x 3 . . . 7 8 9 si tu sais que les deux cases x ne peuvent contenir que 1 et 2, alors les trois autres sont forcément ni 1 ni 2

Cela dit, en parlant de cela, je réalise que ca sert surtout à mettre les trous, pas à chercher une grille pleine.

[kajtp]

Sinon une autre idée serait peut etre de partir à l'envers de ce que tu voulais faire (je dis ça sans avoir trop creusé, mais ça me semble correct), c'est à dire les chiffres de 1 à 9 sont fixés et ce sont les positions dans la grille que tu tires au sort. Ca donnerait


- tirer une case au hasard parmi les 81
- y placer le nombre 1
- masquer les cases devenues impossibles pour 1 avec le placement précédent (le bloc, la ligne, la colonne)
- tirer à nouveau une case au hasard parmi les cases non masquées précédement
- y placer le nombre 1
- ajouter sur le masque des cases impossibles, les nouvelles cases interdites au 1 par le placement du nouveau 1
... recommencer comme ça jusqu'à avoir placer tout les 1

Puis tirer une case au hasard parmis les 72 (81 moins les 9 occupées par les 1) cases restantes
- y placer le nombre 2
- masquer les case devenues impossibles pour 2 avec le placement précédent (le bloc, la ligne, la colonne )
- tirer à nouveau ...... (etc etc commme le cas 1)

Puis tirer une case au hasard parmis les 64 cases restantes:
- y placer le nombre 3....

etc.. jusqu'à placer les 9 aux derniers emplacements

[bacelar]

Pourquoi faire compliqué ?

Associer à chaque case de la grille, une liste des valeurs encore possibles {1,...,9}

Do
Tirer une case au hasard (des cases restantes), choisir une valeur au hasard dans la liste des valeurs encore possibles pour cette case.
Retirer la case de la liste des cases restantes, la mettre dans la liste des cases avec valeurs affichées.
Supprimer de la liste des valeurs possibles des cases restantes "influencées" par la case sélectionnée, la valeur tirée.
Pour chacune de case influencée:
Si le nombre de valeur possible tombe à 1 pour cette case ajouter cette case à la liste des cases "open".
While (nombre de cases dans la liste "open")>1
Retirer la case en tête de liste "open" de la liste des cases restantes et de la liste des opens.
tirer au hasard si cette case (ex-tête) est ajoutée à la liste des cases avec valeurs affichées. (en fonction du niveau de difficulté : très simple toujours, très difficile jamais)
Supprimer de la liste des valeurs possibles des cases restantes "influencées" par la case "open" courante, la seule valeur restante de la case "open" courante.
(Ici, il est possible de rendre une case "influencée" avec 0 valeur possible) => cas d'erreur qui devra être gérer en utilisant les mécanismes de fonctions récursives copiant le contexte.
Si le nombre de valeur de la case "influencée" n'a plus qu'une valeur possible, l'ajouter à la liste des cases "open".
Repeat

While (nombre de cases restantes) > 1

[ternel]

Si au bout d'un moment, tu es toujours en panne seche, il y a des générateurs de sudoku partout sur le web (en javascript), et gsudoku (dont le code source est accessible).

Cela dit, c'est comme lire la solution d'un sudoku: pas drôle du tout, mais utile pour apprendre

[Kaamui]

@bacelar, ton algo ne peut pas fonctionner systématiquement et c'est le problème avec les grilles de sudoku, il y a un nombre fini de combinaisons. Il suffit que ton algo commences avec une "mauvaise" série de cases choisies pseudo-aléatoirement pour rentrer dans un cas d'impossibilité et donc terminer en erreur ou boucle infinie dans ton cas

[bacelar]

>un cas d'impossibilité et donc terminer en erreur ou boucle infinie dans ton cas
Non, il faut utiliser une mécanique d’empilement de contexte, comme indiqué maladroitement.
Quand on explore un choix, on le fait par l'appel d'une fonction qui copie le contexte, si la fonction retourne une impossibilité de résolution, on grille le choix et on tire un autre choix possible et on recommence. S'il n'y a plus de choix, on une remonte une impossibilité de résolution à la fonction appelante.

[bisthebis]

Pfiou, les idées ici déferlent beuacoup plus vite que je ne travaille
Pour l'instant (je suis pas très productif ^^) je n'ai testé que ceci :

Une idée, empruntée à un ami: générer des blocs de 3 sur 3, et chercher 9 blocs compatibles.

Alors, résultat, en prenant un carré généré et en le comparant avec un autre qu'on reroll tant que ca marche pas, sur 2 000 000 de tentatives (20 minutes pour ma machine), AUCUNE combinaison n'était compatible horizontalement (càd en comparant que les lignes).
Bon, je suis pas assez matheux pour calculer les probabilités, mais cette méthode ne me parait pas optimale :p
Du coup, je vais voir si ya moyen d'optimiser ça (en prenant le carré voisin comme référence et faire une grille de possibilités pour chaque ligne, ou quoi).
Sinon je vais tenter une de vos nombreuses autres propositions

[prgasp77]

Non, il faut utiliser une mécanique d’empilement de contexte, comme indiqué maladroitement.
Quand on explore un choix, on le fait par l'appel d'une fonction qui copie le contexte, si la fonction retourne une impossibilité de résolution, on grille le choix et on tire un autre choix possible et on recommence. S'il n'y a plus de choix, on une remonte une impossibilité de résolution à la fonction appelante.

Dans les années 70 on parlait du backtracking qu'on présentait comme une panacée et qu'on proposait comme solution à chaque problème rencontré. Seulement voila, à l'époque les langages n'aidaient pas (voir le papier* d'E.W. Dijkstra concernant son problème de perles) et les implémentations étaient souvent truffées de goto, d'où Goto Statment Considered Harmful.

Aujourd'hui, on peut implémenter du backtracking proprement et facilement, et peu pensent à utiliser ce genre de méthodes ; j'ai fait toutes mes études sans entendre une fois ce terme. Tout ça pour conclure : bacelar.

* Impossible de retrouver le papier, mais je sais qu'il date de 1972 dans Communications of the ACM.

[bacelar]

J'ai l'impression d'être Mr Jourdain.

[Kaamui]

ça change rien à ce que j'ai dit, le backtracking pose de vrais soucis d'efficacité avec la génération de sudoku, parce que tu peux avoir une combinaison relevant d'un cas d'impossibilité à un niveau n mais qu'il faille reevnir à un niveau n-10 pour trouver une solution, les combinaisons ne sont vraiment pas nombreuses parmi les combinaisons possibles, et le backtracking ici s'en aperçoit assez souvent très tardivement. Un autre souci, une fois que la grille est rempli, c'est de la "trouer", il est difficile mathématiquement de prouver que la version trouée que tu vas généré est résolvable. D'ailleurs, le plus difficile cas de sudoku trouvé était avec 16 chiffres restants je crois, mais tu peux très bien laisser 20 chiffres et qu'il ne soit pas résolvable.

C'est pour ça que je maintiens, s'attaquer à la génération d'une grille de sudoku est vraiment très intéressant, mais cela devient un cas d'étude pour les thèses comme l'IA du morpion, c'est vraiment pas évident. Même en math y'a des recherches très poussées là dessus. D'ailleurs, les sites de sudoku que vous trouvez en lignes propose des grilles faites à la main, pas par algo, car c'est plus facile/rapide d'en générer à la main, et de proposer une liste finie (bien moins finie que dans le champ des possibles) de grilles.

Enfin ça fait maintenant quelques années que j'ai arrêté de suivre, mais je penses pas qu'il y ait eu énormément d'avancement dans ces algos... Après pour le souci d'efficacité faut travailler sur gpu directement mais c'est autre chose...

[bisthebis]

Bon, on dirait que j'ai ouvert la Boite de Pandore; je suis totalement dépassé par le niveau de la conversation
De mon côté, je continue de me prendre des murs en codant et j'aime ça.
Travaillant sur la piste des 9 blocs comaptibles, je me suis heurté à ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
8 4 7     1 5 2
1 5 3     7 8 6
6 2 9     4 3 ?

J'ai beau devoir tout mettre à la poubelle quasi quotidiennement, ça reste très instructif (quoi que fort empirique)
Je vais tester la méthode de kajtp (au cas où ça marcherait, mais ca m'a l'air trop simple pour fonctionner)
Sinon, j'explorerai la piste ô combien effrayante du backtracking.
D'ailleurs, petite question, quelle est la méthode la plus simple de faire du backtracking ? Des fonctions récursives ?

[ternel]

Conceptuellement, ca revient à parcourir l'arbre des grilles possibles.
Les fonctions récursives sont la solution classique, mais ce n'est pas forcément la seule.

A toi de voir comment annuler un choix.

typiquement, ca donnerait pour moi un algo du genre:

essayer de remplir une case:
    remplir un vecteur avec les 9 valeurs possibles.
    le mélanger
    pour chaque valeur de ce vecteur
        essayer cette valeur.
        si elle est possible
            choisir une autre case
            essayer de remplir cette case
        si la grille est pleine, bingo!

Ecrit à la va-vite, c'est une base de travail

[bisthebis]

Dans ton brouillon d'algo, je pense que j'ai compris l'idée. Histoire d'être sûr :

essayer de remplir une case:
remplir un vecteur avec les 9 valeurs possibles.
le mélanger
pour chaque valeur de ce vecteur
essayer cette valeur.
si elle est possible -----> On laisse une des possibilités avant de passer à la suite j'imagine ?
choisir une autre case
essayer de remplir cette case ----> On appelle la fonction initiale de façon récursive ?
si la grille est pleine, bingo!

Sinon, après tests, la méthode de kajtp s'est révélée très prometteuse... Je ne bloque à chaque fois que sur 1, 2, 3, ou 4 paires de cases qui sont impossibles.
Exemple, avec un 7 et un 5 impossibles à placer :
A titre informatif, il faut 5-6 secondes pour arriver à ce qu'il ne reste que 10 trous.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
9 1 7  8 6 4  2 5 3
8 2 6  5 3 1  7 4 9
4 5 3  2 7 9  1 8 6
 
7 6 8  4 5 2  9 3 1
2 X 1  7 9 3  8 6 4
3 9 4  1 8 6  5 2 7
 
5 3 2  6 1 7  4 9 8
6 4 X  9 2 8  3 1 5
1 8 9  3 4 5  6 7 2

Je sais pas trop si c'est possible de la rendre possible avec des simples retouches (mentalement j'y arrive pas ^^)
Ou si en retouchant simplement mon algo ca peut marcher
Ca me semblerait bete de tout réécrire avec du backtracking alors que je suis si près du but. A moins d'utiliser cet algo pour les X premières cases puis faire du BT pour fignoler ?

[jo_link_noir]

5 secondes me semble énorme . J'ai essayé une implémentation en brute force (backtracking en récursive) et en 5 secondes j'ai 1 million de résultats.
Même pour générer une grille aléatoire, il faut beaucoup moins d'une seconde.

Je ne sais pas quel est le type de cases, mais mon avis qu'il n'est pas adapté.

Du coup, je vais quand même dire mon procédé :
- générer 81 tableaux de 9 éléments triés aléatoirement.
- prendre le premier chiffre valide dans le tableau 9 éléments aléatoire de la première case.
- sauvegarder la position, passer à la case suivante et continuer jusqu'à la fin
- si pas de solution, reprendre avec la case et la position précédentes

La recherche sur ligne, colonne, carré est fait avec 3 conditions (+ 3 tableaux de 9 masques binaires) et sans boucle. Si ce n'est pas plus rapide, c'est amha plus facile à écrire.