如何存儲具有未知深度的遞歸函數的結果？

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循環重複遍歷可能的移動數組，產生新的座標並檢查它們是否在棋盤上，或者如果該棋盤之前被「訪問過」。如果找到有效的移動，則函數將再次用新座標調用。

（正如你所看到$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" 
} 

[...] 

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

?> 

說明

1. 功能nextMoves會添加到全局變量$valid_paths從給定位置開始的所有有效路徑。
2. 首先檢查是否所有瓷磚都已被訪問過。如果這是真的，則將$visited陣列添加到$valid_paths
3. 如果不是所有瓷磚都被訪問過，則它將當前的$position添加到$visited陣列。
4. 接下來它遍歷每個$direction，並且如果可以在該方向上移動到網格中並未訪問的圖塊，則會將該新圖塊添加爲有效的下一步移動。
5. 完成計算後，所有可能的有效下一步移動將重新開始，每次新的$position和新的$visted。

我改進了一些代碼。它可以生成一定數量的可能答案的有效板。我不會在這裏發佈代碼，因爲它與thw答案無關。您可以在此PHPFiddle中查看改進的代碼。