Implémentation du jeu Sudoku en Common Lisp

Version imprimable

26/11/2015, 18h05
atosbi

Implémentation du jeu Sudoku en Common Lisp

Bonsoir,
Je dois implémenter le jeu sudoku en Lisp et je voulais savoir quel choix d'implémentation est le plus simple entre un tableau à deux dimensions et un objet d'objets.
En effet j'ai commencé par ne créer qu'un tableau à deux dimenssion je me suis rendu compte que j'ai des problèmes pour gérer les carrés de la grille sudoku. En objet je ne sais pas du tou comment generer la grille.
En vous remerciant d'avance pour vos réponses.
02/12/2015, 23h23
byjav

Citation:

Envoyé par atosbi

En effet j'ai commencé par ne créer qu'un tableau à deux dimenssion je me suis rendu compte que j'ai des problèmes pour gérer les carrés de la grille sudoku.

Quelle sorte de problèmes ?
04/12/2015, 10h25
jack-ft

Bonjour.
Tu le fais en Common Lisp ou en CLOS?
Si j'avais le choix, je le ferais en CLOS.
Amha, tu as certainement moins besoin de puissance de calcul que de puissance de modélisation.
As-tu commencé ton modèle?
Quelles sont les méthodes dont tu as besoin?
04/12/2015, 13h57
byjav

Citation:

Envoyé par jack-ft

Tu le fais en Common Lisp ou en CLOS?

Comment ça, CLOS fait partie de Common Lisp.

Personnellement, je ne vois pas encore comment les fonctions génériques puissent être utiles dans ce cas.
04/12/2015, 14h31
jack-ft

Citation:

Envoyé par byjav

Comment ça, CLOS fait partie de Common Lisp.

Oui, bien sûr.

Comme l'utilisateur parlait de "choix d'implémentation" et de "tableau à 2 dimensions", je voulais attirer son attention sur le choix d'un modèle abstrait, si possible indépendant de son implémentation.

Se concentrer sur ce dont il a besoin avant de choisir comment l'implémenter.

Citation:

Personnellement, je ne vois pas encore comment les fonctions génériques puissent être utiles dans ce cas.

Pour CLOS, je pensais plus à l'encapsulation qu'aux fonctions génériques.

Bref, un bon modèle objet, koa!

Après, il faudrait savoir quel genre d'interface utilisateur il veut.

Et aussi et surtout, il faudrait savoir de quel genre de programme il s'agit:
- un jeu interactif, partant d'une grille de départ donnée,
- ou un programme pour résoudre une grille donnée
- ou un programme pour générer des grilles.
04/12/2015, 20h54
byjav

Je suis d'accord. L'interface aux données est peut-être plus importante que l'implémentation des données.
08/12/2015, 14h03
atosbi

