алгоритм — Решение головоломки 3х3 с помощью PHP с использованием поиска в ширину

я делаю решатель головоломок 3х3 используя php. Ноль — это свободное пространство, куда вы можете двигаться. Например:

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];
}
}
}