2

The superqueen is a chess piece that can move not only like a queen, but also like a knight. What is the maximal number of superqueens on an $8 \times 8$ chessboard such that no one can capture any other?

Additional information: Of course at most $8$, but it can be checked that every solution of the $8$-queens puzzle contains two queens that can capture each other by a knight move, so at most $7$. I can place $6$ of them. I am aware of the fact that on a $10 \times 10$ board, one can put $10$ of them.

Cookie
  • 13,532
Daniel Soltész
  • 206
  • If there is such an 7-queens solution, it can't be found by deleting one queen from a traditional 8-queen solution: all of the 12 fundamental solutions of the 8-queens puzzle ( http://en.wikipedia.org/wiki/Eight_queens_puzzle#Solutions ) involve multiple independent pairs of queens a knight's move from each other. This doesn't answer the question, of course, because there are 7-queen partial solutions of the traditional problem that can't be extended to an 8-queen solution. It shouldn't take long to check all of them with a standard branch-and-bound search, though. – Steven Stadnicki Sep 10 '14 at 18:19
  • Have you tried computer search? Finding ordinary queen arrangements on an 8x8 board with no attack is an undergraduate coding exercise. – almagest Sep 10 '14 at 18:37

2 Answers2

2

Nice question. If I programmed it right one cannot quite get 7. There are dozens of ways to put 7 "superqueens" (a.k.a. Amazons) on the board so that there's only one attacking pair, e.g. a5,b3,d6,e7,f1,g4,h8 with one B-attack or a2,c7,d4,e1,f8,g5,h3 with one N-attack. I looked only for configurations with no R-attacks; such a configuration can be represented by a permutation of the numbers from 1 to 8 with one number missing. None of the one-off configurations fits into a $7 \times 8$ board, though it might be possible to do that with two "superqueens" on the same rank or file and no other attacking pairs.

Here is the gp code. "k" is the empty column, which can be assumed to be 1, 2, 3, or 4 by symmetry.

Q(x1,y1,x2,y2) = ((x1-x2)^2 + (y1-y2)^2 == 5) || (abs(x1-x2) == abs(y1-y2))
\\ true iff (x1,y1) is a N- or B-move from (x2,y2)

{
for(n=1,8!,
  a = numtoperm(8,n);
  for(k=1,4,
    s = sum(i=1,7,sum(j=i+1,8, (i!=k) && (j!=k) && Q(i,a[i],j,a[j])));
    if(s==0, print(k,a));
  )
)
}

The output is empty. Changing "s==0" to "s==1" yields 172 solutions, including

2[5, 2, 3, 6, 7, 1, 4, 8]
2[2, 6, 7, 4, 1, 8, 5, 3]

which correspond to the B- and N-attack examples respectively.

P.S. Extending this calculation to a $9 \times 9$ board finds that 9 "superqueens" still cannot be accommodated, but there's a unique permutation (up to the 8 board symmetries) that fails at only one pair. I do not exhibit this configuration here because finding it might make for a fun puzzle. There's a number of nonattacking configurations of 8 superqueens on this board; alas none has any symmetry, nor does any fit in an $8 \times 9$ rectangle $-$ indeed only one (up to symmetry) omits the second column. I leave this last as a puzzle as well.

Noam D. Elkies
  • 25,917
  • 1
  • 64
  • 82
1

See http://oeis.org/A133143 or my book http://problem64.beda.cz/silo/kotesovec_non_attacking_chess_pieces_2013_6ed.pdf, page 751-752.

Vaclav Kotesovec
  • 145