This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

95. N Queens

The label

  • DFS + back
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

The classic N Queen problem is the study of how to place n queens on an n× N chessboard so that queens cannot attack each other. (The queen in chess can move horizontally, vertically and diagonally, so she is the most powerful chess player.)

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

As you can see, these queens can’t attack each other, which means the attack returns don’t overlap.

The basic idea

Those unfamiliar with basic DFS + backtracking move to DFS + backtracking

The solution is a reference to this text and I think his diagram is very clear.

Difference of the problem: the diagonal and we use the chart can clearly see that I + j = = = row + col | | I – j = = = row – col and on the diagonal.

a00 a01 a02 a03            0 -1 -2 -3           0  1  2  3
a10 a11 a12 a13    i-j     1  0 -1 -2    i+j    1  2  3  4
a20 a21 a22 a23            2  1  0 -1           2  3  4  5
a30 a31 a32 a33            3  2  1  0           3  4  5  6
Copy the code

Writing implement

const solveNQueens = (n) = > {
  let res = []
  // board initialization, each position is temporarily empty is '.'
  const board = new Array(n).fill(0).map(item= > new Array(n).fill('. '))
  // Determine whether the position function is valid to ensure that there is no conflict between queens
  const isValidPosition = (row, col) = > {
    // Scan each line before
    for (let i = 0; i < row; i++) {
      // Iterate over all columns
      for (let j = 0; j < n; j++) {
        // If the position has Q and is in the same column or on a diagonal, it is illegal
        // There is no judgment here because we are in a row, so we will not be in a row
        if (board[i][j] === 'Q'
          && (j === col || i + j === row + col || i - j === row - col)) {
          return false; }}}return true;
  }
  // Back to DFS + backtracking
  const dfs = (row) = > {
    // Place the current row
    if (row === n) {
      // The recursive exit has exceeded the last line, save the current disk
      let boardBackup = board.slice()
      let tempRes = boardBackup.map(item= > item.join(' '))
      res.push(tempRes);
      return
    }
    // Start traversing the position of each column in the row
    for (let col = 0; col < n; col++) {
      // If it is a valid position, drop Q
      if (isValidPosition(row, col)) {         
        board[row][col] = "Q";  
        // Recursive DFS next line
        dfs(row + 1);
        // Backtrace, undo selection
        board[row][col] = '. '; }}}// Start at line 0
  dfs(0)
  return res
}

console.log(solveNQueens(4))
Copy the code

To optimize the implementation

It is better to have three arrays or sets of columns, diagonal lines, and antidiagonal lines that have queens, trading space for time.

const solveNQueens = (n) = > {
  let res = []
  // board initialization, each position is temporarily empty is '.'
  const board = new Array(n).fill(0).map(item= > new Array(n).fill('. '))
  // Determine whether the position function is valid to ensure that there is no conflict between queens
  
  // Record the occupied column, the diagonal set
  const occupiedCols = new Set(a)/ / column
  const occupiedDiags = new Set(a)/ / diagonal
  const occupiedReverseDiags = new Set(a)// Counter diagonal

  // Back to DFS + backtracking
  const dfs = (row) = > {
    // Place the current row
    if (row === n) {
      // The recursive exit has exceeded the last line, save the current disk
      let boardBackup = board.slice()
      let tempRes = boardBackup.map(item= > item.join(' '))
      res.push(tempRes);
      return
    }
    // Start traversing the position of each column in the row
    for (let col = 0; col < n; col++) {
      // If the current point is in a column and the diagonal has no queen, select it; otherwise, skip this row
      if(! occupiedCols.has(col) && ! occupiedDiags.has(row - col) && ! occupiedReverseDiags.has(row + col)) {// can place Q
        board[row][col] = 'Q';
        occupiedCols.add(col)
        occupiedDiags.add(row - col)
        occupiedReverseDiags.add(row + col)
        // Proceed to the next line
        dfs(row + 1)
        / / back
        board[row][col] = '. ';
        occupiedCols.delete(col)
        occupiedDiags.delete(row - col)
        occupiedReverseDiags.delete(row + col)
      }
    }
  }
  // Start at line 0
  dfs(0)
  return res
}

console.log(solveNQueens(4))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference

  • Leetcode-cn.com/problems/n-…