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...

[yahiko]

Il me semble qu'avant de se perdre dans des considérations d'implémentations, il serait plus judicieux de poser l'algorithme pour résoudre le puzzle.

[souviron34]

Il me semble que c'est ce que j'essaie de faire plus haut, puisque justement je ne comprenais guère les problèmes de hashs et autres mémoire, à partir des pointeurs qu'il a mis en tête..



Mais je m'exprime sans doute mal..

[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.

[yahiko]

Il me semble que c'est ce que j'essaie de faire plus haut, puisque justement je ne comprenais guère les problèmes de hashs et autres mémoire, à partir des pointeurs qu'il a mis en tête..



Mais je m'exprime sans doute mal..

Ca s'adressait à l'auteur original du topic

Sinon, c'est un problème de combinatoire avec effectivement un arbre où chaque nœud correspond à une étape de construction du puzzle.
Chaque pièce du puzzle a 4 types de côtés possibles qu'on peut identifier par convention dans le sens horaire N, E, S, W, et chaque pièce a une orientation pour un agencement possible (et éventuellement partiel) du puzzle.

A la fin, chaque feuille de l'arbre correspond soit à une solution du puzzle, soit à un agencement incomplet du puzzle.

[souviron34]

- 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)

Ben c'est là que je suis pas d'accord ;-)

Si tu as classé les "couleurs" comme des lettres, et que tu as fait un tri lexicographique, tu as beaucoup moins de 50 à chaque fois...


Si la première posée est par exemple "aejm", on peut sans contrainte dire que les 2 premiers sont sur les bords.. Il faut donc trouver les pièces qui contiennent "j".. et les pièces qui contiennnent "m" , la liaison étant faite par les pièces qui contiennent et "j" et "m"..

Donc à mon avis le nombre de pièces à chaque étape est très réduit (je dirais à vue de nez au max une 12)

[kolodz]

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)

Oui, elles sont légèrement particulières, car elles ont leurs bords extérieurs grisés. Cela réduit les possibles pour les bords, mais ce n'est pas particulièrement intéressant par rapport à mon algorithme.

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..

Quand je recherches parmi les 256 pièces, il n'y a pas de problème de mémoire.
Je suis en accès direct sur les pièces :
Voici l'exemple suivant :

Je veux trouver les pièces solutions : je n'ai qu'à accéder à mon tableau :

Code Java :

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

1
2
3
4
5
6
/** déclaration **/
	//  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];
/** utilisation**/
//liste de mes solutions
int[] solutionDeLImage = cacheIdSolutions[14][15][9][16];

Dans ce cas, je suis en en O(4) pour trouver les pièces qui sont solutions.

C'est une variante de la solution qu tu présent, mais en beaucoup plus violant, car non récursif. Je saute simplement à l'index du tableau que je veux. Cependant, cette version est consommatrice en mémoire. Car, il faut que l'ensemble des cases de mon tableau existe. J'alloue l’équivalente d'un tableau de 331 776 cases mémoires.

La problématique d'un groupe de pièces :
Pour faire la même chose avec groupe de 2*2 la taille nécessaire est 110 075 314 176 cases mémoires (Largement au dessus du Téra).
De même le nombre de groupe de 2*2 est de 4 357 212, faire un algorithme qui a besoin de parcourir la collection systématiquement va être particulièrement lent.

Le trie, même si on trie les pièces en priorisant un certain ordre dans les contraints ceux du haut en premier. Si je dois faire un match qui implique le côté gauche et le côté droit. Le trie ne sera pas utilisable facilement. C'est d'ailleurs pour cela que j'ai une taille de 24(et non 23) sur mon tableau, car je peux dire contrainte libre pour tel emplacement.

Par rapport à l'algorithme de recherche de solution :
J'ai opté pour une solution assez simple et efficace :
Propagation par "heatmap".
L'initialisation :
Je place les pièces de base (indice et contraints). Puis, je regarde combien, il y a de possibilité pour chaque cases adjacentes.

