为什么这个 R 版本的 Knight's Tour 不起作用？

Question

我是 R 的新手，我正在尝试找出马从角开始绕棋盘移动所需的最少步数。

我使用了这个网站的 Python 算法： https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/

我试着把它翻译成 R。

但是，当我运行这个程序时，它的输出是：

 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
[1,]    0   -1   -1   -1   -1   -1   -1   -1
[2,]   -1   -1   -1   -1   -1   -1   -1   -1
[3,]   -1   -1   -1   -1   -1   -1   -1   -1
[4,]   -1   -1   -1   -1   -1   -1   -1   -1
[5,]   -1   -1   -1   -1   -1   -1   -1   -1
[6,]   -1   -1   -1   -1   -1   -1   -1   -1
[7,]   -1   -1   -1   -1   -1   -1   -1   -1
[8,]   -1   -1   -1   -1   -1   -1   -1   -1
[1] "Minimum number of moves:  -1"

我该怎么做才能解决这个问题？

这是代码：

chess = rep(-1, times = 64)
board = matrix(data = chess, nrow = 8, ncol = 8, byrow = TRUE)

move_x = c(2, 1, -1, -2, -2, -1, 1, 2)
move_y = c(1, 2, 2, 1, -1, -2, -2, -1)
board[1, 1] = 0
pos = 1

valid_move <- function (x, y, board) {
    if (x >= 1 && y >= 1 && x <= 8 && y <= 8 && board[x, y] == -1) {
        return (T)
    }
    return (F)
}   

solve <- function (board, curr_x, curr_y, move_x, move_y, pos) {
    
    if (pos == 64) {
        return (T)
    }
    for (i in seq(1, 8)) {
        new_x = curr_x + move_x[i]
        new_y = curr_y + move_y[i]

        if (valid_move(new_x, new_y, board)) {
            board[new_x, new_y] = pos
            if (solve(board, new_x, new_y, move_x, move_y, (pos+1))) {
                return (TRUE)
            }
            board[new_x, new_y] = -1
        }
    }
    return (F)
}

main <- function() {
    sims = 10
    ctr = 0
    number_of_moves = c()

    solve(board, 1, 1, move_x, move_y, pos)



    for (x in board) {
        for (y in board) {
            number_of_moves <- c(number_of_moves, board[x, y])
        }
    }
    print(board)
    print(paste("Minimum number of moves: ", min(number_of_moves)))
}


main()

Answer 1

在 R 中，当一个函数对其参数之一进行更改时，它只会更改本地副本，而不是原始变量。

例如，在此 R 代码段中，我们可以看到该函数实际上并未修改变量 l。

try_to_modify <- function(l) l[[1]] <- -100

l <- list(1)
try_to_modify(l)
l
#> [[1]]
#> [1] 1

将此与 python 进行对比，它实际上确实修改了 l.

# (python code)
def try_to_modify(l):
  l[0] = -100

l = [1]
try_to_modify(l)
l
#> [-100]

如果你想让一个函数向调用者传达一些东西，它要么需要修改一个全局变量（这通常不是最好的解决方案），要么它需要使用 return 值。（有一些例外，但通常是这样的）。

因此，您可以 return board 或 NULL.

而不是 returning TRUE 或 FALSE

valid_move <- function (x, y, board) {
  x >= 1 && y >= 1 && x <= 8 && y <= 8 && board[x, y] == -1
}

solve <- function (board, curr_x, curr_y, move_x, move_y, pos) {
  if (pos == 64) {
    return (board)
  }
  for (i in seq(1, 8)) {
    new_x = curr_x + move_x[i]
    new_y = curr_y + move_y[i]
    
    if (valid_move(new_x, new_y, board)) {
      board[new_x, new_y] = pos
      result <- solve(board, new_x, new_y, move_x, move_y, (pos + 1))
      if (!is.null(result)) {
        return (result)
      }
      board[new_x, new_y] = -1
    }
  }
  # Return NULL
  # As this is the last result of the function, you don't need to write `return (NULL)`
  NULL
}

final_board <- solve(
  board = matrix(
    c(0, rep_len(-1, 63)),
    nrow = 8,
    ncol = 8,
    byrow = TRUE
  ),
  curr_x = 1,
  curr_y = 1,
  move_x = c(2, 1,-1,-2,-2,-1, 1, 2),
  move_y = c(1, 2, 2, 1,-1,-2,-2,-1),
  pos = 1
)

final_board
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    0   59   38   33   30   17    8   63
#> [2,]   37   34   31   60    9   62   29   16
#> [3,]   58    1   36   39   32   27   18    7
#> [4,]   35   48   41   26   61   10   15   28
#> [5,]   42   57    2   49   40   23    6   19
#> [6,]   47   50   45   54   25   20   11   14
#> [7,]   56   43   52    3   22   13   24    5
#> [8,]   51   46   55   44   53    4   21   12

为什么这个 R 版本的 Knight's Tour 不起作用？

Why is this R version of Knight's Tour not working?

r

oop

knights-tour