驭码——C++语言算法强度测试

#include <iostream>
#include <vector>
using namespace std;

class NQueens {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;
        vector<string> board(n, string(n, '.'));  // 初始化棋盘
        backtrack(0, board, solutions);
        return solutions;
    }

private:
    void backtrack(int row, vector<string>& board, vector<vector<string>>& solutions) {
        if (row == board.size()) {
            solutions.push_back(board);
            return;
        }
        
        int n = board.size();
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';  // 放置皇后
                backtrack(row + 1, board, solutions);  // 递归下一行
                board[row][col] = '.';  // 回溯
            }
        }
    }
    
    bool isValid(vector<string>& board, int row, int col) {
        // 检查上方列
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        
        // 检查左上方对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        // 检查右上方对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.size(); i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        return true;
    }
};

// 打印解决方案
void printSolutions(const vector<vector<string>>& solutions) {
    for (size_t k = 0; k < solutions.size(); k++) {
        cout << "Solution " << k + 1 << ":" << endl;
        for (const auto& row : solutions[k]) {
            cout << row << endl;
        }
        cout << endl;
    }
}

int main() {
    int n = 8;
    NQueens solver;
    vector<vector<string>> solutions = solver.solveNQueens(n);
    
    cout << "Total solutions for " << n << " queens: " << solutions.size() << endl;
    cout << "First 2 solutions:" << endl;
    printSolutions(vector<vector<string>>(solutions.begin(), solutions.begin() + min(2, (int)solutions.size())));
    
    return 0;
}

2 
2 
S. 
#T 
2 
RD 
DR 
3 
S.# 
.#. 
.T# 
3 
RL 
DDD 
DDRR 

I get there!
I am dizzy!
I have no idea!
I am out!
I get there!