2017-11-10 16 views
1

N-Queens 문제에 대한 해결책을 찾기 위해 오늘 일찍 게시 한 게시물을 작성했습니다.R : N-Queens 대각선 찾기

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

기본적에 작동 : I는 수평 및 수직 평면에 다음 코드를

>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 

Currentley :

>safe(chess.piece,chess.board) 

이 첫 번째 부분은 다음 함수를 판정한다 행/열 합계 및 더 큰지 (FALSE) 또는 같음 (TRUE)을 0으로 확인합니다. 그러나 세계에서 어떻게 결정된 행/열을 기준으로 체스 보드 행렬의 대각선 합계를 찾을 수 있습니까? 체스 조각으로?! 나는 R을 처음부터 알기 때문에 머리카락을 찢어 내고있다. 그러나 나는 해결책이 필요하고 그것을 이해하는 것처럼 보이지 않는다. 도움이 될 것입니다. 사전에 감사드립니다, JS

답변

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 
+0

귀하의 생명의 은인 존. 훌륭한 일! 나는 그것에 대해 너무 좌절감을 느낀다. 나는 문제 해결을 돕기 위해 다른 기능을 개발하는 것을 결코 고려하지 않았다! 다시 한 번 감사드립니다! –

1

는 검사해야 고려한다면 판 소자 (X, Y) 어떤 대각선 요소에서 공격을받을 수 있습니다. (x, y)는 대각선 요소에 놓인 요소가 여왕이면 대각선으로 공격 할 수 있습니다. 여론 (p, q)은 여왕이있는 보드 요소입니다. 요소 (x, y)가 보드의 대각선 좌표에 놓이는 조건 요소 (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]에있는 요소가 대각선 요소에 의해 공격 받거나 그렇지 않으면 다음과 같이됩니다 : -

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

희망이 도움이!