【力扣每日一题】——N皇后

一、题目描述

原题链接
设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展
示例:

输入：4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

二、题目描述

经典回溯问题,整体使用回溯框架。
剪枝的思路:
判断row行col列 是否能放皇后

1. 每行只能放一个皇后，因此从第一行开始一行一行进行尝试
2. 每列只能放一个皇后,使用ans[i]表示 第i行 的皇后放在 第ans[i] 列,只需要判断row行之前的所有行ans[i]的值是否与col列相等如果相等,说明本列之前有皇后
3. 判断对角线上是否有皇后,根据数学直线斜率等于±1,遍历row之前每行 如果 (i,ans[i]) (row,col) 符合 row - i == |col - ans[i]| 说明对角线上存在皇后

三、代码实现

class Solution {
    //ans[i]表示第i行的皇后在 第ans[i]列
    int[] ans;
    int len = 0 ;
     List<List<String>> res = new ArrayList<>();
     List<String> list = new ArrayList<>();
  
      List<List<String>> solveNQueens(int n) {
            len = n;
               ans = new int[n];
            backTracking(0);
           return res;
       }
   

    void backTracking(int row) {
         if(row == len){
             for(int i = 0;i < len;i++){
                 char[] chars = new char[len];
           
              Arrays.fill(chars,'.');
            chars[ans[i]] = 'Q';                
     list.add(new String(chars));
                 }
                
             
             res.add(new ArrayList<>(list));
             list = new ArrayList();
             return;
         }
         for(int i = 0;i < len;i++){
             //剪枝 判断row行 i列是否可以放皇后
             if(isValid(row,i)){
                 //可以放皇后
                 ans[row] = i;
                 //进行下一行
                 backTracking(row + 1);
             }
             //不能放就继续循环下一列直至本行全部不能放 回溯
         }
   }

   boolean isValid(int row, int col) {

          for(int i = 0;i < row; i++){
              //如果 第i行 ans[i]列有皇后 即 ans[i] == col 那么col这一列不能再放皇后了
               if(ans[i] == col) return false;
               // 通过斜率比较斜线上是否有皇后 (i,ans[i]) (row,col)
               if (  row - i == Math.abs( col- ans[i]) ) return false;
          }

          return true;
   }

}