c++ - 寻求帮助解决 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>是真的。

我将添加对这后两个错误的更正作为你的练习，因为这很可能是家庭作业(如果是，你应该在问题中添加 [homework] 标签)。