python解决八皇后问题¶

八皇后问题，乍一看好像很复杂，毕竟8*8的棋盘，8个棋子的组合实在太多，让人无从下手。

面对复杂问题，往往有个很好的出发点，就是：能不能简化问题？

简化八皇后问题¶

八皇后问题碰巧就特别容易简化：

1. 假如前7个棋子已经摆好了（当然是一行一个），那么在第八行放最后一个棋子的时候，我们只需要依次尝试第八行的8个位置就可以了
2. 那么前7个棋子又怎么摆放呢？答案是：假设前6个棋子已经摆好了，我只需要逐个尝试第7行的8个位置就可以了。
3. 很显然，这又是个递归的解决方案，最终，我们一定可以达到一个场景：把第一行摆好就行了。这很简单，第一行的每个位置都可以摆。

代码¶

代码分两块，第一个是判断新棋子是否可以摆放，第二个是主函数。

def conflict(state, new_x):
    # 参数state是一个数组，下标0的元素表示第一行中棋子的列数，下标1的元素表示第二行中棋子的列数……
    rows = len(state)
    for y in range(rows):
        # 依次判断前面各行的棋子和新棋子是否冲突
        x = state[y]
        if x == new_x or abs(x - new_x) == rows - y:
            return True
    return False


def queens(N=8, state=()):
    solutions = []  # 存放有效的棋子摆放方案
    rows = len(state)
    for new_x in range(N):
        # 在前面rows行已经摆好的情况下，
        # 在第rows+1行，从第1列，到第8列，逐个尝试新棋子的位置。
        if not conflict(state, new_x):
            if rows == N - 1:
                # 如果前面已经摆好了7行，那么加上新的棋子，整个棋局就成功摆完了，形成一个有效的摆放方案
                solutions.append((new_x,))
            else:
                # 只摆完一部分，必须接着摆，
                # 不过，接下来的摆放就容易一些了，因为是以前面的摆放为基础的。
                for result in queens(N, state + (new_x,)):
                    # 当前的摆放结果，加上之后的摆放结果，共同构成一个摆放方案
                    solutions.append((new_x,) + result)
    return solutions

if __name__ == '__main__':
    solutions = list(queens(8))
    for i, rs in enumerate(solutions):
        print '%d->%s' % (i, rs)

本文为kyleblog.cn原创，转载请注明出处：https://www.kyleblog.cn/posts/python_8queens