I have a grid 5 x 5 grid. And my initial position is at (0,0)

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

I have a method that finds all possible position in 'L' shape from that position So from (0,0).

我有一个方法,从那个位置找到'L'形状的所有可能位置从(0,0)。

So either

( x + 2 )( y + 1 )

(x + 2)(y + 1)

( x + 1 )( y + 2 )

(x + 1)(y + 2)

We have two positions

我们有两个职位

Then my method will call it self from the list of all the possible moves and finds the position of each one.

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

The recursion only breaks if the last position in the possible moves list is the same as the initial position.

如果可能移动列表中的最后一个位置与初始位置相同,则递归仅会中断。

So the possible moves for position:

所以可能的位置移动:

(0)(0) is List((1,2),(2,1))

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

列表(((1,2)的可能移动),((2,1)的可能移动))

and so on:

等等:

My method so far

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

However this won't work. How can i fix it?

但是这不起作用。我该如何解决?

1 个解决方案

#1

It looks to me like you don't actually have any working code for this yet. I say this because A) the code you posted has lots of holes, and B) I didn't get a straight answer when I asked what output you're currently getting. For these reasons (and because this looks like a homework assignment) I'm not going to post an answer with real code but, instead, I'll describe what I think should work.

它看起来像你实际上没有任何工作代码。我这样说是因为A)你发布的代码有很多漏洞,而B)当我问你目前得到什么输出时,我没有得到一个直接的答案。由于这些原因(并且因为这看起来像是家庭作业)我不打算用真实的代码发布答案,但相反,我将描述我认为应该起作用的答案。

The goal is to write a function (actually a method) that takes the dimension of the playing board, and a starting point on it, and returns a count of all paths (successive moves) that exhaust the board (no returning to an already visited square).

目标是编写一个函数(实际上是一个方法),它获取游戏板的尺寸,以及它上面的起点,并返回耗尽板的所有路径(连续移动)的计数(不返回已经访问过的板)广场)。

1st - From any starting point there are 8 different positions that can be moved to (2 steps to the east/west/north/south and then 1 step to the left/right). I'd write a procedure that takes the grid dimensions and a starting point. It first creates a collection (maybe a List) of all 8 possible new locations and then keeps only those that fall within the grid (i.e. no negative numbers or coordinates larger than the grid dimension).

1st - 从任何起点开始,有8个不同的位置可以移动到(东/西/北/南两步,然后左/右一步)。我写了一个程序,它采用网格尺寸和起点。它首先创建所有8个可能的新位置的集合(可能是List),然后仅保留落在网格内的那些(即没有负数或大于网格维度的坐标)。

2nd - That list will have to be checked against the list of places that have already been visited and any duplicates removed. I'd use the diff method. Note that ...

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

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

One of those is the one you want.

其中一个就是你想要的那个。

3rd - Now you have a list of all permissible moves. If that list is empty then you're at the end of the road and there are no more moves to make. Return 1 because you've found one path that exhausts the board.

第3名 - 现在你有一份所有允许动作的清单。如果那个清单是空的那么你就在路的尽头而且没有更多的动作了。返回1因为您找到了一条耗尽电路板的路径。

4th - If the list is not empty then you want to re-call this same procedure (recursion) with a new starting point and an updated list of already-been-there squares. The problem is that this list has at least one, and maybe as many as eight, new locations. How can you invoke the recursive call a different number of times with each iteration? Well, what you want to do is change your list from a list of new locations to a list of returned values from the recursive call. You know how to turn a List[A] into a List[B]? (Hint: it rhymes with "nap".)

4th - 如果列表不为空,那么你想用新的起点和已经存在的正方形的更新列表重新调用相同的程序(递归)。问题是这个列表至少有一个,也许多达八个新位置。如何在每次迭代时调用不同次数的递归调用?那么,您要做的是将列表从新位置列表更改为递归调用的返回值列表。您知道如何将List [A]转换为List [B]吗? (提示:它与“午睡”押韵。)

5th - If you've gotten this far then you have a list of numbers, each is a count of how many ways to exhaust the board from each new starting point. Add them together and you've got a count of how many ways to exhaust the board from this starting point, and that's the number you return.

第五 - 如果你已经走到这一步那么你有一个数字列表,每个数字都是从每个新起点消耗电路板的方法数量。将它们加在一起,您就可以计算出从这个起点开始耗尽电路板的方法,这就是您返回的数字。

If I've described your goal correctly, and I've coded it up correctly, then you can check my work. For a 5X5 board, starting at 0,0, I came up with 625,308 different paths. (17 lines of code, but I wasn't trying to be terribly concise.)

如果我已正确描述了您的目标,并且我已正确编码,那么您可以检查我的工作。对于5X5板,从0,0开始,我想出了625,308个不同的路径。 (17行代码,但我并不是非常简洁。)

#1