52_N-Queens II

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 the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4

Output: 2

Explanation:
 There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

Solution: Backtracking

Idea:

• The idea is the same as in 51_N-Queens.

• The only difference is return the number of solution instead of all the solutions.

• Make sure output is a global variable to be updated in the helper function.

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        def helper(row):
            if row == n:
                # global output
                self.output += 1
                return
            for col in range(n):
                if all(abs(col-b) not in (0, row-a) 
                       for a, b in enumerate(col_index[ :row])):
                    col_index[row] = col
                    helper(row + 1)


        self.output = 0
        col_index = [0] * n
        helper(0)
        return self.output