4
\$\begingroup\$

I have made a game that consists of a pyramid of hexagons with numbers from 00 to 99 randomly positioned in groups of 6, 10 or 15 elements. Now, I'm working to create an auto-solver but for the last 2 weeks, I have got nothing really worth produced, and would like your help. My objective is to determine the minimum swaps need to turn the left pyramid into the right pyramid:

enter image description here

Obviously, there's a catch: every cell can be exchanged only with it's neighbors cells, as below:

enter image description here

I've tried a lot of approaches with binary heap, BST and others, but I can't seems to find a proper answer. What would be the best algorithm choice to determine the minimum swaps needed to sort this hive?

Thanks in advance for any help,

Marcelo

\$\endgroup\$
5
\$\begingroup\$

This is very nice example of problem suited for A* algorithm. I will not go into details how to implement A* here as it has been done better before and this very easy to find, however this is how I would apply A* for your problem:
As you can see, there is only a limited number of states that you can "move" to using single swap (14 for this case if I am not mistaken), you can think of them as a nodes in the (pathfinding)graph searched by A*. Naturally, you can only move to adjacent nodes and the distance from start node is the number of swaps made to reach "current" node.
What you also need for A* is function estimating the distance to goal state. Choosing good one is the key to speed of the algorithm, however pretty much any decent one will lead to the solution. I suggest using the sum of distances to goal postion, e.g. "1" is 1 swap away from its place, similarly "3" is two swaps away, all summing up to distance = 8 for the state in your example.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot - will try to pursuit this approach. My goal for this special presentation is to get 6 movements (which is what I get by doing the swaps myself), I'll try to adapt an A* to it. \$\endgroup\$ – the-alchemist Sep 16 '15 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.