The n-queens puzzle is the problem of placing n queens on ann×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where'Q' and '.' both indicate a queen and an empty space respectively.

Thinking:

Classic N Queen’s question, you can refer to any algorithm book. Generally, it is solved through the retrospective method. Here is a solution that has not been optimized.

In fact, I have considered this problem, because the symmetry of the chessboard should have a better solution based on group theory. This is to consult a mathematician.

As long as the specific transformation is eliminated, only the number of solutions can be calculated. Of course, I hope the performance is better.

Question solution:

class Solution {
public:
    vector<vector<string>> solution;
    
    void generate_solution(const vector<int>& queen)
    {
        vector<string> s;
        for(int i = 0; i < queen.size(); ++i)
        {
            string l(queen.size(), '.');
            l[queen[i]] = 'Q';
            s.emplace_back(move(l));     // avoid copy!
        }
        solution.emplace_back(move(s));
    }
    
    void traverse_solution_space(vector<int>& queen, int placed, int total)
    {
        if (placed == total)
        {
            generate_solution(queen);    
            return;
        }
        
        // try place the queens
        for(int i = 0; i < queen.size(); ++i)
        {
            bool valid = true;
            // verify the position
            for(int j = 0; j < placed; ++j)
            {
                if (i == queen[j] ||  // same column
                    abs(queen[j] - i) == placed - j) // diagonal attack
                {
                    valid = false;
                    break;
                }
            }
            
            if (valid)
            {
                queen[placed] = i;
                traverse_solution_space(queen, placed + 1, total);
            }
        }
    }

    vector<vector<string> > solveNQueens(int n) {
        solution.clear();
        vector<int> queen(n);
        
        traverse_solution_space(queen, 0, n);
        
        return solution;
    }
};

class Solution {
public:
    vector<int> board;
    vector<int> avail;
    
    int valid_solutions;
    
    void traverse_solution_space(int k, int n)
    {
        if (k == n)
        {
            ++valid_solutions;
            return;
        }
        
        for(int i = 0; i < n; ++i)
            if (avail[i] == 0)
            {
                bool iok = true;
                for(int j = 0; j < k; ++j)
                    if (abs(board[j] - i) == k - j)
                    {
                        iok = false;
                        break;
                    }
                if (iok)
                {
                    avail[i] = 1;
                    board[k] = i;
                    traverse_solution_space(k + 1, n);
                    avail[i] = 0;
                }
            }
    }
    
    int totalNQueens(int n) 
    {
        valid_solutions = 0;
        
        board.resize(n);
        avail.resize(n);
        
        fill(begin(avail), end(avail), 0);
        
        traverse_solution_space(0, n);
        
        return valid_solutions;
    }
};