Discussion :

[kolodz]

Bonjour,

L'une de mes problématiques précédentes était de réaliser une cache/indexation matriciel pour des pièces de puzzle.
Il y a un billet ici : [Retour][Optimisation][Eternity II] Problème récurrent et optimisation par cache matriciel
Et une discutions sur la problématique précédente ici : Hash/clé : permutation circulaire et unicité [Résolu]

L'idée de base était d'avoir un index permettant de savoir quel pièces permet de résoudre quel problème sans faire de test sur la pièce.

La solution retenu était :

Code java :

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

1
2
//  Contrainte Top /  Contrainte Left / Contrainte Bottom / Contrainte Right / Id de la pièce de la solution X [0..n]
	private static int[][][][][] cacheIdSolutions = new int[24][24][24][24][0];

Celui-ci est performant pour une indexation sur un pièce. Mais, j'aimerai étendre le principe sur l'indexation d'un groupe de pièce (2x2 ou plus). La problématique est qu'il m'est impossible d'instancier la matrice d'index, car il serai nécessaire d'avoir :

Code java :

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

	private static MetaHash[][][][][][][][][] cacheIdSolutions =new MetaHash[24][24][24][24][24][24][24][24][0];

ou

Code java :

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

	private static MetaHash[][][][][] cacheIdSolutions =new MetaHash[576][576][576][576][0]; // Regroupe les côtés en

Ce qui représente 1,1x10¹¹ espace mémoire ce que je n'ai pas.

A savoir que le nombre de groupe de pièces à indexé est 4 357 212, ce qui représente une quantité non négligeable.

Ma première piste étant une demi indexation :

Code java :

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

1
2
 // Contrainte TopRight // Contrainte TopLeft // Contrainte LeftTop // Contrainte LeftBot
public static MetaHash[][][][][] cacheTopLeft = new MetaHash[24][24][24][24][0];

Ce qui me permet d'avoir un index sur les match suivant :

_II_
IPP*
IPP*
_**_
I : match indexé
P : pièce
* : match non indexé

Sachant que les groupes de pièces peuvent être tournée. J'ai indirectement l'indexation pour le reste (le bas et la droite). Cependant, il m'est impossible de réaliser un index par rapport à 3 côtés ou plus avec un complexité O(1).
En effet, si je veux faire un match sur 3 côtés, il m'est nécessaire faire deux recherches dans mon index et de faire l'intersection des deux ensembles retournées.

Du coup, je me demande si il n'y aurai pas un moyen pour faire une indexation adaptable par rapport à cette problématique.
Si vous avez des avis ou idées sur la question, hésitez pas !

Cordialement,
Patrick Kolodziejczyk.

[souviron34]

Salut

j'ai parcouru les liens, mais je m'y perd un peu, je pense à cause de l'introduction de la notion de cache , de hash, etc..

Si je résume ce que je comprend du problème :

• tu as des piièces de puzzle pouvant avoir 23 découpes.
• tu as des puzzles (M) pouvant avoir N pièces.
• tu veux trouver les solutions des puzzles tout en ayant optimisé et la vitesse et la mémoire

me trompe-je ?

Mon "pansement" à ce stade-ci :

chaque puzzle a été fabriqué avec N pièces, dont les découpes sont connues à la fabrication
puis on mélange les pièces, et on veut la solution, c'est bien ça ?

[kolodz]

C'est ça, cependant il n'y a qu'un seul puzzle qui a été découpé en 256 pièces.
Celui-ci est un puzzle de 16 par 16.

chaque puzzle a été fabriqué avec N pièces, dont les découpes sont connues à la fabrication
puis on mélange les pièces, et on veut la solution, c'est bien ça ?

Donc, j'ai une liste de (256) pièces qui doivent faire le puzzle mentionné.
C'est ce qu'on visualise ici :

Le bût ultime c'est de résoudre le puzzle.
Dans un premier temps, j'avais une résolution bête et méchante qui parcourait l'ensemble des pièces et qui les essayait toutes une par une.

Pour la case que tu veux résoudre prendre la première pièces disponibles.
Si celle-ci ne correspond pas prend la pièce suivant et test pour celle-ci.
Si celle-ci correspond pose là et passe à la case suivante.

L'idée du "cache/hash" etc. C'est de ne plus tester l'ensemble des pièces, mais d'avoir la liste des pièces qui sont possible pour les contraintes données.

Pour la case que tu veux résoudre prend note les contraintes.
Consulte la liste des pièces possibles pour ces contraintes.
Prend la première pièce disponible dans la liste. (ie prendre la pièce première pièce pas encore posé.)

Maintenant, j'aimerai avoir la même logique non pas pour une case mais pour un groupe de case. C'est exactement la même logique, mais au lieu de vouloir résoudre le puzzle case par case, je voudrais le résoudre par groupe de 2*2 cases. Cela réduit le nombre d'étape à réaliser, vue que je n'ai plus 256 pièces à poser, mais 64 groupe de 2*2.
Sachant que je vérifie avant de poser une nouvelle pièce qu'il n'y a pas un endroit où je ne peux pas poser de pièces. Si je passe à une résolution de 2*2 au lieu de vérifier qu'il y a un pièce possible pour l'ensemble des cases vides. Je vais vérifier si il existe un groupe de pièce 2*2 possible pour l'ensemble des cases vides.
Ce qui veux dire que les impossibilités seront détecté plus rapidement.

