力扣00052.N 皇后 II

发表于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 7 分钟
N 皇后 II、回溯、困难

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：1

提示：

  • 1 <= n <= 9

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        vector<int> board(n, -1);
        placeQueen(board, 0, count);
        return count;
    }
private:
    bool isNotUnderAttack(const vector<int>& board, int row, int col) {
        for (int prevRow = 0; prevRow < row; ++prevRow) {
            if (board[prevRow] == col || 
                abs(board[prevRow] - col) == row - prevRow) {
                return false;
            }
        }
        return true;
    }
    void placeQueen(vector<int>& board, int row, int& count) {
        int n = board.size();
        if (row == n) {
            ++count;
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (isNotUnderAttack(board, row, col)) {
                board[row] = col;
                placeQueen(board, row + 1, count);
                board[row] = -1;
            }
        }
    }
};

结果

执行用时 : 2 ms, 击败 74.56% 使用 C++ 的用户

内存消耗 : 6.99 MB, 击败 47.09% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int totalNQueens(int n) {
        int[] board = new int[n];
        return placeQueens(board, 0);
    }
    private boolean isNotUnderAttack(int[] board, int row, int col) {
        for (int prevRow = 0; prevRow < row; ++prevRow) {
            if (board[prevRow] == col || Math.abs(board[prevRow] - col) == row - prevRow) {
                return false;
            }
        }
        return true;
    }
    private int placeQueens(int[] board, int row) {
        int n = board.length;
        int count = 0;
        if (row == n) {
            return 1;
        }
        for (int col = 0; col < n; ++col) {
            if (isNotUnderAttack(board, row, col)) {
                board[row] = col;
                count += placeQueens(board, row + 1);
            }
        }
        return count;
    }
}

结果

执行用时 : 1 ms, 击败 80.81% 使用 Java 的用户

内存消耗 : 39.18 MB, 击败 65.14% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        def is_not_under_attack(row, col):
            for prev_row in range(row):
                if board[prev_row] == col or \
                   board[prev_row] - prev_row == col - row or \
                   board[prev_row] + prev_row == col + row:
                    return False
            return True
        def place_queen(row):
            if row == n:
                self.count[0] += 1
                return
            for col in range(n):
                if is_not_under_attack(row, col):
                    board[row] = col
                    place_queen(row + 1)
        self.count = [0]
        board = [-1] * n
        place_queen(0)
        return self.count[0]

结果

执行用时 : 52 ms, 击败 52.31% 使用 Python 的用户

内存消耗 : 11.39 MB, 击败 90.77% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def totalNQueens(self, n: int) -> int:
        def is_not_under_attack(row, col):
            for prev_row in range(row):
                if board[prev_row] == col or \
                   board[prev_row] - prev_row == col - row or \
                   board[prev_row] + prev_row == col + row:
                    return False
            return True
        def place_queen(row):
            if row == n:
                self.count += 1
                return
            for col in range(n):
                if is_not_under_attack(row, col):
                    board[row] = col
                    place_queen(row + 1)
        self.count = 0
        board = [-1] * n
        place_queen(0)
        return self.count

结果

执行用时 : 62 ms, 击败 42.31% 使用 Python3 的用户

内存消耗 : 16.43 MB, 击败 51.02% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void printSolution(int* board, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i] == j) {
                printf("Q ");
            } else {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}
bool isNotUnderAttack(int* board, int row, int col) {
    for (int prevRow = 0; prevRow < row; ++prevRow) {
        if (board[prevRow] == col || abs(board[prevRow] - col) == row - prevRow) {
            return false;
        }
    }
    return true;
}
void placeQueen(int* board, int row, int n, int* count) {
    if (row == n) {
        (*count)++;
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (isNotUnderAttack(board, row, col)) {
            board[row] = col;
            placeQueen(board, row + 1, n, count);
        }
    }
}
int totalNQueens(int n) {
    int* board = (int*)malloc(n * sizeof(int));
    int count = 0;
    placeQueen(board, 0, n, &count);
    free(board);
    return count;
}

结果

执行用时 : 3 ms, 击败 72.43% 使用 C 的用户

