力扣00051.N 皇后

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

题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[[“Q”]]

提示：

  • 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
34
35
36
37
38
39
40
41
42

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> current_board(n, string(n, '.'));

        solveNQueensRecursive(result, current_board, 0, n);
        
        return result;
    }
private:
    void solveNQueensRecursive(vector<vector<string>>& result, 
                               vector<string>& current_board, 
                               int row, int n) {
        if (row == n) {
            result.push_back(current_board);
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (isNotUnderAttack(current_board, row, col, n)) {
                current_board[row][col] = 'Q';
                solveNQueensRecursive(result, current_board, row + 1, n);
                current_board[row][col] = '.';
            }
        }
    }
    bool isNotUnderAttack(const vector<string>& current_board, int row, int col, int n) {
        for (int i = 0; i < row; ++i) {
            if (current_board[i][col] == 'Q') {
                return false;
            }
            if (col - (row - i) >= 0 && current_board[i][col - (row - i)] == 'Q') {
                return false;
            }
            if (col + (row - i) < n && current_board[i][col + (row - i)] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

结果

执行用时 : 7 ms, 击败 55.24% 使用 C++ 的用户

内存消耗 : 9.03 MB, 击败 49.91% 使用 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
    public 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++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        solveNQueensRecursive(result, board, 0, n);
        return result;
    }
    private void solveNQueensRecursive(List<List<String>> result, char[][] board, int row, int n) {
        if (row == n) {
            result.add(generateBoard(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isNotUnderAttack(board, row, col, n)) {
                board[row][col] = 'Q';
                solveNQueensRecursive(result, board, row + 1, n);
                board[row][col] = '.';
            }
        }
    }
    private boolean isNotUnderAttack(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
            if (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') {
                return false;
            }
            if (col + (row - i) < n && board[i][col + (row - i)] == 'Q') {
                return false;
            }
        }
        return true;
    }
    private List<String> generateBoard(char[][] board) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            result.add(new String(board[i]));
        }
        return result;
    }
}

结果

执行用时 : 2 ms, 击败 89.58% 使用 Java 的用户

内存消耗 : 43.92 MB, 击败 16.22% 使用 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
27
28
29
30
31
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def is_not_under_attack(row, col, queens):
            for prev_row, prev_col in queens:
                if prev_col == col or \
                   prev_row - prev_col == row - col or \
                   prev_row + prev_col == row + col:
                    return False
            return True
        def place_queen(row, queens, result):
            if row == n:
                result.append(queens[:])
                return
            for col in range(n):
                if is_not_under_attack(row, col, queens):
                    queens.append((row, col))
                    place_queen(row + 1, queens, result)
                    queens.pop()
        result = []
        place_queen(0, [], result)
        def format_solution(queens):
            solution = []
            for row, col in queens:
                row_str = '.' * col + 'Q' + '.' * (n - col - 1)
                solution.append(row_str)
            return solution
        return [format_solution(queens) for queens in result]

结果

执行用时 : 53 ms, 击败 65.08% 使用 Python 的用户

内存消耗 : 11.82 MB, 击败 78.96% 使用 Python 的用户

Python3

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
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def is_not_under_attack(row, col, queens):
            for prev_row, prev_col in queens:
                if prev_col == col or \
                   prev_row - prev_col == row - col or \
                   prev_row + prev_col == row + col:
                    return False
            return True
        def place_queen(row, queens, result):
            if row == n:
                result.append(queens[:])
                return
            for col in range(n):
                if is_not_under_attack(row, col, queens):
                    queens.append((row, col))
                    place_queen(row + 1, queens, result)
                    queens.pop()
        result = []
        place_queen(0, [], result)
        def format_solution(queens):
            solution = []
            for row, col in queens:
                row_str = '.' * col + 'Q' + '.' * (n - col - 1)
                solution.append(row_str)
            return solution
        return [format_solution(queens) for queens in result]

结果

执行用时 : 53 ms, 击败 73.96% 使用 Python3 的用户

