A383738 Number of solutions to the n-queens puzzle in a n X n board that are not square root permutations of {n-1,...,2,1,0}.

0, 0, 0, 0, 8, 4, 40, 92, 352, 724, 2680, 14192, 73704, 365596, 2279184, 14772448, 95814976, 666090624, 4968057848, 39029188404, 314666222008, 2691008701644, 24233937684440, 227514171970408, 2207893435805088, 22317699616364044, 234907967154122528

Offset: 1

Author

Darío Clavijo, May 07 2025

Keywords

• nonn

Comments

Each solution to the n-queens problem can be represented as a permutation of {0,1,2,...,n-1}.

Conversely, the number of solutions to the n-queens puzzle in a n X n board that are also square root permutations of {n-1,...,2,1,0} is A033148.

a(n) is always even because every solution to the puzzle has its own reflection in the horizontal axis, e.g., {0,2,4,1,3} and {3,1,4,2,0}.

Examples

			For n = 5, we have:
     0 1 2 3 4      0 1 2 3 4      0 1 2 3 4      0 1 2 3 4      0 1 2 3 4
   +-----------+  +-----------+  +-----------+  +-----------+  +-----------+
 0 | Q         |  | Q         |  |   Q       |  |   Q       |  |     Q     |
 1 |     Q     |  |       Q   |  |       Q   |  |         Q |  | Q         |
 2 |         Q |  |   Q       |  | Q         |  |     Q     |  |       Q   |
 3 |   Q       |  |         Q |  |     Q     |  | Q      Q  |  |   Q       |
 4 |      Q    |  |     Q     |  |         Q |  |           |  |         Q |
   +-----------+  +-----------+  +-----------+  +-----------+  +-----------+
     0,2,4,1,3      0,3,1,4,2      1,3,0,2,4      1,4,2,0,3      2,0,3,1,4
is sqrt perm: no             no           no            yes              no
     0 1 2 3 4      0 1 2 3 4      0 1 2 3 4      0 1 2 3 4      0 1 2 3 4
   +-----------+  +-----------+  +-----------+  +-----------+  +-----------+
 0 |     Q     |  |       Q   |  |       Q   |  |         Q |  |         Q |
 1 |         Q |  | Q         |  |   Q       |  |   Q       |  |     Q     |
 2 |   Q       |  |     Q     |  |         Q |  |       Q   |  | Q         |
 3 |       Q   |  |         Q |  |     Q     |  | Q         |  |       Q   |
 4 | Q         |  |   Q       |  | Q         |  |     Q     |  |   Q       |
   +-----------+  +-----------+  +-----------+  +-----------+  +-----------+
    2,4,1,3,0      3,0,2,4,1       3,1,4,2,0      4,1,3,0,2      4,2,0,3,1
is sqrt perm: no            yes           no            no              no
In total there are 10 solutions for a 5 X 5 board with 5 queens, of which 8 are not square root permutations of {n-1,...,2,1,0}.
Then, a(5) = 10.
		

Links

• Darío Clavijo, Python program, Github.
• Mathematics Stack Exchange, How to find the square root of a permutation
• Wikipedia, Eight queens puzzle

Crossrefs

Cf. A000170, A033148.

Formula

a(n) = A000170(n) - A033148(n).