51. N 皇后

52. N皇后 II

  1. class Solution {
  2.     public List<List<String>> solveNQueens(int n) {
  3.         List<List<String>> result=new ArrayList<>();
  4.         char[][] board=new char[n][n];
  5.         for(int i=0;i<n;i++){
  6.             for(int j=0;j<n;j++){
  7.                 board[i][j]='.';
  8.             }
  9.         }
  10.         dfs(0,n,board,result);
  11.         return result;
  12.     }
  14.     private void dfs(int i,int n,char[][] board,List<List<String>> result){
  15.         if(i==n){
  16.             //generate answer
  17.             List<String> path=new ArrayList<>();
  18.             for(int x=0;x<n;x++){
  19.                 StringBuilder sb=new StringBuilder();
  20.                 for(int y=0;y<n;y++){
  21.                     sb.append(board[x][y]);
  22.                 }
  23.                 path.add(sb.toString());
  24.             }
  25.             result.add(new ArrayList<>(path));
  26.             return;
  27.         }
  28.         for(int j=0;j<n;j++){
  29.             if(inRightPlace(i, j, board)){
  30.                 board[i][j]='Q';
  31.                 dfs(i+1,n,board,result);
  32.                 board[i][j]='.';
  33.             }
  34.         }
  35.     }
  37.     private boolean inRightPlace(int i,int j,char[][] board){
  38.         //row
  39.         for(int y=0;y<board.length;y++){
  40.             if(board[i][y]=='Q') return false;
  41.         }
  42.         //col
  43.         for(int x=0;x<board.length;x++){
  44.             if(board[x][j]=='Q') return false;
  45.         }
  46.         //k=1
  47.         for(int x=0;x<board.length;x++){
  48.             int y=x-i+j;
  49.             if(y<board.length&&y>=0&&board[x][y]=='Q') return false;
  50.         }
  51.         //k=-1
  52.         for(int x=0;x<board.length;x++){
  53.             int y=i+j-x;
  54.             if(y<board.length&&y>=0&&board[x][y]=='Q') return false;
  55.         }
  56.         return true;
  57.     }
  58. }