内存消耗 : 16.84 MB, 击败 46.26% 使用 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
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    char*** result = (char***)malloc(sizeof(char**) * 1000);
    *returnColumnSizes = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    char** board = (char**)malloc(sizeof(char*) * n);
    for (int i = 0; i < n; ++i) {
        board[i] = (char*)malloc(sizeof(char) * (n + 1));
        for (int j = 0; j < n; ++j) {
            board[i][j] = '.';
        }
        board[i][n] = '\0';
    }
    solveNQueensRecursive(result, board, 0, n, returnSize, returnColumnSizes);
    return result;
}
void solveNQueensRecursive(char*** result, char** board, int row, int n, int* returnSize, int** returnColumnSizes) {
    if (row == n) {
        result[*returnSize] = (char**)malloc(sizeof(char*) * n);
        for (int i = 0; i < n; ++i) {
            result[*returnSize][i] = (char*)malloc(sizeof(char) * (n + 1));
            strcpy(result[*returnSize][i], board[i]);
        }
        (*returnColumnSizes)[*returnSize] = n;
        (*returnSize)++;
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (isNotUnderAttack(board, row, col, n)) {
            board[row][col] = 'Q';
            solveNQueensRecursive(result, board, row + 1, n, returnSize, returnColumnSizes);
            board[row][col] = '.';
        }
    }
}
int isNotUnderAttack(char** board, int row, int col, int n) {
    for (int i = 0; i < row; ++i) {
        if (board[i][col] == 'Q') {
            return 0;
        }
        if (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') {
            return 0;
        }
        if (col + (row - i) < n && board[i][col + (row - i)] == 'Q') {
            return 0;
        }
    }
    return 1;
}

结果

执行用时 : 9 ms, 击败 21.48% 使用 C 的用户

内存消耗 : 6.90 MB, 击败 89.77% 使用 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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        IList<IList<string>> result = new List<IList<string>>();
        char[,] board = new char[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i, j] = '.';
            }
        }
        SolveNQueensRecursive(result, board, 0, n);
        return result;
    }
    private void SolveNQueensRecursive(IList<IList<string>> result, char[,] board, int row, int n) {
        if (row == n) {
            result.Add(GenerateBoard(board));
            return;
        }
        for (int col = 0; col < n; col++) {
            if (IsNotUnderAttack(board, row, col, n)) {
                board[row, col] = 'Q';
                SolveNQueensRecursive(result, board, row + 1, n);
                board[row, col] = '.';
            }
        }
    }
    private bool IsNotUnderAttack(char[,] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            if (board[i, col] == 'Q') {
                return false;
            }
            if (col - (row - i) >= 0 && board[i, col - (row - i)] == 'Q') {
                return false;
            }
            if (col + (row - i) < n && board[i, col + (row - i)] == 'Q') {
                return false;
            }
        }
        return true;
    }
    private IList<string> GenerateBoard(char[,] board) {
        IList<string> solution = new List<string>();
        for (int i = 0; i < board.GetLength(0); i++) {
            StringBuilder rowStr = new StringBuilder();
            for (int j = 0; j < board.GetLength(1); j++) {
                rowStr.Append(board[i, j]);
            }
            solution.Add(rowStr.ToString());
        }
        return solution;
    }
}

结果

执行用时 : 115 ms, 击败 54.84% 使用 C# 的用户

内存消耗 : 52.49 MB, 击败 25.80% 使用 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
32
33
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
    let result = [];
    let board = Array.from({ length: n }, () => Array(n).fill('.'));
    const solveNQueensRecursive = (row) => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isNotUnderAttack(row, col)) {
                board[row][col] = 'Q';
                solveNQueensRecursive(row + 1);
                board[row][col] = '.';
            }
        }
    };
    const isNotUnderAttack = (row, col) => {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q' ||
                (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') ||
                (col + (row - i) < n && board[i][col + (row - i)] === 'Q')) {
                return false;
            }
        }
        return true;
    };
    solveNQueensRecursive(0);
    return result;
};

结果

执行用时 : 68 ms, 击败 89.66% 使用 JavaScript 的用户

