用回溯方法解决Nqueens问题，并将其作为CSP的最大约束值

Question

所以我现在正在做一个项目，把N个皇后放在NxN板上，防止它们互相攻击。这个项目是一个入门级的人工智能课程。它有几个特定的标准来获得满分，即在5秒或更短的时间内为任何板大小找到最多3个解决方案，最多为N=100。我目前正试图通过选择最受约束的行来使其成为约束满足问题，如果我正确理解，这将防止更接近完全受攻击的行到达该问题。

最初，用户将输入一个列号，一个皇后将放在该列的第一行。从那里，攻击板将通过增加所有对角线和行和列的值来使用行和列的组合来更新，下面是前者和后者的一个小示例

        void main()
    {
        int size, row, col;
        row = 1;
        cout << "Enter the board size: ";
        cin >> size;
        cout << "Enter column of first queen: ";
        cin >> col;

        cols[row] = col; // cols store the column value of each queen in that particular row.
        updateAttack(row, col, +1, size);
        findNextQueen(size);

        // return here if we found all the solution
        //cout << solutionCount << " solutions found. see NQueen.out.\n";
        cout << solutionCount << " solutions found. see NQueen.out.\n";
        fout.close();
        system("pause");
    }

void updateAttack(int r, int c, int change, int size)       // Updates the attack board given the location a queen being placed
{
    int r1, c1;

    // update diagnals
    for (r1 = r - 1, c1 = c - 1; r1 >= 1 && c1 >= 1; r1--, c1--)
        attack[r1][c1] += change;

    for (r1 = r + 1, c1 = c + 1; r1 <= size && c1 <= size; r1++, c1++)
        attack[r1][c1] += change;

    for (r1 = r - 1, c1 = c + 1; r1 >= 1 && c1 <= size; r1--, c1++)
        attack[r1][c1] += change;

    for (r1 = r + 1, c1 = c - 1; r1 <= size && c1 >= 1; r1++, c1--)
        attack[r1][c1] += change;

    // update columns 
    for (r1 = 1, c1 = c; r1 <= size; r1++) // k goes to each row          
        attack[r1][c1] += change;
}

这个节目的主要问题是选择把女王放在哪一排。在一个简单的回溯方法中，通过递归调用放置皇后，您可以向下增加行，并将皇后放置在当前没有受到攻击的行的第一个空格中，然后对下一行和下一个皇后执行相同的操作，直到无法放置皇后，在这种情况下，您可以回溯并试图通过将前一个皇后移动到下一个位置来修复它。下面的一个例子是用回溯和没有实现CSP来完成的。

    void findNextQueen(int r, int size)
{
      for (int c=1;c<=size;c++)
      {
        if (attack[r][c]==0) // not under attack
        {   
            cols[r]=c;  // assign another queen
            if (r<size)
            {
                updateAttack(r,c,+1, size);
                findNextQueen(r+1, size);
                updateAttack(r,c, -1, size);
            }
            else
            {
                print1solution(size);
                if (solutionCount >= 3)
                {
                    cout << solutionCount << " solutions found. see NQueen.out.\n";
                    system("pause");
                    exit(0);
                }
            }
        }
      }
    return;
}

约束满足试图解决回溯过程中引起的一个问题，在该问题中，稍后可能会用攻击值完全填充下面的行，这将导致需要大量的回溯，从而增加大量的回溯时间。它通过尝试首先选择有更多空间的行来进行攻击，以防止它们丢失，并要求后期回溯。我的例子，这是造成的问题，目前，它似乎总是来0解决方案可能在下面。

void findNextQueen(int size)
{
    int bestRowCount = 0;
    int bestRow = 2;

    for (int r = 2; r <= size; r++)         // Meant to find the most constrained row and use that as my r value for attack array
    {

            int aRowCount = 0;      // Count of attacks in current row
            for (int c = 1; c <= size; c++)
            {
                if (attack[r][c] >= 1)
                {
                    aRowCount++;
                }
            }
            if ((aRowCount > bestRowCount) && (aRowCount != size))
            {
                bestRowCount = aRowCount;
                bestRow = r;
            }
    }
    for (int c = 1; c <= size; c++)
    {
        if (attack[bestRow][c] == 0) // not under attack
        {
            cols[bestRow] = c;  // assign another queen
            if (queensLeft(size) == 1)  // returns true if there are rows that still lack a queen
            {
                updateAttack(bestRow, c, +1, size);
                findNextQueen(size);
                cols[bestRow] = 0;
                updateAttack(bestRow, c, -1, size);
            }
            else
            {
                print1solution(size);
                if (solutionCount >= 3)
                {
                    cout << solutionCount << " solutions found. see NQueen.out.\n";
                    system("pause");
                    exit(0);
                }
            }
        }
    }
    return;
}

Answer 1

LeetCode中也引入了非常类似的问题：

https://leetcode.com/problems/n-queens-ii

您可以转到讨论并找到带有代码解决方案的解释。您将需要修改代码，以便在达到限制时返回可能的结果。