Discussion :

[pseudocode]

Si quelqu'un a fait les pièces avec les mêmes schémas que SOMA du Bedlam je pense qu'avec mon programme une solution est pliée en moins d'une seconde.

Sauf erreur, j'ai défini les pièces comme cela:

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
 
A : {0,1,0},{1,1,0},{2,1,0},{2,2,0},{1,0,0}
B : {0,1,0},{1,1,0},{2,1,0},{1,2,0},{1,0,0}
C : {1,0,0},{2,0,0},{0,1,0},{1,1,0},{0,2,0}
D : {1,0,0},{0,1,0},{1,1,0},{0,2,0},{0,2,1}
E : {0,0,0},{0,1,0},{1,1,0},{0,1,1},{0,2,0}
F : {1,0,0},{0,1,0},{1,1,0},{0,1,1},{0,2,0}
G : {0,0,0},{0,1,0},{0,2,0},{0,1,1},{1,1,1}
H : {0,0,0},{0,1,0},{0,2,0},{0,0,1},{1,0,0}
I : {0,0,0},{0,1,0},{0,2,0},{1,0,0},{0,2,1}
J : {0,0,0},{0,1,0},{0,2,0},{1,2,0},{1,2,1}
K : {1,0,0},{0,1,0},{1,1,0},{0,1,1},{0,2,1}
L : {0,0,0},{1,0,0},{0,1,0},{0,1,1},{0,2,0}
M : {0,0,0},{1,0,0},{1,0,1},{0,1,0}

[Ulmo]

Euh, la pièce L aussi, si je ne me trompe

La pièce L est plane, elle est donc superposable à son image-miroir.

Une solution-miroir c'est encore un cube mais il n'est pas constitué des 7 mêmes pièces physiques que les 7 pièces du Soma. On peut engendrer l'image par une symétrie axiale au moyen d'une simple rotation. Par contre il n'y a pas de moyen physique pour engendrer une image-miroir.

Tu n'obtiens pas la même solution, mais une autre solution (valide) que tu as déjà eu / auras autrement.

J'essaye de donner un exemple, mais sans dessin cela demande un effort certain au lecteur.

Voici les 3 étages du cube :
PPL
PBL
BBL

PTL
ABV
AAV

TTT
AZZ
ZZV

Je prend le symétrique droite/gauche :
LPP
LBP
LBB

LTP
VBA
VAA

TTT
ZZA
VZZ

On peut vérifier que toutes les pièces sont valables, sauf que la pièce A a maintenant la forme de la pièce B et vice versa.

[SpiceGuid]

J'essaye de donner un exemple, mais sans dessin cela demande un effort certain au lecteur.

Au contraire, c'est très clair.

On peut vérifier que toutes les pièces sont valables, sauf que la pièce A a maintenant la forme de la pièce B et vice versa.

Tu n'obtiens pas une solution symétrique pour le même puzzle, ce que tu obtiens c'est une solution pour un puzzle symétrique.
Pour moi la symétrie a une interprétation physique: les solutions symétriques du Soma ce sont celles que tu peux obtenir sans démonter le cube.

[Ulmo]

Tu n'obtiens pas une solution symétrique pour le même puzzle, ce que tu obtiens c'est une solution pour un puzzle symétrique.
Pour moi la symétrie a une interprétation physique: les solutions symétriques du Soma ce sont celles que tu peux obtenir sans démonter le cube.

OK, c'est une différence de définition alors.

Pour information, le nombre de 240 solutions indiqué sur la page du défi prend en compte les symétries planes (c'est à dire qu'il compte mes 2 exemples comme une seule solution) ; c'est pourquoi j'étais si catégorique.

[Daxou31]