内存消耗 : 53.46 MB, 击败 13.59% 使用 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
28
29
function solveNQueens(n: number): string[][] {
    const result: string[][] = [];
    const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));
    const solveNQueensRecursive = (row: number): void => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (isNotUnderAttack(row, col)) {
                board[row][col] = 'Q';
                solveNQueensRecursive(row + 1);
                board[row][col] = '.';
            }
        }
    };
    const isNotUnderAttack = (row: number, col: number): boolean => {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q' ||
                (col - (row - i) >= 0 && board[i][col - (row - i)] === 'Q') ||
                (col + (row - i) < n && board[i][col + (row - i)] === 'Q')) {
                return false;
            }
        }
        return true;
    };
    solveNQueensRecursive(0);
    return result;
}

结果

执行用时 : 82 ms, 击败 46.56% 使用 TypeScript 的用户

内存消耗 : 53.47 MB, 击败 35.87% 使用 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
34
35
36
class Solution {

    /**
     * @param Integer $n
     * @return String[][]
     */
    function solveNQueens($n) {
        $result = [];
        $board = array_fill(0, $n, array_fill(0, $n, '.'));
        $solveNQueensRecursive = function ($row) use (&$result, &$board, $n, &$solveNQueensRecursive) {
            if ($row == $n) {
                $result[] = array_map('implode', $board);
                return;
            }
            for ($col = 0; $col < $n; $col++) {
                if ($this->isNotUnderAttack($row, $col, $board, $n)) {
                    $board[$row][$col] = 'Q';
                    $solveNQueensRecursive($row + 1);
                    $board[$row][$col] = '.';
                }
            }
        };
        $solveNQueensRecursive(0);
        return $result;
    }
    private function isNotUnderAttack($row, $col, $board, $n) {
        for ($i = 0; $i < $row; $i++) {
            if ($board[$i][$col] === 'Q' ||
                ($col - ($row - $i) >= 0 && $board[$i][$col - ($row - $i)] === 'Q') ||
                ($col + ($row - $i) < $n && $board[$i][$col + ($row - $i)] === 'Q')) {
                return false;
            }
        }
        return true;
    }
}

结果

执行用时 : 32 ms, 击败 40.00% 使用 PHP 的用户

内存消耗 : 20.85 MB, 击败 -% 使用 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
30
31
class Solution {
    func solveNQueens(_ n: Int) -> [[String]] {
        var result = [[String]]()
        var board = Array(repeating: Array(repeating: ".", count: n), count: n)
        func solveNQueensRecursive(_ row: Int) {
            if row == n {
                result.append(board.map { $0.joined() })
                return
            }
            for col in 0..<n {
                if isNotUnderAttack(row, col) {
                    board[row][col] = "Q"
                    solveNQueensRecursive(row + 1)
                    board[row][col] = "."
                }
            }
        }
        func isNotUnderAttack(_ row: Int, _ col: Int) -> Bool {
            for i in 0..<row {
                if board[i][col] == "Q" ||
                   (col - (row - i) >= 0 && board[i][col - (row - i)] == "Q") ||
                   (col + (row - i) < n && board[i][col + (row - i)] == "Q") {
                    return false
                }
            }
            return true
        }
        solveNQueensRecursive(0)
        return result
    }
}

结果

执行用时 : 7 ms, 击败 100.00% 使用 Swift 的用户

内存消耗 : 16.07 MB, 击败 6.98% 使用 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
30
31
class Solution {
    fun solveNQueens(n: Int): List<List<String>> {
        val result = mutableListOf<List<String>>()
        val board = Array(n) { CharArray(n) { '.' } }
        fun isNotUnderAttack(row: Int, col: Int): Boolean {
            for (i in 0 until row) {
                if (board[i][col] == 'Q' ||
                    (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') ||
                    (col + (row - i) < n && board[i][col + (row - i)] == 'Q')) {
                    return false
                }
            }
            return true
        }
        fun solveNQueensRecursive(row: Int) {
            if (row == n) {
                result.add(board.map { it.joinToString("") })
                return
            }
            for (col in 0 until n) {
                if (isNotUnderAttack(row, col)) {
                    board[row][col] = 'Q'
                    solveNQueensRecursive(row + 1)
                    board[row][col] = '.'
                }
            }
        }
        solveNQueensRecursive(0)
        return result
    }
}

结果

执行用时 : 211 ms, 击败 46.15% 使用 Kotlin 的用户

内存消耗 : 39.71 MB, 击败 30.77% 使用 Kotlin 的用户

Dart

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
class Solution {
  List<List<String>> solveNQueens(int n) {
    List<List<String>> result = [];
    List<List<String>> board = List.generate(
      n,
      (row) => List.generate(n, (col) => '.'),
    );
    bool isNotUnderAttack(int row, int col) {
      for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q' ||
            (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') ||
            (col + (row - i) < n && board[i][col + (row - i)] == 'Q')) {
          return false;
        }
      }
      return true;
    }
    void solveNQueensRecursive(int row) {
      if (row == n) {
        result.add(List.generate(n, (i) => board[i].join()));
        return;
      }
      for (int col = 0; col < n; col++) {
        if (isNotUnderAttack(row, col)) {
          board[row][col] = 'Q';
          solveNQueensRecursive(row + 1);
          board[row][col] = '.';
        }
      }
    }
    solveNQueensRecursive(0);
    return result;
  }
}

