N皇后問題(python実装)

N皇后問題
n皇后問題はn個の皇后をn*nの碁盤に置くことであり,皇后同士が互いに攻撃することはできない.
整数nを与え,すべての異なるn皇后問題の解決策を返す.
各ソリューションは、「Q」および「.」の明確なn皇后配置レイアウトを含む.それぞれ女王と空の位置を表す.
サンプル
4クイーンズの問題には2つの解決策があります.

[

[".Q..", // Solution 1

 "...Q",

 "Q...",

 "..Q."],

["..Q.", // Solution 2

 "Q...",

 "...Q",

 ".Q.."]

 ]

構想
各行に1つの皇后しかないため、最初の行にはN種類の可能性があり、1行1列から1行1列が皇后を置くことができる場合は、次の行の最初の皇后を置くことができる列を見つけることができます.次の行に条件を満たす列がない場合は、前の行に戻って、皇后を配置できる次の列を見つけます.遍歴した行数==Nは1回の結果を得る.最初の行にも皇后を置く列が見つからない場合は検索が終了します.
インプリメンテーション
ループ実装

class Solution:
    """
    Get all distinct N-Queen solutions
    @param n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        # write your code here
        #                        
        n = int(n)
        result = []
        col = [-1]*n
        k = 0
        #row
        while k>=0:
            #         
            col[k] = col[k]+1
            while col[k]and not self.judgePlace(k,col):
                #col
                col[k] += 1
            if col[k]#     
                if k == n-1:
                    empty = ['.'*n for i in range(0,n)]
                    for i in range(0,n):
                        temp = list(empty[i])
                        temp[col[i]] = 'Q'
                        empty[i] = ''.join(temp)
                    result.append(empty)
                #     
                else:
                    k +=1
                    #      
                    col[k] = -1
            #                
            else:
                k -= 1


        return result

    def judgePlace(self,k,col):
        for i in range(0,k):
            if col[i] == col[k] or (abs(col[k]-col[i]) == abs(k - i)):
                return False
        return True

再帰的な実装

class Solution:
    """
    Get all distinct N-Queen solutions
    @param n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        n = int(n)
        result = []
        record = [0]*(n+1)
        self.findResult(result,n,1,1,record)
        return result


    def findResult(self,result,total,row,col,record):
        if row == 0:
            return result
        record[row] = col
        while record[row]<=total and not self.judgePlace(row,record):
            record[row] += 1
        #      
        if record[row]>total:
            row -= 1
            newCol = record[row] + 1
            self.findResult(result,total,row,newCol,record)
        else:
            if row == total:
                empty = ['.'*total for i in range(0,total)]
                for i in range(0,total):
                    temp = list(empty[i])
                    temp[record[i+1]-1] = 'Q'
                    empty[i] = ''.join(temp)
                result.append(empty)
                #  
                row -= 1
                newCol = record[row] + 1
                self.findResult(result,total,row,newCol,record)
            else:
                row += 1
                self.findResult(result,total,row,1,record)



    def judgePlace(self,row,col):
        for i in range(1,row):
            if col[i] == col[row] or (abs(col[row]-col[i]) == abs(row - i)):
                return False
        return True