In R: Avoid duplicates in selection from many rows

Summary: I have an array of 10 rows and 4 columns filled with numbers. I select one number from each row and want to avoid duplicates in the selection.

Elaborate: I have a grid of 100*100 cells. In that grid are 10 cells that contain a "person". In an iterative process I want to make the persons "walk around" in the grid, but I do not want to occur that two persons are in the same cell at the same time.

I have a vector that describes the positions of the 10 persons. It contains the cell numbers with a person. These positions are counting across all rows and columns (i.e. ranges from 1:10000). For example: Position 234 would be in the 3rd row, 34th column).

Positions<-sample(1:10000,10)   #Initial positions

What I did is to first make an array of the surrounding cells of each person (up, right, down, left) giving 4 positions for each person:

Surroundings<-array(c(Positions+100,Positions+1,Positions-100,Positions-1),dim=c(10,4))

I then take a random direction from each of the rows in Surroundings into vector PosNew. It is this last vector in which I want to avoid duplicates.

I could repeat the random selection process of PosNew until it has no duplicates, but this could take very long. There are probably more efficient ways to do this.

For simplicity sake, let's assume that persons do not walk off the grid and no other errors occur.

My script:

Positions<-sample(1:10000,10)   #Initial positions

for(i in 1:50) {
 Surroundings<-array(c(Positions+100,Positions+1,Positions-100,Positions-1),dim=c(10,4))
 PosNew<-Surroundings[cbind(1:10,sample(1:4,10,replace=TRUE))] 
 Dups<-length(which(duplicated(PosNew)==TRUE))
 Positions<-PosNew
}

I am looking for a way to check for duplicates in the selected new positions and make sure that Dups is never above zero. Any suggestions are welcome, including suggestions to make the code faster/more efficient.

Added: What could I do when at some point one or more of the persons really cannot move to an empty cell, because all 4 sides are occupied? I want that person to stay in its original cell. How to code that?

Thank you so much for your time!