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
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
n is perfectly reasonable, and
all_ones is descriptive.
helper is informative enough given its scope.
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
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
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
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:
- Rather than counting configurations, generate them; then find a canonical representation and add that to a
- Ensure that you only generate the canonical representative of each equivalence class in the first place.
- 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.
- 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.