CODEWITHSUNDEEP
rn-queens
user8915781
user8915781

Reputation:

R: Having trouble with N-Queens

I'm currently trying to complete the N-Queens problem. Specifically it targets 8 queens on an 8x8 board.

The first part is the problem. The first is an "safe" function that determines if a piece is safe when a queen is already pre-allocated in a matrix. So:

>chess.board <- matrix(data=0,8,8)

>chess.board[r,c] <- 1 #the r,c can be any row,column I choose

>chess.piece <- c(x,x) #the x,x could be for example two numbers that also represent a row and column

This then has to be run through an safe function as follows:

>safe(chess.piece,chess.board)

I am having several issues with this. I understand that the sum of the row, column and diagonal of the matrix from the chess.piece should be < 1 to return TRUE or if its more than > 0 it should return FALSE.

So far I have:

>safe <- function(a,b){
  if((sum(b[a,])<1) & (sum(b[,a])<1))
  {return(TRUE)
  }else{
    return(FALSE)
  }
}

This is just for the row/column but this sometimes returns a FALSE when it should be a TRUE. This happens when, for example, the chess.piece is set as c(3,6) and the matrix 1 is located at 1,3. It seems to be taking the 3 from chess.piece and conflating it with the wrong values in say column. Why is it doing this?

The next part is how on earth do I sum the total of a diagonal of a matrix based on the chess.piece location. This is really confusing me.

I'm fairly new to R and wondered if I could pick your guys brains. I don't necessarily want a direct solution but some pointers in the right direction would really help me out.

Thanks in advance, Jim.S

Upvotes: 1

Views: 459

Answers (2)

thc
thc

Reputation: 9705

You forgot to index x. Try this function:

safe <- function(x,y){
  if((sum(y[x[1],])<1) & (sum(y[,x[2]])<1))
  {return(TRUE)
  }else{
    return(FALSE)
  }
}

Upvotes: 2

Josh Eller
Josh Eller

Reputation: 2065

I can't really speak to the R aspect, but in terms of determining whether two queens are on the same diagonal, notice that:

  1. If two queens are on the same forward diagonal (like /) the sums of the row and column will always be equal.

  2. If two queens are on the same back diagonal (like ) the differences between the row and column will always be equal.

Upvotes: 0

Related Questions