[LeetCode] 51. N-Queens Java
题目:
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.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]
题意及分析:求出n皇后算法所有可能的解。这道题使用回溯的方法求解,因为n皇后算法要求没有任何点在同一行、同一列和同一条斜线上,所以这里算法进行下一步运算的边界条件为:求当点前的上方、下方、左方、右方、左上角、右上角、左下角、右下角这8个方向上是否有等于‘Q’的点,如果没有就进行下一步,反之回溯。 这里显然每一行或者每一列只可能有一个皇后点‘Q’,所以我们可以只对当前行和前面的行进行边界条件判断,即只需要判断当前点的上方、左方、左上角和右上角4个方向。
代码:
class Solution { public List<List<String>> solveNQueens(int n) { //所有皇后不在同一条线上 List<List<String>> res = new ArrayList<>(); char[][] matrix = new char[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++) matrix[i][j] = '.'; } backtracking(res,matrix,0,n); return res; } private void backtracking(List<List<String>> res,char[][] matrix,int i,int n){ if(i==n-1){ for(int j=0;j<n;j++){ if(isValid(matrix,i,j,n)){ //合法的皇后 matrix[i][j] = 'Q'; List<String> list = new ArrayList<>(); for(int m=0;m<n;m++){ String s = new String(matrix[m]); list.add(s); } res.add(list); matrix[i][j] = '.'; } } return; } for(int j=0;j<n;j++){ if(isValid(matrix,i,j,n)){ matrix[i][j] = 'Q'; backtracking(res,matrix,i+1,n); matrix[i][j] = '.'; } } } private boolean isValid(char[][] matrix,int i,int j,int n){ boolean res = true; //只对i上面的行检查,判断是否在一列或者在一条斜线上 int up = i-1; while(up>=0){ if(matrix[up][j]=='Q') return false; up--; } //左上 int left = j-1,upleft = i-1; while(left>=0 && upleft>=0){ if(matrix[upleft--][left--]=='Q') return false; } //右上 int right = j+1,upRight = i-1; while(right<n && upRight>=0){ if(matrix[upRight--][right++]=='Q') return false; } return res; } }