-4

n クイーンの Python でプログラムに問題があります (nxn ボードに n クイーンを配置する方法はいくつありますか)。私の再帰に問題があるようですが、私は本当に無力です。誰かが何が悪いのか理解できますか？

def queens(N):

    ''' how many ways to place n queens on an NXN board? '''

    partial = []    # list representing partial placement of queens on the left columns
    return queens_rec(N,partial)

def queens_rec(N, partial):
    '''Given a partial solution to the n-Queens Problem ,
        return the number of options to place the rest of the queens.
        Recursively, in the end we will get the number of the options for
        the whole NxN board'''

    if len(partial)==N:
        return 1

    total = 0 #total of full solutions found
    row = 0

    while row<N:
        if isUnderAttack(partial,N,row)==False: #means it is not under Attack
            partial+=[row]

            total=total+queens_rec(N, partial)

            row+=1
            current = len(partial)

            partial = partial[0:current-1]

        else:
            row+=1

    return total

def isUnderAttack(partial, N, newRow):
    '''Checking if we can add a queen in row newRow, to the next column'''

    newCol = len(partial)

    for col in range(newCol): #not inculding newCol, checking all the previous columns
        oldRow = partial[col]


        #Checking horizontal attack from existing queen:
        if (newRow == oldRow):

            return True

        if (newCol - col == newRow - oldRow):

            return True

        if (newCol - col == oldRow - newRow):

            return True        

    return False
4

1 に答える 1

0

あなたが書いた：

            partial+=[row]
            ...
            partial = partial[0:current-1]

最初のコマンドは、リストのパーシャルをその場で変更します。2 つ目はコピーを作成し、元の配列はそのままにします。

あなたは書くべきです：

partial.append(row) # this is equivalent to:  partial += [row]
...
partial.pop() # modifes list in place
于 2013-12-21T18:16:31.670 に答える