n皇后问题

[编程题]n皇后问题

热度指数：8417 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知正整数n，即在一个nxn的棋盘上放置n个棋子，使每行每列和每条对角线上都只有一个棋子，返回有多少种摆法方法。保证n小于等于15。

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

Python

张淮

# -*- coding:utf-8 -*-
class Queens:
    def nQueens(self, n):
        # write code here
        self.count=0
        self.a=[0 for i in range(n+1)]
        self.Queens1(1,n)
        return self.count
    def Queens1(self,i,n):
        if i>n:
            self.count+=1
            return ;
        for j in range(1,n+1):
            self.a[i]=j
            if self.Place(i):
                self.Queens1(i+1,n)
    def Place(self,i):
        for j in range(1,i):
            if self.a[j]==self.a[i] or self.a[j]-self.a[i]==j-i or self.a[j]-self.a[i]==i-j:
                return 0
        return 1

发表于 2017-07-14 14:28:30 回复(1)

Python

Yannyezixin

回溯法解8皇后问题：从一条路往前走，能进则进，不能进则退回来，换条路再试

# -*- coding:utf-8 -*-
class Queens:
    def nQueens(self, n):
        result = [0] * n
        results = []
        n_row = 0
        while n_row < n:
            pos = self.findLegalPosition(result, n_row, n)
            # print pos
            if pos is not None:
                result[n_row] = pos
                if n_row == n - 1:
                    results.append(result[:])

            if pos is None or n_row == n - 1:
                while 1:
                    n_row -= 1
                    if n_row < 0:
                        print results
                        return len(results)

                    pos = self.findLegalPosition(result, n_row, n, back_tracing=True)
                    if pos:
                        result[n_row] = pos
                        break
            n_row += 1

    def findLegalPosition(self, arr, n_row, n, back_tracing=False):
        start = 0
        if back_tracing:
            start = arr[n_row] + 1
        for col in range(start, n):
            ok = True
            for row in range(n_row):
                if arr[row] == col:
                    ok = False
                    break
                if n_row - row == abs(col - arr[row]):
                    ok = False
                    break
            if ok:
                return col
        return None

PS：由于Python语言本身的原因和题目的AC时间限制，该题目解法是正确的但是超时

发表于 2016-08-07 13:10:14 回复(0)