Fork me on GitHub

N-Queens

Posted on

Description

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        matrix = [ ["." for j in range(n)] for i in range(n)]
        self.solution_list = []
        self.solve(matrix, 0)
        
        return self.solution_list
                        
    def solve(self, matrix, row):
        n = len(matrix)
        if row == n:
            ## Deep copy
            new_matrix = [ "" for i in range(n)]
            
            for i in range(n):
                for j in range(n):
                    new_matrix[i] += matrix[i][j]
            self.solution_list.append(new_matrix)
            return
        
        for col in range(n):
            if self.validate(matrix, row, col):
                matrix[row][col] = "Q"
                self.solve(matrix, row+1)
                matrix[row][col] = '.'

    
    def validate(self, matrix, row, col):
        lens = len(matrix)
        for i in range(lens):
            if matrix[row][i] == "Q":
                return False
            if matrix[i][col] == "Q":
                return False
        
        index = 1
        while row - index >= 0 and col - index >= 0:
            if matrix[row-index][col-index] == "Q":
                return False
            index += 1
            
        index = 1
        while row + index < lens and col + index < lens:
            if matrix[row+index][col+index] == "Q":
                return False
            index += 1
        
        index = 1
        while row + index < lens and col - index >= 0:
            if matrix[row+index][col-index] == "Q":
                return False
            index += 1
            
        index = 1
        while row - index < lens and col + index < lens:
            if matrix[row-index][col+index] == "Q":
                return False
            index += 1
        
        
        return True