首页 > 试题广场 >

八皇后

[编程题]八皇后

热度指数：9648 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入描述:

每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出描述:

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

示例1

输入

1
92

输出

15863724
84136275

算法知识视频讲解

Python

TimeMac

思路比较简单，先找出规则，同一行同一列，同一斜排不能同时有两个。

这里用递归+全局，

从第一行开始，每一行从第一个位置开始检查该位置是否能放皇后（和前面的行比较）

如果能，则寻找下一行能放的位置.....

一直走到找到全部的八个皇后位置，然后加入到全局变量。

def findAllResult(row):
    global results                  
    global tempPos
    if row == 9:
        tmp = ""
        for i in range(1,9):
            tmp += str(tempPos[i])
        results.append(tmp)
    else:
        for i in range(1,9):           #这个循环是寻找放在当前行row的合适皇后位置
            tempPos[row] = i
            flag = True
            for j in range(1,row):     #检查是否不在同一列或者斜线上
                if tempPos[row] == tempPos[j] or row - j == abs(tempPos[row] - tempPos[j]):
                    flag = False
                    break
            if flag:                   #如果放在该行位置不影响前面行的皇后则寻找下一行
                findAllResult(row+1)   #走到最后又会回来这里继续for循环
while True:
    try:
        num = int(input())
        results = []                   #保存着全部92种结果
        tempPos = list(range(9))       #临时存放着每一行皇后的位置
        findAllResult(1)
        results.sort()
        print(results[num-1])
    except Exception:
        break

编辑于 2018-09-28 20:26:43 回复(0)