三种不同算法求解八皇后问题：排列组合、回溯法+递归、生成器+递归

知道同学

排列组合确实慢

Jensona

牛逼嗷

你在说些什么

学习学习

为之奈何

想知道

java2python

学习

java2python

达人的代码太精简了，里面的yield就不懂，用了他的conflict函数，写了一个非递归的：

def conflict(cur_row, row_ptr):
        for i in range(cur_row):
                if abs(row_ptr[i] - row_ptr[cur_row]) in (0, cur_row - i):
                        return True
        return False

def solve(QUEEN_SUM):
    row_ptr = [0]*QUEEN_SUM
    cur_row = 0
    while(True) :
        while(row_ptr[cur_row] == QUEEN_SUM or conflict(cur_row,row_ptr)):
            if(row_ptr[cur_row] == QUEEN_SUM):
                cur_row -= 1
            if(cur_row < 0 ):
                return
            row_ptr[cur_row] += 1
        if(cur_row ==QUEEN_SUM-1) :
            chest = [[0]*QUEEN_SUM for i in range(QUEEN_SUM)]
            for i in range(QUEEN_SUM):
                    chest[i][row_ptr[i]] = 1
                    print (chest[i])
            print ()
            row_ptr[cur_row] += 1
        else:
            cur_row += 1
            row_ptr[cur_row] = 0

solve(8)

yield看了网上的知识，还是半懂不懂，有点超出理解范围，做了一个没有yield的版本，对比代码，总算大致知道意思，yield是同一层的结果扔到turple后再return：

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 = 3, state = (),cfloor=0):
    res = None        #这里要res要初始化
    for pos in range(num):
        if not conflict(state, pos):
            #if len(state) == num - 1:
            #        yield (pos,)
            if len(state) == num - 1:
                return ((pos,),)
            else:
                #for result in queens(num, state + (pos,)):
                #        yield (pos,) + result
                result = queens(num, state + (pos,),cfloor+1)
                if result == None:       #这里要None判别
                    continue
                for ren in result:
                    if res == None:      #这里要None判别
                        res = (((pos,) + ren),)
                    else:
                        res =  (((pos,) + ren),) + res
    return res
c = 0
result = queens(6,(),0)
for res in result:
        c+=1
        print ('Solution %d: ' % c)
        chest = [[0]*len(res) for i in range(len(res))]
        for i in range(len(res)):
                chest[i][res[i]] = 1
                print (chest[i])
        print ()        

java2python

八皇后全排列做法（一共是16777216组合，如果找到第一个布局就跳出，就10秒，全部的话3分多钟）：

pows = [pow(8,0),pow(8,1),pow(8,2),pow(8,3),pow(8,4),pow(8,5),pow(8,6),pow(8,7),pow(8,8)]

def check(rows):
    for row in range(1,8):
        for i in range(row):
            if abs(rows[i] - rows[row]) in (0, row - i):
                return True
    return False

rows = [0]*8
for sts in range(0,pow(8,8)):
    for bit in range(0,8):
        rows[bit]=(sts%pows[bit+1])//pows[bit]
    if check(rows) == False:
        chest = [[0]*8 for i in range(8)]
        for i in range(8):
            chest[i][rows[i]] = 1
            print (chest[i])
        print ()
        #break

当然全排列太慢了，不过可以稍作改进，就和快速搜索是一样速度了（当然每一位用pows取余数再除，会多一点时间，不过没有数量级的区别）,就是检测局面的时候，哪一行出问题（check函数返回true，false改为行号，如果是0，就是原来的false），那么就直接进入这一行的下一个选项（这一行已经出问题，后面的排列搜索全是无用功，实际逻辑和快速搜索一样，不过全排列的程序是最容易理解的）：

pows = [pow(8,8),pow(8,7),pow(8,6),pow(8,5),pow(8,4),pow(8,3),pow(8,2),pow(8,1),pow(8,0)]

def check(rows):
    for row in range(1,8):
        for i in range(row):
            if abs(rows[i] - rows[row]) in (0, row - i):
                return row
    return 0

rows = [0]*8
sts = 0
while sts < pow(8,8):
    for bit in range(0,8):
        rows[bit]=(sts%pows[bit])//pows[bit+1]
    err_row = check(rows)
    if err_row == 0:
        chest = [[0]*8 for i in range(8)]
        for i in range(8):
            chest[i][rows[i]] = 1
            print (chest[i])
        print ()
        sts += 1
    else:
        sts += pows[err_row+1]

口木呆

那份开始开始疯狂

zjc999

随宇

嗷嗷嗷

罗密欧与梁山伯

谢谢

2002122

要看

Minecraft程序猿

3255536441

666

sjh110

666

DefSw0rd

布耶特呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃呃

山有扶苏|溪潺

1