c++ - c++八皇后拼图程序的修改

Question

所以八皇后问题已经解决了很多次，但我还没有看到一个用 c++ 编写的程序允许用户输入一行以开始搜索。

作业指导:修改这个程序使得main() 不必仅从第 0 行开始。相反，程序将读取起始行从键盘输入数字(范围为 0 – 7)。对四大功能进行适当修改原始程序，这样它仍然可以打印出从指定行开始的可行位置。

这是原始程序的代码:

#include <iostream>
using namespace std;
const int NUMBER_OF_QUEENS = 8; // Constant: eight queens
int queens[NUMBER_OF_QUEENS];
// Check whether a queen can be placed at row i and column j
bool isValid(int row, int column)
{
 for (int i = 1; i <= row; i++)
 if (queens[row - i] == column // Check column
 || queens[row - i] == column - i // Check upper left diagonal
 || queens[row - i] == column + i) // Check upper right diagonal
 return false; // There is a conflict
 return true; // No conflict
}
// Display the chessboard with eight queens
void printResult()
{
 cout << "\n---------------------------------\n";
 for (int row = 0; row < NUMBER_OF_QUEENS; row++)
 {
 for (int column = 0; column < NUMBER_OF_QUEENS; column++)
 printf(column == queens[row] ? "| Q " : "| ");
 cout << "|\n---------------------------------\n";
 }
}
// Search to place a queen at the specified row
bool search(int row)
{
 if (row == NUMBER_OF_QUEENS) // Stopping condition
 return true; // A solution found to place 8 queens in 8 rows
 for (int column = 0; column < NUMBER_OF_QUEENS; column++)
 {
 queens[row] = column; // Place a queen at (row, column)
 if (isValid(row, column) && search(row + 1))
 return true; // Found, thus return true to exit for loop
 }
 // No solution for a queen placed at any column of this row
 return false;
}
int main()
{
 search(0); // Start search from row 0. Note row indices are 0 to 7
 printResult(); // Display result
 return 0;
}

这里是我到目前为止编写的代码，它运行不正确，我只做了轻微的修改。我不完全确定如何解决这个问题，但 main() 完全符合修改的要求。

#include <iostream>
using namespace std;
const int NUMBER_OF_QUEENS = 8; // Constant: eight queens
int queens[NUMBER_OF_QUEENS];
// Check whether a queen can be placed at row i and column j
bool isValid(int row, int column)
{
    for (int i = 1; i <= row; i++)
        if (queens[row - i] == column // Check column
            || queens[row - i] == column - i // Check upper left diagonal
            || queens[row - i] == column + i) // Check upper right diagonal
            return false; // There is a conflict
    return true; // No conflict
}
// Display the chessboard with eight queens
void printResult(int row)
{
    cout << "\n---------------------------------\n";
    for (row; row < NUMBER_OF_QUEENS; row++)
    {
        for (int column = 0; column < NUMBER_OF_QUEENS; column++)
            printf(column == queens[row] ? "| Q " : "| ");
        cout << "|\n---------------------------------\n";
    }
}
// Search to place a queen at the specified row
bool search(int row)
{
    if (row == NUMBER_OF_QUEENS) // Stopping condition
        return true; // A solution found to place 8 queens in 8 rows
    for (int column = 0; column < NUMBER_OF_QUEENS; column++)
    {
        queens[row] = column; // Place a queen at (row, column)
        if (isValid(row, column) && search(row + 1))
            return true; // Found, thus return true to exit for loop
        }
        // No solution for a queen placed at any column of this row
        return false;
    }
    int main()
    {
        int inputRow;
        cout << "Enter the row to search from:" << endl;
        cin >> inputRow;
        search(inputRow); // Start search from row 0. Note row indices are 0         to 7
    printResult(inputRow); // Display result
    return 0;
}

现在我对编程和网站还很陌生，因为我去年才开始使用 java，一个半月前才开始使用 c++，所以如果我的格式不正确或措辞不佳，我深表歉意，但我对这个问题感到很困惑，非常感谢程序员在此站点上花费的任何时间以及您能给我的任何帮助。

Answer 1

您的实现存在一些错误。

如果要泛化算法，可以让用户选择第一个皇后的位置(行和列)。

#include <iostream>
using namespace std;
const int NUMBER_OF_QUEENS = 8; // Constant: eight queens
int queens[NUMBER_OF_QUEENS];

bool isValid(int row, int column);
bool search(int q);
                                    // Display the chessboard with the queens
void printResult()
{
    cout << "\n+---+---+---+---+---+---+---+---+\n";
    for ( int row = 0; row < NUMBER_OF_QUEENS; row++)
    {
        for (int column = 0; column < NUMBER_OF_QUEENS; column++)
            printf(column == queens[row] ? "| Q " : "|   ");
        cout << "|\n+---+---+---+---+---+---+---+---+\n";
    }
}

int main() {
    int iRow, iColumn;

    cout << "Please, enter the row and the column of the cell where you want to put the first Queen into." << endl;
    cout << "Input values must be in the range 0 - " << NUMBER_OF_QUEENS << ". Enter a letter to stop." << endl;        
    while (cin >> iRow && cin >> iColumn) {
        if ( iRow < 0 || iRow > NUMBER_OF_QUEENS - 1
             || iColumn < 0 || iColumn > NUMBER_OF_QUEENS - 1 ) continue;

        for ( int k = 0; k < NUMBER_OF_QUEENS; k++) queens[k] = - NUMBER_OF_QUEENS;
        queens[iRow] = iColumn;             // initialize the array with significant values. Ugly, I know.

        if ( !search(0) )                   // Start the search
            cerr << "Error: Unable to find a solution!\n";      
        printResult();                  // Display result
        }
    return 0;
}

你的检查功能没有做完整的扫描，我更喜欢这个:

// Check whether a queen can be placed at row i and column j
bool isValid(int row, int column)
{
    int d1 = column - row;
    int d2 = column + row;
    for (int i = 0; i < NUMBER_OF_QUEENS; i++) {
        if ( queens[i] == column                // Check column
            || queens [i] == d1                 // Check diagonals
            || queens [i] == d2 )
                return false; // There is a conflict
       d1++;
       d2--;
    }
   return true; // No conflict
}

但主要问题是搜索功能，它必须尝试一个可能的位置，如果无效则拒绝它:

// Search to place a queen at the specified row
bool search(int q)
{
    if (q >= NUMBER_OF_QUEENS)                          // Stopping condition, all rows visited
        return true;                                    // A solution found to place 8 queens in 8 rows
    if ( queens[q] != -NUMBER_OF_QUEENS )               // Skip the row if a queen is already there
        return search(q+1);                 
    else {

        for (int column = 0; column < NUMBER_OF_QUEENS; column++) {
            if (isValid(q, column)) {                   // First check, then
                queens[q] = column;                     // place a queen at (row, column)
                if ( search(q + 1) )  return true;      // Found, thus return true to exit for loop
                else queens[q] = - NUMBER_OF_QUEENS;    // Reject the wrong position
            }
        }
    }
        // No solution for a queen placed at any column of this row
    return false;
}

现在您可以测试程序了。例如，如果您输入 2 5，则输出为:

+---+---+---+---+---+---+---+---+
|   | Q |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   | Q |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   | Q |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   | Q |
+---+---+---+---+---+---+---+---+
|   |   | Q |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
| Q |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   | Q |   |
+---+---+---+---+---+---+---+---+
|   |   |   |   | Q |   |   |   |
+---+---+---+---+---+---+---+---+