如何递归获取元素的数量，直到到达 scala 中 5 x 5 网格中的所有正方形

Question

我有一个 5 x 5 的网格。我的初始位置是 (0,0)

我有一种方法可以从该位置找到 'L' 形状中的所有可能位置所以从(0,0)。

所以要么

( x + 2 )( y + 1 )

或

( x + 1 )( y + 2 )

我们有两个位置

然后我的方法将从所有可能的移动列表中调用它自己并找到每个移动的位置。

仅当可能移动列表中的最后一个位置与初始位置相同时，递归才会中断。

所以位置的可能移动：

(0)(0) 是 List((1,2),(2,1))
List((possible moves for (1,2) ), (possible moves for (2,1) ) )

等等：

到目前为止我的方法

def CountTour(dimension: Int, path: Path): Int = {
  // possibleMoves returns list of possible moves
  val Moves = possibleMoves(dimension, path, path.head).contains(path.last)

  // if the last element is not the same as first position, and has visited the whole graph, then break the recursion
  if (legalMoves && path.size == (dimension * dimension)) {
    1
  } else {
    // else call the same method again with each possible move
    val newList = for (i <- legal_moves(dimension, path, path.head)) yield i
    count_tours(dimension,newList)
  }
}

但是这行不通。我该如何解决？

Answer 1

在我看来，您实际上还没有这方面的任何工作代码。我这样说是因为 A) 您 post 编辑的代码有很多漏洞，并且 B) 当我询问您当前获得的输出时，我没有得到直接的回答。出于这些原因（并且因为这看起来像是一项家庭作业），我不会 post 使用真实代码给出答案，而是描述我认为应该起作用的方法。

目标是编写一个函数（实际上是一个方法），它采用棋盘的尺寸和棋盘上的起点，returns 是所有路径（连续移动）的计数董事会（没有 return 到一个已经访问过的广场）。

1st - 从任何起点开始，有 8 个不同的位置可以移动到（2 步到 east/west/north/south，然后 1 步到 left/right）。我会编写一个采用网格尺寸和起点的过程。它首先创建一个包含所有 8 个可能的新位置的集合（可能是 List），然后只保留那些落在网格内的位置（即没有负数或坐标大于网格维度）。

2nd - 必须根据已经访问过的地点列表检查该列表，并删除任何重复项。我会使用 diff 方法。请注意...

possible_moves diff already_been_there  // one result
already_been_there diff possible_moves  // different result

其中之一就是您想要的。

3rd - 现在你有了所有允许移动的列表。如果该列表为空，那么您就走到了路的尽头，没有更多的动作可做。 Return 1 因为您找到了一条耗尽棋盘的路径。

4th - 如果列表不为空，那么您想使用新的起点和更新的已存在方块列表重新调用相同的过程（递归）。问题是这个列表至少有一个，可能多达八个新位置。如何在每次迭代中调用不同次数的递归调用？那么，您想要做的是将列表从新位置列表更改为递归调用的 returned 值列表。你知道如何将 List[A] 变成 List[B] 吗？（提示：它与 "nap" 押韵。）

5th - 如果你已经走到这一步，那么你就有了一个数字列表，每个数字都是从每个新起点用尽棋盘的方法的计数。将它们加在一起，您就可以计算出从这个起点开始用尽棋盘的方法，这就是您 return.

的数字

如果我正确描述了你的目标，并且我已经正确编码，那么你可以检查我的工作。对于 5X5 板，从 0,0 开始，我想出了 625,308 条不同的路径。（17 行代码，但我并没有试图非常简洁。）

如何递归获取元素的数量，直到到达 scala 中 5 x 5 网格中的所有正方形

How to recursively get the number of elements until reached all squares in 5 x 5 grid in scala

recursion

for-loop

scala

chess

list

到目前为止我的方法