php - 使用广度优先搜索用 PHP 解决 3x3 难题

Question

我正在使用 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];
        }
    }
}

Answer 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测试告诉你哪些要扔掉。它还提供了有关如何编写一种比我建议的算法占用更少内存并找到低效解决方案的算法的提示，但在找到这些解决方案时会做更少的工作。