Discussion :

[souviron34]

Je m'excuse, mais je ne comprend toujours pas..

J'ai bien l'impression que tu es parti avec "pourquoi faire simple alors qu'on peut faire compliqué"..

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.

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.

L'ensemble des cases du tableau est 256, je ne sais pas comment tu peux atteindre 331 776..

Il ne PEUT PAS y avoir 4 054 704 milieux..

Peut-être que si tu nous fournissais le pointeur sur le puzzle, ou les pièces, on pourrait essayer..

Mais là, il faut qu'on parte de ton hypothèse/pensée, et je pense que cette hypothèse/pensée est fausse.. ou abominablement compliquée..

Je ré-itère ma suggestion plus haut :

• 5 arbres à développer en parallèle, avec au max chacun 256/4 pièces / items
• pièces rangées par ordre lexicographique. au max 21 essais possibles par emplacement.

Mais bon, vu que je ne comprend pas ton raisonnement...


Quant à ton problème d'indexation, si tu as 8 variables qui prennent chacune 23 valeurs, ça tient sur 16 bits. Mais, si je reprend encore les caractères, FORCEMENT ton groupe de 2*2 sera caractérsé par une liste de 8 lettres, dans l'ordre N->E->S->O... Je ré_itérerais la suggestion d'un ordre lexicographique pour accélérer et limiter la recherche des autres blocs correspondants..

[kolodz]

Il ne PEUT PAS y avoir 4 054 704 milieux..

Il y a 4 054 704 groupes (G2) de 2 par 2 pièces possibles qui n'inclue pas une pièces bords ou coin.

Un groupe G2 est une combinaison de 4 pièces qui forment un carré de 2 sur 2. Le nombre précédemment cité est le nombre de combinaison différentes qu'il est possible d'avoir avec les 255 pièces et qui sont valides.

Il n'est donc pas possible d'avoir 4 054 704 milieux en même temps, mais on peut les construire.

Peut-être que si tu nous fournissais le pointeur sur le puzzle, ou les pièces, on pourrait essayer..

Dans ce poste , je donne les pièces et les informations que j'ai !
Le fichier .txt pour les pièces et juste après la configurations des pièces indices et de la pièce contrainte. (Et la nomenclature du fichier .txt)
Libre à toi de les utiliser !

Mais là, il faut qu'on parte de ton hypothèse/pensée, et je pense que cette hypothèse/pensée est fausse.. ou abominablement compliquée..

Mon approche est compliquée. Ça fait un peu plus d'un an que je code/recherche autour de ce problème. Ma vision du problème et de la solution à apporter a évolué avec le temps.

Quant à ton problème d'indexation, si tu as 8 variables qui prennent chacune 23 valeurs, ça tient sur 16 bits. Mais, si je reprend encore les caractères, FORCEMENT ton groupe de 2*2 sera caractérsé par une liste de 8 lettres, dans l'ordre N->E->S->O... Je ré_itérerais la suggestion d'un ordre lexicographique pour accélérer et limiter la recherche des autres blocs correspondants..

Oui, mais cette solution à un défaut d'ordre prédéfinit. Supposons que l'on décide de trier les G2 d'en haut à droit, puis dans le sens anti-horaire. Si on veut trouver les G2 possible avec une contrainte en bas. On est bon pour faire toute la liste.
De même dans le cas où on a une contrainte sur les côtés du haut et les côtés du bas.

Encore une fois, ce n'est pas la caractérisation du groupe G2 qui me pose problème, c'est d'avoir un accès rapide en fonction d'une contrainte donnée.
Exemple :
Quelles sont les G2 ayant pour gauche 10/11 et pour droite 12/13 ?
Quelles sont les G2 ayant pour top 0/0 et gauche 18/12 ?

La solution que tu propose, c'est ce que j'avais avec le G1, il y a quelques mois. Ca fait le job, certes, mais c'est incroyablement lent par rapport à un accès direct. C'est d'ailleurs ce que j'explique dans mon premier post et dans mon blog.
Il est beaucoup plus rapide de réalisé l'opération suivante :

Code java :

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

1
2
// Recherche des pièces ayant à gauche 10 et à droit 12.
int[] listeDesPiecepossible = cacheIdSolutions[FREE][10][FREE][12];

Que d'avoir une liste ordonné et de faire un parcours de celle-ci.

Bien sûr pour du G2, ce n'est pas viable pour les raisons que j'explique dans le premier post. Du moins, de manière brute de fonderie.

[souviron34]

J'ai pensé à un truc :

en plus de tes 5 pièces, tu n'as que 4 coins.. Ces coins forcément il y a 16 possibilités seulement..(les coins ont 2 bords grisés, donc ils n'ont pas 4 rotations comme les autres pièces : ils n'ont que 4 emplacements chacun)

