Discussion :

[SpiceGuid]

Le fil de discussion pour les stratégies de résolutions du cube de SOMA et les performances de vos solutions au 1ier défi inter langage.
Autant que possible essayez de respecter le cadre inter langage du défi, afin que chacun puisse suivre votre argumentation, quelque soit son langage de prédilection.

Commençons par un petit sondage :

1. votre algorithme est-il du type brute force ? avec ou sans backtracking ?
2. quels étaient les autres algos possibles ?
3. pourquoi avoir choisi celui-ci ?
4. votre temps pour trouver une solution du Soma
5. votre temps pour trouver toutes les solutions du Soma
6. le point fort/faible de votre approche
7. cette approche vous facilite-t-elle la démonstration demandée ?
8. comment améliorer la performance et attaquer de plus gros cubes comme le http://en.wikipedia.org/wiki/Bedlam_cube ?

[ilellouc]

Bonjour,

je me lance :

1. Algorithme de Brute Force sans backtracking.
3. Pour le moment c'est le seul que j'ai ^^
5. J'ai pas fais encore beaucoup de test de vitesse, mais en gros 4 min pour toutes les solutions.
6. Faible : C'est lent et je suis débutant !

[phymbert]

Bonjour à tous,

1 - Backtracking
2 - bruteforce / backtracking + parité
3 - Le plus simple
4 - 1 secondes
5 - 77 secondes
6 - J'y réfléchi
7 - Oui
8 - parité

Je rajoute d'autre questions :

9 - Combien de solution trouvez-vous au cube de soma ?
10 -Combien de solution trouvez-vous au puzzle valide proposé dans l'explication du défi ? (Moi 7)
11 - En combien de temps votre algo determine si le puzzle invalide proposé dans l'explication du défi est irréalisable ? (Moi 0,1 seconde)

Bon courage à tous!

Pierrick

Update du 23/09:

Histoires de ne pas laisser de fausses infos, je reviens sur mes propos...

L'algo précédent ne calculait pas toutes les possibilités pour toutes les pièces (merci à Ulmo pour le 240*48 = 11520):

1 - Backtracking
2 - Bruteforce / ilots / parité
3 - Le plus simple
4 - 371ms
5 - 235s
6 - Recherche incrémentale des solutions par pièce
7 - Oui
8 - ilots / parité
9 - 11520
10 - 28
11 - 157ms

12 - Quel est votre processeur ?
12 - Core2 2,1GHz 2,1GHz

Bonne continuation,

Pierrick

[plegat]

Je viens de finir mon premier test, donc ce sont des réponses temporaires avant optimisation/nettoyage/tests plus poussés (techno Java 6 sans lib hors jdk):

