首页 > 试题广场 >

【八皇后问题】设在初始状态下国际象棋棋盘上没有任何棋子(皇后

[问答题]

【八皇后问题】设在初始状态下国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行,第2行,…,第8行上布放棋子。在每一行中有8个可选位置,但在任意时刻,棋盘的合法布局都必须满足3个制条件,即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的合法布局。

Cunkou

发表于 2019-02-21 15:13:43 回复(0)

张强201810222256310

python示例，在代码中修改MAX的值，可求解N皇后问题。

MAX = 8 
queen = [0] * MAX * MAX
valid = [0] * MAX 
count = 1


def putQueen(row):
    global count
    for i in xrange(MAX):
        if queen[row*MAX + i] == 0:
            valid[row] = i
            mark = setMark(row, i)
            if row == MAX - 1:
                print count, valid
                count += 1
            else:
                putQueen(row+1)
            unSetMark(mark)


def setMark(row, col):
    """mark"""
    mark = []

    for i in xrange(MAX):
        if queen[row*MAX + i] ==0:
            queen[row*MAX + i] = 1
            mark.append((row, i))

    for i in xrange(row, MAX):
        if queen[i*MAX + col] ==0:
            queen[i*MAX + col] = 1
            mark.append((i, col))

    r, c = row, col
    while r < MAX and c < MAX:
        if queen[r*MAX + c] == 0:
            queen[r*MAX + c] = 1
            mark.append((r, c))
        r += 1
        c += 1

    r, c = row, col
    while r < MAX and c >= 0:
        if queen[r*MAX + c] == 0:
            queen[r*MAX + c] = 1
            mark.append((r, c))
        r += 1
        c -= 1

    return mark


def unSetMark(mark):
    for row, col in mark:
        queen[row*MAX + col] = 0


putQueen(0)

编辑于 2018-10-27 11:45:26 回复(0)