Thread: 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!

I was able to successfully place 27 queens. I wonder what the maximum is!

mmm, is it possible for you to post the solution you had? because the answer they gave is less than that

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



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.

the queen can only attack 1 other maximum, not 2 , 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
and by the way, i think you might have not realized queens move in diagonals as well..

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!

The best I can get is 22, totalling 10 points. I'd be interested to see the solution with 27.

Actually, 26.

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".

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.

does not work still for many other queens many of them are attacking two other ones..

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.

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.