題目鏈接

/**

? ? ? ? ? ? 將n個棋子放在n*n的棋盤上,不同列,不同行,不同斜線

? ? ? ? ? ? 大致執行流程:

? ? ? ? ? ? ? ? ? ? 首先選取第一行第一格放置第一個棋子,再從第二行第一個位置開始選取合法的位置(不同行不同列不同斜線)放置棋子,重復上述流程迭代行數,

? ? ? ? ? ? ? ? ? ? 直到放置n個棋子。

? ? ? ? ? ? ? ? ? ? 若放置途中出現無合法位置的情況,回溯將上一行棋子放置在其他合法位置,再重復上述流程繼續放置直到n個棋子。

? ? ? ? ? ? ? ? ? ? 成功放置n個棋子后得到第一種情況,開始回溯重復上述流程,直到回溯至第一行的每個格子都嘗試過,得到所有結果

? ? ? ? ? ? 額外方法:

? ? ? ? ? ? ? ? ? ? boolean isValid 檢查欲放置位置的合法性

? ? ? ? ? ? ? ? ? ? List<String> BoardToList 棋盤格式轉換

?*/

class Solution {//棋盤private char[][] board;//保存結果private List<List<String>> res = new ArrayList<>();//避免重復傳參private int n;public List<List<String>> solveNQueens(int n) {/**將n個棋子放在n*n的棋盤上,不同列,不同行,不同斜線大致執行流程:首先選取第一行第一格放置第一個棋子,再從第二行第一個位置開始選取合法的位置(不同行不同列不同斜線)放置棋子,重復上述流程迭代行數,直到放置n個棋子。若放置途中出現無合法位置的情況,回溯將上一行棋子放置在其他合法位置,再重復上述流程繼續放置直到n個棋子。成功放置n個棋子后得到第一種情況,開始回溯重復上述流程,直到回溯至第一行的每個格子都嘗試過,得到所有結果額外方法:boolean isValid 檢查欲放置位置的合法性List<String> BoardToList 棋盤格式轉換*/this.n = n;this.board = new char[n][n];//初始化棋盤for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {board[i][j] = '.';}}//開始放置backtrack(0);return res;}private void backtrack(int row) {//已放置n個棋子,保存結果if(row == n) {res.add(BoardToList());return;}for(int col = 0; col < n; col++) {//當前位置合法if(isValid(row,col)) {board[row][col] = 'Q';backtrack(row + 1);//回溯board[row][col] = '.';}}}//判斷合法性 判斷不同列不同斜線即可,同行已由index控制private boolean isValid(int row, int col) {//檢查列沖突 row可體現出已放置棋子數 i < row 避免不必要的檢查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;}// 將棋盤轉換為結果格式（List<String>）private List<String> BoardToList() {List<String> list = new ArrayList<>();for (int i = 0; i < n; i++) {list.add(new String(board[i])); //按行批量轉化}return list;}}