Code Heatmap initial :

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
4	56	56	56	56	56	56	56	56	56	56	56	56	56	56	4	
56	XX	45	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	45	XX	56	
56	46	0	48	XX	XX	XX	XX	XX	XX	XX	XX	44	0	46	56	
56	XX	45	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	45	XX	56	
56	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	XX	44	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	45	0	42	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	XX	42	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	56	
56	XX	44	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	45	XX	56	
56	45	0	42	XX	XX	XX	XX	XX	XX	XX	XX	47	0	45	56	
56	XX	45	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	43	XX	56	
4	56	56	56	56	56	56	56	56	56	56	56	56	56	56	4

Voici le puzzle correspondant :

Code Version avec un emplacement impossible :

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
0	12	52	52	52	52	52	52	52	52	52	52	8	0	0	0	
0	43	44	XX	XX	XX	XX	XX	XX	XX	XX	XX	41	0	0	-1	
11	46	0	48	XX	XX	XX	XX	XX	XX	XX	XX	44	0	2	52	
52	XX	44	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	44	XX	52	
52	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	XX	43	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	44	0	41	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	XX	41	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	52	
52	XX	44	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	45	XX	52	
52	44	0	41	XX	XX	XX	XX	XX	XX	XX	XX	47	0	45	52	
12	XX	45	XX	XX	XX	XX	XX	XX	XX	XX	XX	XX	43	44	11	
0	12	52	52	52	52	52	52	52	52	52	52	52	12	0	0

Les XX correspondent à des cases, dont je ne calcule pas le nombre de pièces possible, car pas de contrainte sur celle-ci.
Les 0 correspondent à des pièces, où il y a déjà un pièce.

Cependant, cela demande de compter le nombre de pièces possibles à chaque itération. Dans le dernière cas, cela représente 73 recherches de contraintes. D'où la volonté de passé un un maillage plus grand (2*2). Où la validation se ferait 4 fois moins souvent (par rapport au nombre de pièces posées) et le nombre de recherche de contraintes seraient aussi réduit, car validé par groupe de 2*2.

Cordialement,
Patrick Kolodziejczyk.

[tbc92]

Ben c'est là que je suis pas d'accord ;-)

Si tu as classé les "couleurs" comme des lettres, et que tu as fait un tri lexicographique, tu as beaucoup moins de 50 à chaque fois...


Si la première posée est par exemple "aejm", on peut sans contrainte dire que les 2 premiers sont sur les bords.. Il faut donc trouver les pièces qui contiennent "j".. et les pièces qui contiennnent "m" , la liaison étant faite par les pièces qui contiennent et "j" et "m"..

Donc à mon avis le nombre de pièces à chaque étape est très réduit (je dirais à vue de nez au max une 12)

Pas d'accord.

J'ai posé une pièce au coin (0,0)
Le bord droit porte la lettre A par exemple.
Je cherche donc parmi les 255 autres pièces une pièce dont le bord gauche porte la lettre A ... soit effectivement une douzaine de pièces qui conviennent, puisque 23 lettres dans notre alphabet ( 255 / 23 )
Mais on a le droit de tourner les pièces.
On a donc statistiquement 4 * 255 /23 possibilités pour la 2ème pièce, si un seul bord est imposé.


MAIS !!!

Nouvelle information extrêmement utile : les bords ont un bord grisé.
Ca limite de façon considérable la taille de l'arbre.
Sans cette contrainte, on était sur des arbres avec 10^45 feuilles. Maintenant, on doit tomber à quelques millions au grand maximum.
On passe d'un problème quasiment insoluble à un problème raisonnable.

Et avec cette nouvelle information, c'est clair qu'il faut commencer par un coin, et chercher une solution pour tout le tour du puzzle.
On a 60 pièces à poser ... et le nombres de solutions pour disposer ces 60 pièces ne devrait pas dépasser 50 ou 100.

[souviron34]

Pas d'accord.

J'ai posé une pièce au coin (0,0)
Le bord droit porte la lettre A par exemple.
Je cherche donc parmi les 255 autres pièces une pièce dont le bord gauche porte la lettre A ... soit effectivement une douzaine de pièces qui conviennent, puisque 23 lettres dans notre alphabet ( 255 / 23 )
Mais on a le droit de tourner les pièces.
On a donc statistiquement 4 * 255 /23 possibilités pour la 2ème pièce, si un seul bord est imposé.

