Problem statement

https://binarysearch.com/problems/Valid-N-Queens/

Solution

For each column, row and two types of diagonal check queens on them.

Complexity

It is O(n^2) for time and O(1) for space.

Code

class Solution:
    def solve(self, M):
        n = len(M)
        c0, c1, c2, c3 = 0, 0, 0, 0
        for i, j in product(range(n), range(n)):
            if M[i][j] == 1:
                if c0 & 1<<i or c1 & 1<<j or c2 & 1<<i-j+n or c3 & 1<<i+j: return False
                c0 ^= 1<<i
                c1 ^= 1<<j
                c2 ^= 1<<i-j+n
                c3 ^= 1<<i+j

        return c0 + 1 == 1 << n