13
\$\begingroup\$

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 & all_ones:
                current_bit = possible_slots & -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) << 1
                next_ld_bit = (ld | current_bit) >> 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.

\$\endgroup\$
9
+50
\$\begingroup\$

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:

>>> from timeit import timeit
>>> timeit(lambda:totalNQueens(13), number=1)
4.241301966001629
  1. Move the mask against all_ones out of the loop. That is, instead of:

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

    write:

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

    This saves about 6%:

    >>> timeit(lambda:totalNQueens(13), number=1)
    3.999626944991178
    
  2. 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) & all_ones
            while possible_slots:
                current_bit = possible_slots & -possible_slots
                possible_slots -= current_bit
                next_column_bit = column | current_bit
                next_rd_bit = (rd | current_bit) << 1
                next_ld_bit = (ld | current_bit) >> 1
                helper(next_ld_bit, next_column_bit, next_rd_bit)
    
        helper(0, 0, 0)
        return count
    

    This saves another 3% or so:

    >>> timeit(lambda:totalNQueens(13), number=1)
    3.8595934879995184
    
  3. 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) & all_ones
            while possible_slots:
                current_bit = possible_slots & -possible_slots
                possible_slots -= current_bit
                helper((ld | current_bit) >> 1,
                       column | current_bit,
                       (rd | current_bit) << 1)
    
        helper(0, 0, 0)
        return count
    

    This saves roughly another 4%:

    >>> timeit(lambda:totalNQueens(13), number=1)
    3.706758002997958
    

That's about 13% improvement in all.

\$\endgroup\$
5
\$\begingroup\$

What would you improve code-quality/readability wise?

Firstly, documentation. The existing comments help a bit, but mainly as aids to reverse engineering the meaning of the variables and the helper method. Three lines of documentation explaining the arguments and return value of helper would be a big improvement.

Secondly, the names.

  • I suspect that Solution and totalNQueens are imposed on you by the online judge, but if not then Solution is a remarkably uninformative name and I'd favour something like NQueens.totalSolutions(...).
  • n is perfectly reasonable, and all_ones is descriptive.
  • helper is informative enough given its scope.
  • ld and rd had me puzzled for a while until I figured out that they're probably short for left diagonal and right diagonal.
  • column misled me completely: I initially assumed it would range from 0 to n-1 and that you were filling in queens column-by-column rather than row-by-row.
  • count is a reasonable name, but I'm not sure why it's an argument rather than a local variable.
  • possible_slots sounds self-documenting, but what is a slot?
  • current_bit at least hints at the range of values, but what's the difference between bit and slot?
  • next_column_bit, next_rd_bit, and next_ld_bit all sound like they should have a single bit set, but actually they're more complicated masks.

I would favour names like column_mask, major_diag_mask, minor_diag_mask, possible_columns, selected_column.


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.

The standard approaches for counting distinct configurations are:

  1. Rather than counting configurations, generate them; then find a canonical representation and add that to a set.
  2. Ensure that you only generate the canonical representative of each equivalence class in the first place.
  3. Count them (generating if you must), but at the same time count symmetries, and record counts per symmetry. Then divide the count for each symmetry by the size of its symmetry group and sum.
  4. Run various counts, one per symmetry, and then account for the double-counting.

If we consider the last one, because I think it will require the least adaptation: what symmetries can a solution have? The square has eight symmetries:

AB  AC  BD  BA  CA  CD  DB  DC
CD  BD  AC  DC  DB  AB  CA  BA

However, a solution for n > 1 cannot have horizontal or vertical mirror symmetry, because that would require both that n be odd and that all queens be on the central column/row; it can't have diagonal symmetry, because that would require that all queens be on the same major or minor diagonal; so we're left with rotations. There are three possibilities: no rotational symmetry (so totalNQueens finds 8 equivalent solutions), rotational symmetry of order 2 (it finds 4 equivalent solutions), or rotational symmetry of order 4 (it finds 2 equivalent solutions).

It may be possible to argue further that for some sizes rotations are impossible; alternatively you could try to just assume that they are possible and count them. A relatively simple modification for the "just count" approach would require shifting everything left by n bits so that you can mark "future" diagonals as used and tracking both the current row and a mask of rows which already have their queen by symmetry.

\$\endgroup\$
  • \$\begingroup\$ Great review, thank you! I was actually subconsciously hoping for someone to mention symmetry! It appears that we can still use symmetry for odd squares as well, this is a good read on how to do it: liujoycec.github.io/2015/09/20/n_queens_symmetry. \$\endgroup\$ – alecxe Jun 14 '17 at 15:23
  • \$\begingroup\$ @alecxe, I think you're reading something into my comments about symmetry which I don't think is there. That blog post is about using something along the lines of the second standard approach I mentioned in order to speed up counting all solutions; my comments are about implementing the fourth standard approach in order to count distinct solutions. \$\endgroup\$ – Peter Taylor Jun 14 '17 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.