Every researcher dreams of solving a classical problem, one that has remained open and unsolved for over a hundred years. There is something romantic about communicating across the generations, being part of the evolution of science, helping to climb another rung up the ladder of human progress. There is also a pleasant sense of smugness that comes from figuring out how to do something that nobody else could do before you.
There are several possible reasons why a problem might stay open for such a long period of time. Perhaps the problem is so difficult and profound that it requires a uniquely powerful intellect to solve. A second reason is technological - the ideas or techniques required to solve the problem may not have existed when the problem was first posed. A final possibility is that no one may have cared enough about the problem in the interim to seriously bother with it. Once, I was involved in solving a problem that had been open for over a hundred years. Decide for yourself which reason best explains why.
Chess is a game that has fascinated mankind for thousands of years.
In addition, it has inspired a number of combinatorial problems of
independent interest.
The combinatorial explosion was first recognized in the legend that the
inventor of chess demanded as payment one grain of rice for the first
square of the board, and twice the amount of the ith square for the
(i+1)st square, for a total
of 
36,893,488,147,419,103,231 grains.
In beheading him, the wise king first established pruning as a technique for
dealing with the combinatorial explosion.
In 1849, Kling posed the question of whether all 64 squares on the board can be simultaneously threatened by an arrangement of the eight main pieces on the chess board - the king, queen, two knights, two rooks, and two oppositely colored bishops. Configurations that simultaneously threaten 63 squares have been known for a long time, but whether this was the best possible remained an open problem. This problem seemed ripe for solution by exhaustive combinatorial searching, although whether it was solvable would depend upon the size of the search space.
Consider the 8 main pieces in chess (king, queen, two rooks, two bishops,
two knights).
How many ways can they be positioned on a chessboard?
The trivial bound is
positions.
Anything much larger than about 
positions would be
unreasonable to search on a modest
computer in a modest amount of time.
Getting the job done would require significant pruning. The first idea is to remove symmetries. Considering the orthogonal and diagonal symmetries, there are only ten distinct positions for the queen.
Once the queen is placed, there are 2,080 distinct ways to position a pair of
rooks or knights,
64 places to locate the king, and 32 spots for each of the white and
black bishops.
Thus to perform an exhaustive search, we must
test 2,835,349,504,000 
distinct positions, still much too large to try.
We could use backtracking to construct all of the positions, but we had to find a way to prune the search space significantly if we could hope to finish in our lifetime. Pruning the search meant that we needed a quick way to prove, for a partially filled-in position, that there was no possible way to complete it so as to cover all 64 squares. Suppose we had already placed seven pieces on the board, and together they covered all but 10 squares of the board. Say the remaining piece was the king. Is there any possible position to place the king so that all squares are threatened? The answer must be no, because the king can threaten at most eight squares according to the rules of chess. There can be no reason to bother testing any of the subsequent positions. By pruning these positions, we might win big.
Optimizing this pruning strategy required carefully ordering the evaluation of the pieces. Each piece could threaten a certain maximum number of squares: the queen 27, the king 8, the rook 14, and the bishop 13. To maximize the chances of a cutoff, we would want to insert the pieces in decreasing order of mobility. Whenever the number of unthreatened squares exceeds the sum of the maximum coverage of the unplaced pieces, we can prune. This sum is minimized by using the decreasing order of mobility.
When we implemented backtrack search with this pruning strategy, we found
that it eliminated over 
of the search space.
After optimizing our move generation, our
program could search over 1,000 positions per second.
But this was still too slow, for
seconds meant 1,000 days!
Although we might further tweak the program to speed it up
by an order of magnitude or so,
what we really needed was to find a way to prune more nodes.
Effective pruning meant eliminating large numbers of positions at a single stroke. Our previous attempt was too weak. What if instead of placing up to eight pieces on the board simultaneously, we placed more than eight pieces. Obviously, the more pieces we placed simultaneously, the less likely it would be that they didn't threaten all 64 squares. But if they didn't cover, all subsets of eight distinct pieces from the set couldn't possibly threaten all squares. The potential existed to eliminate a vast number of positions by pruning a single node.
Thus the nodes of our search tree corresponded to chessboards that could have any number of pieces, and more than one piece on a square. For a given board, we would distinguish two kinds of attack on a square: strong and weak. The notion of strong attack corresponds to the usual notion of attack in chess. A square is weakly attacked if the square is strongly attacked by some subset of the board, that is, weak attack ignores any possible blocking effects of intervening pieces. All 64 squares can be weakly attacked with eight pieces.
Our algorithm consists of two passes. The first pass lists all boards such that every square is weakly attacked. The second pass filters the list by considering blocking and reports any boards with n or fewer safe squares. The advantage of separating weak and strong attack computations is that weak attack is faster to compute (no blocking to worry about), and yet the strong attack set is always a subset of the weak attack set. Whenever there was a non-weakly-threatened square, the position could be pruned.
This program was efficient enough to complete the search on a machine as slow as a 1988-era IBM PC-RT in under one day. More details of our searching procedure and results appear in our paper [RHS89]. It did not find a single position covering all 64 squares with the bishops on opposite colored squares. However, our program showed that it is possible to cover the board with seven pieces if a queen and a knight can occupy the same square.
The take-home lesson of this war story should be clear. Clever pruning can make short work of surprisingly hard combinatorial search problems.