题目描述:
The n-queens puzzle is the problem of placing n queens on an n×n
chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens’
placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space
respectively.
解决方法:
两个方法都是通过递归来解决问题,方法一是我自己编写的,方法二是参考leetcode代码的,方法二的思路与方法一类似,但是方法二对皇后状态的存储进行优化,加快了运行速度同时也减少了运行时间。
class Solution {public List<List<String>> solveNQueens(int n) {int[][] chessboard = new int[n][n];int[][] au = new int[n][n];for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)au[i][j] = n;return solve(chessboard, au, 0, n);}public List<List<String>> solve(int[][] chessboard, int[][] au, int row, int n){List<List<String>> res = new ArrayList<>();StringBuilder sb = new StringBuilder();for (int i = 0; i < n; i++){sb.append(\".\");}if (row == n-1){for (int i = 0; i < n; i++){if (chessboard[row][i] == 0){List<String> temp = new ArrayList<>();sb.replace(i,i+1,\"Q\");temp.add(sb.toString());res.add(temp);return res;}}}for (int i = 0; i < n; i++){if (chessboard[row][i] == 0){chessboard[row][i] = 1;au[row][i] = Math.min(row,au[row][i]);sb.replace(i,i+1,\"Q\");for (int j = row+1; j < n; j++){chessboard[j][i] = 1;au[j][i] = Math.min(row,au[j][i]);if ((j-row+i)<= n-1){chessboard[j][j-row+i] = 1;au[j][j-row+i] = Math.min(au[j][j - row + i], row);}if ((i-j+row) >= 0){chessboard[j][i-j+row] = 1;au[j][i-j+row] = Math.min(au[j][i - j + row], row);}}List<List<String>> l = solve(chessboard, au, row+1, n);for (List<String> strings : l) {strings.add(0, sb.toString());res.add(strings);}sb.replace(i,i+1,\".\");if (au[row][i] >= row){chessboard[row][i] = 0;au[row][i] = n;}for (int j = row+1; j < n; j++){if (au[j][i] >= row && au[j][i] >= row){chessboard[j][i] = 0;au[j][i] = n;}if ((j-row+i)<= n-1 && au[j][j-row+i]>=row){chessboard[j][j-row+i] = 0;au[j][j-row+i] = n;}if ((i-j+row) >= 0 && au[j][i-j+row]>=row){chessboard[j][i-j+row] = 0;au[j][i-j+row] = n;}}}}return res;}}
上叙方法的不足之处对每一行每一列皇后状态的存储,通过int来存储浪费操作的时间和空间,通过位来进行存储可以极大的节约时间
int availableBit = (~usedBits) & (usedBits + 1);
通过该方法可以获取到最后一个可以用的位,就是可以被赋值的位置,使用位操作还有一个好处就是不需要恢复之前的状态
usedBits |= availableBit;
该方法可以给特定的位进行赋值。
以下是参考leetcode的代码
class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> results = new ArrayList();char[] letters = new char[n];Arrays.fill(letters, \'.\');int[] positions = new int[n];find(0, 0, 0, 0, n, results, letters, positions);return results;}private void find(int index, int upBits, int leftBits, int rightBits, int size, List<List<String>> results, char[] letters, int[] positions) {int usedBits = upBits | leftBits | rightBits;for (int i = 0; i < size; ++i) {int availableBit = (~usedBits) & (usedBits + 1);if (availableBit == (1 << i)) {positions[index] = i;usedBits |= availableBit;if (index == size - 1) {List<String> result = new ArrayList();for (int position : positions) {letters[position] = \'Q\';result.add(new String(letters));letters[position] = \'.\';}results.add(result);} else {find(index + 1,upBits | availableBit,(leftBits | availableBit) << 1,(rightBits | availableBit) >> 1,size,results,letters,positions);}}}}}