力扣0052-N皇后 II

Posted on | In |

问题：

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

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

  • 按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
  • 回溯是深度优先搜索的一种

皇后问题的解的个数：

问题规模 0 1 2 3 4 5 6 7 8 9 10 11 12
解的个数 0 1 0 0 2 10 4 40 92 352 724 2680 14200

循环+递归

获得解的列表

  • Queen(foundK, queenStore)接受参数是一个数foundK（表示已经找到了foundK个皇后，现在要找索引为foundK的皇后，也就是第foundK+1个皇后），和一个列表queenStore（其长度与皇后问题规模N相同）。
    • queenStore列表的前foundK个元素，表示已经找到的foundK个皇后在其所在行的位置。
    • 返回值是皇后问题的解（N个皇后的摆放方案）的列表，如果没有则返回空列表。
  • 子函数_check(idx, foundQs)接受参数是一个数idx（假定第foundK+1个皇后在其所在行的位置）和一个列表foundQs（已经找到的foundK个皇后的列表），返回值表示第foundK+1个皇后放在i这个位置是否成立。
  • 进入分支之前用_check(idx, foundQs)进行审核，审核通过的才会进入分支。
    • 边界判断语句if k > N or k < 0 or N == 0: return res，只要调用最初调用Queen(foundK, queenStore)的参数没问题，这个判断语句就不会起作用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def Queen(foundK, queenStore): 
    def _check(idx, foundQs):
        #用于检查(foundK,idx)这个位置是否可以放置一个皇后
        for q_idx, q in enumerate(foundQs):
            if idx == q or abs(idx - q) == abs(len(foundQs) - q_idx):
                return False
        return True 
    N = len(queenStore) # 皇后问题的规模
    if foundK > N or foundK < 0 or N == 0:
        # 边界情况，返回空列表
        return []  
    elif foundK == N: # 找到一个解
        return [queenStore[::]]
    else:
        res = [] # 存储问题的解
        for idx in range(N):
            if _check(idx, queenStore[:foundK]):        
                queenStore[foundK] = idx
                res.extend(Queen(foundK+1, queenStore))
        return res

用Queen(foundK, queenStore)求解6皇后问题的用法：

1
2
N = 6
Queen(0, [0]*N)

获得解的个数

如果只要返回解的数量，而非具体的摆放皇后的方案，则可将上述代码改成如下版本：

  • 如果参数有误则返回0，如果找到一个解（最后一行，且能放置皇后）则返回1，其它情况（所在位置放置了皇后，且不在最后一行）则各分支的返回值求和并返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def Queen(foundK, queenStore): 
    def _check(idx, foundQs):
        #用于检查(foundK,idx)这个位置是否可以放置一个皇后
        for q_idx, q in enumerate(foundQs):
            if idx == q or abs(idx - q) == abs(len(foundQs) - q_idx):
                return False
        return True 
    N = len(queenStore) # 皇后问题的规模
    if foundK > N or foundK < 0 or N == 0:
        return 0  
    elif foundK == N: # 找到一个解
        return 1
    else:
        count = 0
        for idx in range(N):
            if _check(idx, queenStore[:foundK]):        
                queenStore[foundK] = idx
                count += Queen(foundK+1, queenStore)
        return count

纯递归

纯递归

  • 只用递归，不用循环。纯递归与循环+递归都是深度优先，区别在于前者搜索路径上任意一点在往下搜索时不记录该点的其它分支，搜索路径是一条线，而后者通过循环结构记录了其它分支，其搜索路径是一棵树。
  • 相比循环+递归方案，纯递归方案的递归层数大大增加，而且一直累加，问题规模大于6时就发生栈溢出而导致该方案不可用。前者的栈的深度等于皇后问题的规模N，而后者的上限可能是\(N^N\)。
  • Queen(foundK, idx, pathStore)返回值是方案个数，三个输入参数是搜索所需要的全部信息。这三个输入参数是
    • 一个数foundK\(\in [0, 1, \cdots, N]\)（表示已经找到了foundK个皇后，现在要找行索引为foundK的皇后，也就是第foundK+1个皇后），
    • idx是要检测的第foundK行的\(idx\in [0, 1, \cdots, N-1]\)位置，
    • 一个列表queenStore（其长度与皇后问题规模N相同）,
  • Queen函数的递归调用形成一个不断增长的栈，每个栈上有个值用于标记该栈上产生的解的数量（0个或1个），直到搜索完毕。搜索完毕后不断出栈，同时将抛出栈的解的数量累加并将该值往调用处传递，如此则最初调用Queen函数处的返回值就是皇后问题的解的数量。
  • 当某一层已经搜索到最后一个位置且审核未通过，或者搜索到最后一层的最后一个位置（通过与否无所谓），就要用_goback(foundK, queenStore)往之前的层回退，直到遇到第一个该层皇后的位置不是该行最后一个位置的层，继续搜索。如果这样的层不存在，则开启出栈过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def Queen(foundK, idx, queenStore):    
    def _check(idx, foundQs):
        #用于检查(foundK,idx)这个位置是否可以放置一个皇后
        for q_idx, q in enumerate(foundQs):
            if idx == q or abs(idx - q) == abs(len(foundQs) - q_idx):
                return False
        return True 
    def _goback(foundK, queenStore):
        N = len(queenStore)
        for i in range(foundK - 1, -1, -1):
            if queenStore[i] != N - 1:
                return i

    N = len(queenStore)
    new = 0 # 标记是否产生了一个新的解   
    if _check(idx, queenStore[:foundK]):
        # 审核通过，按是否是最后一个皇后，分两种情况处理
        queenStore[foundK] = idx 
        if foundK != N -1: 
            # 如果找到的不是最后一层的皇后，则检查下一层的第一个位置
            return Queen(foundK+1, 0, queenStore) 
        else: # 找到一个解
            new += 1
    # 接下来覆盖两种情况，一种是审核未通过，第二种是审核通过了且是最后一层的皇后
    if idx != N -1: # idx不是该行最后一个位置
        ret = Queen(foundK, idx+1, queenStore)
        return new + ret
    else: # 此时idx = N -1 
        foundK = _goback(foundK, queenStore)
        ret = 0
        if foundK is not None:
            idx = queenStore[foundK]+1
            ret = Queen(foundK, idx, queenStore)
        return new + ret

