R：N-Queens找到了对角线

Question

今天早些时候做了一个帖子，表示我试图找到解决N-Queens问题的方法。第一部分是确定以下功能：

>safe(chess.piece,chess.board)

哪里：

>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

目前我有水平和垂直平面的以下代码：

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

基本上用于对行/列进行求和并检查是否更大（FALSE）或等于（TRUE）为0.但是在世界上如何找到基于国际象棋确定的行/列的chess.board矩阵的对角线和.piece？！我正在扯掉我的头发，因为我对R很不错，但我需要一个解决方案而且似乎无法弄明白。任何帮助将不胜感激！在此先感谢，J.S

Answer 1

一种方法是编写几个函数来从方形矩阵中提取部分对角线，使用的事实是您可以使用1维索引，因为矩阵只是引擎盖下的向量，这些对角线对应于某些算术的索引序列：

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)]
}

这两个函数分别提取向上倾斜和向下倾斜的对角线。您可以使用这两个函数并像这样编写safe：

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
}

编辑：鉴于目标应用，我写了udiag()和ddiag()只用于方形矩阵。由于它们可能在潜在的非方形矩阵中有其他用途，因此可以轻松修改它们以处理此类情况：

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)]
}

例如：

> 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

Answer 2

考虑您必须检查板元素（x，y）是否可以从任何对角线元素进行攻击。如果位于其对角元素上的任何元素是一个女王，则（x，y）可以被对角攻击。假设（p，q）是具有皇后的棋盘元素。元素（x，y）的现在条件位于棋盘的对角线坐标上element（p，q）将是p + q == x + y或pq == xy。这也可以解释为元素（p，q）和（x，y）位于同一对角线上的条件。所以，如果（p，q）有女王，我们必须检查（x，y）是否可以被这位女王攻击，其条件是： -

            if((board[p][q] == 1 ) && ((p+q == x+y) || (p-q == x-y))){
                return true; 
            }

用于检查（x，y）处的元素（即，板[x，y]是否受对角线元素攻击）的完整函数将是： -

for(int p=1;p<board.length;p++){
        for(int q=1;q<board.length;q++){

            if(p==x && q==y){   //skipping check if element under consideration is same
                continue;
            }

            if((board[p][q] == 1 )&& ((p+q == x+y) || (p-q == x-y))){
                return true;
            }
        }
    }

用于检查元素（x，y）是否受到攻击的完整函数将是： -

    public static boolean is_attacked(int x,int y,int board[][],int n){
    for(int i = 1;i < board.length;i++){
        if(board[x][i] == 1){            //if any cell in xth row is 1 i.e.,queen is there in that row
            return true;
        }
    }
    for(int i = 1;i < board.length;i++){     
        if(board[i][y] == 1){         //if any cell in yth column is 1 i.e.,queen is there in that column
            return true;
        }
    }
    for(int p=1;p<board.length;p++){
        for(int q=1;q<board.length;q++){

            if(p==x && q==y){
                continue;
            }

            if((board[p][q]== 1 )&& ((p+q== x+y) || (p-q == x-y))){
                return true;
            }
        }
    }
    return false;
}

希望这可以帮助！！！