Excellente idée ça !! (C'est ce que je fais ici aussi )

Idem ^^

Et merci pour les pièces, je m'y pencherais quand j'aurais plus de temps, un peu de repos ce soir

[JeitEmgie]

Code :

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

1
2
3
4
5
6
7
8
 
time ./build/Release/Soma_Test soma.pieces.txt 001-024/cube.txt 
11520 (nombre solutions)
0.306261 s (solve all)
 
real	0m0.387s
user	0m0.311s
sys	0m0.005s

306 ms pour la résolution complète proprement dite (les 11520 solutions mais sans I/O hors lire les data et les 2 lignes "(nombre solutions)" et "(solve all)" ),
le reste pour la lecture des données et la phase de préparation (calcul des rotations des pièces et de leurs positions possibles dans la forme cible)

Constat quant aux optimisations possibles :

a. le problème du Soma est trop petit : toutes les optimisations intelligentes classiques (couvertures, parité, …) conduisent à un allongement du temps de calcul.

la seule optimisation qui aboutisse au meilleur résultat est spécifiquement liée à l'implémentation choisie : l'essentiel des tests se faisant sur des std::bitset<>, il a été constaté que 35% du temps de calcul de la routine de résolution est passé uniquement dans les opérations liées à la manipulation des std::bitset<> (booléennes ou allocations temporaires - les 65 autres % de la routine de résolution sont distribués dans des fonctionnalités dont aucune ne dépasse 2% de la routine…) et que ce temps est directement proportionnel à la taille du bitset qui, si N est la taille de l'espace, vaut (N+1)^3.
Comme dans l'énoncé N vaut 10 => nous avons donc 1331…
réduire cette taille au parallélépipède (ou au moins au cube) englobant de la forme cible est la seule optimisation qui jusqu'à présent apporte quelque chose (donc pour le cube on passe de 1331 à 64 bits…).
Le temps de calcul s'améliore dans une proportion du même ordre (20x moins de bits et 25x plus rapide…) et on aboutit au résultat ci-dessus.

(Le seul hic est que std::bitset<> est statique… il faudrait donc passer à un dynamic_bitset…)

b. en ce qui concerne l'optimisation de parité, le simple fait de traiter les pièces dans l'ordre imposé par ce test (la #1 ou V d'abord et sans pour autant activé le test de parité lui-même…) plutôt que dans l'ordre croissant de positions possibles dans la forme ralentit le résultat…

[Zwiter]

si N est la taille de l'espace, vaut (N+1)^3.

Je ne saisi pas la notion de +1.
En codant cela avec 10^3 bits, on envisage deja toutes les positions, non ?

[JeitEmgie]

Je ne saisi pas la notion de +1.
En codant cela avec 10^3 bits, on envisage deja toutes les positions, non ?

on code oui… mais il "faut" une rangée blanche autour de l'espace de travail pour les tests des positions possibles des pièces dans la forme cible… sinon on a des faux positifs (grosse cata…)…
car ce test se fait simplement en décalant à chaque étape la représentation de la position de la pièce sous forme de bitset…
sans la rangée blanche : les bits correspondant à (N,y,z) et (0,y+1,z) seraient adjacents dans le bitset et donc il faudrait faire des boucles imbriquées pour tester la condition de bord… avec la rangée vide on peut faire une seule boucle et même si l'on teste plus de "positions" que nécessaire cela s'avère en fin de compte plus rapide…
mais pour le moment, ce n'est pas fondamental dans la mesure où ce code ne s'exécute que dans la phase préparatoire…
il est probable que pour un bedlam on pourrait le réutiliser dans le cadre des optimisations de type "couvertures"… ce qui alors serait marginalement payant…

[SpiceGuid]

Pour information, le nombre de 240 solutions indiqué sur la page du défi prend en compte les symétries planes (c'est à dire qu'il compte mes 2 exemples comme une seule solution) ; c'est pourquoi j'étais si catégorique.

Alors j'avais mal interprété le chiffre, dans ce cas chacune des 240 solutions du Soma donne lieu à 48 solutions symétriques.

Pour ce qui est d'éviter de parcourir l'ensemble de ces solutions chirales je ne vois pas de méthode suffisamment simple pour en valoir la peine puisque cette chiralité n'existe pas dans le cas du Bedlam cube.

En modifiant la stratégie d'exploration, mon algo résout le Cube de Bedlam en 400 ms

Une optimisation sans doute efficace du backtracking c'est de réduire agressivement l'ensemble des pièces, chaque fois que l'on insère une pièce on peut anticiper en éliminant toutes celles qui l'intersectent, on les réintroduira lors du retour arrière.

[JeitEmgie]

Une optimisation sans doute efficace du backtracking c'est de réduire agressivement l'ensemble des pièces, chaque fois que l'on insère une pièce on peut anticiper en éliminant toutes celles qui l'intersectent, on les réintroduira lors du retour arrière.

exprimé comme cela, çà me semble avoir un petit goût de tourner en rond :

une pièce est placée justement parce qu'elle n'intersecte pas celles qui sont choisies…
anticiper sur ce test n'est-il pas redondant ? … les positions des pièces suivantes qui intersectent celles déjà placées sont éliminées par le test de base du choix de la position de la pièce courante…

par contre, quand on a une pièce potentiellement valide (qui n'intersecte pas celles déjà placées), vérifier que l'ensemble des positions possibles des pièces suivantes couvrent l'espace qui resterait si l'on place effectivement la pièce que l'on teste, permet de l'éliminer si le test n'est pas vérifié… (est-ce que l'ensemble des positions des pièces qui restent couvrent le nouvel espace non encore couvert…)

d'autant plus qu'une fois qu'on a choisit l'ordre de placement des pièces, l'ensemble des cellules couvertes par les positions possibles pour les pièces suivantes est calculable une fois pour toute dans la phase de préparation…

l'autre test de couverture étant de regarder si pour la pièce que l'on veut placer, toutes les pièces non encore placées ont au moins une position qui n'intersecte pas le nouvel ensemble potentiel de cellules remplies… (est-ce qu'on peut placer toutes les autres si on place celle-ci…)… (mais ici en profiter pour garder les sous-listes de positions "intéressantes" peut rejoindre l'idée originale d'anticipation dans le sens que si les tests sont coûteux on a tout intérêt à ne pas les faire 2x… à condition que le "garder" ne soit pas plus coûteux que le test lui-même…)

et comme dit plus haut : dans le cas du soma, ces améliorations n'améliorent pas (toujours) le benchmark… mais cela dépend aussi du langage… il est probable qu'une implémentation en langage interprété bénéficiera plus de ces améliorations…

[pseudocode]

Une optimisation sans doute efficace du backtracking c'est de réduire agressivement l'ensemble des pièces, chaque fois que l'on insère une pièce on peut anticiper en éliminant toutes celles qui l'intersectent, on les réintroduira lors du retour arrière.

Ce n'est pas ce que j'ai fait. je n'ai pas fait de traitement supplémentaire dans l'algo de backtracking. J'ai changé la stratégie de recherche : mon espace d'exploration n'est plus l'ensemble des pièces possibles.

[SpiceGuid]

Est-ce que mon test est redondant
Quand je dis anticiper je veux dire faire le test d'intersection au plus tôt, pas dupliquer ce test.
Il ne s'agit pas de refaire un test d'intersection avant insertion, c'est inutile si ça a déjà été fait.

Est-ce que mon idée tourne en rond
Evidemment si on ne faisait que redistribuer le même nombre de tests ça ne changerait rien du tout.
L'avantage de retirer une pièce du jeu disponible c'est que le test d'intersection a lieu une seule fois.
Dans le cas contraire la pièce reste en jeu et son intersection doit être testée un nombre de fois arbitrairement grand.
En retirant plus de pièces du jeu disponible on accélère la réduction du facteur de branchement.

à condition que le "garder" ne soit pas plus coûteux que le test lui-même…

Retirer/réintroduire c'est un pop/push, c'est une opération de pile qui peut se faire en temps constant. On peut l'implanter ou bien à l'aide d'une liste doublement chaînée ou bien à l'aide d'un tableau et d'un curseur :

• à gauche du curseur les pièces encore en jeu
• à droite du curseur les pièces hors-jeu
• pour mettre une pièce hors-jeu on l'échange avec la pièce en jeu la plus à droite et on déplace le curseur d'une case à gauche
• pour remettre n pièces en jeu il suffit de déplacer le curseur de n cases à droite

[plegat]

Bon, ça fait un petit moment que ça n'a pas bougé ici...

J'ai repris mon algo, qui était beaucoup trop complexe à force de chercher à optimiser, et je suis revenu à une bête récursion.

Respectivement fichier/nb de solution(s)/temps (en sachant que je n'ai demandé qu'une seule solution pour la résolution), d'après les fichiers fournis par monnomamoi sur l'autre fil:

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
 
001.txt	1	140 ms
002.txt	1	16 ms
003.txt	1	688 ms
004.txt	1	1187 ms
005.txt	1	5515 ms
006.txt	1	3156 ms
007.txt	1	2328 ms
008.txt	1	188 ms
009.txt	1	468 ms
010.txt	1	78 ms
011.txt	0	21016 ms
012.txt	0	1172 ms
013.txt	1	500 ms
014.txt	1	531 ms
016.txt	1	406 ms
017.txt	1	31 ms
018.txt	1	812 ms
019.txt	0	4515 ms
020.txt	1	688 ms
021.txt	1	157 ms
023.txt	1	907 ms

avec une temps de 100 ms environ pour le cube.

Les résultats ne sont pas trop mauvais à mon goût, hormis pour les problèmes sans solution qui peuvent parfois être un peu long à détecter.

Donc je considère la partie programmation terminée pour moi, je vais m'occuper de la doc maintenant. Et me faire une sortie graphique pour le fun, mais que je ne livrerai pas (par contre j'ai mis un flag pour bedlam )

