在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，用Python编写程序，问有多少种摆法？并列举出所有摆法。_在8×8格的国际象棋棋盘上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处

可以扩展问题以使用NxN大小的板来解决难题。

代码

'''N Queens problem'''

from functools import reduce
from itertools import chain


# queenPuzzle :: Int -> Int -> [[Int]]
def queenPuzzle(nCols):
    '''All board patterns of this dimension
       in which no two Queens share a row,
       column, or diagonal.
    '''

    def go(nRows):
        lessRows = nRows - 1
        return reduce(
            lambda a, xys: a + reduce(
                lambda b, iCol: b + [xys + [iCol]] if (
                    safe(lessRows, iCol, xys)
                ) else b,
                enumFromTo(1)(nCols),
                []
            ),
            go(lessRows),
            []
        ) if 0 < nRows else [[]]

    return go


# safe :: Int -> Int -> [Int] -> Bool
def safe(iRow, iCol, pattern):
    '''True if no two queens in the pattern
       share a row, column or diagonal.
    '''

    def p(sc, sr):
        return (iCol == sc) or (
                sc + sr == (iCol + iRow)
        ) or (sc - sr == (iCol - iRow))

    return not any(map(p, pattern, range(0, iRow)))


# ------------------------- TEST -------------------------
# main :: IO ()
def main():
    '''Number of solutions for boards of various sizes'''

    n = 8
    xs = queenPuzzle(n)(n)

    print(
        str(len(xs)) + ' solutions for a {n} * {n} board:\n'.format(n=n)
    )
    print(showBoards(10)(xs))

    print(
        fTable(
            '\n\n' + main.__doc__ + ':\n'
        )(str)(lambda n: str(n).rjust(3, ' '))(
            lambda n: len(queenPuzzle(n)(n))
        )(enumFromTo(1)(10))
    )


# ---------------------- FORMATTING ----------------------

# showBoards :: Int -> [[Int]] -> String
def showBoards(nCols):
    '''String representation, with N columns
       of a set of board patterns.
    '''

    def showBlock(b):
        return '\n'.join(map(intercalate('  '), zip(*b)))

    def go(bs):
        return '\n\n'.join(map(
            showBlock,
            chunksOf(nCols)([
                showBoard(b) for b in bs
            ])
        ))

    return go


# showBoard :: [Int] -> String
def showBoard(xs):
    '''String representation of a Queens board.'''
    lng = len(xs)

    def showLine(n):
        return ('.' * (n - 1)) + '♛' + ('.' * (lng - n))

    return map(showLine, xs)


# fTable :: String -> (a -> String) ->
#                     (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
    '''Heading -> x display function -> fx display function ->
                     f -> xs -> tabular string.
    '''

    def go(xShow, fxShow, f, xs):
        ys = [xShow(x) for x in xs]
        w = max(map(len, ys))
        return s + '\n' + '\n'.join(map(
            lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
            xs, ys
        ))

    return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
        xShow, fxShow, f, xs
    )


# ----------------------- GENERIC ------------------------

# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
    '''Integer enumeration from m to n.'''
    return lambda n: range(m, 1 + n)


# chunksOf :: Int -> [a] -> [[a]]
def chunksOf(n):
    '''A series of lists of length n, subdividing the
       contents of xs. Where the length of xs is not evenly
       divible, the final list will be shorter than n.
    '''
    return lambda xs: reduce(
        lambda a, i: a + [xs[i:n + i]],
        range(0, len(xs), n), []
    ) if 0 < n else []


# intercalate :: [a] -> [[a]] -> [a]
# intercalate :: String -> [String] -> String
def intercalate(x):
    '''The concatenation of xs
       interspersed with copies of x.
    '''
    return lambda xs: x.join(xs) if isinstance(x, str) else list(
        chain.from_iterable(
            reduce(lambda a, v: a + [x, v], xs[1:], [xs[0]])
        )
    ) if xs else []


# MAIN ---
if __name__ == '__main__':
    main()
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
'
运行
运行

输出结果

92 solutions for a 8 * 8 board:

♛.......  ♛.......  ♛.......  ♛.......  .♛......  .♛......  .♛......  .♛......  .♛......  .♛......
....♛...  .....♛..  ......♛.  ......♛.  ...♛....  ....♛...  ....♛...  .....♛..  .....♛..  ......♛.
.......♛  .......♛  ...♛....  ....♛...  .....♛..  ......♛.  ......♛.  ♛.......  .......♛  ..♛.....
.....♛..  ..♛.....  .....♛..  .......♛  .......♛  ♛.......  ...♛....  ......♛.  ..♛.....  .....♛..
..♛.....  ......♛.  .......♛  .♛......  ..♛.....  ..♛.....  ♛.......  ...♛....  ♛.......  .......♛
......♛.  ...♛....  .♛......  ...♛....  ♛.......  .......♛  .......♛  .......♛  ...♛....  ....♛...
.♛......  .♛......  ....♛...  .....♛..  ......♛.  .....♛..  .....♛..  ..♛.....  ......♛.  ♛.......
...♛....  ....♛...  ..♛.....  ..♛.....  ....♛...  ...♛....  ..♛.....  ....♛...  ....♛...  ...♛....

