N-Queens, bitwise approach I've recently solved the famous N-Queens problem:


  Can you place \$N\$ chess queens on a \$N × N\$ board in such a way that no one
  attacks another queen?


The idea here is based on the ideas from several blogposts describing a bitwise approach - approaching the board row by row, keeping track of bits of 3 numbers - columns, major and minor diagonals:

class Solution(object):
    def totalNQueens(self, n):
        all_ones = 2 ** n - 1

        def helper(ld, column, rd, count=0):
            if column == all_ones:  # filled out all vacant positions
                return 1

            possible_slots = ~(ld | column | rd)  # mark possible vacant slots as 1s
            while possible_slots &amp; all_ones:
                current_bit = possible_slots &amp; -possible_slots  # get first 1 from the right
                possible_slots -= current_bit  # occupy a slot

                # mark conflicts in the next row
                next_column_bit = column | current_bit
                next_rd_bit = (rd | current_bit) &lt;&lt; 1
                next_ld_bit = (ld | current_bit) &gt;&gt; 1

                count += helper(next_ld_bit, next_column_bit, next_rd_bit)
            return count

        return helper(0, 0, 0)


The solution was accepted by the LeetCode OJ and actually beats 98.97% of Python solutions. But, can we optimize it even further? What would you improve code-quality/readability wise?

Another follow-up concern is that I don't see an easy way for this problem to instead of counting possible board arrangements, collect all possible distinct board configurations.
Micro-optimizing Python is a bit of a quixotic endeavour — if you wanted the fastest possible performance then you wouldn't be using Python. But so long as we understand the nature of the exercise, then it's just a matter of trying lots of changes and measuring the results to see which ones are improvements:

Here's the baseline measurement for comparison with the improvements:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:totalNQueens(13), number=1)
4.241301966001629



Move the mask against all_ones out of the loop. That is, instead of:

possible_slots = ~(ld | column | rd)
while possible_slots &amp; all_ones:


write:

possible_slots = ~(ld | column | rd) &amp; all_ones
while possible_slots:


This saves about 6%:

&gt;&gt;&gt; timeit(lambda:totalNQueens(13), number=1)
3.999626944991178

Accumulate count via a variable local to totalNQueens instead of returning it from helper:

def totalNQueens(n):
    all_ones = 2 ** n - 1
    count = 0

    def helper(ld, column, rd):
        nonlocal count
        if column == all_ones:
            count += 1
            return
        possible_slots = ~(ld | column | rd) &amp; all_ones
        while possible_slots:
            current_bit = possible_slots &amp; -possible_slots
            possible_slots -= current_bit
            next_column_bit = column | current_bit
            next_rd_bit = (rd | current_bit) &lt;&lt; 1
            next_ld_bit = (ld | current_bit) &gt;&gt; 1
            helper(next_ld_bit, next_column_bit, next_rd_bit)

    helper(0, 0, 0)
    return count


This saves another 3% or so:

&gt;&gt;&gt; timeit(lambda:totalNQueens(13), number=1)
3.8595934879995184

Avoid the local variables next_column_bit and so on:

def totalNQueens(n):
    all_ones = 2 ** n - 1
    count = 0

    def helper(ld, column, rd):
        nonlocal count
        if column == all_ones:
            count += 1
            return
        possible_slots = ~(ld | column | rd) &amp; all_ones
        while possible_slots:
            current_bit = possible_slots &amp; -possible_slots
            possible_slots -= current_bit
            helper((ld | current_bit) &gt;&gt; 1,
                   column | current_bit,
                   (rd | current_bit) &lt;&lt; 1)

    helper(0, 0, 0)
    return count


This saves roughly another 4%:

&gt;&gt;&gt; timeit(lambda:totalNQueens(13), number=1)
3.706758002997958



That's about 13% improvement in all.