[Daxou31]

Respectivement fichier/nb de solution(s)/temps

Tu es sur ?
Tu n'as qu'une seule solution à chaque fois ...

[plegat]

Tu es sur ?
Tu n'as qu'une seule solution à chaque fois ...

Respectivement fichier/nb de solution(s)/temps (en sachant que je n'ai demandé qu'une seule solution pour la résolution)

J'ai un flag en ligne de commande pour préciser si on souhaite toutes les solutions ou non (auquel cas on s'arrête à la première si le problème est résolvable)

Par contre avoir des fichiers à 0 solution, ça m'a interpelé... et j'ai vu que j'oubliais quelques transformations sur mes pièces. Donc après correction (et toujours avec arrêt à la première solution trouvée):

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
 
001.txt	1	171 ms
002.txt	1	16 ms
003.txt	1	797 ms
004.txt	1	1641 ms
005.txt	1	7593 ms
006.txt	1	515 ms
007.txt	1	12031 ms
008.txt	1	360 ms
009.txt	1	250 ms
010.txt	1	78 ms
011.txt	1	4656 ms
012.txt	1	563 ms
013.txt	1	500 ms
014.txt	1	813 ms
016.txt	1	156 ms
017.txt	1	16 ms
018.txt	1	969 ms
019.txt	1	2750 ms
020.txt	1	1203 ms
021.txt	1	203 ms
023.txt	1	62 ms

