LeetCode–N 皇后
博客說明
文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！
介紹
51. N 皇后
題目
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊，
給定一個整數 n，回傳所有不同的 n 皇后問題的解決方案，
每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位，
示例：
輸入：4
輸出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解釋: 4 皇后問題存在兩個不同的解法，
提示：
皇后彼此不能相互攻擊，也就是說：任何兩個皇后都不能處于同一條橫行、縱行或斜線上，
思路
使用回溯法
使用一個陣列記錄每行放置的皇后的列下標，依次在每一行放置一個皇后，每次新放置的皇后都不能和已經放置的皇后之間有攻擊：即新放置的皇后不能和任何一個已經放置的皇后在同一列以及同一條斜線上，并更新陣列中的當前行的皇后列下標，當 NN 個皇后都放置完畢，則找到一個可能的解，當找到一個可能的解之后，將陣列轉換成表示棋盤狀態的串列，并將該棋盤狀態的串列加入回傳串列
代碼
class Solution {
public List<List<String>> solveNQueens(int n) {
int[] queens = new int[n];
Arrays.fill(queens, -1);
List<List<String>> solutions = new ArrayList<List<String>>();
solve(solutions, queens, n, 0, 0, 0, 0);
return solutions;
}
public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
List<String> board = generateBoard(queens, n);
solutions.add(board);
} else {
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
int column = Integer.bitCount(position - 1);
queens[row] = column;
solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
queens[row] = -1;
}
}
}
public List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
感謝
Leetcode
以及勤勞的自己，個人博客，GitHub
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/13880.html
標籤：Java
下一篇：Java基礎之集合