51N 皇后

题目描述

51. N 皇后 - 力扣（LeetCode）

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

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

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

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

示例 1：

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

示例 2：

输入：n = 1输出：[["Q"]]

代码思路

class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); // 创建棋盘，初始全为'.' char[][] board = new char[n][n]; for (char[] row : board) { Arrays.fill(row, '.'); } // 从第0行开始回溯 backtrack(result, board, 0, n); return result; } private void backtrack(List<List<String>> result, char[][] board, int row, int n) { // 终止条件：已经成功放置了n个皇后 if (row == n) { result.add(boardToList(board)); return; } // 尝试在当前行的每一列放置皇后 for (int col = 0; col < n; col++) { // 检查当前位置(row, col)是否可以放置皇后 if (isValid(board, row, col, n)) { // 做选择：放置皇后 board[row][col] = 'Q'; // 递归处理下一行 backtrack(result, board, row + 1, n); // 撤销选择：回溯 board[row][col] = '.'; } } } private boolean isValid(char[][] board, int row, int col, int n) { // 检查同一列是否有皇后（从第0行检查到当前行的上一行） for (int i = 0; i < row; i++) { if (board[i][col] == 'Q') { return false; // 同一列有皇后，冲突 } } // 检查左上方对角线是否有皇后 // 对角线上的坐标特点：行索引和列索引同时递减 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') { return false; // 左上方对角线有皇后，冲突 } } // 检查右上方对角线是否有皇后 // 对角线上的坐标特点：行索引递减，列索引递增 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') { return false; // 右上方对角线有皇后，冲突 } } // 不需要检查同一行，因为我们是逐行放置的 return true; // 所有检查都通过，可以放置 } private List<String> boardToList(char[][] board) { List<String> list = new ArrayList<>(); for (char[] row : board) { list.add(new String(row)); } return list; } }