4

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

1

Q

def solveNQueens(n):
    result = []

    # 检查当前位置是否可以放置皇后
    def is_valid(row, col, cols, diag1, diag2):
        if col in cols or (row - col) in diag1 or (row + col) in diag2:
            return False
        return True

    # 回溯函数
    def backtrack(row, cols, diag1, diag2, board):
        # 如果所有的皇后都已放置，则保存当前解法
        if row == n:
            result.append(["".join(row) for row in board])
            return
        
        for col in range(n):
            if is_valid(row, col, cols, diag1, diag2):
                # 放置皇后
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = 'Q'
                
                # 递归放置下一行
                backtrack(row + 1, cols, diag1, diag2, board)
                
                # 回溯
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
                board[row][col] = '.'

    # 初始化棋盘
    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return result

n = int(input())
solutions = solveNQueens(n)
for solution in solutions:
    for row in solution:
        print(row)
    print()  # 每个解法之间空一行

import java.util.*;

public class Main {
    
    // 判断当前位置是否合法
    public static boolean isValid(int row, int col, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) {
        return !cols.contains(col) && !diag1.contains(row - col) && !diag2.contains(row + col);
    }

    // 回溯函数
    public static void backtrack(int row, int n, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2, List<List<String>> result, char[][] board) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] rowArray : board) {
                solution.add(new String(rowArray));
            }
            result.add(solution);
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, cols, diag1, diag2)) {
                board[row][col] = 'Q';
                cols.add(col);
                diag1.add(row - col);
                diag2.add(row + col);
                backtrack(row + 1, n, cols, diag1, diag2, result, board);
                board[row][col] = '.';  // 回溯
                cols.remove(col);
                diag1.remove(row - col);
                diag2.remove(row + col);
            }
        }
    }

    // 主函数
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>();
        Set<Integer> diag2 = new HashSet<>();
        backtrack(0, n, cols, diag1, diag2, result, board);
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<List<String>> solutions = solveNQueens(n);
        for (List<String> solution : solutions) {
            for (String row : solution) {
                System.out.println(row);
            }
            System.out.println();  // 每个解法之间空一行
        }
    }
}

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

// 判断当前位置是否合法
bool isValid(int row, int col, set<int>& cols, set<int>& diag1, set<int>& diag2) {
    return !cols.count(col) && !diag1.count(row - col) && !diag2.count(row + col);
}

// 回溯函数
void backtrack(int row, int n, set<int>& cols, set<int>& diag1, set<int>& diag2, vector<vector<string>>& result, vector<string>& board) {
    if (row == n) {
        result.push_back(board);
        return;
    }
    
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, cols, diag1, diag2)) {
            board[row][col] = 'Q';
            cols.insert(col);
            diag1.insert(row - col);
            diag2.insert(row + col);
            backtrack(row + 1, n, cols, diag1, diag2, result, board);
            board[row][col] = '.';  // 回溯
            cols.erase(col);
            diag1.erase(row - col);
            diag2.erase(row + col);
        }
    }
}

// 主函数
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    set<int> cols, diag1, diag2;
    backtrack(0, n, cols, diag1, diag2, result, board);
    return result;
}

int main() {
    int n;
    cin >> n;
    vector<vector<string>> solutions = solveNQueens(n);
    for (const auto& solution : solutions) {
        for (const auto& row : solution) {
            cout << row << endl;
        }
        cout << endl;  // 每个解法之间空一行
    }
    return 0;
}