3 ms·
Just to make the point more clear, solutions to the N-rook problem are in bijection with permutations of n. The bijection is that each element of the permutatio
by JulianWasTaken 14y ago
Just to make the point more clear, solutions to the N-rook problem are in bijection with permutations of n. The bijection is that each element of the permutation tells you what column that rook should go in (and it'd fairly easy to see why this works). E.g. the "trivial" solution given with rooks on the diagonal corresponds to the identity permutation (1 2 3 ... n) since that permutation puts rook i in column i.
- xiaoma 14y agoAuthor here: Thanks for adding some explanation! The All N-Rooks solution was much more interesting than the single N-Queens one, but it's not as easy to understand.
- arnarbi 14y agoI think JulianWasTaken is hinting that your solution is exactly a recursive solution to generate all permutations (google "recursively generate permutations"). This is because any N-rook solution is just a reordering of the columns of the trivial solution. It may be interesting for you to try to come up with a different solution, where the basic operation is to swap adjacent columns - and try to minimize the number of swaps.
- xiaoma 14y agoYes, the solution for any N is all permutations. I realized that the morning after writing the recursive algorithm I shared. It was pretty fun trying to come up with a recursive step to generate all queens for N, given all queens for N-1. Even now I can't say for sure that no such recursive step exists.