WARNING: The text below provides a guidance for a Project Euler problem.
If you pride yourself in tackling problems entirely on your own, you are encouraged to exit this post right now.
If you are simply looking for a hint for the problem, please visit the »Project Euler’s official forum«. You may find some hints here, but if you don’t want your problem spoiled, scroll cautiously.
If you are looking for a readily available copy/paste answer, you will not find it here. All of the code snippets in the post have been stripped of some crucial lines (these are clearly marked). It is my aim that anyone able to replicate the answer based on such snippets will have to understand the solution conceptually. At that point, by virtue of learning something new, I believe he deserves it anyway.
Guidance for future problems will not be published before 100 people have solved the problem and there are at least two more recent problems.
Open chess positions
Yet another problem from the recent “counting” streak tasks us with computing the number of configurations of pawns on an board, such that the following conditions hold:
- (1) No two pawns share a row or column.
- (2) It is possible for a rook to get from the bottom-left corner to the top-right corner of the board.
How does a position that satisfies both of the above look like? It seems to be the easiest to work with the complement. We will characterise instead the positions where the pawns are positioned according to the first rule, but the rook has no way of getting from one corner to the other.
Lemma: Rook has no way between the bottom-left corner and top-right corner if and only if some of the board’s “subdiagonals” (as represented by different colors in the picture above) is completely obstructed.
Proof. If any of the subdiagonals is obstructed, the way between the corners clearly doesn’t exist. Suppose that none of the subdiagonals is completely obstructed. Consider the pawn that was placed somewhere in the first column. Without loss of generality, on our picture, this would be on the yellow subdiagonal. On the subdiagonal of this pawn (yellow), there is going to be a sequence of pawns going right-downward, running until the first free square (which exists by assumption). The key realization is then that any square in the same row as is necessarily free and reachable with the rook from the bottom-left corner.
With a similar logic, there must also be some pawn in the first row. If , we have already found a way for rook to reach the other corner. Assume therefore that . For this pawn, any square in the same column as is necessarily free and reachable with the rook from the top-right corner. But the column of and the row of must intersect, and thus the rook can safely move between the corners at his leisure.
Another handy observation we can make straight away is the fact that at most 2 subdiagonals of the board can be completely obstructed - one in the lower-left (triangular) region below the main diagonal, and one in the upper-right region above the main diagonal (For if there were two subdiagonals obstructed on either side, we would need to have more than 1 pawns in the same row/column). Let us get to counting now.
Let be the total number of configurations of pawns that satisfy rule 1. Clearly, (When placing pawns row by row, the number of options after the -th pawn was placed is ).
Let be the total number of configurations of pawns that satisfy rule 1, where subdiagonal of length in the lower-left region below the main diagonal is completely obstructed, and subdiagonal of length in the upper-right region above the main diagonal is completely obstructed. In case no subdiagonal in either region is completely obstructed, we set or respectively. Then:
where comes from the case where the main diagonal itself is obstructed.
By the same combinatorial argument that we used to find , we can fix any and determine:
and symetrically for any :
For any we also have .
By carefully treating the indices, we can also rewrite the required double sum:
where in the last step, in the second sum, we have just counted how many times appears in . Altogether, we obtain a sum that can be computed in linear time:
The following piece of Python code gives the answer in below 5 seconds, when run with PyPy: