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

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 に答える