Yêu cầu trợ giúp khắc phục sự cố C++ Tám mã câu đố queens

Question

Tôi đã viết một hàm trong mã C++ cho eight queens problem. Chương trình được cho là in ra tất cả 92 giải pháp có thể. Tôi chỉ có thể chạy tới 40. Không biết vấn đề ở đâu. Cố gắng gỡ lỗi nhưng tôi vẫn bị mắc kẹt.

#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

Sự cố của bạn ở chức năng ok. Nó có ba lỗi, tất cả liên quan đến giới hạn của ma trận của bạn. Lỗi đầu tiên (mà sẽ nếu bất cứ điều gì làm cho bạn nhận quá nhiều giải pháp), là ở đây:

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

này sẽ không bao giờ kiểm tra cột 0. Xét nghiệm này nên c >= 0.

Hai lỗi khác, mà gây ra hành vi không thể đoán trước, đang ở đây:

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 

Điều này có thể gây ra ok chức năng để trả lại một số tùy ý các âm tính giả. Trong trường hợp của tôi, biên dịch và chạy chương trình của bạn với hai lỗi này không tạo ra giải pháp nào. Nó chỉ là tình cờ mà nó tạo ra 40 giải pháp cho bạn.

Sự cố là một lần nữa với giới hạn. Biến số i đang di chuyển từ 1 đến và bao gồm c, vì vậy, c-i sẽ di chuyển xuống từ c-1 đến 0, như dự định.

Tuy nhiên, bạn không kiểm tra xem r-i và r+i vẫn nằm trong giới hạn của ma trận hay không. Hãy xem xét trường hợp r = 7 và i = 4. Sau đó, r+i = 11, chạy qua cuối hàng. Tương tự, nếu r = 0 và i là bất kỳ điều gì khác ngoài 0, r-i sẽ là số âm và chạy qua đầu hàng.

Bạn cần thêm các kiểm tra bổ sung để đảm bảo rằng các giá trị hàng được sử dụng trong các thử nghiệm trong vòng lặp này nằm trong khoảng từ 0 đến 7. Bạn có thể tận dụng hành vi đoản mạch của các toán tử logic trong C++ để làm điều này, ví dụ:

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

sẽ kiểm tra board[r-i][c-i] chỉ khi <test> là đúng.

Tôi sẽ thêm các sửa chữa vào hai lỗi thứ hai này dưới dạng bài tập cho bạn, vì đây rất có thể là bài tập về nhà (và nếu có, bạn nên thêm thẻ bài tập về nhà vào câu hỏi) .