Original link: leetcode-cn.com/problems/n-…

Answer:

  1. The queen can attack all pieces in the same row, column, and hypotenuse.
  2. To find n queens is to find one queen on each row, and none of them can attack each other.
  3. Traverses the board line by line, placing the queen in a position in each row, saving her attackable columns and hypotenuse information toSetIn the.
  4. Then see if she attacks the queen already on the board by seeing if her columns and hypotenuse are already onSetIn the preserve.
  5. Repeat steps 2 and 3 recursively to find all possible queen positions.
  6. According to the queen position found, according to the requirements of the checkerboard pattern can be generated.
/ * * *@param {number} n
 * @return {string[][]}* /
var solveNQueens = function (n) {
  // The result of the final recursive output
  let queenPositions = []; // Save the position of the queen on the board in all solutions

  // Cache intermediate state
  let queenRow = []; // Save the queen position for each row
  let colSet = new Set(a);// Save the columns that the current queen may attack
  // Save the diagonal from upper right to lower left that the current queen may attack
  // In a square checkerboard, the points from the upper right corner to the lower left corner add up to the same values
  let trToBlSet = new Set(a);// Save the diagonal from top left to bottom right that the current queen may attack
  // In a square checkerboard, the points from the top left corner to the bottom right corner subtract the values of the vertical and horizontal axes
  let tlToBrSet = new Set(a);// Fix the current row to find all the positions in the current row that cannot be attacked by other queens
  function dfs(row) {
    // Recursive termination condition
    // When all rows have been traversed, it means that the queen can be placed in each row
    // Save the result and exit the recursion
    if (row >= n) {
      queenPositions.push(queenRow.slice());
      return;
    }

    // Iterate over the row corresponding to the current column, and print the unattacked queen position for each column through the for loop
    for (let col = 0; col < n; col++) {
      // The sum of row indexes plus column indexes, if the value has already been saved in Set
      // Indicates that the position can be attacked diagonally from the upper right corner to the lower left corner by the existing queen
      const colPlusRow = col + row;
      // The difference between the row index and the column index, if the value is already saved in Set
      // Indicates that the position can be attacked diagonally from the top left to the bottom right of the existing queen
      const colSubtractRow = col - row;

      // Check if the queen in the current position can be attacked, if so, skip the position
      // Since queens can attack each other, there will be no omissions even if the previous rows match a Set with fewer states
      if (
        // View current position can be attacked from column by other queens
        colSet.has(col) ||
        // Check if the current position can be attacked diagonally from upper right to lower left by other queens
        trToBlSet.has(colPlusRow) ||
        // Check to see if the current position can be attacked diagonally from top left to bottom right by other queens
        tlToBrSet.has(colSubtractRow)
      ) {
        // If the current position can be attacked, continue to match the next position
        continue;
      }

      // The current recursive logic
      // If the current position is unassailable and a queen can be placed in the current position, store the columns and diagonals that can be attacked by the current queen
      // The current queen can attack other queens in the current column to store the current column index
      colSet.add(col);
      // The sum of current row and column indexes, representing the diagonal from the upper right corner to the lower left corner
      trToBlSet.add(colPlusRow);
      // The difference between the current row and column index, representing the diagonal from the upper left to the lower right corner
      tlToBrSet.add(colSubtractRow);
      // Save the position of the queen row corresponding to the current column
      queenRow.push(col);

      // descends to the lower level recursion
      // Each dip continues to generate more states because of the for loop
      // The current row will not have two columns, because each row will be plumped down to the next row
      // In other words, there is only one queen in each row, so there are no attacks
      dfs(row + 1);

      // Clear the recursive state
      // By the time we get to this point, we have already done a complete recursion and can clear all intermediate states for the next recursion
      queenRow.pop();
      colSet.delete(col);
      trToBlSet.delete(colPlusRow);
      tlToBrSet.delete(colSubtractRow);
    }
  }
  dfs(0); // Recurse from the first line

  // Generate all checkerboard patterns
  function generate() {
    let patterns = []; // Save the checkerboard pattern

    // Generate the chessboard by traversing the current queen position
    for (let i = 0; i < queenPositions.length; i++) {
      patterns.push([]); // Store an empty checkerboard for placing patterns

      // Iterate over n lines to generate a row pattern
      for (let row = 0; row < n; row++) {
        let rowPattern = ' '; // Store the pattern of the current row

        // Iterate over the current column to generate a pattern
        for (let col = 0; col < n; col++) {
          if (col === queenPositions[i][row]) {
            // If the position traversed is equal to the position of the stored queen, save the Q pattern
            rowPattern += 'Q';
          } else {
            // Otherwise save. pattern
            rowPattern += '. '; }}// Stores the pattern of the current row into the checkerboardpatterns[i].push(rowPattern); }}// Returns all patterns generated
    return patterns;
  }

  // Generate all checkerboard patterns and return the result
  return generate();
};
Copy the code