[datatable-help] unable to stop a recursive function performing knight's tour

[jadame]

Hi all, 

I am trying to develop a function to perform knight moves over a
"chessboard" of 10 rows and 14 columns.

I want to be able to choose one random position of the board and then tour
the board with knight moves from that position, so that I can obtain a
matrix of moves afterwards (given an initial position). Then, I would like
to include the code producing the matrix of moves in a loop to finally
obtain a set of 1000 different matrices, each one from random initial
positions.

I adapted the code appearing in this website
https://rosettacode.org/wiki/Knight%27s_tour#R

#---------------------------------------------------------------------
# M x N 
M = 10; N = 14; board = matrix(0, nrow = M, ncol = N)

# Get/Set value on a board position.
getboard = function (position)    { board[position[1], position[2]] }
setboard = function (position, x) { board[position[1], position[2]] <<- x }

# (Relative) Hops of a Knight.
hops = cbind(c(-2, -1), c(-1, -2), c(+1, -2), c(+2, -1),
             c(+2, +1), c(+1, +2), c(-1, +2), c(-2, +1))

# Validate a move.
valid = function (move) {
  all(1 <= move & move <= c(M, N)) && (getboard(move) == 0)
}

# Moves possible from a given position.
explore = function (position) {
  moves = position + hops
  cbind(moves[, apply(moves, 2, valid)])
}

# Possible moves sorted according to their Wornsdorff cost.
candidates = function (position) {
  moves = explore(position)
  
  # No candidate moves available.
  if (ncol(moves) == 0) { return(moves) }
  
  wcosts = apply(moves, 2, function (position) { ncol(explore(position)) })
  cbind(moves[, order(wcosts)])
}

# Recursive function for touring the board.
knightTour = function (position, moveN) {
  
  if(moveN>(M*N)){
    print(board) #as an example to observe the result, but I actually would
like to do is to store the matrix board
  }
  # Available moves.
  moves = candidates(position) 
  
  # None possible. Backtrack.
  if (ncol(moves) == 0) { return() }
  
  # Make a move, and continue the tour.
  apply(moves, 2, function (position) {
    setboard(position, moveN)
    knightTour(position, moveN + 1)
    setboard(position, 0)
  })
  
}

#As an example to begin a tour:
position<-c(1,1)        #coordinates of the first position
setboard(position,1)    #assign 1 to the first position
knightTour(position,2)  #begin tour

#---------------------------------------------------------------------

When I run the code described above, I get the same matrix board printed
over and over in the console until I have to press the stop button.
Apparently, the recursive function knightTour enters in a loop that I'm not
able to stop. I thought that the if(moveN>(M*N)) would avoid to continue the
loop once moveN>140, but doesn't happen, I think, so I don't know how to
break the cycle.  

I've used functions like stop() or quit() after the line print(board), but
they break the loop for debugging or end the R session, so they are not
useful for me as I want to use the function knightTour in a loop to finally
enable the performance of 1000 simulations (i.e. to obtain 1000 matrices).

Additionally, I would like to be able to save the result of the knightTour
function, i.e. the matrix of moves. I've used return(board) instead of
print(board) but doesn't work so I'm not able to save the board matrix as a
result either.

The thing is that I would like to do something like this:

#My objective pursues....
position=list();BOARD=list()
for(i in 1:1000){
  position[[i]]<-c(sample(1:10,1),sample(1:14,1))
  setboard(position[[i]],1)
  BOARD[[i]]<-knightTour(position[[i]],2)  #store BOARD list containing the
1000 matrices obtained
}

Your help would be very welcome
Thank you so much




--
Sent from: http://r.789695.n4.nabble.com/datatable-help-f2315188.html