卖萌的弱渣

I am stupid, I am hungry.

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

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

There exist two distinct solutions to the 4-queens puzzle:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

Solution

  • Judge if two elements (a,b) and (i,j) are in the diagnoal of the array. b-a == j-i or a+b == i+j
(N-Queens.py) download
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
66

class Solution:
    """
    Get all distinct N-Queen solutions
    @param n: The number of queens
    @return: All distinct solutions
    """
    def validPos(self,i,j,n,solution):
        if i == 0:
            return True
        row_index = 0
        for row in solution:
            col_index = row.find('Q')
            # same col
            if col_index == j:
                return False
            # diagonal
            if col_index-row_index == j-i or col_index+row_index == j+i:
                return False
            row_index += 1
        return True

    def recursiveNQ(self, result,solution,row,row_index,n):
        if n == row_index:
            tmp_sol =[]
            for i in solution:
                tmp_sol.append(i)
            result.append(tmp_sol)
            return

        for j in range(n):
            # check if <i,j> can be put Q
            if self.validPos(row_index,j,n,solution) == True:
                # create a new row
                row_new = ""
                for i in range(j):
                    row_new += "."
                row_new += "Q"
                for i in range(n-j-1):
                    row_new += "."
                solution.append(row_new)
                # check another line
                self.recursiveNQ(result,solution,row_new,row_index+1,n)
                solution.pop()

        return


    def solveNQueens(self, n):
        # write your code here
        if n < 1:
            return None
        if n == 1:
            return [['Q']]

        result = []
        solution = []
        # init solution
        row = ""
        for i in range(n):
            row += "."
        self.recursiveNQ(result,solution,row,0,n)
        return result

if __name__ == "__main__":
    sol = Solution()
    print(sol.solveNQueens(10))