LeetCode51. N皇后
本文最后更新于 1156 天前,其中的信息可能已经有所发展或是发生改变。

一、介绍

这题看似简单的回溯,却有很多边界问题,足足搞了3-4个小时才通过。

二、题目

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

上图为 8 皇后问题的一种解法。

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q''.' 分别代表了皇后和空位。

 

示例:

输入:4
输出:[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

 

提示:

  • 皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
Related Topics
  • 回溯算法
  • \n

  • 👍 702
  • 👎 0
  • 三、代码

    class Solution {
    
            private int[][] arr;
    
            private List<List<String>> ans = new ArrayList<>();
    
            private int n;
            private int countQ = 0;
    
    
            public List<List<String>> solveNQueens(int n) {
                this.n = n;
                arr = new int[n + 2][n + 2];
                for (int i = 0; i < n; i++) {
                    dg(1, i + 1);
                    arr[1][i + 1] = 0;
                    countQ--;
                }
                return ans;
            }
    
            private void dg(int x, int y) {
                arr[x][y] = 1;
                countQ++;
                if (validate(x, y)) {
                    if (countQ == n) {
                        output();
                        return;
                    }
                    if (x < n) {
                        x++;
                        for (int i = 0; i < n; i++) {
                            y = i + 1;
                            dg(x, y);
                            arr[x][y] = 0;
                            countQ--;
                        }
                    }
                }
            }
    
            private void output() {
                ArrayList<String> strings = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    StringBuilder builder = new StringBuilder();
                    for (int j = 0; j < n; j++) {
                        builder.append(arr[i + 1][j + 1] == 1 ? "Q" : ".");
                    }
                    strings.add(builder.toString());
                }
                ans.add(strings);
            }
    
            private boolean validate(int x, int y) {
                int countXQ = 0;
                int countYQ = 0;
                int countLUQ = 0;
                int countRDQ = 0;
                int countRUQ = 0;
                int countLDQ = 0;
                for (int i = 0; i < n; i++) {
                    if (arr[x][i + 1] == 1) {
                        countYQ++;
                    }
                    if (arr[i + 1][y] == 1) {
                        countXQ++;
                    }
                    if (x - i > 0 && y - i > 0 && arr[x - i][y - i] == 1) {
                        countLUQ++;
                    }
                    if (x + i <= n && y + i <= n && arr[x + i][y + i] == 1) {
                        countRDQ++;
                    }
                    if (x - i > 0 && y + i <= n && arr[x - i][y + i] == 1) {
                        countRUQ++;
                    }
                    if (x + i <= n && y - i > 0 && arr[x + i][y - i] == 1) {
                        countLDQ++;
                    }
    
                }
                if (countXQ > 1
                        || countYQ > 1
                        || countLUQ > 1
                        || countRDQ > 1
                        || countRUQ > 1
                        || countLDQ > 1
                ) {
                    return false;
                }
                return true;
            }
        }
    
    作者:Yuyy
    博客:https://yuyy.info
    暂无评论

    发送评论 编辑评论

    
    				
    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