Comment résoudre le puzzle en bois Log Pile avec un programme informatique?

Suivant les conseils de Jay Elston, je le mettrais en œuvre en utilisant le pseudocode suivant:

Read in the pieces Annotate each piece with its number of pegs and holes Generate all possible base layers (10 over 5 = 252, selecting 5 from the set), so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes) For each base layer, (5! = 120 of them, permuting the 'below' pieces) compute 'rotated pieces' for the base layer if one-to-one match between top layer and rotated base-layer pieces, report successful solution 

Où les “pièces en rotation” seraient, pour une couche de base donnée, les pièces idéales dont vous auriez besoin pour la recouvrir. En calculant ces pièces et en les faisant correspondre aux pièces de la couche supérieure, vous pouvez utiliser un sorting O (N log N) pour faire correspondre les pièces pivotées à la couche supérieure réelle au lieu de les faire correspondre à toutes les N! arrangements possibles de la couche supérieure. De plus, lors du premier match, vous pouvez sortir plus tôt.

La clé pour écrire des algorithmes efficaces consiste à ajuster votre recherche le plus tôt possible et à exploiter les symésortinges. Par exemple, vous pouvez réduire de moitié le temps d’exécution si vous pensez que le puzzle est symésortingque et vous affectez donc arbitrairement une pièce au calque du bas: vous n’aurez alors plus que 9 calques de base à explorer.

Ce problème semble être une forme du problème de satisfiabilité booléenne . Si c’est le cas, l’approche la plus connue est la force brute.

Mais il existe certaines symésortinges et certaines propriétés du problème qui peuvent vous permettre de réduire le nombre de solutions à essayer. Par exemple —

• Si vous divisez les journaux en deux sous-ensembles de 5 pièces, TOP et BOT, les # piquets dans TOP doivent correspondre aux # trous dans BOTTOM, et les # trous dans TOP doivent correspondre aux # piquets dans FOT et les # plats dans TOP. doit correspondre au nombre d’appartements en bas. Si les chevilles et les trous # correspondent, alors les # appartements correspondent également, de sorte que vous n’avez pas besoin de vérifier les # appartements.
• Il existe 10 * 9 * 8 * 7 * 6 manières de partitionner les journaux en deux sous-ensembles de 5 éléments. (Une fois que vous avez sélectionné les 5 premiers journaux pour le sous-ensemble TOP, les autres journaux se trouvent dans le sous-ensemble BOTTOM.
• Lorsque vous testez un sous-ensemble de 5 éléments, vous disposez de 5 * 8 * 6 * 4 * deux méthodes pour organiser une couche de journaux. En d’autres termes, une fois que vous avez sélectionné le journal 1, il rest 4 journaux. Pour le deuxième journal, vous pouvez en choisir quatre et vous pouvez l’orienter de deux manières par rapport au premier journal.
• Une fois que vous avez un calque de base, vous pouvez essayer d’ajuster chaque journal de l’autre calque, l’un après l’autre, jusqu’à ce que vous en trouviez un qui ne s’adapte pas. À ce stade, vous abandonnez la configuration actuelle du journal de la couche de base et essayez la suivante.

Prolog est populaire pour les problèmes de ce type. J’ai mis en place des problèmes de casse-tête plus simples qui ont des solutions relativement intéressantes dans Prolog.

Il existe des moyens très élégants de résoudre ce genre de problèmes en Haskell, en utilisant des fonctions et en faisant un retour en arrière. Un de mes amis a résolu un casse-tête physique très épineux – Puzzling Pets – en un peu plus de 200 lignes de Haskell, comprenant des descriptions de toutes les pièces et de tout le rest. Un bon moyen d’apprendre les techniques appropriées est de lire l’article de John Hughes intitulé Why Functional Programming Matters , d’installer la plate – forme Haskell et de tenter votre chance.

J’ai une solution (désordonnée!) En javascript, mais j’ai eu du mal à l’afficher. L’algorithme de base utilisé est le suivant: rechercher toutes les itérations de 5 journaux parmi un total de 10 journaux et, avec chaque ensemble de 5 journaux, créer toutes les itérations possibles en inversant les journaux. Pour chacun de ces états, nous saurons quel modèle de journaux devra être placé en haut. Nous déterminons ensuite si les 5 journaux restants peuvent être placés en haut.

Ce qui conduit à cette représentation d’une solution:

 (Bottom, right-> left) [0,0,1,-1,1],[-1,-1,0,0,-1],[0,0,1,0,1],[-1,1,0,-1,0],[1,0,-1,0,0] (Top, up->down) [0,1,0,1,-1],[0,1,0,-1,0],[-1,0,-1,0,1],[1,0,0,1,0],[-1,1,-1,0,0] 0 - flat 1 - dowel -1 - hole