cp's OEIS Frontend

A181500 Triangle read by rows: number of solutions of n queens problem for given n and given number of queens engaged in conflicts.

%I A181500 #20 Jan 01 2018 04:13:23
%S A181500 0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,10,0,0,0,0,0,0,0,0,0,4,0,0,28,0,0,0,0,
%T A181500 0,12,0,0,0,0,0,64,0,28,0,0,0,0,0,0,232,8,32,48,32
%N A181500 Triangle read by rows: number of solutions of n queens problem for given n and given number of queens engaged in conflicts.
%C A181500 Schlude and Specker investigate if it is possible to set n-1 non-attacking queens on an n X n toroidal chessboard. That is equivalent to searching for normal (i.e., non-toroidal) solutions of 3 engaged queens. In this case, one of the three queens has conflicts with both other queens. If you remove this queen, you get a setting of n-1 queens without conflicts, i.e., a toroidal solution.
%H A181500 M. Engelhardt, <a href="/A181500/b181500.txt">Rows n=0..16 of triangle, flattened</a>
%H A181500 Matthias Engelhardt, <a href="http://nqueens.de/sub/Conflicts.en.html">Conflicts in the n-queens problem</a>
%H A181500 Matthias Engelhardt, <a href="http://nqueens.de/sub/Conflicts.en.html">Conflict tables for the n-queens problem</a>
%H A181500 M. R. Engelhardt, <a href="http://dx.doi.org/10.1016/j.disc.2007.01.007">A group-based search for solutions of the n-queens problem</a>, Discr. Math., 307 (2007), 2535-2551.
%H A181500 Konrad Schlude and Ernst Specker, <a href="https://doi.org/10.3929/ethz-a-006666110">Zum Problem der Damen auf dem Torus</a>, Technical Report 412, Computer Science Department ETH Zurich, 2003.
%F A181500 Row sum = A000170 (number of n-queen placements).
%F A181500 Column 0 has same values as A007705 (torus n-queen solutions).
%F A181500 Columns 1 and 2 are always zero.
%F A181500 Column 3 counts solutions of the special "Schlude-Specker" situation.
%e A181500 Triangle begins:
%e A181500    0;
%e A181500    1, 0;
%e A181500    0, 0, 0;
%e A181500    0, 0, 0, 0;
%e A181500    0, 0, 0, 0, 2;
%e A181500   10, 0, 0, 0, 0, 0;
%e A181500    0, 0, 0, 0, 4, 0,  0;
%e A181500   28, 0, 0, 0, 0, 0, 12, 0;
%e A181500 ... - _Andrew Howroyd_, Dec 31 2017
%e A181500 For n=4, there are only the two solutions 2-4-1-3 and 3-1-4-2. For both solutions, all 4 queens are engaged in conflicts. So the terms for n=4 are 0 (0 solutions for n=4 having 0 engaged queens), 0, 0, 0 and 2 (the two cited above). These are members 11 to 15 of the sequence.
%Y A181500 Cf. A181499, A181501, A181502.
%K A181500 nonn,tabl
%O A181500 0,15
%A A181500 _Matthias Engelhardt_, Oct 30 2010
%E A181500 Offset corrected by _Andrew Howroyd_, Dec 31 2017