【Hot100】LeetCode—51. N 皇后

---

• 原题链接：51. N 皇后

---

1- 思路

题目识别

• 识别1 ：给定一个整数 n ，求解如何放置棋子的问题。

回溯

回溯三部曲

• 1- 回溯参数和返回值
  • 传参 cheeseBoard、n、row 传递三个参数
  • row 用来控制，当前遍历到了第几行
• 2- 终止条件
  • if( row == n) 收集结果
• 3- 回溯过程
  • 因为回溯的参数传递了 row，其中 row 代表的是行
  • 因此在回溯的过程中需要遍历 n ，遍历列

---

2- 实现

⭐51. N 皇后——题解思路

class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] cheesBoard = new char[n][n];for(char[] c:cheesBoard){Arrays.fill(c,'.');}backTracing(0,n,cheesBoard);return res;}public void backTracing(int row,int n, char[][] chessBoard){// 1. 终止条件if(row == n){res.add(ArrayToList(chessBoard));return;}// 3. 回溯for(int i = 0 ; i < n ; i++){if(isValid(row,i,n,chessBoard)){chessBoard[row][i] = 'Q';backTracing(row+1,n,chessBoard);chessBoard[row][i] = '.';}}}private List<String> ArrayToList(char[][] board){List<String> path = new ArrayList<>();for(char[] c:board){path.add(String.copyValueOf(c));}return path;}private boolean isValid(int row,int col,int n ,char[][] chessBoard){// 列判断for(int i = 0 ; i < row ; i++){if(chessBoard[i][col] == 'Q'){return false;}}// 45度for(int i = row-1,j=col-1; i>=0 && j>=0 ;i--,j--){if(chessBoard[i][j] == 'Q'){return false;}}// 145 度for(int i = row-1,j=col+1; i >=0 && j<n ;i--,j++){if(chessBoard[i][j] == 'Q'){return false;}}return true;}
}

---

3- ACM 实现

public class solveQueens {static List<List<String>> res = new ArrayList<>();public static List<List<String>> solveN(int n ){char[][] cheesBoard = new char[n][n];backTracking(0,n,cheesBoard);return res;}public static void backTracking(int row,int n ,char[][] chessBoard){// 终止条件if(row == n){res.add(ArrayToList(chessBoard));return;}// 3. 回溯for(int i = 0 ; i < n;i++){if(isValid(row,i,n,chessBoard)){chessBoard[row][i] = 'Q';backTracking(row+1,n,chessBoard);chessBoard[row][i] = '.';}}}private static List<String> ArrayToList(char[][] chessBoard){List<String> path = new ArrayList<>();for(char[] c:chessBoard){path.add(String.copyValueOf(c));}return path;}private static boolean isValid(int row,int col,int n,char[][] chessBoard){// 列for(int i = 0 ; i < row;i++){if(chessBoard[i][col] == 'Q'){return false;}}// 45for(int i = row-1,j = col-1 ; i>=0 && j>=0 ;i--,j--){if(chessBoard[i][j] == 'Q'){return false;}}// 135for(int i = row-1,j=col+1 ; i >=0 && j<n ; i--,j++){if(chessBoard[i][j] == 'Q'){return false;}}return true;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入棋盘n");int n = sc.nextInt();System.out.println("结果是"+solveN(n).toString());}
}