如何存储未知深度的递归函数的结果？

Question

我最近遇到了一个生成 NxN（2x2、4x4...）棋盘的游戏，棋盘上有编号的方块（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 循环遍历可能移动的数组，生成新坐标并检查它们是否在棋盘上或者该棋子之前是否已经 'visited'。如果找到有效移动，将使用新坐标再次调用该函数。

（如你所见$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 步后结束，有时棋盘可以被清除。

有什么方法可以让函数遍历所有可能的组合并 store/return 它们分开（可能处理起来太多而且不是必需的，但如果只有 1-2 个方块可以的话可能会很有趣' t被使用）或至少检查是否可以清除整个板并return解决方案（这很重要，因为结果应该存储起来供以后使用）？

脚本应该这样工作：

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"
}

[...]

Answer 1

好的，这是我想出的：

<?php

$width = 2;
$height = 2;

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

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

$valid_paths = array();

function nextMoves($position, $visited = array()){
    global $directions, $tiles, $valid_paths, $height, $width;

    $visited[] = $position;
    if(count($visited) == $width * $height){
        $valid_paths[] = $visited;
        return;
    }

    $next_moves = array();
    $position = explode(',', $position);
    $x = $position[0];
    $y = $position[1];

    $tile_value = $tiles[$x][$y];

    foreach($directions as $direction){
        $new_x = $x + $direction['x'] * $tile_value;
        $new_y = $y + $direction['y'] * $tile_value;
        $new_pos = "$new_x,$new_y";

        if (($new_x >= 1) && ($new_x <= $width) && ($new_y >= 1) && ($new_y <= $height) && !in_array($new_pos, $visited)){
            $next_moves[] = $new_pos;
        }
    }

    foreach($next_moves as $next_move){
        nextMoves($next_move, $visited);
    }   
}

nextMoves('1,1');

echo "<pre>";
var_dump($valid_paths);
echo "</pre>";

?>

说明

函数 nextMoves 将添加到全局变量 $valid_paths 从给定位置开始的所有有效路径。
首先它检查是否所有的图块都被访问过。如果是这样，它会将 $visited 数组添加到 $valid_paths
如果不是所有的图块都被访问过，它会将当前的 $position 添加到 $visited 数组。
接下来它会遍历每个 $direction，如果可以沿该方向移动到网格中未访问过的图块，它会将该新图块添加为有效的下一步移动。
在计算完所有可能的有效下一步之后，它会重新开始计算每个新的 $position 和新的 $visted。

我对代码做了更多改进。它可以生成具有一定数量可能答案的有效板。我不会 post 这里的代码，因为它与答案无关。您可以在 PHPFiddle.

中查看改进后的代码

如何存储未知深度的递归函数的结果？

How to store results from recursive function with unknown depth?

php

arrays

recursion

function

depth