4
$\begingroup$

How many queens can be placed in a standard $8*8$ chessboard to threat each of them exactly once by other queens?

$\endgroup$
  • 2
    $\begingroup$ Are other pieces allow on the board? $\endgroup$ – d'alar'cop Oct 11 '14 at 8:01
  • $\begingroup$ I might come up with a proper proof about those limits btw $\endgroup$ – d'alar'cop Oct 11 '14 at 12:49
  • $\begingroup$ that would be nice :) $\endgroup$ – Rafe Oct 11 '14 at 16:03
6
$\begingroup$

I found a 10 queen answer. I realized that d'alar'cop's reasoning was slightly off, because threatening is part of the puzzle, so 8 wasn't necessarily a limit. With the 8 inner queens in this position, you can put the final 2 queens in any 2 corners.

10 Queens

Update: I have a proof for a maximum of 10 queens.

Given that 2 queens in a row or a column use 1x2 and 2 queens diagonally use 2x2, it is advantageous to avoid the diagonals.

Put 2 queens in a row. You have now used up 1 row and 2 columns.
Do this again. 2 rows, 4 columns.
Again. 3 rows, 6 columns.
If you do it a 4th time, you will have used all 8 columns, so don't.
Put 2 queens in a column. 5 rows, 7 columns.
Do this again. 7 rows, 8 columns.

You can no longer add any queens, as your columns are used up.
Repeat swapping columns and rows and you end up with 8 rows and 7 columns, so you still cannot add any queens.

Any attempts at using diagonals simply make the problem end faster (exception: a single diagonal, like my displayed answer, gets you to 8 rows, 8 columns).

Therefore, 10 queens is the maximum.

Now as for allowing other pieces, I noticed that there might be extra space from d'alar'cop's 24 queens answer, and I was able to get 2 more queens in.

26 Queens

$\endgroup$
  • $\begingroup$ Nicely done. As expected all the columns and rows are occupied $\endgroup$ – d'alar'cop Oct 12 '14 at 3:12
  • $\begingroup$ awesome! I have been convinced that 8 is a limit :D thanks $\endgroup$ – Rafe Oct 12 '14 at 6:59
7
$\begingroup$

A queen cannot have a paired queen on the same column if it also has one on the same row. So, queens will pair up every other row and every other column. This will yield 8 queens. There are many configurations (100s probably). Here is one example:

enter image description here

The question didn't strictly state if this matters, but I believe this is a maximum.

If other pieces are allowed, then other pawns can be used to block queens from each other. 24 queens can be placed on the board in this case.

enter image description here

$\endgroup$
  • $\begingroup$ Note that the original where this question comes from (how many queens can you place on a n*n board without any threatening another, without other pieces) also has n as solution. There's probably a paper worth of logic behind it, but it makes sense. $\endgroup$ – Mast Oct 11 '14 at 13:13
  • $\begingroup$ @Mast I thought that would be easier to prove. Because you can use the pigeon-hole-pricinple. With more than 8 queens, you'd have one row or column with 2 or more queens - i.e. threatening. $\endgroup$ – d'alar'cop Oct 11 '14 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.