1 
# -*- coding: utf-8 -*-


def puzzle(rows, cols):
    if rows == 0:
        return [[]]
    else:
        return new_queen(rows - 1, cols, puzzle(rows - 1, cols))


def new_queen(new_row, cols, plsd_queens):
    new_solutions = []
    for solution in plsd_queens:
        for new_col in range(cols):
            if test(new_row, new_col, solution):
                new_solutions.append(solution + [new_col])
    return new_solutions


def test(new_row, new_col, solution):
    for row in range(new_row):
        if solution[row] == new_col or solution[row] + row == new_col + new_row or\
                                solution[row] - row == new_col - new_row:
            return False
    return True

Hello all! How can I find the unique solutions of this recursive algorithm of N-queens puzzle? It finds only all solutions: on board 8x8 it will be 92 solutions, but unique is only 12 (the other solutions are translations and mirrored from this 12)

4

1 に答える 1

0

これらは便利だと思います: link1 link2

最良の結果を得るには、動的プログラミングによってアルゴリズムを設計する必要があり、次の場所にあります: google Stackoverflow

配列 a[n][count] を設定し、状態 i を a[..][i] に保存します。これは n=8 による item first のサンプルです:

a = {5,1,8,4,2,7,3,6}{1} , .....

注：各ソリューションは、対称と回転によって8つの状態に変更できます。したがって、各結果について、対称と回転をチェックするソリューションは、配列に保存するかどうかです。

于 2013-03-03T15:01:13.143 に答える