N-Queens疑问

1. public class Solution {
   
2.     public List<List<String>> solveNQueens(int n) {
   
3.         List<List<String>> res = new ArrayList<List<String>>();
   
4.         List<String> item = new ArrayList<String>();
   
5.         if(n == 0)
   
6.             return res;
   
7.         int[] columnVal = new int[n];
   
8.         dfs(n, res, columnVal, 0, item);
   
9.         return res;
   
10.     }
    
11.     public boolean isValid(int row, int[] columnVal) {
    
12.         for(int i = 0; i < row; i++) {
    
13.             if(columnVal[row] == columnVal[i] || Math.abs(columnVal[row] - columnVal[i]) == row - i) {
    
14.                 return false;
    
15.             }
    
16.         }
    
17.         return true;
    
18.     }
    
19.     public void dfs(int n, List<List<String>> res, int[] columnVal, int row, List<String> item) {
    
20.         if(n == row) {
    
21.             for(int i = 0; i < n; i++) {
    
22.                 StringBuilder tmp = new StringBuilder();
    
23.                 for(int j = 0;j < n; j++) {
    
24.                     if(j == columnVal[i])
    
25.                         tmp.append('Q');
    
26.                     else
    
27.                         tmp.append('.');
    
28.                 }
    
29.                 item.add(tmp.toString());
    
30.         }
    
31.             res.add(item);
    
32.             return ;
    
33.     }
    
34.         for(int i = 0; i < n; i++) {
    
35.             columnVal[row] = i;
    
36.             if(isValid(row, columnVal)) {
    
37.                 dfs(n, res, columnVal, row + 1, item);
    
38.             }
    
39.         }
    
40.     }
    
41. }

复制代码

问下大侠这个oj上用9测试的时候为什么会超时啊。。。还有这个题的回溯为什么可以省掉= =谢谢了。。

每次判断一个位置是否可放置只要O(1)的时间，为何要用循环？效率应该是差在这儿了。
你试试sudoku solver那题？同样类型的DFS回溯问题。


回溯与否倒不是问题的关键。

zhuli19901106 发表于 2015-7-9 10:53
每次判断一个位置是否可放置只要O(1)的时间，为何要用循环？效率应该是差在这儿了。
你试试sudoku solver ...

请问判断一个位置是否可以放置如何用O(1)做到呢？是用HashSet之类的记录下之前的放置位置么？

stellari 发表于 2015-7-9 17:10
请问判断一个位置是否可以放置如何用O(1)做到呢？是用HashSet之类的记录下之前的放置位置么？

八皇后要求不能同行、同列、同对角线或者同反对角线
如果我们一行一行地放，那么肯定不会同行，因此开三个数组分别记录 列、对角线、反对角线的占用情况
如果x和y的范围是[0, n - 1]，那么对角线和反对角线位置分别可以表示为x + y和x - y + n - 1，范围都是[0, 2n - 2]
时刻维护这三个数组，就能O(1) 时间检查一个位置能不能放了。

zhuli19901106 发表于 2015-7-9 21:28
八皇后要求不能同行、同列、同对角线或者同反对角线
如果我们一行一行地放，那么肯定不会同行，因此开三 ...

okay，这确实是个好办法。多谢分享！

zhuli19901106 发表于 2015-7-9 10:53
每次判断一个位置是否可放置只要O(1)的时间，为何要用循环？效率应该是差在这儿了。
你试试sudoku solver ...

谢谢回答！我还想问下为什么回溯不是关键呢。。。因为我看网上很多都说是要回溯的。。。

zh355245849 发表于 2015-7-10 12:55
谢谢回答！我还想问下为什么回溯不是关键呢。。。因为我看网上很多都说是要回溯的。。。

我从一开始就想问了：什么叫“省掉回溯”？在我看来这是很标准的Backtracking算法，你说它“省掉"的哪一部分呢？

zhuli19901106 发表于 2015-7-9 21:28
八皇后要求不能同行、同列、同对角线或者同反对角线
如果我们一行一行地放，那么肯定不会同行，因此开三 ...

大神，能写一下具体代码实现么，谢啦。大概明白你的意思，还是不知道怎么写。

发重了，请忽略

pyx115 发表于 2015-7-12 06:13
大神，能写一下具体代码实现么，谢啦。大概明白你的意思，还是不知道怎么写。

此处有代码，可供参考
https://raw.githubusercontent.co ... ode/master/n-queens(AC).cpp