结果

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

内存消耗 : 143.24 MB, 击败 100.00% 使用 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
func solveNQueens(n int) [][]string {
	var result [][]string
	board := make([][]rune, n)
	for i := 0; i < n; i++ {
		board[i] = make([]rune, n)
		for j := 0; j < n; j++ {
			board[i][j] = '.'
		}
	}
	var solveNQueensRecursive func(row int)
	solveNQueensRecursive = func(row int) {
		if row == n {
			copyBoard := make([][]rune, n)
			for i := 0; i < n; i++ {
				copyBoard[i] = make([]rune, n)
				copy(copyBoard[i], board[i])
			}
			result = append(result, generateBoard(copyBoard))
			return
		}
		for col := 0; col < n; col++ {
			if isNotUnderAttack(row, col, board, n) {
				board[row][col] = 'Q'
				solveNQueensRecursive(row + 1)
				board[row][col] = '.'
			}
		}
	}
	solveNQueensRecursive(0)
	return result
}
func isNotUnderAttack(row, col int, board [][]rune, n int) bool {
	for i := 0; i < row; i++ {
		if board[i][col] == 'Q' ||
			(col-(row-i) >= 0 && board[i][col-(row-i)] == 'Q') ||
			(col+(row-i) < n && board[i][col+(row-i)] == 'Q') {
			return false
		}
	}
	return true
}
func generateBoard(board [][]rune) []string {
	var solution []string
	for i := 0; i < len(board); i++ {
		solution = append(solution, string(board[i]))
	}
	return solution
}

结果

执行用时 : 4 ms, 击败 74.53% 使用 Go 的用户

内存消耗 : 3.46 MB, 击败 13.50% 使用 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
def solve_n_queens(n)
  result = []
  board = Array.new(n) { Array.new(n, '.') }
  solve_n_queens_recursive = lambda do |row|
    if row == n
      result << board.map { |row| row.join('') }
      return
    end
    is_not_under_attack = lambda do |row, col, board, n|
      (0...row).each do |i|
        return false if board[i][col] == 'Q' ||
                        (col - (row - i) >= 0 && board[i][col - (row - i)] == 'Q') ||
                        (col + (row - i) < n && board[i][col + (row - i)] == 'Q')
      end
      true
    end
    (0...n).each do |col|
      if is_not_under_attack.call(row, col, board, n)
        board[row][col] = 'Q'
        solve_n_queens_recursive.call(row + 1)
        board[row][col] = '.'
      end
    end
  end
  solve_n_queens_recursive.call(0)
  result
end

结果

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

内存消耗 : 207.64 MB, 击败 50.00% 使用 Ruby 的用户

Scala

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
object Solution {
  def solveNQueens(n: Int): List[List[String]] = {
    var result = List[List[String]]()
    var board = Array.fill(n, n)('.')
    def solveNQueensRecursive(row: Int): Unit = {
      if (row == n) {
        result = result :+ board.map(_.mkString("")).toList
        return
      }
      def isNotUnderAttack(row: Int, col: Int): Boolean = {
        for (i <- 0 until row) {
          if (board(i)(col) == 'Q' ||
              (col - (row - i) >= 0 && board(i)(col - (row - i)) == 'Q') ||
              (col + (row - i) < n && board(i)(col + (row - i)) == 'Q')) {
            return false
          }
        }
        true
      }
      for (col <- 0 until n) {
        if (isNotUnderAttack(row, col)) {
          board(row)(col) = 'Q'
          solveNQueensRecursive(row + 1)
          board(row)(col) = '.'
        }
      }
    }
    solveNQueensRecursive(0)
    result
  }
}

