【Hot100】LeetCode—51. N 皇后

• 原题链接：51. N 皇后

---

1- 思路

使用回溯的方式实现，回溯三部曲

• 数据结构：定义三维数组，收集结果
• 1- 回溯终止条件：如果遍历到 row == n-1 此时就是结果收集的时刻
• 2- 执行 for 循环遍历，执行递归和回溯

---

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(n,0,cheesBoard);return res;}private void backTracing(int n,int row,char[][] cheesBoard){// 1.终止条件收集结果if(row==n){res.add(Array2List(cheesBoard));return ;}// 2. 遍历for(int i = 0; i < n ; i++){if(isValid(row,i,n,cheesBoard)){cheesBoard[row][i] = 'Q';backTracing(n,row+1,cheesBoard);cheesBoard[row][i] = '.';}}}private List<String> Array2List(char[][] cheesBoard){List<String> list = new ArrayList<>();for(char[] c:cheesBoard){list.add(String.copyValueOf(c));}return list;}private boolean isValid(int row,int col,int n,char[][] cheesBoard){// 列for (int i = 0; i < row; i++) {if (cheesBoard[i][col] == 'Q') {return false;}}/// 45for(int i = row-1,j = col-1;i>=0 && j>=0;i--,j--){if(cheesBoard[i][j] == 'Q'){return false;}}// 135for(int i = row-1,j = col+1;i>=0 && j<n;i--, j++){if(cheesBoard[i][j] == 'Q'){return false;}}return true;}
}

---

3- ACM 实现

package Daily_LC.Month8_Week2.Day124;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** NQueens** @author alcohol* @Description* @since 2024-08-09 10:28*/
public class NQueens {static List<List<String>> res = new ArrayList<>();public static List<List<String>> nQueens(int n){char[][] cheesBoard = new char[n][n];for(char[] c:cheesBoard){Arrays.fill(c,'.');}backTracing(n,0,cheesBoard);return res;}public static void backTracing(int n,int row,char[][] cheesBoard){// 1. 终止条件if(row==n){res.add(Array2List(cheesBoard));return;}// 2. 遍历for(int i = 0 ; i < n;i++){if(isValid(row,i,n,cheesBoard)){cheesBoard[row][i] = 'Q';backTracing(n,row+1,cheesBoard);cheesBoard[row][i] = '.';}}}private static List<String> Array2List(char[][] cheesBoard){List<String> list = new ArrayList<>();for(char[] c: cheesBoard){list.add(String.copyValueOf(c));}return list;}private static boolean isValid(int row, int col,int n, char[][] cheesBoard){// 列for(int i = 0 ; i < row;i++){if(cheesBoard[i][col] == 'Q'){return false;}}// 45度for(int i = row-1,j=col-1 ; i>=0 && j>=0 ;i--,j--){if(cheesBoard[i][j] =='Q'){return false;}}// 135 度for(int i = row-1,j=col+1; i>=0 && j<n;i--,j++){if(cheesBoard[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();nQueens(n);System.out.println("结果是");System.out.println(res.toString());}
}