当前位置:   article > 正文

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

在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
声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号