N-Queens II

Problem: N-Queens II

This problem is similar to N-Queens. The difference lies in that we only need to know number of solutions. So once we use backtracking to achieve a solution, we add 1 to the number.

Code in Python:

class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.ans = 0
        def addQueen(placed):
            length = len(placed)
            for i in xrange(n):
                canPlace = True
                for pos, num in enumerate(placed):
                    if num == i or num-i == length-pos or i-num == length-pos:
                        canPlace = False
                        break
                if canPlace and length == n-1: self.ans += 1
                elif canPlace: addQueen(placed+[i])
        addQueen([])
        return self.ans