백 트랙을 사용하는 N 개의 퀸

Question

백 트랙을 사용하여 N 개의 퀸즈 문제에 대한 솔루션을 구현했습니다. 나는 모든 왼쪽 여왕의 위치가 안전한지 여부를 확인하고 있는데, 왼쪽 위, 오른쪽 위, 위쪽을 확인한 다음 그것을 행에 배치합니다. 그렇지 않으면 되돌아갑니다.

여기에는 내가 놓친 거지 모르는

6으로, 다른 사람을 위해 같은 4, 8로 N의 일부 값에 대한 정확한 솔루션을 제공하지만, 올바르지 않습니다. 어떤 도움을 주시면 감사하겠습니다. 여기

코드입니다 :

int S; 
static int cnt=0; 

int safepos(int board[][S+1],int i,int j) 
{ 
    if(i==1)   
    return 1; 

    int a,b; 
    a=i-1; 
    b=j-1; 

    //checking for top-left side 
    while(a>0 && b>0) 
    { 
     if(board[a--][b--]==1) 
     return 0; 
    } 

    a=i-1; 
    b=j+1; 
    //checking for top-right side  
    while(a>0 && b<=S) 
    { 
     if(board[a--][b++]==1) 
     return 0; 
    } 

    //checking for the same column   
    for(a=1;a<i;a++) 
     if(board[a][j]==1) 
      return 0; 
    return 1; 
} 

void Nqueens(int board[][S+1],int N,int n) //n is the number of the rows 
{ 
    if(n==N+1) //for those which reaches the last position we will have a solution 
    { 
     cnt++; 
     return;  
    } 
    int i;  
    for(i=1;i<=N;i++) //for every column 
    { 
     if(safepos(board,n,i)) 
     { 
      board[n][i]=1;  
      Nqueens(board,N,n+1); //checking for next row 
     } 
     board[n][i]=0; 
    } 
} 

int main() 
{ 
    int N=6; 
    S=N; 
    int board[N+1][N+1];  
    Nqueens(board,N,1); 
    printf("%d",cnt); 
    return 0; 
} 

Answer 1

되돌아 아이디어의 구현이 올바른지

이 문제는 기본에 의해, 배열 '보드'의 값을 수동으로 0으로 초기화 될 수있다는 사실에서 온다 배열에는 정의되지 않은 값이 있습니다. 그렇게하면 정답을 얻어야하며 코드를 테스트했습니다. 배열 초기화와 관련된 자세한 내용은 http://www.fredosaurus.com/notes-cpp/arrayptr/array-initialization.html

Answer 2

을 참조하십시오.이 답변을 수락했지만 행 0 = 0에 대한 오프셋을 방해하지 않으므로 0으로 초기화 된 벡터를 사용하는 구현을 공유하려고합니다.

#include <iostream> 
#include <vector> 

const int GRID_SIZE = 8; 


bool isValid (int queenNum, int col, std::vector<int>& cols) 
{ 
    // check for other queen number that collide with this one 
    for (int queenRow = 0; queenRow < queenNum; ++queenRow) 
    { 
    int queenCol = cols[queenRow]; 

    if (col == queenCol) 
     return false; // same col 

    if ((queenNum - queenRow) == abs(queenCol-col)) 
     return false; // same diagonal 
    } 
    return true; 
} 

void solve(int queenNum, std::vector<int>& cols, std::vector<std::vector<int> >& results ) 
{ 
    if (queenNum == GRID_SIZE) 
    { 
    // we have a solution 
    results.push_back (cols); 
    } 

    for (int i = 0; i < GRID_SIZE; ++ i) 
    { 
    if (isValid(queenNum,i,cols)) 
    { 
     cols[queenNum] = i; 
     solve(queenNum + 1,cols, results); 
    } 
    } 
} 

void drawLine() { 
    std::string line; 
    for (int i=0;i<GRID_SIZE*2+1;i++) 
    line.append("-"); 
    std::cout << line << std::endl; 
} 

void printBoard(std::vector<int>& cols) 
{ 
    drawLine(); 
    for(int i = 0; i < GRID_SIZE; i++){ 
    std::cout << "|"; 
    for (int j = 0; j < GRID_SIZE; j++){ 
     if (cols[i] == j) { 
     std::cout << "Q|"; 
     } else { 
     std::cout << " |"; 
     } 
    } 
    std::cout << std::endl; 
    drawLine(); 
    } 
    std::cout << "" << std::endl;; 
} 

void printBoards(std::vector<std::vector<int> >& boards) { 
    for (int i = 0; i < (int)boards.size(); i++) 
    { 
    printBoard(boards[i]); 
    } 
} 



int main() 
{ 
    std::vector<int> cols (GRID_SIZE, -1); 
    std::vector<std::vector<int> > results; 
    solve(0, cols, results); 
    printBoards(results); 
    std::cout << results.size() << std::endl; 
    return 0; 
}