我们可以解决N皇后没有回溯？以及如何计算，哪些将是回溯解决方案的复杂性？ [英] Can we solve N Queens without backtracking? and How to calculate and what will be the complexity of the backtracking solution?

问题描述

我试图解决这个问题回溯，并打印所有可能的解决方案。

I have tried solving this problem with backtracking and it prints all possible solutions.

两个问题上来：

1 我可以实现N使用其他技术的女王？

2 是否有可能作出以下打印code只有第一个解决方案，然后终止？

我目前的code采用回溯：

My current code uses backtracking:

n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
        if k == n-1:
            print "SOLUTION", x
        else:
            nqueen(k+1)

nqueen(0)

注意：我感兴趣的技术，不依赖于特定的编程语言

Note: I am interested in techniques that do not depend on a particular programming language.

推荐答案

根据维基百科，您可以使用启发式做的：

According to Wikipedia, you can do using heuristics:

此启发式解决N后的任意n≥4，形成了皇后与水平位置（列）仅仅增加了垂直位置（行）号码列表。 N是8八皇后问题。

This heuristic solves N queens for any N ≥ 4. It forms the list of numbers for vertical positions (rows) of queens with horizontal position (column) simply increasing. N is 8 for eight queens puzzle.

1. 如果除以N的6余数不为2或3，那么列表只是所有偶数然后是所有奇数＆le; N
2. 否则，写奇数和偶数号码的名单（即2,4,6,8 - 1,3,5,7）
3. 如果余数为2，交换1和3在奇列表中并移动5到端（即3,1,7,5）
4. 如果余数为3，移动2至甚至列表的末端和1,3-到的奇列表中的端部（即4,6,8,2 - 5,7,9,1,3）
5. 附加奇列表中由这些数字给定的行中的偶数列表和地点王后，从左至右（即A2，B4，C6，D8，E3中，f1，G7，H5）

这启发是 O（N），因为它只是打印一些如果语句后的结果。

This heuristics is O(n) since it's just printing the result after some if statements.

关于你提到的第二个问题：是否有可能作出以下code只打印第一个解决方案，然后终止

Regarding your second question: "Is it possible to make code below to print only first solution and then terminate?"

您只需调用 sys.exit（0）打印后：

import sys
n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
            if k == n-1:
                print "SOLUTION", x
                sys.exit(0)
            else:
                nqueen(k+1)

nqueen(0)

，或者你可以返回一个值，然后传播的价值，如果它表示终止：

or, alternatively you can return a value and then propagate the value if it indicates termination:

n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
            if k == n-1:
                print "SOLUTION", x
                return True # Found a solution, send this good news!
            else:
                if nqueen(k+1): # Good news!
                    return True # Share the good news to parent!
    return False # We have searched every possible combinations, and I regret to tell you that I could not find any solution.

nqueen(0)

对于时间复杂度，因为它是一个完整的搜索，它的ñ^ N 。虽然由于修剪（使用安全（K，I），在实践中是快了很多。

As for the time complexity, since it's a complete search, it's n^n. Although due to the pruning (using safe(k,i), in practice it's a lot faster.

这篇关于我们可以解决N皇后没有回溯？以及如何计算，哪些将是回溯解决方案的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！