用法，求五皇后问题的解的个数：

1
2
3
N = 5
count = Queen(0, 0, [0]*N)
print(count)

尾递归

如果既要用纯递归，又要摆脱栈溢出问题，只能采用尾递归。尾递归就是操作的最后一步是调用自身的递归。它和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。与普通递归相比，调用递归函数是用return语句，另外搜索状态完全由递归函数的参数决定，而不依赖函数参数之外的参数。

  • Python语言不直接支持尾递归，因此写了个装饰器@tail_call_optimized修饰Queen函数，用以手工操作尾递归的栈数据。
  • 与上边的纯递归版本相比，尾递归版本的所有的Queen函数递归调用都是直接将其本身执行return。只好定义一个引用变量(单元素列表)记录找到的解的数量，作为递归函数的全局变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def tail_call_optimized(g):   
    class TailRecurseException(BaseException):  
        def __init__(self, args, kwargs):  
            self.args = args  
            self.kwargs = kwargs 
    def func(*args, **kwargs):  
        import sys 
        f = sys._getframe()  
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:  
            raise TailRecurseException(args, kwargs)    
        else:  
            while 1:  
                try:  
                    return g(*args, **kwargs)  
                except TailRecurseException as e:  
                    args = e.args  
                    kwargs = e.kwargs  
    func.__doc__ = g.__doc__  
    return func

@tail_call_optimized
def Queen(foundK, idx, queenStore, count):    
    def _check(idx, foundQs):
        #用于检查(foundK,idx)这个位置是否可以放置一个皇后
        for q_idx, q in enumerate(foundQs):
            if idx == q or abs(idx - q) == abs(len(foundQs) - q_idx):
                return False
        return True 
    def _goback(foundK, queenStore):
        N = len(queenStore)
        for i in range(foundK - 1, -1, -1):
            if queenStore[i] != N - 1:
                return i

    N = len(queenStore)
    new = 0 # 标记是否产生了一个新的解   
    if _check(idx, queenStore[:foundK]):
        # 审核通过，按是否是最后一个皇后，分两种情况处理
        queenStore[foundK] = idx 
        if foundK != N -1: 
            # 如果找到的不是最后一层的皇后，则检查下一层的第一个位置
            return Queen(foundK+1, 0, queenStore, count) 
        else: # 找到一个解
            new += 1
    # 接下来覆盖两种情况，一种是审核未通过，第二种是审核通过了且是最后一层的皇后
    count[0] += new
    if idx != N -1: # idx不是该行最后一个位置
        return Queen(foundK, idx+1, queenStore, count)
    else: # 此时idx = N -1 
        foundK = _goback(foundK, queenStore)
        if foundK is not None:
            idx = queenStore[foundK]+1
            return Queen(foundK, idx, queenStore, count)

用法，求八皇后问题的解的个数：

1
2
3
4
N = 8
count = [0]
Queen(0, 0, [0]*N, count)
print(count[0])

纯循环

尾递归仍然进行大量栈操作，效率不佳。好在尾递归可以很容易改造成纯循环，大大降低栈的开销。

  • 尾递归改成纯循环的方法：主要在每个循环体开始时把递归函数需要的几个参数准备好即可，也就是在尾递归的递归调用处，更新参数并用continue进入下一个循环体。循环体共用一个全局变量来统计解的个数。
  • _goback(foundK, queenStore)无返回值时，打破循环，返回解的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def Queen(foundK, idx, queenStore):    
    def _check(idx, foundQs):
        #用于检查(foundK,idx)这个位置是否可以放置一个皇后
        for q_idx, q in enumerate(foundQs):
            if idx == q or abs(idx - q) == abs(len(foundQs) - q_idx):
                return False
        return True 
    def _goback(foundK, queenStore):
        N = len(queenStore)
        for i in range(foundK - 1, -1, -1):
            if queenStore[i] != N - 1:
                return i

    N = len(queenStore)
    count = 0
    while True:
        if _check(idx, queenStore[:foundK]):
            # 审核通过，按是否是最后一个皇后，分两种情况处理
            queenStore[foundK] = idx 
            if foundK != N -1: 
                # 如果找到的不是最后一层的皇后，则检查下一层的第一个位置
                foundK, idx = foundK+1, 0
                continue
            else: # 找到一个解
                count += 1
        # 接下来覆盖两种情况，一种是审核未通过，第二种是审核通过了且是最后一层的皇后
        if idx != N -1: # idx不是该行最后一个位置
            idx += 1
            continue
        else: # 此时idx = N -1 
            foundK = _goback(foundK, queenStore)
            if foundK is not None:
                idx = queenStore[foundK]+1
                continue
            else:
                break
    return count