8 Queens Puzzle++
Yesterday I wrote about a Python solution to the 8 Queens puzzle.
n = 8
sqs = range(n)
Qs = (Q for Q in itertools.permutations(sqs)
if n == len({Q[i]+i for i in sqs})
== len({Q[i]-i for i in sqs}))
It’s possible to reproduce this strategy in C++:
- range(n) → std::iota
- itertools.permutations → std::next_permutation
- set comprehension → set insertion
The std::next_permutation algorithm stands alone in the C++ standard library. Used here, it pairs well with the similarly uncommon do ... while loop. The solution depends on the vector sqs starting off in sorted order, and by the end of the loop the vector will have been returned to this state.
Articles