tu veux trouver les solutions des puzzles tout en ayant optimisé et la vitesse et la mémoire

La problématique du puzzle est qu'il est très complexe. Chaque optimisation permet de se rapprocher un peu de la solution. La vitesse me semble le plus important. Mais, comme je tente de l'expliquer dans mon premier post, je ne peux pas tout mettre en mémoire comme je l'entends. Simplement parce qu'il y a pas assez de mémoire.

Dans l'approche que j'ai dans ce post, l'idée est de chercher une façon de trouver les groupes de 2*2 qui correspondent à un set de contraintes données le plus rapidement possible.
Potentiellement, trouver une solution qui pourrai être utiliser pour du n*n.

Ayant perdu espoir de trouver un moyen efficace de mémoriser l'ensemble des 8 contraintes que match un groupe de pièce 2*2. Je pense que je vais tenter une approche un peu plus complexe :
Mémoriser 4 des 8 contraintes. (le haut et la gauche par exemple)

Si j'ai seulement des contraintes sur le haut ou la gauche, j'ai directement le résultat.
Si j'ai des contraintes sur un côté ou deux côtes consécutif qui ne sont pas le haut ou la gauche, j'ai le résultat après une rotation.
Si j'ai plus de deux côté avec des contraintes, je fait deux recherches et je fait l'intersection des deux set de solutions.

Cependant, je ne pense pas que cette solution soit envisageable pour du 4*4 par exemple.

Cordialement,
Patrick Kolodziejczyk.

[souviron34]

Je continue à avoir du mal à voir ton problème..

Pour moi :

• Chacune des pièces a un attriibut "forme x", x étant 1 <-> 23.
  
  
• Ton puzzle (le board, la solution) a été fabriqué avec N (256) pièces, mais pour le fabriquer on sait très exactement le nombre de pièces de chaque forme, et leur place.

Donc, si on prend le processus depuis le début :

• on a une image (carrée ou rectangulaire)
  
  
• on la découpe petit à petit suivant les 23 formes, pour avoir 256 pièces.
  
  
• l'image (donc la solution) devient donc une matrice de pointeurs vers les pièces
  
  
• chaque pièce a donc 2 attributs : un visible à l'utilisateur (la forme), l'autre invisible (sa place initiale).
  
  
• on mélange les pièces et on veut donc revenir à la solution, en n'ayant que la partie visible à portée de main, si on est un utilisateur.. MAIS si on est un programme, on dispose d'une information supplémentaire, son vrai emplacement.

Me trompe-je ?
Alors ce que tu veux faire, c'est simuler un vrai utilisateur, ou résoudre de manière programme ?

[kolodz]

Chaque pièces a 5 attributs :

• haut (0 à 22)
• bas (0 à 22)
• gauche (0 à 22)
• droit (0 à 22)
• id (1 à 256)

L'identifiant, est pour reconnaitre la pièce. Sachant que la combinaison (haut,bas,gauche,droit) est suffisante pour reconnaitre une pièce. Le haut correspond à un haut arbitraire et n'est pas forcément l'orientation à utiliser pour résoudre le puzzle.

Ton puzzle (le board, la solution) a été fabriqué avec N (256) pièces, mais pour le fabriquer on sait très exactement le nombre de pièces de chaque forme, et leur place.

Je ne dispose que de la liste des pièces et de leurs attributs. Je ne connais la position que de 5 pièces sur le puzzle, 4 d'entre elles étant des indices et la 5ième une contrainte à respecté.

Donc, si on prend le processus depuis le début :

Tout ce que tu dis est potentiellement comment le puzzle a été crée. Mais, ce n'est pas moi qui l'ai crée. Je n'ai donc pas ces informations.

Alors ce que tu veux faire, c'est simuler un vrai utilisateur, ou résoudre de manière programme ?

L'idée est de résoudre le puzzle par programmation, je me fout de simuler un utilisateur. Après, il faut bien que le programme ai une manière d'approcher le puzzle. (Qui se rapproche donc d'un utilisateur.)

La photo que j'ai mise juste avant correspond à mon puzzle physique avec un non solution approchante déduit par mon programme actuelle. (Il n'y a actuellement pas de solution connu du puzzle )

Cordialement,
Patrick Kolodziejczyk.

[souviron34]

J'ai encore une petite question, même si ta photo donne une idée.. Les pièces du bord (ou des 4 angles) sont-elles particulières ? (si oui, tu as autant de "pièces spéciales" en plus)

Bon, alors mon idée de base :

tes 23 formes rentrent dans un octet (byte = caractère)

Les 4 attributs de forme rentrent donc dans un entier, ou dans 4 caractères
L'id rentre aussi dans un caractère. Mais à mon avis on s'en fout, de l'id.. On pourrait n'utiliser que 2 booléens (utilsé ou pas, définitif ou pas)

