I'm new to R and I'm trying to find the least number of moves it takes for the knight to move around a chess board when it starts from the corner.
I used the Python algorithm from this website: https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/
and I tried to translate it to R.
However, when I run the program, its output is:
[,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"
What can I do to fix this issue?
This is the code:
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()
In R, when a function makes changes to one of its arguments, it only makes changes to a local copy, not the original variable.
For example, in this R snippet, we can see the function doesn't actually modify the variable l.
try_to_modify <- function(l) l[[1]] <- -100
l <- list(1)
try_to_modify(l)
l
#> [[1]]
#> [1] 1
Contrast this to python, where it actually does modify l.
# (python code)
def try_to_modify(l):
l[0] = -100
l = [1]
try_to_modify(l)
l
#> [-100]
If you want a function to communicate somthing to the caller, it either needs to modify a global variable (which generally isn't the best solution), or it needs to use the return value. (There are some exceptions, but that's generally how it works).
So instead of returning TRUE or FALSE, you can return board or 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