LeetCode 笔记系列 14 N-Queen II [思考的深度问题]

题目： Follow up for N-Queens problem.

　　Now, instead outputting board configurations, return the total number of distinct solutions.

就是让你输出N皇后问题的解法数目。

直接求解，每次还记录整个棋盘位置那种方法就不说了，必须超时。

有一个牛逼大了的超级无敌帅的位移动解法。我们暂且不表。看看我当时想的一个解法。

首先，对于皇后的那个递归方法，我有三个变量分别表示1.一个int值，表示递归到当前的level，当前的哪几个col被占领了，例如11011就表示我们下一个Q只能放在第三个（从第一个位置开始数）位置上了；2.一个hash table，表示左对角线到目前为止，是否有Queen占领过了；2.一个hash table，表示右对角线是否有Queen占领过了。然后每次都去查询row上的可用格子，再去看看两个hash table上的可用格子，一起决定这一层我们选取那一（几）个作为备选项。

说说那个表示对角线的hash table，是一个Integer到boolean的映射。因为，所有某条固定左对角线上的点（row, col)，row - col都是定值，那么可以用row - col表示一条左对角线嘛！同理可以用row + col表示右对角线嘛。

然后任意一个点，我们就知道它左右对角线的key了，就可以去那个hash 表里面查看是不是有Queen占领过啦。

所以，给出一个当前被占领的状态，一个左对角线被占领的状态，一个右对角线被占领的状态，我们就可以计算出下一步在哪里放Queen啦。方法如下：

1  private static int available(int cur_row_status, 
2             HashMap<Integer, Boolean> left_digra_status, HashMap<Integer, Boolean> right_digra_status, int row, int n){
3         int avail = cur_row_status;
4         for(int j = 0; j < n; j++){
5             if((left_digra_status.containsKey(row + j) && left_digra_status.get(row + j))
6                     || (right_digra_status.containsKey(row - j) && right_digra_status.get(row - j))) avail = set(avail, j);
7         }
8         return avail;
9     }

available方法

例如，返回如果是而110011（二进制），那么中间两位是可以放Q的。

那，我们就可以定义递归函数咯哦。

private static void collectSolutions(int cur_row_status, 
            HashMap<Integer, Boolean> left_digra_status, HashMap<Integer, Boolean> right_digra_status, 
            int row, int n, int[] count){
        if(row == n) {
            count[0]++;
            return;
        }
        int avail = available(cur_row_status, left_digra_status,right_digra_status, row, n);
        for(int i = 0; i < n; i++){
            if(!isSet(avail, i)){
                left_digra_status.put(row + i, true);
                right_digra_status.put(row - i, true);
                collectSolutions(set(cur_row_status, i), left_digra_status, right_digra_status, row + 1, 
                        n, count);
                left_digra_status.put(row + i, false);
                right_digra_status.put(row - i, false);
            }
        }
    }

collectSolutions

count里面就放我们的计数。注意每次递归子函数返回后，要重新设置对角线。col的那个状态不用重置了，因为java函数不会改变int值的。

主函数这样写：

 1 public static int  totalNQueens(int n) {
 2         // Start typing your Java solution below
 3         // DO NOT write main() function
 4         int cur_row_status = 0;
 5         int[] count = new int[1];
 6         HashMap<Integer, Boolean> left_digra_status = new HashMap<Integer, Boolean>();
 7         HashMap<Integer, Boolean> right_digra_status = new HashMap<Integer, Boolean>();
 8         collectSolutions(cur_row_status, left_digra_status, right_digra_status, 0, n, count);
 9         return count[0];
10     }

然后我觉得我这方法已经不错了吧，结果还是让大集合潮湿了。

牛逼闪闪，刺瞎我的24k钛合金狗眼的位移算法来鸟。

 1 public int totalNQueens(int n){
 2         cnt = 0;
 3         upper = (1<<n)-1 ;
 4         Queen(0,0,0);
 5         return cnt;
 6     }
 7     
 8     //为啥说大牛niub呢，看看我下面那个，再对比ld和rd，人大牛一眼就看出来了，没必要保存
 9     //所有对角线信息啊。下一个状态，完全由当前状态决定！！
10     private void Queen(int row, int ld, int rd){//ld, left 对角线; rd, right 对角线
11          int pos, p;
12          if(row!=upper)
13          {
14              //so pos in binary is like, under current row/ld/rd restriction, what is available slot to put Q
15              pos = upper & (~(row | ld |rd));
16              while(pos!=0)//available is 1
17              {
18                  p = pos & (-pos);//from right to left, the first "1" in pos
19                  //now, we occupy the most right available position
20                  pos = pos - p;//now take this available as ”Q“，pos kind of like a available slot marker
21                  Queen(row+p,(ld+p)<<1,(rd+p)>>1);
22              }
23          }
24          else ++cnt;
25     }

Niubility N Queen

好一个不明觉厉，男默女泪的算法！

。。。。。

首先，再次承认和牛人的差距。

其次，反思，反思，深刻地反思。为毛牛人就知道这一点呢？其实所有中间信息都可以用一个整数来表示啊。

特别是那个左右对角线的事情，弄的本娃很郁闷。仔细想想，可不是嘛，当设置了一个Q以后，就是设置其左下方和右下方不能访问嘛。随着层次的深入（向最后一行靠近），对角线的状态可不就是左对角线左移，右对角线右移嘛。天，好有画面感的事情。

这里还有个小技巧。11100这个二进制数，怎么知道从右向左边第一个1的位置啊？

p = (pos) & (-pos)

我真是不知道这个，如果你也不知道负数在计算机中的表示方法的话，建议google之。

哦，这里有个关于这个算法的图图，看看有帮助。http://www.matrix67.com/blog/archives/266

我想去买这位blogger的书了。

总结：

1. 思考要有深度。就是说，理解一下，当前的信息到底是怎么样得出来的，而不是看表象。

2. 要有画面感。