@@ -0,0 +1,2006 @@
+%60%60%60%0AGiven an integer n, return all distinct solutions to the n-queens puzzle.%0A%0AEach solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.%0A%0AFor example,%0AThere exist two distinct solutions to the 4-queens puzzle:%0A%0A%5B%0A %5B%22.Q..%22,  // Solution 1%0A  %22...Q%22,%0A  %22Q...%22,%0A  %22..Q.%22%5D,%0A%0A %5B%22..Q.%22,  // Solution 2%0A  %22Q...%22,%0A  %22...Q%22,%0A  %22.Q..%22%5D%0A%5D%0A%60%60%60%0A%0Aclass Solution:%0A    # @return a list of lists of string%0A    def solveNQueens(self, n):%0A        result = %5B%5D%0A        if n == 0: return result %0A        checklist = %5B-1 for i in xrange(n)%5D%0A        self.queen_helper(result, n, %5B%5D, checklist, 0)%0A        return result %0A    %0A    def check_helper(self, checklist, depth, i):%0A        for k in xrange(depth):%0A            if (checklist%5Bk%5D == i) or (abs(checklist%5Bk%5D-i) == depth-k):%0A                    return False%0A        return True %0A        %0A    def queen_helper(self, result, n, sublist, checklist, depth):%0A        if depth == n:%0A            result.append(sublist); return%0A        %0A        for i in xrange(n):%0A            if self.check_helper(checklist, depth, i):%0A                checklist%5Bdepth%5D = i%0A                s = '.'*n%0A                self.queen_helper(result, n, sublist + %5Bs%5B:i%5D+'Q'+s%5Bi+1:%5D%5D, checklist, depth + 1)%0A                %0A    def solveNQueens_1(self, n):%0A        def check(depth, j):%0A            for i in xrange(depth):%0A                #if board%5Bi%5D == j or abs(board%5Bi%5D-j) == abs(depth-i):%0A                if board%5Bi%5D == j:%0A                    return False%0A            return True        %0A            %0A        def dfs(depth, valuelist):%0A            if depth == n: result.append(valuelist); return%0A            for i in xrange(n):%0A                if check(depth, i):%0A                    board%5Bdepth%5D = i%0A                    s = '.' * n%0A                    dfs(depth+1, valuelist + %5Bs%5B:i%5D+'Q'+s%5Bi+1:%5D%5D)%0A            %0A        board = %5B-1 for i in xrange(n)%5D%0A        result = %5B%5D%0A        dfs(0,%5B%5D)%0A        return result%0A

Create N_Queens.py