.♛......  .♛......  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....
......♛.  .......♛  ♛.......  ....♛...  ....♛...  ....♛...  ....♛...  .....♛..  .....♛..  .....♛..
....♛...  .....♛..  ......♛.  .♛......  .♛......  ......♛.  .......♛  .♛......  .♛......  .♛......
.......♛  ♛.......  ....♛...  .......♛  .......♛  ♛.......  ...♛....  ....♛...  ......♛.  ......♛.
♛.......  ..♛.....  .......♛  ♛.......  .....♛..  ...♛....  ♛.......  .......♛  ♛.......  ....♛...
...♛....  ....♛...  .♛......  ......♛.  ...♛....  .♛......  ......♛.  ♛.......  ...♛....  ♛.......
.....♛..  ......♛.  ...♛....  ...♛....  ......♛.  .......♛  .♛......  ......♛.  .......♛  .......♛
..♛.....  ...♛....  .....♛..  .....♛..  ♛.......  .....♛..  .....♛..  ...♛....  ....♛...  ...♛....

..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ...♛....  ...♛....
.....♛..  .....♛..  .....♛..  .....♛..  .....♛..  ......♛.  ......♛.  .......♛  ♛.......  ♛.......
...♛....  ...♛....  .......♛  .......♛  .......♛  .♛......  .♛......  ...♛....  ....♛...  ....♛...
♛.......  .♛......  ♛.......  ♛.......  .♛......  .......♛  .......♛  ......♛.  .......♛  .......♛
.......♛  .......♛  ...♛....  ....♛...  ...♛....  ....♛...  .....♛..  ♛.......  .♛......  .....♛..
....♛...  ....♛...  ......♛.  ......♛.  ♛.......  ♛.......  ...♛....  .....♛..  ......♛.  ..♛.....
......♛.  ......♛.  ....♛...  .♛......  ......♛.  ...♛....  ♛.......  .♛......  ..♛.....  ......♛.
.♛......  ♛.......  .♛......  ...♛....  ....♛...  .....♛..  ....♛...  ....♛...  .....♛..  .♛......

...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ...♛....
.♛......  .♛......  .♛......  .♛......  .♛......  .♛......  .....♛..  .....♛..  .....♛..  ......♛.
....♛...  ......♛.  ......♛.  ......♛.  .......♛  .......♛  ♛.......  .......♛  .......♛  ♛.......
.......♛  ..♛.....  ..♛.....  ....♛...  ....♛...  .....♛..  ....♛...  .♛......  ..♛.....  .......♛
.....♛..  .....♛..  .....♛..  ♛.......  ......♛.  ♛.......  .♛......  ......♛.  ♛.......  ....♛...
♛.......  .......♛  .......♛  .......♛  ♛.......  ..♛.....  .......♛  ♛.......  ......♛.  .♛......
..♛.....  ♛.......  ....♛...  .....♛..  ..♛.....  ....♛...  ..♛.....  ..♛.....  ....♛...  .....♛..
......♛.  ....♛...  ♛.......  ..♛.....  .....♛..  ......♛.  ......♛.  ....♛...  .♛......  ..♛.....

...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ...♛....  ....♛...  ....♛...  ....♛...  ....♛...
......♛.  ......♛.  ......♛.  .......♛  .......♛  .......♛  ♛.......  ♛.......  ♛.......  .♛......
..♛.....  ....♛...  ....♛...  ♛.......  ♛.......  ....♛...  ...♛....  .......♛  .......♛  ...♛....
.......♛  .♛......  ..♛.....  ..♛.....  ....♛...  ..♛.....  .....♛..  ...♛....  .....♛..  .....♛..
.♛......  .....♛..  ♛.......  .....♛..  ......♛.  ♛.......  .......♛  .♛......  ..♛.....  .......♛
....♛...  ♛.......  .....♛..  .♛......  .♛......  ......♛.  .♛......  ......♛.  ......♛.  ..♛.....
♛.......  ..♛.....  .......♛  ......♛.  .....♛..  .♛......  ......♛.  ..♛.....  .♛......  ♛.......
.....♛..  .......♛  .♛......  ....♛...  ..♛.....  .....♛..  ..♛.....  .....♛..  ...♛....  ......♛.

