n皇后問題是一個典型的回溯算法的題目，就是在n*n的面板上，放n個皇后，每個皇后會攻擊同一列和同一行還有兩個斜邊上的元素，問你放的方法，返回形式是一個List嵌套List，每個List里都是一種解決方案，每一個解決方案都是畫一個面板，解決方案里的每一個元素都是每一個橫行，如果沒有放皇后，則以.來形容，如果放了皇后，以Q填充，在思想上肯定還是有一定難度的，先貼上java代碼的實現，這里已經優化了很多，因為我們是一行一行來放的，所以在放入一行之后，這一行(執行方法isVaild時還沒有往該行放Q的操作，所以此行是不可能有Q的存在的)以及這一行下面的所有行都是.，不存在有沒有Q的存在，所以只需要判斷現在的棋盤面板上的上方、左上方、右上方是否有Q的存在(isVaild實現)即可，這樣看起來通俗易懂，當然這個思想是用了回溯算法，在每一個循環里面，先實施放Q的操作，在遞歸進去之后的一行代碼，再將其還原，這就是回溯，因為有可能我們放到某一行之后，全部continue掉了，也就是此時遍歷完當前行的所有列都沒有找到一個合適的位置放皇后，相當于此路不通，所以我們要還原之前的現場，換一列重新遞歸，甚至這一行的所有列遍歷完后，他的下一列還是無解，此時還要返回到更上面一行，這樣就更有回溯的感覺了:

class Solution {List<List<String>> res = new ArrayList<List<String>>();//創建一個List[List用來存放最終結果并返回public List<List<String>> solveNQueens(int n) {char[][] borad = new char[n][n];//設置一個n*n的正方形char型數組for(char[] rchar: borad){//遍歷二維數組的每一行Arrays.fill(rchar,'.');//填充每一行，棋盤初始化，開始都沒有放皇后Q，直接.初始化}sovleQuestion(borad,0);//真正執行解決方案 return res;}public void sovleQuestion(char[][] borad,int row){int n = borad.length;//判斷一下這個是幾個皇后的問題，也就是棋盤的寬度 if(row==n){//如果n-1也便利完了，那么此時就會row==n，說明找到了一組解，將這個解放到返回的集合中res.add(charToList(borad)); //進行了將每一行char變為String的操作，返回一個List<String>并添加到List<List<String>>中return;//返回 } for(int col = 0; col < n; col++){//進行每一列試探 if(!isValid(borad,row,col)){//判斷這個位置是否能放Qcontinue;//不能放就到當前行的下一列 } borad[row][col] = 'Q';//說明可以放，填入(做選擇) sovleQuestion(borad,row+1);//進行下一行的遞歸 borad[row][col] = '.';//撤銷選擇 }}public boolean isValid(char[][] board,int row, int col){for(int i = 0;i<row;i++){//判斷當前元素的所有前面行的同列元素是否存在Qif(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<board[row].length;i--,j++){if(board[i][j] == 'Q'){//判斷右上方是否有Qreturn false;}}return true;}public List<String> charToList(char[][] board){//數組變為List操作List<String> list = new ArrayList<String>();for(char[] rchar: board){ list.add(String.copyValueOf(rchar));}return list;} }

總結

以上是生活随笔為你收集整理的n皇后问题java版的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。