LeetCode 51. N皇后

╰+攻爆jí腚メ 2022-09-03 00:18 177阅读 0赞

#### 题目重述 ####

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

##### 示例 1： #####

输入：n = 4  
输出：\[\[".Q…","…Q",“Q…”,"…Q."\],\["…Q.",“Q…”,"…Q",".Q…"\]\]  
解释：如上图所示，4 皇后问题存在两个不同的解法。

##### 示例 2： #####

输入：n = 1  
输出：\[\[“Q”\]\]

##### 提示： #####

1 <= n <= 9  
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/n-queens  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 思路 ####

回溯法，设定`a[]`，代表代表第i行皇后要放置的位置

#### Java实现 ####

class Solution {
        
        List<List<String>> result = new ArrayList<>();
        /**
         * a[i]的值 代表第i行 放置的位置
         */
        int[] a = new int[10];
    
        public List<List<String>> solveNQueens(int n) {
        
            List<String> t = new ArrayList<>();
            find(0, n,t);
            return result;
        }
    
        /**
         * 回溯法实现
         *
         * @return void
         * @author wyh
         * @date 2021/8/4
         * @Params [k, N]
         */
        public void find(int k, int N, List<String> list) {
        
            //如果k=N 代表能放下
            if (k == N) {
        
                result.add(list);
                return;
            }
            int j;
            // 0到N是横着的一行，对这一行的每个位置进行判断
            for (int i = 0; i < N; i++) {
        
                // 对已经放置的前k-1行进行check检查
                for (j = 0; j < k; j++) {
        
                    //如果冲突
                    // a[j] == i 代表处于同一列了
                    // Math.abs (a[j] - i) == Math.abs(j - k) 代表处于斜线上了
                    if (a[j] == i || Math.abs (a[j] - i) == Math.abs(j - k)) {
        
                        break;
                    }
                }
                //如果遍历完这一行，都不冲突，代表这个位置可以放置
                if (j == k) {
        
                    // 放置皇后
                    a[k] = i;
                    StringBuilder t = new StringBuilder();
                    // 保存遍历结果
                    for (int z = 0; z < N; z++) {
        
                        if(z != i)
                        {
        
                            t.append('.');
                        }else{
        
                            t.append('Q');
                        }
                    }
                    list.add(t.toString());
                    // 回溯法
                    List<String> newList = new ArrayList<>(list);
                    find(k + 1, N,newList);
                    list.remove(list.size()-1);
                }
            }
        }
    }