1

我正在使用 php 制作一个 3x3 的解谜器。零是您可以移动的自由空间。例如： 

1 2 3  
4 0 5  
7 8 6

至 

1 2 3  
4 5 0  
7 8 6

至

1 2 3  
4 5 6  
7 8 0

我已经制作了随机发生器 - 制作了 50 个随机动作。但我是堆栈，使用求解器算法。

输出应该是解决它的所有步骤。

我已经有了解决一步难题的工作方法，但我不知道如何递归地使用它。 

public function makeMoves($elements)
{
    $pos = $this->findSpace($elements); //returns position of the free space

    $actions = $this->findActions($pos); //returns all actions positions (left, right, top, bottom)

    $possibleActions = $this->findPossibleActions($actions); //return number of possible actions

    for ($i = 1; $i <= $possibleActions; ++$i) { //let's do all possible actions
        $move = $this->selectAction($actions, $i, $pos); //get new position for the space
        $perform = $this->performAction($elements, $pos, $move); //swap the space with the element on that position

        $this->tree[] = new Elements;

        end($this->tree);
        $last_id = key($this->tree);

        $this->tree[$last_id]->setState($perform);
        $this->tree[$last_id]->setAncestor(0);

        $step = [$move, $pos];

        $this->tree[$last_id]->setStep($step);

        if ($perform == $this->elementsDone) { 
            return $this->tree[$last_id];
        }
    }
}
4

1 回答 1

1

一种解决方案是使用 A* 算法找到解决方案的最短路径。每次移动的成本为 2。每个位置与每个棋子必须移动的距离之和的期望解的距离。（一个角到另一个角的距离为 4。）如果有的话，你可以保证找到最短的解决方案。

有关该算法的实现，请参阅http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript 。

请注意，所有随机配置的一半将无法解决。请参阅https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html进行测试，告诉您哪些要扔掉。它还提供了有关如何编写一种算法的提示，该算法占用的内存少于我建议的算法，并找到低效的解决方案，但会减少找到这些解决方案的工作。

于 2016-02-25T19:15:05.550 回答