....♛...  ....♛...  ....♛...  ....♛...  ....♛...  ....♛...  ....♛...  ....♛...  ....♛...  ....♛...
.♛......  .♛......  .♛......  ..♛.....  ..♛.....  ..♛.....  ......♛.  ......♛.  ......♛.  ......♛.
...♛....  .....♛..  .......♛  ♛.......  ♛.......  .......♛  ♛.......  ♛.......  .♛......  .♛......
......♛.  ♛.......  ♛.......  .....♛..  ......♛.  ...♛....  ..♛.....  ...♛....  ...♛....  .....♛..
..♛.....  ......♛.  ...♛....  .......♛  .♛......  ......♛.  .......♛  .♛......  .......♛  ..♛.....
.......♛  ...♛....  ......♛.  .♛......  .......♛  ♛.......  .....♛..  .......♛  ♛.......  ♛.......
.....♛..  .......♛  ..♛.....  ...♛....  .....♛..  .....♛..  ...♛....  .....♛..  ..♛.....  ...♛....
♛.......  ..♛.....  .....♛..  ......♛.  ...♛....  .♛......  .♛......  ..♛.....  .....♛..  .......♛

....♛...  ....♛...  ....♛...  ....♛...  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..
......♛.  ......♛.  .......♛  .......♛  ♛.......  .♛......  .♛......  ..♛.....  ..♛.....  ..♛.....
.♛......  ...♛....  ...♛....  ...♛....  ....♛...  ......♛.  ......♛.  ♛.......  ♛.......  ♛.......
.....♛..  ♛.......  ♛.......  ♛.......  .♛......  ♛.......  ♛.......  ......♛.  .......♛  .......♛
..♛.....  ..♛.....  ..♛.....  ......♛.  .......♛  ..♛.....  ...♛....  ....♛...  ...♛....  ....♛...
♛.......  .......♛  .....♛..  .♛......  ..♛.....  ....♛...  .......♛  .......♛  .♛......  .♛......
.......♛  .....♛..  .♛......  .....♛..  ......♛.  .......♛  ....♛...  .♛......  ......♛.  ...♛....
...♛....  .♛......  ......♛.  ..♛.....  ...♛....  ...♛....  ..♛.....  ...♛....  ....♛...  ......♛.

.....♛..  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..  .....♛..
..♛.....  ..♛.....  ..♛.....  ..♛.....  ..♛.....  ...♛....  ...♛....  ...♛....  ...♛....  .......♛
....♛...  ....♛...  ......♛.  ......♛.  ......♛.  ♛.......  .♛......  ......♛.  ......♛.  .♛......
......♛.  .......♛  .♛......  .♛......  ...♛....  ....♛...  .......♛  ♛.......  ♛.......  ...♛....
♛.......  ♛.......  ...♛....  .......♛  ♛.......  .......♛  ....♛...  ..♛.....  .......♛  ♛.......
...♛....  ...♛....  .......♛  ....♛...  .......♛  .♛......  ......♛.  ....♛...  .♛......  ......♛.
.♛......  .♛......  ♛.......  ♛.......  .♛......  ......♛.  ♛.......  .♛......  ....♛...  ....♛...
.......♛  ......♛.  ....♛...  ...♛....  ....♛...  ..♛.....  ..♛.....  .......♛  ..♛.....  ..♛.....

......♛.  ......♛.  ......♛.  ......♛.  ......♛.  ......♛.  ......♛.  ......♛.  .......♛  .......♛
♛.......  .♛......  .♛......  ..♛.....  ..♛.....  ...♛....  ...♛....  ....♛...  .♛......  .♛......
..♛.....  ...♛....  .....♛..  ♛.......  .......♛  .♛......  .♛......  ..♛.....  ...♛....  ....♛...
.......♛  ♛.......  ..♛.....  .....♛..  .♛......  ....♛...  .......♛  ♛.......  ♛.......  ..♛.....
.....♛..  .......♛  ♛.......  .......♛  ....♛...  .......♛  .....♛..  .....♛..  ......♛.  ♛.......
...♛....  ....♛...  ...♛....  ....♛...  ♛.......  ♛.......  ♛.......  .......♛  ....♛...  ......♛.
.♛......  ..♛.....  .......♛  .♛......  .....♛..  ..♛.....  ..♛.....  .♛......  ..♛.....  ...♛....
....♛...  .....♛..  ....♛...  ...♛....  ...♛....  .....♛..  ....♛...  ...♛....  .....♛..  .....♛..

.......♛  .......♛
..♛.....  ...♛....
♛.......  ♛.......
.....♛..  ..♛.....
.♛......  .....♛..
....♛...  .♛......
......♛.  ......♛.
...♛....  ....♛...


Number of solutions for boards of various sizes:

 1 ->   1
 2 ->   0
 3 ->   0
 4 ->   2
 5 ->  10
 6 ->   4
 7 ->  40
 8 ->  92
 9 -> 352
10 -> 724
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105