结果

执行用时 : 557 ms, 击败 88.89% 使用 Scala 的用户

内存消耗 : 62.87 MB, 击败 11.11% 使用 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
28
29
30
31
32
33
34
impl Solution {
    pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
        let mut result = Vec::new();
        let mut board = vec![vec!['.'; n as usize]; n as usize];
        fn solve_n_queens_recursive(row: usize, n: usize, board: &mut Vec<Vec<char>>, result: &mut Vec<Vec<String>>) {
            if row == n {
                result.push(board.iter().map(|row| row.iter().collect()).collect());
                return;
            }
            fn is_not_under_attack(row: usize, col: usize, board: &Vec<Vec<char>>, n: usize) -> bool {
                for i in 0..row {
                    if board[i][col] == 'Q'
                        || (col as isize - (row as isize - i as isize)) >= 0
                            && board[i][col - (row - i)] == 'Q'
                        || (col + (row - i)) < n
                            && board[i][col + (row - i)] == 'Q'
                    {
                        return false;
                    }
                }
                true
            }
            for col in 0..n {
                if is_not_under_attack(row, col, &board, n) {
                    board[row][col] = 'Q';
                    solve_n_queens_recursive(row + 1, n, board, result);
                    board[row][col] = '.';
                }
            }
        }
        solve_n_queens_recursive(0, n as usize, &mut board, &mut result);
        result
    }
}

结果

执行用时 : 3 ms, 击败 47.62% 使用 Rust 的用户

内存消耗 : 2.19 MB, 击败 92.86% 使用 Rust 的用户

Racket

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
(define/contract (solve-n-queens n)
  (-> exact-integer? (listof (listof string?)))
  (define (is-safe? row col queens)
    (define (under-attack? r1 c1 r2 c2)
      (or (= r1 r2)
          (= c1 c2)
          (= (abs (- r1 r2)) (abs (- c1 c2)))))
    (define (safe-in-current-row? r c)
      (not (ormap (lambda (queen) (under-attack? r c (car queen) (cdr queen))) queens)))
    (safe-in-current-row? row col))
  (define (generate-result queens)
    (map (lambda (queen)
           (list->string
            (for/list ([i (in-range n)])
              (if (= i (cdr queen)) #\Q #\.))))
         queens))
  (define (solve-n-queens-recursive row queens)
    (cond
      ((= row n) (list (generate-result queens)))
      (else
       (append-map (lambda (col)
                     (if (is-safe? row col queens)
                         (solve-n-queens-recursive (add1 row) (cons (cons row col) queens))
                         '()))
                   (range n)))))
  (solve-n-queens-recursive 0 '()))

结果

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

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

Erlang

暂时未解决

1

结果

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

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

Elixir

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
defmodule Solution do
  @spec solve_n_queens(n :: integer) :: [[String.t]]
  def solve_n_queens(n) do
    solve_n_queens_recursive(n, 0, [])
  end
  defp solve_n_queens_recursive(_n, n, queens) when n == _n do
    [generate_result(queens)]
  end
  defp solve_n_queens_recursive(n, row, queens) do
    Enum.flat_map(0..(n-1), fn col ->
      if is_safe?(row, col, queens) do
        solve_n_queens_recursive(n, row + 1, [{row, col} | queens])
      else
        []
      end
    end)
  end
  defp generate_result(queens) do
    Enum.map(queens, fn {r, c} ->
      String.duplicate(".", c) <> "Q" <> String.duplicate(".", length(queens) - c - 1)
    end)
  end
  defp is_safe?(row, col, queens) do
    Enum.all?(queens, fn {r, c} ->
      row != r and col != c and abs(row - r) != abs(col - c)
    end)
  end
end

结果

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

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