sauf si on a déjà pris en compte cette possibilité en ayant classé lexicographiquement, mais en gardant l'ordre des côtés..

Si on a classé les pièces par lexicographie, on se fout pas mal de l'ordre "supposé"... Il n'y a ni haut ni bas ni gauche ni droite, mais simplement 4 côtés.. Avec 4 lettres.

Je répète donc : si le bord droit de la pièce est A, tu ne cherches que parmi les pièces qui ont A, forcément en première place..

Mais au départ, les pièces ABCD, GAFH, MDJA ou DKLA seront toutes classées en tête par "A", en fait on aura dans l'ordre : ABCD ADKL AFHG AMDJ

C'est ce que je voulais dire plus haut..

Si donc la première pièce posée en (0,0) est AJMS, et qu'on la pose dans le sens où A est à droite (donc S en haut), alors on ne cherchera comme correspondance à droite que dans les pièces commençant par A et non utilisées.

MAIS !!!

Nouvelle information extrêmement utile : les bords ont un bord grisé.
Ca limite de façon considérable la taille de l'arbre.
Sans cette contrainte, on était sur des arbres avec 10^45 feuilles. Maintenant, on doit tomber à quelques millions au grand maximum.
On passe d'un problème quasiment insoluble à un problème raisonnable.

Et avec cette nouvelle information, c'est clair qu'il faut commencer par un coin, et chercher une solution pour tout le tour du puzzle.
On a 60 pièces à poser ... et le nombres de solutions pour disposer ces 60 pièces ne devrait pas dépasser 50 ou 100.

Tout à fait, je ne comprend pas pourquoi kolodtz rejette ça...

En plus, 256 - 60 - 5 : on a déjà plus que 191 pièces au lieu de 256 pour appliquer un algo "total".. soit environ une diminution de 25% de la taille du problème..

[Invité]

hello,

pas trop chaud pour l'escargot et l'exploration aux alentours des pièces spéciales.
m'est avis que chercher à trouver un coin, puis explorer en agrandissant le coin de carré en plus grand carré est plus efficient:
à chaque pièce ajoutée, on maximise le nombre de contraintes (par rapport aux degré de liberté)

Si on va en ligne droite type escargot, on ajoute une seule contrainte pour deux degré de libertés...

alors que par propagation, hormis les deux pièces du bord, on ajoute deux contraintes pour deux degrés de liberté!

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
 
1ere étape
xoo...
ooo
ooo
.
.
.
2eme étape
xxo...
xxo
ooo
.
.
.
 
3eme étape
xxx...
xxx
xxx
.
.
.

bref, le tengen est là pour faire joli, il sert pas à grand chose

[kolodz]

Petit update :

Voici a quoi ressemble la "heatmap" si celle-ci est réalise avec des bloques de 2*2 :

Code :

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

1
2
3
4
5
6
7
8
1312	4035	75627	75627	75627	75627	4517	1312
4326	5855	XXXX	XXXX	XXXX	XXXX	3134	4281
75627	XXXX	XXXX	XXXX	XXXX	XXXX	XXXX	75627
75627	XXXX	XXXX	237953	XXXX	XXXX	XXXX	75627
75627	XXXX	XXXX	5247	236044	XXXX	XXXX	75627
75627	XXXX	XXXX	XXXX	XXXX	XXXX	XXXX	75627
4436	5553	XXXX	XXXX	XXXX	XXXX	5544	4575
1312	4078	75627	75627	75627	75627	4871	1312

Celle-ci représente le nombre de possibilités pour chaque emplacement en fonction des contraintes connu.
Note : Celle-ci est probablement pessimiste, car je n'ai pas exclus certains cas impossible en réalité.

Cela étant toujours avec la même configuration :

Nouvelle information extrêmement utile : les bords ont un bord grisé.
Ca limite de façon considérable la taille de l'arbre.

En réalité, les bords sont un peu plus spécifique que ça :

• Côté extérieur grisé (valeur 0)
• Côté lié à un autre bord dessin spécifique (valeur 18 à 22)