cube en 188ms, les 11520 solutions en 3'04" (vu que c'est hors défi, je me demande si je vais chercher à améliorer...)

[TresNulDev]

Hé oui Plegat, c'est encore moi (un vrai boulet!). Voulez-vous bien m'expliquer comment vous faites vos benchmarks s'il-vous-plaît?

[plegat]

Voulez-vous bien m'expliquer comment vous faites vos benchmarks s'il-vous-plaît?

Vous pouvez me tutoyer cher TresNulDev

Démarrage du chrono au début de la résolution, et arrêt en fin de résolution. Tout le reste n'est pas chronométré (lecture du fichier de données, préparation du problème et préparation des pièces).
Si je dois tout compter, avec le temps de démarrage de la JVM ça va se compter en secondes! Ou alors je mets en place une procédure pour optimiser tout ça.

C'est juste à titre d'information... de toute façon je tourne avec une antiquité du début du siècle.

[TresNulDev]

Merci Plegat de ta réponse (je te tutoie comme tu me l'as permis!). J'ai compris le principe mais je ne savais pas que tu faisais ton projet en Java, désolé. Moi je le fais en C++; j'ai lu quelque part qu'il ne fallait pas utiliser les fonctions de gestion du temps issues du langage C (<time.h> en C, <ctime> en C++) pour faire des benchmarks. Saurais-tu (toi ou quelqu'un d'autre...) me conseiller une fonction qui me permettrait de chronométrer précisément, sachant que je programe sous Windows XP? Merci.

[dingoth]

J'ai un bug dans mon algorithme : je ne trouve que 4320 solutions pour le cube. Aussi, afin d'avoir de quoi comparer pour réparer le bug, est-il possible que quelqu'un me dise si l'un des fichiers mentionnés ci-dessus n'a qu'une seule solution ? Si ce n'est pas le cas, je vais tenter de faire un puzzle avec une seule solution, genre en écartant toutes les pièces et de leur filer une unique place. Merci !

[plegat]

J'ai un bug dans mon algorithme : je ne trouve que 4320 solutions pour le cube.

Ca me rappelle quelque chose ça!

As-tu vérifié que toutes les positions et orientations de pièces étaient bien explorées? Je simplifiais un peu trop les possibilités d'orientations dans mon premier algo, et il me sortait également dans les 4000 solutions...