# 原创
：  八皇后问题

# 八皇后问题

## 八皇后问题

> 
参考：维基百科[八皇后问题](https://zh.wikipedia.org/wiki/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98)


**八皇后问题**是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条**横行、纵行或斜线**上。八皇后问题可以推广为更一般的**n皇后摆放问题**：这时棋盘的大小变为**n**×**n**，而皇后个数也变成**n**。**当且仅当**n** = 1或**n** ≥ 4时问题有解。**维基百科给出了很详细的解答。

### 状态表示

用元祖或列表表示一个解决方案，state[0]==3表示第一行的皇后在第四列上。当递归到某一层面，只知道上一行的皇后状态，因此需要一个长度小于8的状态元组

### 条件限定

```
def conflict(state,nextX):
    nextY = len(state)
    for i in range(nextY):
        if abs(state[i]-nextX) in (0,nextY-i):
            return True
    return False

```

### 基本情况

```
# 如果只有最后一个皇后没有放置，那么遍历它所有可能的位置，返回没有冲突的位置
# num是皇后总数，state是存放前面皇后的位置
# 不是最后一个皇后则递归确定前一个皇后位置
def queens(num=8,state=()):
    for pos in range(num):
        if not conflict(state,pos):
            if len(state)==num-1:
                yield (pos,)
            else:
                for result in queens(num,state+(pos,)):
                    yield (pos,)+result

```

### 打包

```
def prettyprint(solution):
    def line(pos,length=len(solution)):
        return ". "*(pos)+"X "+". "*(length-pos-1)
    for pos in solution:
        print line(pos)

```

一共92中答案。