Donc pour chaque pièce on a 5 caractères de mémoire. Si on les met dans une liste circulaire, ajouter 2 entiers.

• Quand tu crées les pièces, mettre dans l'ordre lexicographique les 4 caractères de position/forme (O(N))
  
• Une fois toutes les pièces créées, les trier par ordre lexicographique (un tri normal style qsort O(N logN), un tri sophistiqué O(N))
  
• identifier les 5 pièces "spéciales" (par leur indice ou leur adresse, suivant qu'on a un tableau ou une liste) (O(N))
  
• puisqu'on a trié par ordre lexicographique, il est aisé d'explorer de chaque côté de chacune des pièces "spéciales" et d'avoir une recherche très limitée : dès qu'on ne satisfait plus, on a fini : si une des pièces est "bfgh", on ne cherchera forcément que parmi les pièces classées sous "b"... et d'itérer..

Par contre, cette dernière recherche est récursive. Et, pour être une "vraie" solution", il faudrait faire la démarche sur les 5 pièces en // : trouver simutanément pour chaque pièce "spéciale" une des pièces correspondantes, et propager parallèllement, jusqu'à aboutir soit à une impasse, soit à une solution. L'impasse serait de ne plus trouver de pièces comportant le caractère demandé dans les pièces disponibles. Pour ça , on utiliserait les 2 booleens, "utilisé", et "pas définitif", et on fabriquerait un arbre.

Mais je ne vois pas trop où des problèmes de mémoire pourraient surgir, vu que tu ne cherches pas les combinaisons de 256, mais qu'à chaque fois tu as les 256 pièces en mémoire et tu cherches un arbre..

Disons que la différence par rapport à un utilisateur normal avec un puzzle normal, c'est justement la notion de "bloc".. Un utilisateur normal face à un puzzle normal peut vérifier avec ses yeux qu'un bloc est correct ou pas.. Là, à moins de comparer avec une image d'origine de la solution, je ne vois pas comment on peut faire pour définir des blocs. A chaque fois il faut tester tout l'arbre, si on arrive à emboiter toutes les pièces ou si il en reste "non matchées..

Mais peut-être - sans doute - que je n'ai pas tout compris...

[tbc92]

Je reformule :
- chaque pièce du puzzle est un carré. Chaque bord du carré correspond à une couleur, numérotée entre 0 et 22.
- Une pièce est donc identifiée par les 4 couleurs des 4 côtés, mais on a le droit de faire tourner chaque pièce d'un quart de tour, ou d'un demi-tour.
- Il y a 256 pièces dans le puzzle, et il faut disposer ces 256 pièces pour former un carré de 16 x 16
- Et bien entendu, Si 2 pièces sont disposées cote à cote, le bord droit de l'une et le bord gauche de l'autre doivent être de même couleur. ( Ou le bord bas et haut ... si les 2 pièces sont cote à cote , mais à la verticale l'une de l'autre)
- Tu sais qu'il y a au moins une solution au problème ... et 5 éléments sont déjà disposés , à titre d'indice ou de contrainte ( ... je ne vois pas trop la différence entre indice et contrainte dans ce cas de figure !)

Déjà, la piste de faire des groupes de 2x2 me paraît très mauvaise. Au lieu d'avoir 256 éléments de base, tu te retrouves avec plusieurs milliers d'éléments de base... ingérable.

Pour moi, c'est du parcours d'arbre.

Prenons un cas un peu différent du problème donné : on n'a pas les 5 contraintes.
On va donc commencer par un coin : 256x4 options pour le coin en haut à gauche (0,0) : 256 pièces, et 4 orientations possibles pour chaque pièce.
- On choisit au hasard une de ces 1024 options pour la case (0,0) ( ... mais on garde au chaud les 1023 autres options )
- Puis pour la case (0,1), on a en gros une cinquantaine d'options
- Et encore une cinquantaine d'options pour la case (0,2)
- etc ...
C'est jouable,mais effectivement, le temps de parcours va être long.

Maintenant, on a une aide, c'est que 5 pièces sont déjà disposées.
Imaginons que l'on nous impose les pièces placées en (0,4), (1,3) , (1,5) , (2,4) et (2,6)
De façon évidente, on va poser en premier la seule et unique pièce qui peut aller en (1,4)
Puis on va chercher quelles pièces peuvent aller en (2,5) ... 3 cotés sont imposés, peu de pièces peuvent convenir
Puis on va chercher à remplir les pièces qui ont des contraintes sur 2 cotés ...
C'est la démarche pour limiter au mieux la taille de l'arbre.

Ca veut dire qu'il y a un premier travail à faire, quand on connait les 5 cases imposées : Classer les 251 cases restantes pour définir une fois pour toutes l'ordre dans lequel on va remplir le puzzle.
Ca va logiquement être un parcours plus ou moins en 'escargot'.

Quand 2 bords sont imposés, il y a statistiquement 2 ou 3 pièces qui conviennent. Ca fait un arbre qui grandit beaucoup moins vite à chaque étape ... mais quand même un nombre de combinaisons énorme à analyser.