Désolé de ne pas avoir répondu. Comme je ne suis pas un habitué de ce forum je n'ai pas fait attention au message qui me disait que la discussion que j'avais créé avait été déplacée.
Pour répondre à vos questions, je dois développer le jeux en Common Lisp, et j'hésitait à considérer ma grille comme un tableau à deux dimensions ou comme un ensemble d'objets (c'est-à-dire que chaque case est un objet).
J'ai finalement choisi d'implémenter ma grille avec un tableau à deux dimensions.
Cependant je dois maintenant créer une stratégie qui remplie une, grille de sudoku en moins de 20 ms.
J'ai essayer de parcourir la grille dans un premier temps pour classer les cases où on peut jouer suivant le nombre de coups possibles de ces derniers dans une table de hashage.
Ensuite j'ai une fonction qui parcours la table et pour chaque case, il essaie un chiffre parmi ceux possibles et ainsi de suite. Si dans une case aucun des chiffres possibles n'est valide alors on revient en arriere.
Cette stratégie ne fonctionne pas car elle revient trop en arrière.

Si quelqu'un voit comment je peux l'améliorer ou voit une autre stratégie plus efficace je suis preneur.

Merci d'avance pour vos réponses.
09/12/2015, 18h52
jack-ft

Citation:

Envoyé par atosbi

Pour répondre à vos questions, je dois développer le jeux en Common Lisp, et j'hésitait à considérer ma grille comme un tableau à deux dimensions ou comme un ensemble d'objets (c'est-à-dire que chaque case est un objet).
J'ai finalement choisi d'implémenter ma grille avec un tableau à deux dimensions.

ok

Citation:

Cependant je dois maintenant créer une stratégie qui remplie une, grille de sudoku en moins de 20 ms.

Bon. Apparemment, c'est la réponse n°2:
- un programme pour résoudre une grille donnée

Citation:

J'ai essayer de parcourir la grille dans un premier temps pour classer les cases où on peut jouer suivant le nombre de coups possibles de ces derniers dans une table de hashage.

Bonne idée de classer les cases en fonction du nombre de coups possibles pour chacune.
Dans les problèmes à base de contraintes, il est très souvent bon de commencer par les coups les plus contraints!
Mais pourquoi une table de hashage?

Citation:

Ensuite j'ai une fonction qui parcours la table et pour chaque case, il essaie un chiffre parmi ceux possibles et ainsi de suite. Si dans une case aucun des chiffres possibles n'est valide alors on revient en arriere.
Cette stratégie ne fonctionne pas car elle revient trop en arrière.

Si quelqu'un voit comment je peux l'améliorer ou voit une autre stratégie plus efficace je suis preneur.

Ben, ç'a l'air pas trop mal.
Il faut juste gérer proprement le backtrack.

A priori, et sans trop réfléchir (et dans une première version non optimisée), je parcourrais la liste des cases non affectées et créerais une a-list avec la case (peut-être un couple (i, j)) et la liste des nombres possibles pour la case.
Ensuite, un coup de "sort" pour trier la a-list en mettant en tête les cases dont la liste de possibilités sont les plus courtes.
Ensuite, on parcourt la liste:
Si la liste associée au premier élément est vide, c'est que le dernier essai est pas bon => backtrack
Si la liste associée au premier élément contient un seul nombre, c'est un coup forcé, on le fait et on continue.
Si la liste associée au premier élément contient plusieurs nombres, il faut les essayer, mais en se donnant la possibilité de revenir en arrière.

Pour pouvoir revenir en arrière, il faut soit compter sur la pile de récursivité, soit le gérer à la main.

La méthode brute consiste à dupliquer tout le tableau pour chaque essai.
Du coup, quand on revient en arrière dans la récursivité, on retrouve les données telles qu'elles étaient avant l'essai.

Écris-nous ton algorithme et on te dira ce qu'on en pense.
10/12/2015, 13h01
atosbi

Mais pourquoi une table de hashage?

J'ai choisi la table de hachage parce qu'un accès à elle coûte moins chère.
10/12/2015, 13h35
atosbi

Écris-nous ton algorithme et on te dira ce qu'on en pense.

les clés pour les accès a la table vont de 1 au nombre de case vide (dans la grille). Et chaque case contient un objet Box qui contient les coordonnées de la case, la valeur jouée et la liste des possibilités sur cette case (dans la quelle on ajoute 0 en queue de liste).

Algo:

--->strategy (grille, table, index)
----> dernier-index = taille(table)
----> si getValeur(table, dernier-index) != 0 alors
---->retrourner true;
----> sinon
---->si jouerUnCoup(grille, table, index) == true alors
----> strategy (grille, table, (index+1));
---->sinon
----> strategy(grille, table, (index-1))

Pour la fonction jouerUnCoup
---->jouerUnCoup (grille, table, index)
---->play = false
---->si premierElementListe(table, index) == 0 alors
---->on la place en queue de liste
----> retourner false;
---->sinon
---->Tant premierElementListe(table, index)!= 0 et play == false faire
---->si valide(grille, premierElementListe(table, index), getX(table, index), getY(table, index)) alors
---->grille[getX(table, index)][getY(table, index)] = premierElementListe(table, index)
---->setValeur(table, index, premierElementListe(table, index))
---->play = true
----> on la place le premier element en queue de liste
---->retuourner play

Sauf que dans ce cas il fait une boucle infinie ou essaie d'accéder la l'index 0 de la table de hachage (ce qui n'existe pas).

Citation:

Envoyé par atosbi

J'ai choisi la table de hachage parce qu'un accès à elle coûte moins chère.

Je sais bien qu'une hashtable permet un accès plus rapide, mais c'est pas clair ce que tu utilises comme structure...

Citation:

Envoyé par atosbi

les clés pour les accès a la table vont de 1 au nombre de case vide (dans la grille). Et chaque case contient un objet Box qui contient les coordonnées de la case, la valeur jouée et la liste des possibilités sur cette case (dans la quelle on ajoute 0 en queue de liste).

Pour formatter du texte (surtout avec des espaces), il faut utiliser la balise CODE, par exemple en cliquant sur le dièse # de la barre. (je ne peux pas modifier ton message)

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
26
27
Algo:
 
--->strategy (grille, table, index)
    ----> dernier-index = taille(table)
    ---->  si getValeur(table, dernier-index) != 0 alors
           ---->retrourner true;
    ----> sinon 
          ---->si jouerUnCoup(grille, table, index) == true alors
                ----> strategy (grille, table, (index+1));
          ---->sinon
                ----> strategy(grille, table, (index-1))
 
 
Pour la fonction jouerUnCoup
---->jouerUnCoup (grille, table, index)
      ---->play = false
      ---->si premierElementListe(table, index) == 0 alors
            ---->on la place en queue de liste 
            ----> retourner false;
      ---->sinon
            ---->Tant premierElementListe(table, index)!= 0 et play == false faire
                  ---->si valide(grille, premierElementListe(table, index), getX(table, index), getY(table, index)) alors
                        ---->grille[getX(table, index)][getY(table, index)] = premierElementListe(table, index)
                        ---->setValeur(table, index, premierElementListe(table, index))
                        ---->play = true
                  ----> on la place le premier element en queue de liste 
      ---->retuourner play

Ma proposition d'algorithme serait la suivante:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
Pour résoudre (grille)
  si grille est résolue
  alors retourner la grille
  pour chaque case de la grille
    si la case est non affectée
    alors stocker pour cette case la liste des valeurs possibles
  trouver la case la plus contrainte, ayant le moins de valeurs possibles (on aurait intérêt à le faire pendant l'énumération précédente)
  si cette case n'a aucune possibilité
  alors retourner nil
  pour chaque possibilité de cette case
    résoudre la grille obtenue en jouant cette possibilité
    et cumuler et retourner les résultats obtenus

Je te code ça ce soir et te donne le résultat demain...

10/12/2015, 19h57
atosbi

Je te code ça ce soir et te donne le résultat demain...

Merci. C'est vraiment gentillle.
17/12/2015, 08h01
jack-ft

Citation:

Envoyé par jack-ft

Pour formatter du texte (surtout avec des espaces), il faut utiliser la balise CODE

Ou bien indenter avec des tirets...

Citation:

Je te code ça ce soir et te donne le résultat demain...

Une semaine plus tard... l'algo a quelque peu évolué...

Pour résoudre (grille-brute)
---- pour chaque solution de trouver-solutions (construire-grille grille-brute)
-------- imprimer solution
---- fin pour
fin pour

Pour trouver-solutions (grille)
---- // D'abord on joue tous les coups forcés
---- tant qu'il reste une case avec une seule valeur possible
-------- suivant résultat après avoir mis cette valeur dans cette case:
----------- * solution: arrêter trouver-solutions et retourner cette solution
----------- * échec: arrêter trouver-solutions et retourner rien
----------- * ok: continuer
-------- fin suivant
---- fin tant que

---- // Plus de coups forcés: il faut commencer le backtrack

---- choisir la case la plus contrainte
---- collecter
-------- pour chaque valeur possible pour cette case
------------ copier la grille en une nouvelle grille
------------ suivant résultat après avoir mis cette valeur dans cette case de la nouvelle grille:
--------------- * solution: collecter cette solution
--------------- * échec: collecter rien // y a peu de chances...
--------------- * ok: collecter trouver-solutions de cette nouvelle grille
------------ fin suivant
-------- fin pour
---- fin collecter
---- retourner le résultat de la collecte
fin pour