Как сохранить результаты от рекурсивной функции с неизвестной глубиной?

Недавно я наткнулся на игру, которая генерирует доску NxN (2×2, 4×4 …) с пронумерованными тайлами (1, 2, 3 …), где каждое число определяет разрешенные ходы. Цель состоит в том, чтобы очистить всю доску, если это возможно, в то время как каждый тайл можно использовать только один раз.

Маленькая доска может выглядеть так:

| 1 1 |
| 1 1 |

большая доска:

| 1 2 2 3 |
| 2 1 1 1 |
| 3 2 1 3 |
| 2 2 3 1 |

Поскольку я часто сталкивался с ситуацией, когда решение было невозможно, я пытался написать короткий сценарий, который проверяет, можно ли найти решение или нет, прежде чем использовать доску.

Хотя это работало частично, проверка каждой возможной комбинации и хранение всех результатов по отдельности стало более сложным, и я даже не уверен, возможно ли это вообще.

Вот упрощенный пример:

$tiles[1][1] = 'p1';
$tiles[2][1] = 'p1';
$tiles[1][2] = 'p1';
$tiles[2][2] = 'p1';

$moves = array(
array('x' => -1, 'y' => -1),
array('x' =>  0, 'y' => -1),
array('x' =>  1, 'y' => -1),
array('x' => -1, 'y' =>  0),
array('x' =>  1, 'y' =>  0),
array('x' => -1, 'y' =>  1),
array('x' =>  0, 'y' =>  1),
array('x' =>  1, 'y' =>  1)
);

function nextMove($x, $y, &$visited)
{
global $moves;

$max_loops = count($moves);
$visited[] = $x. ', ' .$y;

for ($j = 0; $j < $max_loops; $j++)
{
$new_x = $x + $moves[$j]['x'];
$new_y = $y + $moves[$j]['y'];

if (($new_x >= 1) && ($new_x <= 2) && ($new_y >= 1) && ($new_y <= 2))
{
$new_pos = $new_x. ', ' .$new_y;

if (!in_array($new_pos, $visited))
{
$j = $max_loops - 1;

nextMove($new_x, $new_y, $visited);
}
}
}
}

nextMove(1, 1, $visited, $moves_done);
var_dump($visited);

Итак, что здесь происходит, довольно просто:

Функция вызывается с начальными координатами, подсчитывает максимальное количество ходов (для этой плитки) и добавляет текущую позицию к $visited массив.

После этого for Проходите по всему массиву возможных ходов, генерируете новые координаты и проверяете, есть ли они на доске или эта плитка уже посещалась. Если верный ход был найден, функция вызывается снова с новыми координатами.

(Как вы видете $j = $max_loops - 1; завершает цикл здесь, чтобы избежать неправильных значений, добавленных к $visited, если действительный ход не был найден позже)

Вот что получается прямо сейчас:

array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "1, 2"[2]=>
string(4) "2, 1"[3]=>
string(4) "2, 2"}

Пока что скрипт работает, но как только нет возможности переместиться, скрипт заканчивается и не проверяет дальнейшие комбинации (с $j = $max_loops - 1;) или добавляет неправильные координаты $visited, Чтобы избежать этого, я должен либо сохранять результаты отдельно, либо менять функцию, и именно здесь я застрял.

Одна большая проблема — неизвестное количество возможных ходов, потому что иногда игра заканчивается после 2 ходов, иногда доска может быть очищена.

Есть ли способ заставить функцию перебирать все возможные комбинации и сохранять / возвращать их отдельно (может быть слишком много для обработки и не нужно, но может быть интересно, если нельзя использовать только 1-2 плитки) ИЛИ ЖЕ хотя бы проверить, можно ли очистить всю доску, и вернуть решение (это важно, потому что результат должен быть сохранен и использован позже)?

Сценарий должен работать так:

array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "1, 2"[2]=>
string(4) "2, 1"[3]=>
string(4) "2, 2"}
array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "1, 2"[2]=>
string(4) "2, 2"[3]=>
string(4) "2, 1"}
array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "2, 1"[2]=>
string(4) "1, 2"[3]=>
string(4) "2, 2"}
array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "2, 1"[2]=>
string(4) "2, 2"[3]=>
string(4) "1, 2"}
array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "2, 2"[2]=>
string(4) "2, 1"[3]=>
string(4) "1, 2"}
array(4) {
[0]=>
string(4) "1, 1"[1]=>
string(4) "2, 2"[2]=>
string(4) "1, 2"[3]=>
string(4) "2, 1"}

[...]