LeetCode: 【L4】N-Queens 解题报告-白红宇

LeetCode: 【L4】N-Queens 解题报告

阅读量：6815 次

发布时间：2019-06-26

本文共 3284 字，大约阅读时间需要 10 分钟。

【L4】N-Queens 解题报告

N-Queens Total Accepted: 16418 Total Submissions: 63309 My Submissions

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.."]

]

经典的

SOLUTION 1：

<此题的难度级别为LEVEL-4>

使用DFS来求解。

主页君写了二个版本来求解。

第一个版本，放置一个皇后之后，从某皇后之后找所有的可能的放置点。这样在Eclipse中可以测试通过，但是

过不了Leetcode的检查。也就是说复杂度过高了。

SOLUTION 2：

后来查资料后，得知为了加快搜索速度，我们应该以这样的思路来思考：

1. 假如我们要放置8个皇后，皇后是会攻击同行的，所以8行必须一行放置一个皇后。

所以前面主页君从某个皇后一直搜索到最后是没有必要的。我们要做的是：放置好一个皇后后，搜索下一行中

能否再放一个皇后，如果是不可以，直接就能返回了。这样子可以节省大量的计算量：

主页君代码如下：

December 17th, 重写如下：

1 public class Solution { 2     public List
       
         solveNQueens(int n) { 3         List
        
          ret = new ArrayList
         
          (); 4          5         if (n == 0) { 6             return ret; 7         } 8          9         dfs(n, new ArrayList
          
           (), ret);10         return ret;11     }12     13     public String[] createSolution(ArrayList
           
             path) {14         /*15         [16          [".Q..",  // Solution 117           "...Q",18           "Q...",19           "..Q."],20         21          ["..Q.",  // Solution 222           "Q...",23           "...Q",24           ".Q.."]25         ]26         */27         int size = path.size();28         String[] ret = new String[size];29         30         for (int i = 0; i< size; i++) {31             StringBuilder sb = new StringBuilder();32             for (int j = 0; j < size; j++) {33                 // a queen.34                 if (j == path.get(i)) {35                     sb.append('Q');36                 } else {37                     sb.append('.');38                 }39             }40             41             ret[i] = sb.toString();42         }43         44         return ret;45     }46     47     //ArrayList
            
              path: store the index of the columns of one solution.48 public void dfs(int n, ArrayList
             
               path, List
              
                ret) {49 if (path.size() == n) {50 String[] solution = createSolution(path);51 ret.add(solution);52 return;53 }54 55 for (int i = 0; i < n; i++) {56 // Judge if this is a solution;57 if (!isValid(path, i)) {58 continue;59 }60 61 path.add(i);62 dfs(n, path, ret);63 path.remove(path.size() - 1);64 }65 }66 67 public boolean isValid(ArrayList
               
                 path, int index) {68 int size = path.size();69 for (int i = 0; i < size; i++) {70 // Same column as one queen.71 if (index == path.get(i)) {72 return false;73 }74 75 // 在两条对角线之上76 // bug 3: 少一个)77 if (size - i == Math.abs(index - path.get(i))) {78 return false;79 }80 }81 82 return true;83 }84 }

View Code

步骤：

1. 建立一个arraylist存储每一行的皇后的列值。

例如：第一行皇后在第三列，第二行皇后在第五列，我们会记录3，5在arraylist中，依次这样推下去。

2. 进入DFS后，首先判断array是不是满，满的话说明8个皇后都放好了，创建一个解并返回。

3. 如果没有满，扫描当前行所有的位置，查找是不是能放一个皇后。如果可以放，继续DFS。不能放的话，就退出就好了。

虽然本题了解了思路后，写出来并不难，但主页君认为难点是在于：你怎么能思考到一行一行放皇后？而不是放好一个再找下一个可能放的点？如果想清楚了这一点也就不难了。

LEVEL 4还是实至名归的。

转载地址：http://dfdzl.baihongyu.com/

你可能感兴趣的文章