尋求幫助解決C++八皇后拼圖代碼

Question

我寫了一個函數在C + +代碼爲eight queens problem。該計劃應該打印出所有92種可能的解決方案。我只能運行到40個。不知道問題出在哪裏。嘗試調試，但我仍然卡住。

#include "stdafx.h" 
#include <cmath> 
#include <iostream> 
using namespace std; 

bool ok(int board[8][8]){ 
    for(int c = 7; c > 0; c--){ 
     int r = 0; 
     while(board[r][c] != 1){ 
      r++; 
     } // while loop 

     for(int i = 1; i <= c; i++){ 
      if(board[r][c-i] == 1) 
       return false; 
      else if (board[r-i][c-i] == 1) 
       return false; 
      else if (board[r+i][c-i] == 1) 
       return false; 
     } // for loop 

    } // for loop 
     return true; 
} // ok 

void print(int board[8][8], int count){ 
    cout << count << endl; 
    for(int i = 0; i < 8; i++){ 
     for(int j = 0; j < 8; j++){ 
      cout << board[i][j]; 
     } // for loop 
     cout << endl; 

    } // for loop 

    cout << endl; 
} // print board 

int main(){ 

    int board[8][8]={0}; 
    int count = 0; 
    for(int i0 = 0; i0 < 8; i0++) 
     for(int i1=0; i1 < 8; i1++) 
      for(int i2 = 0; i2 < 8; i2++) 
     for(int i3 = 0; i3 < 8; i3++) 
      for(int i4 = 0; i4 < 8; i4++) 
      for(int i5 = 0; i5 < 8; i5++) 
       for(int i6 = 0; i6 < 8; i6++) 
       for(int i7 = 0; i7 < 8; i7++){ 
       board[i0][0]=1; 
          board[i1][1]=1; 
          board[i2][2]=1; 
          board[i3][3]=1; 
          board[i4][4]=1; 
          board[i5][5]=1; 
          board[i6][6]=1; 
          board[i7][7]=1; 

          if(ok(board))print(board, ++count); 

          board[i0][0]=0; 
          board[i1][1]=0; 
          board[i2][2]=0; 
          board[i3][3]=0;   
          board[i4][4]=0; 
          board[i5][5]=0; 
          board[i6][6]=0; 
          board[i7][7]=0; 

           } 
    return 0; 
} 

Answer 1

你的問題是在ok函數。它有三個錯誤，都與你矩陣的界限有關。第一個錯誤（這將如果有的話，因爲你收到太多解決方案），是在這裏：

for(int c = 7; c > 0; c--){ 

這不會檢查列0的測試應該是c >= 0。

其他兩個錯誤，這會導致不可預知的行爲，都在這裏：

for(int i = 1; i <= c; i++){ 
     if(board[r][c-i] == 1) 
      return false; 
     else if (board[r-i][c-i] == 1) 
      return false; 
     else if (board[r+i][c-i] == 1) 
      return false; 
    } // for loop 

這可能會導致ok函數返回假陰性任意數量。在我的情況下，用這兩個錯誤編譯和運行你的程序不會產生任何解決方案。只有偶然，它纔會爲您生成40個解決方案。

問題再次出現界限。按照預期，i變量從1上移至幷包括c，因此c-i從c-1下移至0。

但是，您不檢查r-i和r+i是否仍在矩陣範圍內。考慮r = 7和i = 4的情況。然後，r+i = 11，它運行在行的末尾。同樣，如果r = 0和i是0以外的任何值，則r-i將爲負數，並且會在該行的開頭處運行。

您需要添加額外的檢查以確保此循環中測試中使用的行值在0到7的範圍內。您可以利用C++中邏輯運算符的短路行爲來執行這一點，例如：

else if (<test> && board[r-i][c-i] == 1) 

將檢查board[r-i][c-i]只有<test>是真實的。

因爲這很可能是一項家庭作業（如果是的話，您應該在問題中添加[家庭作業]標籤），我將離開時添加這些第二個錯誤的更正作爲練習， 。