N-Queens

Problem: N-Queens

The rule of the queen in chess is that it can attacks horizontally, vertically and diagonal. To the matrix, queen at [i,j] can attack all the element with row number equals i, column number equals j, sum of row and column number equals i+j and diff of row minus column number equals i-j. We can use this property to recursively solve this problem. That is, we can try with every position on a certain row, and discuss possibilities of following rows.

To simplify this problem, we can use an array of integers to represent solutions. For example, [3,1,4,2] means the queen is placed at 3rd position on the first row, etc..

Code in Python:

class Solution(object):
    def solveNQueens(self, n):
        def DFS(queens, xy_dif, xy_sum):
            p = len(queens)
            if p==n:
                result.append(queens)
                return None
            for q in range(n):
                if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                    DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
        result = []
        DFS([],[],[])
        return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

In this situation, we use result to store all solutions. List queens represent single solution, and xy_diff and xy_sum stores sums and difference to avoid conflicts. Note that in python, using '+' to concatenate lists creates new lists, not like append operation modifies the original list referred to.