Ce qui fait que les pièces internes varient seulement entre 1 et 17.
Au final, l'arbre reste énorme.

Sans cette contrainte, on était sur des arbres avec 10^45 feuilles. Maintenant, on doit tomber à quelques millions au grand maximum.
On passe d'un problème quasiment insoluble à un problème raisonnable.

Le puzzle a été conçu pour être insoluble à la base...

Voici le fichier CSV des pièces :
pieces.txt
La nomenclature est ID;TOP;LEFT;BOTTOM;RIGHT (inverse des aiguilles d'une montre)
La contraintes est :

• En I8 : pièce 139 le bas en haut.

Les indices sont :

• En C3 : pièce 208 la droite en haut.
• En C14 : pièce 255 la droite en haut.
• En N3 : pièce 181 la droite en haut.
• En N14 : pièce 249 le haut en haut.

Note : Colonnes de A à P et les lignes de 1 à 16.

Comme ça on parlera tous en ayant les informations si nécessaire.

En plus, 256 - 60 - 5 : on a déjà plus que 191 pièces au lieu de 256 pour appliquer un algo "total".. soit environ une diminution de 25% de la taille du problème..

Car, même avec ces réductions et un algorithme capable de placer 8 millions de pièces à la minutes le pourcentage estimé réalisé en une journée est de 1 sur 10⁵².
Et quand je dis que je ne prends pas en compte. C'est simplement que ce n'est pas un cas spécifique dans mon algorithme.

Avant de placer une pièce, celui-ci compte le nombre de pièce possible pour l'ensemble des case vides du puzzle. Pour obtenir les deux informations suivantes :

• Si il y a un endroit où on ne peux pas poser de pièces
• L'endroit où il y a le moins de pièces à poser.

Ainsi, dans les 4 premières itérations les coins sont directement posés. Cependant, une fois quelques pièces posées, il n'est pas rare qu'il soit plus rentable de poser une pièce "normal" qu'une pièce "bord".

Voici a quoi ressemble l'arbre de décision après 1 heures, si il y a 24 joueurs (threads) dessus qui jouent chacun l'une des combinaisons possibles les coins. (Dans la version une pièce par une pièce)

Rouge : Non fait (branche non exploré)
Vert : Fait et non solution (branche exploré et réduite).
Bleu : En cours de calcul.
Chaque nœud représente une pièce posé. L'arbre va de la droite vers la gauche. Chaque branche d'un nœud représente le nombre de pièces possibles pour le puzzle à l'emplacement ayant le moins de possibilité.
Le premier nœud est le nœud racine, représentant les conditions initiales avec les 5 pièces indices déjà posées.

J'espère que ce graphique est suffisamment parlant pour exprimé la problématique que j'ai.

Cordialement,
Patrick Kolodziejczyk.

[tbc92]

Petit changement sur les contraintes ... mais qui change drastiquement la nature du problème !!!!

J'avais fait quelques simulations sur cette base :
- Pour les pièces du bord, le bord est de couleur 0, les 3 autres cotés sont de couleur 1 à 22
- Pour les pièces du centre, les 4 cotés sont de couleur 1 à 22.
Avec ces contraintes, ça donnait pour remplir un carré de 9 cases dans un coin :

Nbre de possibilités pour le coin A1 : 4
Nbre de possibilités pour la case A2 : 56/22 soit en combinant A1 et A2 : 10,18 possibilités en moyenne.
Nbre de possibilités pour la case B1 : 55/22 ... total 25,45
Nbre de possibilités pour la case B2 : 191/22/22 Soit, en combinant A1 A2 B1 B2 : 10,04
Et en continuant, on arrivait à (en moyenne) 9,1 combinaisons pour le carré A1 / C3

Avec les nouvelles informations, ce n'est plus 9 combinaisons, mais un peu plus de 16000 !!!

Avec les hypothèses que j'avais, mon programme test n'avait toujours pas trouvé la solution au bout de quelques heures. Alors, avec ces nouvelles hypothèses, je n'essaie même pas.

[kolodz]

C'est un peu pour ça que je demande un avis pour pouvoir faire une indexation des pièces en 2*2 ! En plus de réduire le nombre d'itération nécessaire pour le même résultat. J'ai constaté un défaut dans la pause des pièces une par une.
En effet, mon algorithme a tendance à laisser un espace de deux pièces non remplit, car n'étant pas le mouvement optimal pour une seule pièces. Cependant, cela laisse des contraintes très fortes ont utilisé, il y a très peu de combinaisons pour un bloque de 2*2 contrains par deux côtés complets. (encore plus quand 50% des pièces sont déjà posées.)

[tbc92]

Si tu crées des groupes de 2x2 en amont du traitement, tu vas par exemple faire un groupe avec les pièces (1,2,3,4), parce qu'il y a moyen de combine ces 4 pièces pour faire un carré.
Mais la pièce 1 pourrait aussi bien être associée avec les pièces (5,6,7)
Tu ne peux pas décider arbitrairement au début que tu vas choisir (1,2,3,4) plutôt que (5,6,7,8)
Et donc au lieu d'avoir 256 pièces, tu as 10000 ou 20000 pièces 'potentielles'
Pour moi, ça complique énormément l'algorithme... et ça n'arrange rien en performance.


D'autre part, je ne comprend pas ce que tu veux dire par :
En effet, mon algorithme a tendance à laisser un espace de deux pièces non remplit, car n'étant pas le mouvement optimal pour une seule pièces.

Pour moi, il faut ABSOLUMENT imposer un ordre de remplissage.
Par exemple commencer par A1 A2 B1 B2 C2 B3 C1 A3 A16 A15 B16 ...

En commençant ainsi, au moment de faire C1, il y a relativement peu de pièces qui peuvent convenir, puisqu'on a des contraintes sur 3 côtés.
C'est à priori le meilleur moyen d'éliminer au plus vite les branches qui conduisent à des impasses.

Il ne faut pas prendre les pièces 1 par 1, en se demandant où cette pièce peut être posée.
Il faut prendre une case (pas au hasard mais dans l'ordre décrit ci-dessus), et chercher quelles pièces peuvent être posées sur cette case.

[kolodz]

Les groupes de deux que je pré-calcul sont tous valide ! C'est donc des permutations que j'aurai de toute manière réalisé. Cela ne change donc le nombre possibilités testé. Cela a même l'effet inverse. La pièce A peut-être solution pour un emplacement mais ne pas avoir de carré 2*2 valide.

Pour moi, il faut ABSOLUMENT imposer un ordre de remplissage.
Par exemple commencer par A1 A2 B1 B2 C2 B3 C1 A3 A16 A15 B16 ...

L'ordre de remplissage statique est un aberration en terme d'élimination de solution. Le but de du remplissage dynamique est de réduire drastiquement le nombre de possible le plus tôt possible. Je remplis donc les emplacements qui ont le moins de possibilité systématiquement. Cela pour effet de rendre certains bord rares les rendant encore plus prioritaires.
Si tu regarde mon dernier graphe, je me retrouve principalement avec des nœuds ayant moins de 5 enfants et très rarement au dessus de 8. Et c'est très important. Plus tu as d'enfants, plus tu as de branche à vérifier qui vont générer encore d'autres branches.

J'ai réfléchie pendant plus d'un an sur l'algorithme qui place les pièces, celui-ci est le meilleur de tout ceux que j'ai testé. Tant au niveau de la rapidité que du nombre de coup joué pour éliminer une branche.

Et donc au lieu d'avoir 256 pièces, tu as 10000 ou 20000 pièces 'potentielles'

Le chiffre exacte est 4 357 212. C'est bien ce que je dis dans mon premier post.
Dont 5 248 angles, 302 508 des bords (angles exclu) et donc 4 054 704 milieux. Sachant que dans ce compte, on a bien sûr les rotations.
Cependant dans la version alpha de mon code en 2*2, montre un potentiel supérieur par rapport à la version 1*1 !
Statistiquement, pour une pièces du milieu, si on deux bords, on a uniquement 65 possibilités, sachant que beaucoup sont exclu dès qu'on pose un pièce. Ce qui est relativement peu. En particulier quand tu favorise les emplacements ayant le moins de possibilités et l'indexation est encore jouable.