内存消耗 : 5.50 MB, 击败 90.12% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int TotalNQueens(int n) {
        int[] board = new int[n];
        int count = 0;
        PlaceQueen(board, 0, ref count);
        return count;
    }
    private bool IsNotUnderAttack(int[] board, int row, int col) {
        for (int prevRow = 0; prevRow < row; ++prevRow) {
            if (board[prevRow] == col || Math.Abs(board[prevRow] - col) == row - prevRow) {
                return false;
            }
        }
        return true;
    }
    private void PlaceQueen(int[] board, int row, ref int count) {
        int n = board.Length;
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (IsNotUnderAttack(board, row, col)) {
                board[row] = col;
                PlaceQueen(board, row + 1, ref count);
            }
        }
    }
}

结果

执行用时 : 33 ms, 击败 16.00% 使用 C# 的用户

内存消耗 : 26.79 MB, 击败 36.00% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    let count = 0;
    const board = new Array(n).fill(-1);
    const isNotUnderAttack = (row, col) => {
        for (let prevRow = 0; prevRow < row; ++prevRow) {
            if (board[prevRow] === col || 
                Math.abs(board[prevRow] - col) === row - prevRow) {
                return false;
            }
        }
        return true;
    };
    const placeQueen = (row) => {
        if (row === n) {
            count++;
            return;
        }
        for (let col = 0; col < n; ++col) {
            if (isNotUnderAttack(row, col)) {
                board[row] = col;
                placeQueen(row + 1);
            }
        }
    };
    placeQueen(0);
    return count;
};

结果

执行用时 : 52 ms, 击败 97.94% 使用 JavaScript 的用户

内存消耗 : 49.46 MB, 击败 41.16% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function totalNQueens(n: number): number {
    let count = 0;
    const board: number[] = Array(n).fill(-1);
    const isNotUnderAttack = (row: number, col: number): boolean => {
        for (let prevRow = 0; prevRow < row; ++prevRow) {
            if (board[prevRow] === col || 
                Math.abs(board[prevRow] - col) === row - prevRow) {
                return false;
            }
        }
        return true;
    };
    const placeQueen = (row: number): void => {
        if (row === n) {
            count++;
            return;
        }
        for (let col = 0; col < n; ++col) {
            if (isNotUnderAttack(row, col)) {
                board[row] = col;
                placeQueen(row + 1);
            }
        }
    };
    placeQueen(0);
    return count;
}

结果

执行用时 : 69 ms, 击败 50.00% 使用 TypeScript 的用户

内存消耗 : 50.49 MB, 击败 51.79% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {

    /**
     * @param Integer $n
     * @return Integer
     */
    function totalNQueens($n) {
        $this->result = [];
        $this->solveQueens($n, 0, []);
        return count($this->result);
    }
    function solveQueens($n, $row, $current) {
        if ($row == $n) {
            $this->result[] = $current;
            return;
        }
        for ($col = 0; $col < $n; ++$col) {
            if ($this->isValid($current, $row, $col, $n)) {
                $current[] = $col;
                $this->solveQueens($n, $row + 1, $current);
                array_pop($current);
            }
        }
    }
    function isValid($current, $row, $col, $n) {
        foreach ($current as $prevRow => $prevCol) {
            if ($col == $prevCol || abs($row - $prevRow) == abs($col - $prevCol)) {
                return false;
            }
        }
        return true;
    }
}

结果

执行用时 : 14 ms, 击败 100.00% 使用 PHP 的用户

内存消耗 : 20.34 MB, 击败 0.00% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private var resultCount = 0
    func totalNQueens(_ n: Int) -> Int {
        var board = Array(repeating: -1, count: n)
        placeQueens(&board, 0)
        return resultCount
    }
    private func isNotUnderAttack(_ board: [Int], _ row: Int, _ col: Int) -> Bool {
        for prevRow in 0..<row {
            if board[prevRow] == col || abs(board[prevRow] - col) == row - prevRow {
                return false
            }
        }
        return true
    }
    private func placeQueens(_ board: inout [Int], _ row: Int) {
        let n = board.count
        if row == n {
            resultCount += 1
            return
        }
        for col in 0..<n {
            if isNotUnderAttack(board, row, col) {
                board[row] = col
                placeQueens(&board, row + 1)
            }
        }
    }
}

结果

执行用时 : 6 ms, 击败 71.43% 使用 Swift 的用户

