Почему эта R-версия Knight's Tour не работает?

Я новичок в R и пытаюсь найти наименьшее количество ходов, которое требуется коню, чтобы перемещаться по шахматной доске, когда он начинает с угла.

Я использовал алгоритм Python с этого веб-сайта: https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/

и я попытался перевести это на Р.

Однако когда я запускаю программу, она выводит:

 [,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()

r oop knights-tour
person Kyle Angelo Gonzales    schedule 16.10.2020    source источник
comment
У вас есть два разных board: один находится в глобальной области видимости, а другой передается через функции. Глобальный не изменяется функцией solve. Если вы добавите print(board) в предложение if (pos == 64) { ... }, вы увидите окончательное состояние платы, которое вы передаете через функции. Изменить глобальную доску изнутри функции можно, например, с помощью board[new_x, new_y] <<- -1.   -  person Bas    schedule 16.10.2020
comment
Я не думаю, что это «правильный» S4 OOP, может кто-нибудь опубликовать ссылку?   -  person smci    schedule 22.10.2020

Ответы (1)


arrow_upward
1
arrow_downward

В 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]

Если вы хотите, чтобы функция что-то сообщала вызывающему, ей необходимо либо изменить глобальную переменную (что обычно не лучшее решение), либо использовать возвращаемое значение. (Есть некоторые исключения, но в основном это работает).

Поэтому вместо возврата TRUE или FALSE вы можете вернуть board или NULL.

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
person Paul    schedule 17.10.2020
comment
Привет, спасибо за помощь! Мне просто интересно, в чем разница между результатом возврата и платой возврата? Кроме того, я добавил оператор печати в final_board, потому что не было вывода, ха-ха - person Kyle Angelo Gonzales; 17.10.2020
comment
board - текущая доска. result - следующая доска - результат повторного вызова solve. Когда вызывается return (board), это базовый случай. Когда вызывается result <- solve(...), это рекурсивный случай. - person Paul; 17.10.2020