Note on chess piece movement:  According to the rules of chess, a pawn is threatened when a queen shares a row, column, or diagonal with it.

General Comment 1: When attacking a problem like this, a good first step is to try and think about how to enumerate the possibilities. One approach is a brute force attack: we have to choose 5 of the 25 squares to place a queen. If you know binomial coefficients, the number of ways is (25 choose 5) or 53,130. While this is a large number for a human to do, for a computer it’s nothing. So, if you are willing to write a program it should be able to investigate and find the answer in a reasonable amount of time. (Note: (n choose r) is n! / (r! (n-r)!), where k! = k(k-1)*…*3*2*1 and 0! = 1; (n choose r) represents the number of ways to choose r objects from n when order does not matter.)

However, just because we can write a computer program doesn’t mean that we should give up on finding a solution by hand. Or, if we are going to write a program, maybe we can write a more efficient one than brute force. It’s often an interesting problem trying to determine how much time one should spend writing efficient code. If your computer is fast enough and the problem simple enough, you can afford to be wasteful; however, as you progress you’ll find harder and harder problems, and thus it is worthwhile to get into good habits, where you program well.

General Comment 2: When confronted with a new problem, try to see if it reminds you of anything else you’ve seen before. If you can find something similar, perhaps you can modify your solution or knowledge of that problem. The analysis for this problem can be aided by recalling a simple game, but which one?

First hint: Consider the dual problem: place 3 queens so that 5 pawns may be safely put on the board, then convert the pawns to queens and the queens to pawns! Instead of having (25 choose 5) possible places to put 5 queens, we instead are studying (25 choose 3) or 2300, which is magnitudes better (specifically, we save more than a factor of 20). 

This principle is known as duality, or we say we’re studying the dual problem. This occurs in a very important area of mathematics / optimization theory: linear programming. At the end of this note is a short video on this.

Second hint: Think back to tic-tac-toe. There are nine squares. How many possible first moves are there? One way to answer this is to say, obviously, there are nine possible first moves! While that is correct, there is another way to view the problem, which leads to another solution. There are just three possible first moves. Why? Moving in any of the four corners is equivalent if we rotate the board. Similarly the four sides are all equivalent, and then there’s the center.

1	2	3	2	1
2	4	5	4	2
3	5	6	5	3
2	4	5	4	2
1	2	3	2	1

Third Hint: Here are some thoughts on placing the three pawns.

• The easiest way to think about the location of the second pawn, taking into account symmetry, is to break the analysis based on where the first pawn is located. For example, if the first pawn is in a 1 position then there are 14  possible places for the second pawn (up to symmetry). We can do such a case analysis for each of the 6 possibilities.
• It gets more involved placing two pawns and then looking for the third. Sometimes it is easier to just brute force all the solutions, especially as we’ve reduced things from putting down 5 pawns to putting down 3. If we don’t use any symmetry there are (25 choose 3) = 25 * 24 * 23 / 3 * 2 * 1 = 2300 options, much smaller than the 53,130 we had from (25 choose 5), and of course we can do better by doing the analysis mentioned above.

Solution and further reading / viewing: The solution is:

[   ] [P] [   ] [    ] [P]
[   ] [   ] [   ] [   ] [P]
[Q] [   ] [   ] [   ] [  ]
[Q] [   ] [   ] [Q] [  ]
[   ] [   ] [Q] [Q] [  ]

Here is a video on this problem and connections to linear programming: