R：N 皇后找到对角线

Question

今天早些时候发了一个 post 表示我正在尝试找到 N 皇后区问题的解决方案。第一部分是确定以下函数：

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

基本上用于对 rows/columns 求和并检查是否大于 (FALSE) 或等于 (TRUE) 为 0。但是我究竟如何找到 chess.board 矩阵的对角线和在 rows/columns 上由 chess.piece 决定？！由于我是 R 的新手，所以我为此大发雷霆，但我需要一个解决方案，但似乎无法弄清楚。任何帮助将不胜感激！提前致谢，J.S

Answer 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
}

On Edit: 鉴于预期的应用，我编写了 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) 是否可以从任何对角线元素攻击。如果位于其对角线元素上的任何元素是 queen.Assume (p,q) 是具有元素 (x,y) 位于其上的 queen.Now 条件的棋盘元素，则 (x,y) 可以被对角线攻击棋盘元素 (p,q) 的对角坐标为 p+q == x+y 或 p-q == x-y 。这也可以解释为元素 (p,q) 和 (x,y) 位于的条件同样diagonal.So，如果在(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;
}

希望对您有所帮助！！！

R：N 皇后找到对角线

R: N-Queens finding the Diagonal

r

chess

n-queens

chessboard.js