Made a post earlier today expressing I was trying to find a solution to the N-Queens problem. The first part of this is determining the following function:
>safe(chess.piece,chess.board)
Where:
>chess.board <- matrix(0,8,8)
>chess.board[r,c] <- 1 #1 represents the queen which can be placed in any row/column on the board
>chess.piece <- c(x,x) #basically and row/column value I choose in the 8x8 matrix
Currently I have the following code for the horizontal and vertical planes:
>safe <- function(a,b){
if((sum(b[a[1],])<1) & (sum(b[,a[2]])<1))
{return(TRUE)
}else{
return(FALSE)
}
}
Basically works on summing the rows/columns and checking if greater (FALSE) or equal (TRUE) to 0. But how in the world do I find the diagonal sum of the chess.board matrix based on the rows/columns determined by the chess.piece ?! I am ripping my hair out over this as I am decently new to R but I need a solution and just can't seem to figure it out.
Any help would be greatly appreciated! Thanks in advance, J.S
One approach is to write a couple of functions to extract partial diagonals from a square matrix, using the fact that you can use 1-dimensional indexing since matrices are just vectors under the hood and these diagonals correspond to certain arithmetical sequences of indices:
udiag <- function(A,i,j){
n <- nrow(A)
a <- i + n*(j-1) - (n-1)*min(n-i,j-1)
b <- i + n*(j-1) + (n-1)*min(i-1,n-j)
A[seq(a,b,n-1)]
}
ddiag <- function(A,i,j){
n <- nrow(A)
a <- i + n*(j-1) - (n+1)*min(i-1,j-1)
b <- i + n*(j-1) + (n+1)*min(n-i,n-j)
A[seq(a,b,n+1)]
}
These two functions extract the upward slanting and downward slanting diagonals respectively. You can use these two functions and write your safe like this:
safe <- function(x,y){
i <- x[1]
j <- x[2]
sum(y[i,]) == 0 & sum(y[,j]) == 0 & sum(udiag(y,i,j)) == 0 & sum(ddiag(y,i,j)) == 0
}
On Edit: In view of the intended application, I wrote udiag() and ddiag() to work with square matrices only. Since they may have other uses in potentially nonsquare matrices, they can be easily modified to handle such cases:
udiag <- function(A,i,j){
m <- nrow(A)
n <- ncol(A)
a <- i + m*(j-1) - (m-1)*min(m-i,j-1)
b <- i + m*(j-1) + (m-1)*min(i-1,n-j)
A[seq(a,b,m-1)]
}
ddiag <- function(A,i,j){
m <- nrow(A)
n <- ncol(A)
a <- i + m*(j-1) - (m+1)*min(i-1,j-1)
b <- i + m*(j-1) + (m+1)*min(m-i,n-j)
A[seq(a,b,m+1)]
}
For example:
> A <- matrix(1:12,nrow = 3)
> A
[,1] [,2] [,3] [,4]
[1,] 1 4 7 10
[2,] 2 5 8 11
[3,] 3 6 9 12
> udiag(A,2,3)
[1] 6 8 10
> ddiag(A,2,3)
[1] 4 8 12