Discussion :

[diogene]

Effectivement, on obtient 81 coups si on accepte pour 1 coup le déplacement d'une seule pièce d'une ou deux lignes ou colonnes ou d'une ligne et d'une colonne (pour les carrés 1x1).

Le critère avec coups "doubles" s'implémente simplement dans un programme écrit pour coups "simples". Les performances obtenues sont très analogues dans les deux cas (En C, 0.14s sur Athlon 32 bits 2.2Ghz)

La solution que j'ai obtenue comportait donc 81 coups dont 39 coups "doubles" ce qui, ramené au critère du défi, donnerai 120 coups "simples", soit plus des 116 trouvés en implémentant uniquement les critères du défi. Autrement dit, une solution optimale avec coups "doubles" ne permet pas d'en déduire une solution optimale en coups "simples".

C'est assez marrant finalement l'Ane Rouge

[SpiceGuid]

En ce qui me concerne : 1 seconde pour la force brute à 1.5 GHz

Par force brute j'entends rechercher en largeur d'abord et examiner toutes les positions atteignables en 116 mouvements, sans en court-circuiter aucune. 1s ça m'impressionne parce que je ne vois pas quelle optimisation je pourrais bien ajouter :

• j'ai une table de transposition de type ABR (j'ai essayé les AVL, aucun gain, donc mon ABR est équilibré)
• mon insertion dans la table de transposition se fait par lot (fusion d'ABR, temps linéaire en nombre d'éléments insérés)
• je reconnais les plateaux identiques quelque soient les permutations de pièces
• je reconnais les mouvements regressifs (court-circuitage de l'insertion dans la table de transposition)

Le critère avec coups "doubles" s'implémente simplement dans un programme écrit pour coups "simples". Les performances obtenues sont très analogues dans les deux cas (En C, 0.14s sur Athlon 32 bits 2.2Ghz)

J'ai tenté ça aussi.
Même performance si je n'autorise les coups doubles que sur les barres.
Et plus de deux fois plus lent si j'autorise aussi les coups doubles sur les carrés
Le problème étant que les coups doubles génèrent plus de nouvelles positions (plus de largeur) qu'ils ne m'économisent de mouvements (moins de profondeur).

[diogene]

Le temps d'exécution est dépensé pour la très grande partie à savoir si une configuration a déjà été trouvée ou non et c'est cette recherche qui doit être optimisée.
J'avais pensé à implémenter une reconnaissance des positions identiques à une symétrie près, parce que je n'avais aucune idée du nombre de configurations à examiner (par la "force brute") avant d'arriver au résultat. Ceci allonge notablement cette recherche. Lorsque j'ai vu que le nombre de configurations différentes, sans prendre en compte les symétries, avant d'arriver au résultat était si faible ( # 24000 configurations) j'ai jugé que c'était inutile.

Même performance si je n'autorise les coups doubles que sur les barres.
Et plus de deux fois plus lent si j'autorise aussi les coups doubles sur les carrés

Ce ne devrait pas changer notablement (et ça ne le change pas) le temps d'exécution, et ce parce que il y a peu de configurations qui permettent de l'envisager (il faut que les deux trous forment un rectangle, que le carré ne soit pas 2x2, un coup double sur un barre horizontale implique que les trous forment un rectangle 1x2 horizontal,... )

Le problème étant que les coups doubles génèrent plus de nouvelles positions (plus de largeur) qu'ils ne m'économisent de mouvements (moins de profondeur).

Engendrer de nouvelles positions n'affecte pas les performances, c'est chercher si on ne les a pas déjà trouvées qui est pénalisant.

De toute façon, ce n'est pas une bonne démarche pour trouver la solution au problème posé (où on ne tolère que les coups simples)

[jfouche]

Salut

Par force brute j'entends rechercher en largeur d'abord et examiner toutes les positions atteignables en 116 mouvements, sans en court-circuiter aucune. 1s ça m'impressionne parce que je ne vois pas quelle optimisation je pourrais bien ajouter :

• j'ai une table de transposition de type ABR (j'ai essayé les AVL, aucun gain, donc mon ABR est équilibré)
• mon insertion dans la table de transposition se fait par lot (fusion d'ABR, temps linéaire en nombre d'éléments insérés)
• je reconnais les plateaux identiques quelque soient les permutations de pièces
• je reconnais les mouvements regressifs (court-circuitage de l'insertion dans la table de transposition)

Je ne sais pas trop si il n'y a qu'une méthode de force brute. De plus, je ne comprends pas les termes utilisés (table de transposition de type ABR, AVL, ...), il faudrait que je regarde ça. Peut être ma méthode est elle un peu plus que de la force brute. Je confirme que ma principale (et de loin) optimisation à été sur le moyen de savoir si une position à déjà été atteinte. Ma solution m'a offert un gain de plus de 1000% (!).

Je n'utilise que de C++, pas de C. Je ne suis pas sûr que l'un à un avantage sur l'autre, en terme de simplicité d'implémentation d'un algo, ainsi que des performances obtenues.
--
Jérémie

[SpiceGuid]

Le temps d'exécution est dépensé pour la très grande partie à savoir si une configuration a déjà été trouvée ou non et c'est cette recherche qui doit être optimisée.

C'est ce que j'ai fait puisque j'ai une complexité optimale pour la recherche/insertion dans ma table de transposition.
Mon problème principal c'est que j'examine en tout 332215 positions.

ABR = arbre binaire de recherche
AVL = arbre binaire équilibré Adelson Velskii Landis

[diogene]

Mon problème principal c'est que j'examine en tout 332215 positions

Oui, ton problème est là. C'est 10 fois trop.

[komput]

Pour ce qui est de la méthode utilisée pour vérifier si une solution a déjà été trouvée... j'ai fait une table de hachage maison, en choisissant 50000 entrées la table prend très peu de place et stocke extrêmement efficacement les configurations trouvées.
Il suffit que le hash code ne dépende que de la géométrie des pièces et leur disposition pour que ça marche bien.

Je rappelle mes résultats : 0.4 seconde @1.8 GHz pour calculer TOUTES les configurations atteignables à partir de celle de départ. Avec l'exemple donné, j'ai 964 solutions différentes et plus de 25000 configurations dans la table de hachage.
Je ne me suis intéressé qu'aux coups simples.

Pour retenir le plus court chemin (solution en un nombre de coups minimal), j'ai utilisé l'algorithme de Dijkstra.
Mais : quand on parle de force brute... j'ai bien entendu essayé de trouver les solutions en limitant le nombre de mouvements à 116. Seulement, le programme ne trouve aucune solution... il faut lui autoriser plus de mouvements, voire pas de restriction, pour que, à force de tester des configurations, il en trouve et qu'il recalcule le plus court chemin...
Donc je prends mes résultats avec des pincettes, vu que ce résultat est aberrant (mais j'ai vérifié que les chemins trouvés sont justes). C'est rageant ce bug débile.

[diogene]

50000 entrées, c'est beaucoup pour stocker 25000 configurations.
La table de hachage ne doit pas servir à grand chose et tu identifies les configurations de jeu presque uniquement sur la clé de hachage. Tout dépend de la complexité et du temps de calcul de cette clé.

[komput]

Oui, en effet 50000 entrées c'est beaucoup par rapport à ce qui serait strictement nécessaire. Mais la taille du tableau d'entrées est vraiment négligeable. Et ainsi j'ai une grande efficacité pour ajouter ou retrouver une configuration dedans, vu qu'il y a pratiquement correspondance directe.

Evidemment, pour des problèmes qui demanderaient de stocker beaucoup plus de données, un arbre bien construit pourrait être une meilleure idée. Dans le cas de ce jeu, la table de hachage est très simple à coder, je n'en dirais pas autant pour un arbre, j'y avais (un peu) réfléchi.

Mais mon choix principal a été au niveau du nombre d'allocations mémoire nécessaires pour remplir la structure choisie... avec ma table de hachage (presque vide, en plus) on trouve immédiatement ce qu'on veut. Pour ajouter une configuration, c'est une seule allocation (dans mon cas. la structure de données utilisée pour représenter une configuration pourrait être généralisée, et il faudrait plusieurs allocations pour dupliquer la configuration dans la table), alors que pour un arbre il faut allouer chaque noeud...
Et faire une allocation mémoire, même pour des faibles tailles, c'est un appel système assez coûteux. Faites des essais et vous verrez !

J'avais pensé à une structure de type "trie", mais c'est équivalent à un arbre du point de vue des allocations.

Le calcul de la clé est un calcul utilisant la position et les dimensions des pièces sur le plateau, c'est très rapide.
Là où je pense que mon programme pourrait être amélioré, c'est surtout dans la recherche des pièces qui peuvent être bougées... j'ai fait la manière brutale, en testant chaque pièce dans les 4 directions. Considérer les cases vides plutôt que les pièces serait dans ce jeu bien plus économique, je ne serais pas étonné que le gain de temps soit un facteur 2 voire 3.

Mais à nouveau, pour ce jeu en particulier, et pour les règles qui ont été demandées, un code simple à écrire à facile à vérifier, mais un peu plus lourd question performances, est très suffisant... et la flemme de grapiller sur 0.4 seconde se fait vite sentir

[SpiceGuid]

Considérer les cases vides plutôt que les pièces serait dans ce jeu bien plus économique, je ne serais pas étonné que le gain de temps soit un facteur 2 voire 3.

Considérer les cases vides, c'est ce que j'ai fait.
Et je n'arrive toujours pas à descendre à moins de 21s × Ghz.

Oui, ton problème est là. C'est 10 fois trop.

Il n'y a pas d'erreur dans mon code.
Ce nombre de positions vient de ce que j'explore l'espace en largeur d'abord et donc je trouve 8 solutions (pour rien puisqu'en fait elles sont similaires) mais pour ça je dois parcourir plus de 10 fois plus de positions.
Apparemment vous feriez une recherche en profondeur d'abord que vous arrêtez à la première solution trouvée. Par contre avec cette méthode je ne comprends pas bien comment vous pouvez être vraiment certains de tenir la (ou au moins une des) solution la plus courte.

[diogene]

Ce nombre de positions vient de ce que j'explore l'espace en largeur d'abord et donc je trouve 8 solutions (pour rien puisqu'en fait elles sont similaires) mais pour ça je dois parcourir plus de 10 fois plus de positions.