内存消耗 : 15.15 MB, 击败 50.00% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private var resultCount = 0
    fun totalNQueens(n: Int): Int {
        val board = IntArray(n) { -1 }
        placeQueens(board, 0)
        return resultCount
    }
    private fun isNotUnderAttack(board: IntArray, row: Int, col: Int): Boolean {
        for (prevRow in 0 until row) {
            if (board[prevRow] == col || Math.abs(board[prevRow] - col) == row - prevRow) {
                return false
            }
        }
        return true
    }
    private fun placeQueens(board: IntArray, row: Int) {
        val n = board.size
        if (row == n) {
            resultCount++
            return
        }
        for (col in 0 until n) {
            if (isNotUnderAttack(board, row, col)) {
                board[row] = col
                placeQueens(board, row + 1)
            }
        }
    }
}

结果

执行用时 : 135 ms, 击败 85.71% 使用 Kotlin 的用户

内存消耗 : 32.34 MB, 击败 78.57% 使用 Kotlin 的用户

Dart

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Dart 的用户

内存消耗 : MB, 击败 % 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func totalNQueens(n int) int {
	count := 0
	board := make([]int, n)
	placeQueens(board, 0, &count)
	return count
}
func isNotUnderAttack(board []int, row, col int) bool {
	for prevRow := 0; prevRow < row; prevRow++ {
		if board[prevRow] == col || abs(board[prevRow]-col) == row-prevRow {
			return false
		}
	}
	return true
}
func placeQueens(board []int, row int, count *int) {
	n := len(board)
	if row == n {
		*count++
		return
	}
	for col := 0; col < n; col++ {
		if isNotUnderAttack(board, row, col) {
			newBoard := append([]int(nil), board...)
			newBoard[row] = col
			placeQueens(newBoard, row+1, count)
		}
	}
}
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

结果

执行用时 : 2 ms, 击败 35.62% 使用 Go 的用户

内存消耗 : 2.66 MB, 击败 5.48% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# @param {Integer} n
# @return {Integer}
def total_n_queens(n)
  count = [0]
  board = Array.new(n, -1)
  place_queens(board, 0, count)
  count[0]
end
def is_not_under_attack(board, row, col)
  (0...row).each do |prev_row|
    return false if board[prev_row] == col || (board[prev_row] - col).abs == row - prev_row
  end
  true
end
def place_queens(board, row, count)
  n = board.length
  if row == n
    count[0] += 1
    return
  end
  (0...n).each do |col|
    if is_not_under_attack(board, row, col)
      new_board = board.dup
      new_board[row] = col
      place_queens(new_board, row + 1, count)
    end
  end
end

结果

执行用时 : 110 ms, 击败 -% 使用 Ruby 的用户

内存消耗 : 206.57 MB, 击败 -% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
object Solution {
  def totalNQueens(n: Int): Int = {
    def placeQueens(board: Array[Int], row: Int, count: Int): Int = {
      if (row == n) count + 1
      else {
        (0 until n).foldLeft(count)((currentCount, col) =>
          if (isNotUnderAttack(board, row, col))
            placeQueens(board.updated(row, col), row + 1, currentCount)
          else
            currentCount
        )
      }
    }
    placeQueens(Array.fill(n)(-1), 0, 0)
  }
  private def isNotUnderAttack(board: Array[Int], row: Int, col: Int): Boolean =
    (0 until row).forall(prevRow =>
      board(prevRow) != col && math.abs(board(prevRow) - col) != row - prevRow
    )
}

结果

执行用时 : 449 ms, 击败 100.00% 使用 Scala 的用户

内存消耗 : 52.83 MB, 击败 100.00% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn total_n_queens(n: i32) -> i32 {
        let mut count = 0;
        let mut board = vec![-1; n as usize];
        Solution::place_queens(&mut board, 0, &mut count);
        count
    }
    fn is_not_under_attack(board: &Vec<i32>, row: usize, col: i32) -> bool {
        (0..row).all(|prev_row| {
            let prev_col = board[prev_row];
            prev_col != col && (prev_col - col).abs() as usize != (row - prev_row)
        })
    }
    fn place_queens(board: &mut Vec<i32>, row: usize, count: &mut i32) {
        let n = board.len();
        if row == n {
            *count += 1;
        } else {
            for col in 0..n as i32 {
                if Solution::is_not_under_attack(board, row, col) {
                    board[row] = col;
                    Solution::place_queens(board, row + 1, count);
                }
            }
        }
    }
}

结果

执行用时 : 1 ms, 击败 37.50% 使用 Rust 的用户

内存消耗 : 2.16 MB, 击败 37.50% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户