欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

八皇后问题独立解Python代码

程序员文章站 2022-05-12 18:32:14
...

八皇后问题其实很有趣,借助这个问题可以很好检验对一门新的语言的理解程度。

 

使用生成器,在8皇后的时候,以下非独立解决代码的计算次数为46752次:

# !/usr/bin/python
# coding:utf-8
# __author__=watson


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


def queens(num=1, 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


if __name__ == "__main__":
    print list(queens(8))

 

使用记忆算法,在8皇后的时候,以下非独立解决代码的计算次数为15720次:

# !/usr/bin/python
# coding:utf-8
# __author__=watson

column = rup = lup = []

def conflict(line, col, num):
    if column[col] == 0 and rup[line+col] == 0 and lup[line-col+num] == 0:
        return False
    return True


def queens(num=1, line=1):
    for col in range(1, num + 1):
        if not conflict(line, col, num):
            if line == num:
                yield (col,)
            else:
                column[col] = rup[line+col] = lup[line-col+num] = 1
                for result in queens(num, line + 1):
                    yield (col,) + result
                column[col] = rup[line+col] = lup[line-col+num] = 0

if __name__ == "__main__":
    number = 8
    column = [0] * (number + 1)
    rup = [0] * (2*number + 1)
    lup = [0] * (2*number + 1)
    print list(queens(number))

 

 使用记忆算法,不使用生成器:

# !/usr/bin/python
# coding:utf-8
# __author__=watson

number = 0
result = [0]
column = [0]
rup = [0]
lup = [0]
no = 0


def backtrack(line):
    if line > number:
        show_result()
    else:
        for col in range(1, number+1):
            if column[col] == 0 and rup[line+col] == 0 and lup[line-col+number] == 0:
                result[line] = col
                column[col] = rup[line+col] = lup[line-col+number] = 1
                backtrack(line + 1)
                column[col] = rup[line+col] = lup[line-col+number] = 0


def show_result():
    global no
    no += 1
    print "result no %r:" % no
    for i in range(1, number + 1):
        for j in range(1, number + 1):
            if result[i] == j:
                print " Q ",
            else:
                print " . ",
        print "\n"

if __name__ == "__main__":
    number = 8
    result = [0] * (number + 1)
    column = [0] * (number + 1)
    rup = [0] * (2*number + 1)
    lup = [0] * (2*number + 1)
    # print column[number]
    backtrack(1)

 

 

上述算法都是递归算法,在皇后数多的都比较消耗内存。

独立解参考《八皇后问题独立解JAVA代码》:

http://kingxss.iteye.com/blog/2290026