# A chessboard problem

• Sep 8th 2012, 01:24 PM
wuzhe
A chessboard problem
I already posted this on a different forum, but since this is a very special problem, I will shared it here as play first post :)

The problem is: you are given a 20x20 chessboard, you are going to place as many queens as possible using the following rules:
You may place and only queens
each queen may attack maximum one other queen

The point system worked as: for the first twenty queens, you get 0 points, then for each queen you place, you get five points. And yes, you try to get as many points as possible.

For the question maker, they did have something more than 20...

Enjoy!
• Sep 9th 2012, 12:30 AM
Vlasev
Re: A chessboard problem
I was able to successfully place 27 queens. I wonder what the maximum is!
• Sep 9th 2012, 07:19 AM
wuzhe
Re: A chessboard problem
mmm, is it possible for you to post the solution you had? because the answer they gave is less than that :o
• Sep 9th 2012, 09:04 AM
Vlasev
Re: A chessboard problem
This is wrong because I thought it was rooks, not queens for some reason!

Actually, my solution has 26 queens haha. You place queens like

$\begin{bmatrix}1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1\end{bmatrix}$

to get 4 queens out of a 3 by 3 square. You place these along the diagonal (you can place 6 of these) and you are left with a 2 by 2 square. You can put 2 queens there, to get a total of 26. All the rest of the squares are either occupied or will be attacked by a queen which attacks another queen, so I cannot put more than that with this solution.
• Sep 9th 2012, 09:58 AM
wuzhe
Re: A chessboard problem
the queen can only attack 1 other maximum, not 2 :p, the queen at the first row second column attacks both first row first column and second row third column, that is attacking 2 other queens :p
and by the way, i think you might have not realized queens move in diagonals as well..
• Sep 9th 2012, 02:36 PM
Vlasev
Re: A chessboard problem
You are absolutely right, haha. I thought the problem involved rooks, not queens for some reason. I'll have to try it with actual queens now!
• Nov 22nd 2012, 03:13 PM
Stephen347
Re: A chessboard problem
The best I can get is 22, totalling 10 points. I'd be interested to see the solution with 27.
• Nov 22nd 2012, 03:23 PM
Stephen347
Re: A chessboard problem
Actually, 26.
• Nov 22nd 2012, 04:26 PM
wuzhe
Re: A chessboard problem
the two last posts does work since the queen at the upper left corner attacks two other queens, the rule is: attack only one or less other queens.
Once again: Queens move up-down, left-right, and diagonally for a unlimited amount of squares. A queen is attacking another one if the other queen is on one of those "possible movement squares".
• Nov 22nd 2012, 05:01 PM
Stephen347
Re: A chessboard problem
Oh, well just move the queen from the top left to the bottom left corner. That should work. Then it is a 30 point board.
• Nov 22nd 2012, 05:51 PM
wuzhe
Re: A chessboard problem
does not work still for many other queens :) many of them are attacking two other ones..
• Nov 26th 2012, 07:53 PM
Re: A chessboard problem
The search for a 27-queen solution continues, but for now I have a 26 queens for 30 points. The stairstep pattern at the upper-left is a good indication how early in the search this is.
The first five queens are in their starting positions and the sixth has only stepped once. There's a lot of room here for a 27 to pop out.
• Nov 28th 2012, 01:58 AM
Re: A chessboard problem
A little analysis shows that 26 queens is the maximum.

After 20 queens are on the board, additional queens have to share a row with another. The same goes for columns.
To get 26 queens, we need 6 horizontal pairs and 6 vertical pairs. That is 12 required pairs. Since 26 queens could form 13 pairs, this can be done.
After forming 6 horizontal pairs and 6 vertical pairs, there are 2 queens free to do as they please so to speak. They may form a pair horizontally, vertically, diagonally or not attack each other at all.
For example, in my previous post, the queens in columns 17 and 18 do not attack any queens at all.

To get 27 queens would require 7 horizontal pairs and 7 vertical pairs. That makes 14 required pairs. Since 27 queens can form no more than 13 pairs this is impossible.
• Jul 12th 2013, 01:30 AM
fanpckt
Re: A chessboard problem
doh yeah, good idea

thiet ke web|du hoc my-----------------