Oui, je suis d'accord avec cette méthode, mais je ne comprend pas pourquoi vous avez ce facteur 10.
A moins que peut être vous n'écartiez pas les configurations déjà obtenues avec un nombre de coups moindre.

[SpiceGuid]

Je conserve toutes les configurations, même la configuration initiale est comprise dedans. C'est obligatoire puisque je n'interdis pas le mouvement Up L.

edit: pour ceux qui veulent pousser leur programme jusqu'à ses limites je recommande cette page avec des puzzles jusqu'à plus de 1000 mouvements minimum.

[philben]

Bonjour,

Quelques statistiques sur le jeu dans le cas d'un plateau 5l x 4c avec :

• 4 carrés de 1 case
• 2 carrés libres de 1 case
• 4 rectangles verticaux de 2 cases
• 1 rectangle horizontal de 2 cases
• 1 carré de 4 cases

1. Nombre de plateaux différents possibles : 65 880
2. Statistiques descriptives sur le nombre de plateaux liés à un autre par un mouvement simple

• Moyenne : 3,139 plateaux liés
• Ecart-type de la population : 0,956
• Maximum : 7 (8 plateaux seulement ont 7 plateaux liés)
• Minimum : 1 (1368 plateaux n'ont qu'un seul plateau lié)
• Médiane : 3
• 1er quartile : 2
• 3ème quartile : 4
• Kurtosis normalisé : -0,189 (pratiquement pas d'aplatissement)
• Skewness : 0,272 (légère trainée à droite)

Graphe


Amicalement,

Philippe

[ram-0000]

Je ne suis pas d'accord avec tes statistiques

• 4 carrés de 1 case OK
• 2 carrés libres de 1 case OK
• 5 rectangles de 2 cases vertical ou horizontal au choix
• 1 carré de 4 cases OK

Les rectangles peuvent être au choix en position verticale ou horizontale. Il est faux de dire qu'il y doit y en avoir 4 verticaux et 1 horizontal.

[philben]

Il est faux de dire qu'il y doit y en avoir 4 verticaux et 1 horizontal.

J'avais pourtant précisé le cas envisagé .

Pour les autres variantes, sauf erreur, le nombre de plateaux s'échelonne de 14 220 à 109 260 avec 1 à 6 ou 7 plateaux liés.

Philippe

[ram-0000]

J'avais pourtant précisé le cas envisagé .

Pour les autres variantes, sauf erreur, le nombre de plateaux s'échelonne de 14 220 à 109 260 avec 1 à 6 ou 7 plateaux liés.

Philippe

Désolé, je n'avais pas compris que c'était des statistiques partielles sur un seul cas de figure.

J'avais surtout peur que d'autres personnes n'en déduisent à tord que les positions initiales ne comprennaient ques les cas avec 4 rectangles verticaux et 1 rectangle horizontal.

[ram-0000]

Ca y est, mon programme fonctionne aussi !!! (ben oui quoi, j'ai aussi le droit de chercher ...).

2 secondes environ pour trouver une solution quelque soit la position initiale (qu'elle soit valide ou non). Ma conf : PIV à 2,4GHz et 1Go RAM sous XP SP3.

Je confirme pour les 116 mouvements de la figure principale proposée dans le défi, c'est optimal.

Sinon, tous les autres positions initiales proposées dans le défis ont des solutions (j'ai eu de la chance) et certaines ont un chemin optimal en nettement moins de coups que 116.

J'ai trouvé le plus long chemin optimal possible vers 160 coups pour 1 grille.

Il y a 363480 positions initiales possibles et 1112092 déplacement différents.

Il y a quelque chose comme 90000 positions initiales qui n'ont pas de solution.

[Chatanga]

Bonjour à tous,

Une petite question qui n'a rien d'algorithmique : serait-il possible de préciser le point suivant du règlement ?

2.7. Licence des codes sources

Les codes sources doivent obligatoirement être libres de droits pour une éventuelle intégration dans la page Sources C. Cette mention doit être apportée explicitement dans tous les sources du projet.

L'accord du participant devra être précisé dans le fichier README qui si trouvera dans l'archive du travail effectué.

Pour ma contribution au projet, je pensais simplement mettre le tout sous licence BSD. J'ai récupéré le projet du précédent gagnant du Solitaire mais j'ai uniquement trouvé la mention "Je donne mon accord..." dans le README. C'est suffisant ou faut-il quelque chose de plus précis ?

[koala01]

La mention minimale est

copyright MachinChose 2009
Les sources présentées sont libre de droit

(le fait de donner à n'importe qui le droit d'utiliser les sources ne veut pas dire pour autant que l'on abandonne la "paternité" du code source qu'on a écrit )
et dans le readme un truc du genre de

Je donne explictement mon accord pour que ...

Mais il est clair qu'il existe une multitude de licences libérant les droits d'utilisation et de modification, allant de BSD à GNU/(L)GPL en passant par toutes les autres, y compris une licence libre "personnalisée"...

Rien ne t'empêche d'utiliser une licence libre particulière, pour autant... que tu libère effectivement les droits et que tu respecte les autres termes de la licence choisie si tu en choisi une parmi les "particulières" qui existent (si tu place ton projet sous licence BSD, il faut que tu en respecte les termes )

[Milos]

Salut, et bienvenue sur le forum

En effet, les 81 déplacements dont il est question dans l'énoncé sont donnés à titre indicatif, car c'est LA solution par excellence qui n'a pas encore pu être battue

Elle risque même, non seulement de n'être jamais battue, mais jamais égalée, du moins si on part de la position de départ standard.

Si j'en crois ce que je vois, les 81 coups comptent des déplacements de deux cases, qui doivent être comptés pour deux coups, et ça fera donc plus de 81 coups pour la solution optimale selon les règles du défi.

A moins qu'il n'y ait plusieurs solutions optimales ? Nos camarades mathématiciens sont très avantagés..

Milos.