1-brute force+backtracking
2-sais pas... j'ai récupéré des docs, mais je n'ai pas encore tout lu. J'ai préféré partir sur mon idée histoire de ne pas me faire trop influencer
3-c'est moi qui y ait pensé!
4-375 ms pour le moment
5-ça ne le fait pas encore, mais on va tabler sur un petit 240*375=90 s (boudiou, ça fait long d'un coup!)
6-point fort: algo relativement simple et intuitif... point faible: un peu long pour toutes les solutions?
7- de mon point de vue oui... l'algo est plus ou moins basé sur une démarche naturelle
8- détermination des solutions impossible pendant les étapes intermédiaires (style détection des espaces vides uniques isolés). Adaptation aux problèmes de dimensions supérieures à 3 sans soucis (architecture assez souple pour ça).

Pour les questions subsidiaires 9 à 11, on verra plus tard

[edit] du 24/09 0h00
4- J'arrive à descendre à 125 ms... mais plutôt 200 ms en moyenne
5- Gros problème de ce côté là... il bloque à 64 solutions sans en trouver d'autres, ça mouline, ça mouline... Mais vu que ce n'est pas demandé dans le défi, je pense que je vais laisser ça de côté pour le moment (même si j'ai une petite idée pour optimiser un peu)

11- 100 ms environ en moyenne
12- Athlon 64 3200+ 2.20 GHz, Win XP SP3, Java 1.6.0-b105

[SpiceGuid]

Bonjour à tous,
et merci pour votre participation.

5-ça ne le fait pas encore, mais on va tabler sur un petit 240*375=90 s (boudiou, ça fait long d'un coup!)

240 solutions c'est sans compter les 24 symétries du cube.
Si ton programme n'élimine pas les symétries alors ça fait plutôt 240 x 24 = 5760 solutions.

Les pistes d'amélioration évoquées jusqu'ici:

• la détection des petits espaces vides (qui ne peuvent pas contenir une pièce). l'ennui avec cette optimisation c'est qu'elle est trop spécialisée, elle devient inefficace dans le cas où l'on a une pièce monocube.
• la parité pour éliminer certaines positions/orientations de pièces avant la recherche. le brute-force/backtracking est fondamentalement lent, chercher à en diminuer le facteur de branchement c'est toujours une bonne idée.

[Mindiell]

C'est quoi ce que vous appelez le backtracking ?

[Chatanga]

C'est quoi ce que vous appelez le backtracking ?

On parle de backtracking lorsqu'on explore un espace de solutions potentielles en profondeur d'abord et en reculant à chaque impasse rencontrée. A chaque étape de la progression, une hypothèse est faite et, lors d'un échec, la dernière hypothèse est remise en question. S'il n'existe plus d'autres hypothèses pour une étape, on recule plus profondément.

par exemple, si tu veux "casser" le digitcode à 4 chiffres de ton immeuble, tu commences par entrer la combinaison 0000. Si ça ne fonctionne pas, tu remets en cause la dernière hypothèse - le chiffre de rang 4 est un 0 - et tentes 0001, et ainsi de suite jusqu'à 0009. Comme il n'existe que 10 chiffres, il faut remonter (backtrack) ensuite plus loin en remettant au cause l'hypothèse pour le chiffre de rang 3 et donc tenter 0010.

Une amélioration classique possible du backtraking est le forward checking qui consiste, à chaque étape, à élager les hypothèses possibles en aval pour gagner du temps. Par exemple, si tu sais que le digitcode ne contient que des chiffres différents, tu peux éviter de tester 00-- à partir de la combinaison 0--- et passer directement à 01--.

[Ulmo]

Bonjour à tous,
et merci pour votre participation.


240 solutions c'est sans compter les 24 symétries du cube.
Si ton programme n'élimine pas les symétries alors ça fait plutôt 240 x 24 = 5760 solutions.

48 symétries

[JeitEmgie]

1. mélange bruteforce + opérations booléennes sur bits sets + backtracking
2. opérations booléennes en 3D sur le GPU, histoire de corser le challenge…
3. envie de refaire du backtracking (et du C++), çà faisait trop longtemps…
4. voir 5 : suffisamment rapide pour sortir toutes les solutions, de toute façon le temps pour la première solution peut dépendre de l'ordre des pièces dans la description du problème à l'intérieur du code… (il faudrait les mélanger au départ et faire une moyenne des benchmarks… ce qui impliquerait de mettre le benchmark dans le code lui-même… pas que çà à faire…)
5. ./benchmark.sh `pwd`/001-024
(toutes les solutions pour chaque fichier du dossier…)
001.txt

real 0m6.015s
user 0m6.006s
sys 0m0.005s
--
002.txt

real 0m0.856s
user 0m0.853s
sys 0m0.002s
--
003.txt

real 0m0.165s
user 0m0.162s
sys 0m0.002s
--
004.txt

real 0m0.397s
user 0m0.394s
sys 0m0.002s
--
005.txt

real 0m8.140s
user 0m8.132s
sys 0m0.005s
--
006.txt

real 0m0.391s
user 0m0.388s
sys 0m0.002s
--
007.txt

real 0m1.823s
user 0m1.819s
sys 0m0.003s
--
008.txt

real 0m0.426s
user 0m0.423s
sys 0m0.002s
--
009.txt

real 0m0.339s
user 0m0.336s
sys 0m0.002s
--
010.txt

real 0m8.095s
user 0m8.090s
sys 0m0.004s
--
011.txt

real 0m0.861s
user 0m0.858s
sys 0m0.002s
--
012.txt

real 0m0.390s
user 0m0.387s
sys 0m0.002s
--
013.txt

real 0m6.449s
user 0m6.442s
sys 0m0.004s
--
014.txt

real 0m19.648s
user 0m19.635s
sys 0m0.009s
--
015_.txt
Invalid file format

real 0m0.004s
user 0m0.002s
sys 0m0.002s
--
016.txt

real 0m6.242s
user 0m6.236s
sys 0m0.004s
--
017.txt

real 0m0.207s
user 0m0.204s
sys 0m0.002s
--
018.txt

real 0m0.027s
user 0m0.025s
sys 0m0.002s
--
019.txt

real 0m0.138s
user 0m0.135s
sys 0m0.002s
--
020.txt

real 0m0.191s
user 0m0.188s
sys 0m0.002s
--
021.txt

real 0m1.135s
user 0m1.130s
sys 0m0.003s
--
022_.txt
Invalid file format

real 0m0.018s
user 0m0.002s
sys 0m0.002s
--
023.txt

real 0m0.344s
user 0m0.341s
sys 0m0.002s
--
024_.txt
Invalid file format

real 0m0.004s
user 0m0.002s
sys 0m0.002s
--

6. voir 5/n'élimine pas les solutions symétriques
7. non, la démonstration peut être faite sans calcul
8. ajouter la division du problème pour dispatcher un parcours multithread de l'arbre des solutions, ce qui pourrait nécessiter d'analyser quel ordre de départ des pièces pourrait être le plus intéressant…

[SpiceGuid]

5- Gros problème de ce côté là... il bloque à 64 solutions sans en trouver d'autres, ça mouline, ça mouline... Mais vu que ce n'est pas demandé dans le défi, je pense que je vais laisser ça de côté pour le moment (même si j'ai une petite idée pour optimiser un peu)

S'il bloque ça n'est sans doute pas une question d'optimisation mais plus probablement une question de correction de l'algorithme.

À tous:
Il est recommandé, avant de vous soucier de performance :

• de privilégier d'abord la logique, la clarté et la lisibilité
• au minimum vérifiez votre solution
• vous pouvez également vérifier que le Soma possède bien 240 solutions (ou bien 5760 solutions en incluant les symétries)

240 solutions c'est sans compter les 24 symétries du cube.
Si ton programme n'élimine pas les symétries alors ça fait plutôt 240 x 24 = 5760 solutions.

48 symétries

• je peux regarder une quelconque des 6 faces du cube
• à cette face je peux donner 4 orientations possibles
• 6 x 4 = 24

J'ai oublié quelque chose

Par contre j'aurais voulu savoir si du monde avait réussi a régler le problème du fait que le cube a X fois les mêmes résultats à cause de ses rotations.

C'est assez facile. Tu choisi une pièce avec le maximum de rotations possibles (donc pas le tricube V) et tu fixe sa rotation au départ au lieu de lui donner les 24 possibles.
Ça devrait suffire à orienter la totalité du cube et à trouver exactement 240 solutions.

1. mélange bruteforce + opérations booléennes sur bits sets + backtracking

Les opérations booléennes c'est un moyen très rapide pour tester l'intersection.

4. voir 5 : suffisamment rapide pour sortir toutes les solutions, de toute façon le temps pour la première solution peut dépendre de l'ordre des pièces dans la description du problème à l'intérieur du code…

Tu peux encore retirer les symétries, ensuite tu peux envisager de t'attaquer au cube de Bedlam
Il est vrai que le temps pour la première solution dépend des conditions initiales et ne signifie pas grand chose en général, la question est là afin que ceux qui sont déjà satisfaits d'avoir trouvé une solution puissent tout de même communiquer sur leurs résultats (bien que j'ai du mal à voir en quoi trouver toutes les solutions serait tellement plus compliqué).


Pour ceux qui veulent comme moi résoudre le cube de Bedlam, autant s'entendre sur la nomenclature :



Ou, si vous préférez, les mêmes pièces directement sous forme textuelle :

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
24
25
26
27
28
29
30
31
32
 
// Bedlam cube
puzzle Bedlam
  box =
    4 * 4 * 4
  pentacube A =
    unit right (down) right up.
  pentacube B =
    unit right (up) (down) right.
  pentacube C =
    unit down right down right.
  pentacube D =
    unit front down right down.
  pentacube E =
    unit down (back) (right) down.
  pentacube F =
    unit front (up) rigt down.
  pentacube G =
    unit down (back right) down.
  pentacube H =
    unit down down (back) right.
  pentacube I =
    unit front down down right.
  pentacube J =
    unit front left down down.
  pentacube K =
    unit down front right down.
  pentacube L =
    unit down (back) down right.
  tetracube M =
    unit down right back.
endpuzzle

Où :

• unit désigne le monocube unité
• right/left/up/down/front/back est l'ajout d'un monocube juxtaposé dans l'une des 6 directions
• la paire de parenthèses (...) désigne un embranchement

[Chatanga]

48 symétries

Toutes les symétries ne sont pas bonnes à prendre. En l'occurrence, ce sont les symétries axiales - les rotations donc - qui nous intéressent (et, sauf erreur, il n'y en a que 24). Ce serait différent si toutes les pièces présentaient une symétrie propre (au hasard, comme dans l'âne rouge), voire une chiralité avec une voisine, mais ce n'est pas le cas.

4. voir 5 : suffisamment rapide pour sortir toutes les solutions, de toute façon le temps pour la première solution peut dépendre de l'ordre des pièces dans la description du problème à l'intérieur du code… (il faudrait les mélanger au départ et faire une moyenne des benchmarks… ce qui impliquerait de mettre le benchmark dans le code lui-même… pas que çà à faire…)

Le temps pour chercher toutes les solutions d'un puzzle est plus parlant pour un algorithme qui n'utilise pas d'heuristique particulière pour s'orienter dans une bonne direction. Ca semble être le cas de toutes les approches évoquées pour l'instant.

[pseudocode]

1. votre algorithme est-il du type brute force ? avec ou sans backtracking ?

brute force + backtracking

2. quels étaient les autres algos possibles ?

Test de Parité, Test de couverture, ...

3. pourquoi avoir choisi celui-ci ?

J'aime bien le backtracking

4. votre temps pour trouver une solution du Soma

16ms (Core2-Duo)

5. votre temps pour trouver toutes les solutions du Soma

3.4 secondes

6. le point fort/faible de votre approche

Un prétraitement avant de lancer l'exploration des solutions

7. cette approche vous facilite-t-elle la démonstration demandée ?

Non

8. comment améliorer la performance et attaquer de plus gros cubes comme le Bedlam_cube ?

Pas besoin. L'algo est parallelisable par nature. Il suffit d'avoir plusieurs PC a sa disposition

9. Combien de solution trouvez-vous au cube de soma ?

11520

10. Combien de solution trouvez-vous au puzzle valide proposé dans l'explication du défi ?

28

11. En combien de temps votre algo determine si le puzzle invalide proposé dans l'explication du défi est irréalisable ?

15ms

[Ulmo]

Bonjour à tous,
et merci pour votre participation.


240 solutions c'est sans compter les 24 symétries du cube.
Si ton programme n'élimine pas les symétries alors ça fait plutôt 240 x 24 = 5760 solutions.

48 symétries

• je peux regarder une quelconque des 6 faces du cube
• à cette face je peux donner 4 orientations possibles
• 6 x 4 = 24

J'ai oublié quelque chose

(Pardon pour cette intervention un peu sèche)
Il y a aussi les symétries planes :
Tu prends une solution, et tu la regardes dans un miroir ; c'est encore une solution (toutes les pièces sont symétriques sauf les pièces A et B qui sont échangées).

Toutes les symétries ne sont pas bonnes à prendre. En l'occurrence, ce sont les symétries axiales - les rotations donc - qui nous intéressent (et, sauf erreur, il n'y en a que 24). Ce serait différent si toutes les pièces présentaient une symétrie propre (au hasard, comme dans l'âne rouge), voire une chiralité avec une voisine, mais ce n'est pas le cas.

C'est justement bien le cas

[pseudocode]

En modifiant la stratégie d'exploration, mon algo résout le Cube de Bedlam en 400 ms (et le cube de Soma toujours en 16ms).

[plegat]

S'il bloque ça n'est sans doute pas une question d'optimisation mais plus probablement une question de correction de l'algorithme.

Il bloque sur le nombre de solutions trouvées, pas sur l'algo. Il faut que je fasse intervenir quelques tests intermédiaires pour supprimer les solutions "impossibles" au plus tôt histoire de limiter l'exploration. Il explore un peu trop large pour le moment...
Mais on verra ce soir, je ne peux pas y toucher pendant mes heures de travail

[Mindiell]

(Pardon pour cette intervention un peu sèche)
Il y a aussi les symétries planes :
Tu prends une solution, et tu la regardes dans un miroir ; c'est encore une solution (toutes les pièces sont symétriques sauf les pièces A et B qui sont échangées).

C'est justement bien le cas

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

[SpiceGuid]

Il y a aussi les symétries planes :
Tu prends une solution, et tu la regardes dans un miroir ; c'est encore une solution (toutes les pièces sont symétriques sauf les pièces A et B qui sont échangées).

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.

J'aime bien le backtracking

On dirait bien que tu n'es pas le seul

Un prétraitement avant de lancer l'exploration des solutions

Ça a l'air intéressant.
Peux tu nous dire quelle est la nature de ce prétraitement ? Parité ?

En modifiant la stratégie d'exploration, mon algo résout le Cube de Bedlam en 400 ms (et le cube de Soma toujours en 16ms).

J'adore ton image du Bedlam
Pour la stratégie d'exploration, la modification ne vaut la peine que si elle diminue le temps du calcul de l'ensemble des solutions (sinon c'est quand même un peu de la bidouille)

[pseudocode]

Ça a l'air intéressant.
Peux tu nous dire quelle est la nature de ce prétraitement ? Parité ?

non, rien d'aussi compliqué. Je précalcule juste la position/orientation des pièces, et je fais une première passe pour éliminer toutes les positions/orientations qui ne rentrent pas dans le puzzle. Il ne me reste donc que des position/orientation physiquement possibles.

J'adore ton image du Bedlam

J'avoue que les couleurs sont particulièrement bien choisies.

Pour la stratégie d'exploration, la modification ne vaut la peine que si elle diminue le temps du calcul de l'ensemble des solutions (sinon c'est quand même un peu de la bidouille)

La modification améliore le temps de calcul sur l'ensemble des solutions. C'est juste que ce n'est pas mesurable sur un ensemble aussi petit que le puzzle de Soma. Par contre sur Bedlam ca permet de passer de plusieurs heures a 400ms.

[Daxou31]

1 - C'est plutôt du bruteforce pour l'initialisation mais après la phase de recherche est en backtraking.

2 - L'algo le plus bourin qui teste tout. Mais j'ai pas eu le courage d'essayer :p

3 - Ma première idée puis il me semble bien

4 - Première solution : 110 centièmes

5 - Pour le cube, j'ai 11520 résultats en 9 minutes et 9 secondes sans mon sleep donc le plus rapide (cependant il utilise que 1Ghz de mon CPU) et je n'ai pas de sleep dans mon Thread.

6 - une fois l'initialisation faite, le déroulement n'est qu'une itération logique.

7 - ouèp enfin faut tester.

8 - en essayant au max de limiter les test et les boucles mais cela me semble difficile car je l'aurais déja fait. Cela dit j'ai pas ré analysé plus que ca mon code.

9 - 11520 car mon test de doublon (sur les rotations possible est trop long)

10 - Puzzle exemple : 28 différents résolu en 1 seconde et 047 centièmes

11 - Puzzle impossible : 555 centièmes

12 - core2 2GHz mais 1GHz seulement est utilisé

la parité pour éliminer certaines positions/orientations de pièces avant la recherche. le brute-force/backtracking est fondamentalement lent, chercher à en diminuer le facteur de branchement c'est toujours une bonne idée.

J'ai commencé à faire ca dans mon initialisation mais ca laisse encore trop de doublons sur les rotations mais c'est plsu rapide que à chauqe solution trouver, tester si elle n'existe pas dans une des 48 rotations d'une solution :p.

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.

[Invité]

non, rien d'aussi compliqué. Je précalcule juste la position/orientation des pièces, et je fais une première passe pour éliminer toutes les positions/orientations qui ne rentrent pas dans le puzzle. Il ne me reste donc que des position/orientation physiquement possibles.

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