Solution To The Queen's Gambit.

I learned to play chess as a teenager only because my younger brother wanted to learn so he could join the chess club. I never got very good at playing it because no one bothered telling me that I needed to think several moves ahead so I constantly lost. 

There is a chess problem called the queen's gambit which says if you put 8 queens on a normal chessboard of eight squares by eight squares, how many different ways can these queens be arranged so they cannot attack each other.  Remember that a queen can move any number of squares in any direction as long as it's in a straight line.  It can move diagonally, horizontally, or vertically.   answer to this is 92 but what is it is extended to the N-queen version. 

The original n-queen problem was proposed back in 1848 in a German magazine when it appeared as the 8 queen problem. Someone found the answer within the next couple of years. Then in 1869, the question was again asked but using larger numbers and this question remained unanswered until recently. A post doctoral student worked out that there are approximately (0.143n)^n ways the queens can be arranged so that none of them can attack each other on an n by n chessboard, assuming n by n is a huge number.

The (0.143n)^n is not an exact answer but an equation.  The (0.143) represents the average level of uncertainty in the variables possible outcomes. This is multiplied by the value of n and raised to the power of the value of n. This works for larger boards such as n = 1,000,000.  If you multiply 1,000,000 by 0.143, it comes out to 143,000 and that is raised to a million which gives an answer with five million digits. 

This person was able to determine the equation because he understood how queens could be arranged on these huge chessboards. He determined whether they'd be distributed in the center or along the edges and applied the appropriate the appropriate well known mathematical techniques and algorithms to find this equation. Basically, it means that if you tell this person the size of the board and how the queens are arranged, can find the number of solutions for this situation.  In other words, its a type of optimization problem.

He looked at the spaces which had a greater probability of having a queen inhabit them.  He then broke it down sections and then determined a formula to produce a valid number of configurations and used a lower bound or lowest possible number of configurations. After he had that number, he went on to find the upper value or largest number of configurations and discovered the two bounds are quite close.  Thus the answer lies somewhere between the upper and lower bounds. 

This took about 5 years to complete and he got interested in it because he could apply breakthroughs in the field of combinatorics to this problem. The key to really finding this number was to understand that spaces were not equally weighted but some were more likely to have a queen.  This lead to a breakthrough in finding the solution. 

This was cool finding a real life problem that used upper and lower bounds to find the answer.  It was also great finding out that this problem is more of a combinatorics problem and that the answer is an equation.  I hope you find it as interesting as I did and it is one that could be shared with your students.  Let me know what you think, I'd love to hear.  Have a great day.