I think it's very difficult for python to get Accepted.


  • 1
    H

    I get TLE in "Last executed input: 7"

    class Solution:
    n = 0
    def __init__(self):
        self.n = 0
        
    def dfs(self, step, h, x1, x2):
        if step == 0:
            return 1
        k = h | x1 | x2
        ans = 0
        for i in xrange(self.n):
            if (k & (1 << i)) == 0:
                ans += self.dfs(step - 1, h | k, (x1 | k) >> 1, (x2 | k) << 1)
        return ans
            
        
    # @return an integer
    def totalNQueens(self, n):
        self.n = n
        return self.dfs(n, 0, 0, 0)

  • 0
    U

    The same bit manipulation algorithm in previous discussion can be easily ported to python and runs quite fast (184 ms).


  • 0
    H

    Can I give me the link or show me your code? I really don't know how to solve it.


  • 0
    U

    Here it is:

    class Solution:
        ans, limit = 0, 0
        # @return an integer
        def totalNQueens(self, n):
            self.ans = 0
            self.limit = (1<<n) - 1
            self.dfs(0, 0, 0)
            return self.ans
        
        def dfs(self, h, r, l):
            if h == self.limit:
                self.ans += 1
                return
            pos = self.limit & (~(h|r|l))
            while pos:
                p = pos & (-pos)    #return most right bit 1
                pos -= p
                self.dfs(h+p, (r+p)<<1, (l+p)>>1)   #no shift needed for h, left shift for anti diagonal

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.