Donc tu as 16 combinaisons avec 9 pièces fixes. (et en plus, d'après ce que tu dis, les bords n'ont que 5 possiblités de liaisons)

ça réduit encore...


En fait, je pense comme galérien69 qu'en partant des coins et des bords, surtout avec ça (5 posisiblités de liaison seulement), ça devrait être beaucoup plus faisable..

En fait, les 5 "contraintes" seront là pour éliminer des arbres..

[kolodz]

Les permutations des coins c'est 4*3*2*1 = 24, d'où l'image avec les 24 threads pendant une heures. Ca réduit certes les choses. mais comme le montre le graphe, ce n'est pas suffisant.

Je te redonne le graphique pour information :
Pièce jointe 169109

(et en plus, d'après ce que tu dis, les bords n'ont que 5 possiblités de liaisons)

C'est plus, car il y a 60 pièces bords et ceux-ci ont seulement 5 formes différentes, ce qui fait une moyen de 12 pièces possibles.

[kolodz]

J'ai trouvé une solution de contournement pour avoir un index par rapport à 8 variables qui me semble viable et efficace. Celui-ci ce base sur des permutations de plusieurs index à 4 variables.

Pour rappel, l'idée est d'avoir un index pour une pièce ayant 2 contraintes par côté et 4 côtés nommé comme suit :

Code java :

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

1
2
3
4
5
6
7
8
9
//Côté ciblé puis sur la sous partie visé (ordre anti-horaire)
int TopRight;
int TopLeft;
int LeftTop;
int LeftBot;
int BotLeft;
int BotRight;
int RightBot;
int RightTop;

J'ai donc crée 6 caches sur 4 variables (2 côtés) :

Code java :

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

1
2
3
4
5
6
List<G2>[][][][]indexG2TopLeft;
List<G2>[][][][]indexG2BotRight;
List<G2>[][][][]indexG2TopBot;
List<G2>[][][][]indexG2LeftRight;
List<G2>[][][][]indexG2LeftBot;
List<G2>[][][][]indexG2RightTop;

Lors de la recherche :

Code java :

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
public static List<G2> getG2For(int topRight, int topLeft, int leftTop, int leftBot, int botLeft, int botRight, int rightBot, int rightTop) {
	if (topRight != FREE && topLeft != FREE && leftTop != FREE && leftBot != FREE) {
		if (botLeft == FREE && botRight == FREE && rightBot == FREE && rightTop == FREE) {
			return indexG2TopLeft[topRight][topLeft][leftTop][leftBot];
		}
		// Cela évite d'avoir des merge de liste trop long quand il y a trop de dégrée de liberté. Donne des listes de 800 éléments max à merger à la place de 25000.
		if(botLeft == FREE && botRight == FREE ){
			return mergeListG2(indexG2TopLeft[topRight][topLeft][leftTop][leftBot], indexG2LeftRight[leftTop][leftBot][rightBot][rightTop]);
		}
		// La réciproque du teste d'avant.
		if(rightBot == FREE && rightTop == FREE ){
			return mergeListG2(indexG2TopLeft[topRight][topLeft][leftTop][leftBot], indexG2LeftBot[leftTop][leftBot][botLeft][botRight]);
		}
		// Si on a vraiment besoin de faire le merge sur les deux liste
		return mergeListG2( indexG2TopLeft[topRight][topLeft][leftTop][leftBot],indexG2BotRight[botLeft][botRight][rightBot][rightTop]);
	} (
	// Le reste est une suite de permutations équivalentes pour les autres côtés.
	// Dans mon implémentation si il n'y a pas au moins 4 contraintes (2 côtes), il y a une exception, car le résultat est sans intérêt pour ma problématique. Mais, la plus part des cas son traitable simplement et rapidement. (ie : Pas de merge lourd.)
}

La méthode de merge n'est pas optimal pour le moment. Mais les merges réalisés se font sur des deux listes de 800 éléments maximum, avec en général une liste sous les 100.
A savoir que cette méthode de sélection est tellement rapide qu'elle prend pour le moment 2% du CPU, quand la vérification de la liste retournée prendre +80% du CPU. Simplement pour vérifié, si les éléments de la liste n'ont pas une pièces déjà posée ! (Cela est ma prochaine optimisation d'ailleurs)

Sans l'ajout des cas où on réutilisé les contraintes d'un côté pour ajouter les contraintes d'un troisième côté, les performances se détériorent de manière drastique à cause du merge !

Note : Il est possible que je pense à une version encore plus complexe pour avoir un index rapide sur 16 contraintes (4 côtes avec 4 contraintes = G4), mais pour le moment, il me reste à optimiser tout ce qu'il y a autour pour avoir quelque-chose de propre.
Note² : Pour le puzzle la complexité où l'algorithme rame passe de 10⁴² à 10³² avec l'utilisation de cette méthode. c'est donc un gain dans tout les cas !

Cordialement,
Patrick Kolodziejczyk.