This is the 19th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Given an integer n, return solutions to all the different queens of n problems.”

Title link:

Source: LeetCode

Link: 51.N Queen – LeetCode (leetcode-cn.com)

2

The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other.

Given an integer n, return all the different solutions to the n queen problem.

Each solution contains a different chess placement scheme for the N-queen problem, in which ‘Q’ and ‘.’ represent queens and slots, respectively.

Example 1: input: n = 4 output: [[". Q.. ", "... Q ", "Q...", ".. Q. "], [".. Q. ", "Q...", "... Q ", ". Q.. "]] : as shown in the above, 4 queen problems exist two different solutions.Copy the code
Example 2: Input: n = 1 Output: [["Q"]]Copy the code

Second, the problem solving

1. Analysis of ideas

The N queen problem is a classic backtracking problem. First, analyze the rules, N queens are placed on an N*N board, and then queens can’t attack each other.

The direct approach is to enumerate all possible cases of violence, and then judge the case of not attacking each other. However, the time complexity of violence enumeration is very high, and it must be optimized by using constraints.

Possible solutions can be found by backtracking. First, an array is used to record the column subscripts of each queen in each row. After placing a queen in each row in turn, the position where the next queen is placed cannot have an attack on the position where the queen has been placed.

In order to reduce the total time complexity, it is necessary to quickly determine whether each position can have a queen when placing a queen, so that the column and two slashes at that position can be determined in O(1) time.

2. Code implementation

Code reference:

public class Solution {
    List<IList<string>> res;
    public IList<IList<string>> SolveNQueens(int n) {
        res = new List<IList<string> > ();char[][] board = new char[n][];
        for (int i = 0; i < n; ++i) board[i] = new char[n];
        foreach (char[] chars in board){
            Array.Fill(chars, '. ');
        }
        backTrack(board, 0);
        return res;
    }
    private void backTrack(char[][] board, int row){
        if (row == board.Length){
            res.Add(charToString(board));
            return;
        }
        int n = board[row].Length;
        for (int col = 0; col < n; ++col){
            if(! isValid(board, row, col))continue;
            board[row][col] = 'Q';
            backTrack(board, row + 1);
            board[row][col] = '. '; }}private bool isValid(char[][] board, int row, int col){
        int rows = board.Length;
        foreach (char[] chars in board) if (chars[col] == 'Q') return false;
        for (int i = row - 1, j = col + 1; i >= 0 && j < rows; i--, j++){
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    private List<string> charToString(char[][] array){
        List<string> result = new List<string> ();foreach (char[] chars in array) result.Add(new String(chars));
        returnresult; }}Copy the code

3. Time complexity

Time complexity: O(N!)

Where N is the number of queens.

Space complexity: O(N)

Where N is the number of queens.

Third, summary

This is a good way to think about it.

Iqiyi and byte written tests have appeared this question.