拿不下的除了她,还有bug。八皇后问题

从0,0开始dfs

check之后如果ok就下一列继续搜

如果拉了就搜同行的下一列

#include <iostream>
#include <vector>

using namespace std;
// 只需要在nxn的表格中放n个棋子
char board[15][15] = {'0'};
vector<int> line;
vector<vector<int>> ans;
int scale;
inline bool check(int col, int row)
{
    // 检查列
    for (int i = 0; i < scale; i++)
    {
        if (board[i][col] == 'Q')
        {
            return false;
        }
    }
    // 检查行
    for (int i = 0; i < scale; i++)
    {
        if (board[row][i] == 'Q')
        {
            return false;
        }
    }
    // 检查左上
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右上
    for (int i = row, j = col; i >= 0 && j < scale; i--, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查左下
    for (int i = row, j = col; i < scale && j >= 0; i++, j--)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    // 检查右下
    for (int i = row, j = col; i < scale && j < scale; i++, j++)
    {
        if (board[i][j] == 'Q')
        {
            return false;
        }
    }
    return true;
}

void dfs(int col, int row)
{
    if (line.size() == scale)
    {
        ans.push_back(line);
        line.clear();
        return;
    }

    if (col >= scale || row >= scale)
    {
        return;
    }
    if (col >= scale && row >= scale)
    {
        line.clear();
        return;
    }

    if (check(col, row))
    {

        line.push_back(col);

        board[row][col] = 'Q';

        for (int i = 0; i < scale; i++)
        {
            dfs(i, row + 1);
        }

        board[row][col] = '0';

        line.pop_back();
    }
    else
    {
        dfs(col + 1, row);
    }

}
int main()
{
    cin >> scale;
    //把第一行的所有点进行dfs
    //这里写歪了,第一个参数是col,第二个参数是row
    for (int i = 0; i < scale; i++)
    {
        dfs(i, 0);
    }
    int count = 0;
    for (auto p : ans)
    {
        if (count == 3)
        {
            break;
        }
        for (auto q : p)
        {
            cout << q << " ";
        }
        cout << endl;
        count++;
    }
    cout << ans.size() << endl;
    return 0;
}