N皇后使用回溯

Question

我已經通過使用回溯實現了N皇后問題的解決方案。 我正在檢查每個女王的位置是否安全，方法是檢查它的左上角，右上角和頂部，然後將其放在行中，否則我會回溯。

這是給對於N一些值，比如4,8正確的解決方案，但不正確的人，如6

我不知道我錯過了什麼。任何幫助將不勝感激。

下面的代碼：

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

你執行的後退的想法是正確的，問題來自於一個事實，即陣列「公告板」的值必須手動初始化爲零，默認情況下，數組帶有未定義的值。如果你這樣做，你應該得到正確的答案，我測試了代碼。有關數組初始化的更多信息，請參閱http://www.fredosaurus.com/notes-cpp/arrayptr/array-initialization.html

Answer 2

我知道這是一個已接受的答案，但想分享我的實現，它使用的矢量初始化爲-1而不是零，因爲不會干擾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; 
}