Old People Were Really Smart: A Look at the 8 Queens Puzzle

It's May 2019.

Elon Musk is shooting Tesla's into the moon, Jeff Bezos wants to conquer the world with flying drones, yet amongst the modern technological craze it's still amusing to consider the many questions posed by our beloved world of the 64 squares.

Visionaries of today are shooting cars to the moon. | Source: Creative Commons

Computers, smartphones, tablets, and the internet are ubiquitous. Answers to questions bothering us in the modern world are often just a simple Google search away. It makes for an interesting thought experiment wondering how great thinkers of the past were able to come to solutions and conclusions about chess without these silicon beasts.

Perhaps all of these objects can connect to the internet. | Photo: Unsplash

Traveling back to the year 1848, German chess composer Max Bezzel created the 8 queens puzzle. The puzzle challenges any of its participants to place eight queens on a chess board such that no two queens are threatening each other.

Max Bezzel - Inventor of the Eight Queens Puzzle. | Source: Public Domain

Grab a chess board and try to solve this puzzle!

As you might suspect, this problem is actually quite difficult and not trivial despite its simple rules. On the outset, there does not seem to be a simple heuristic to solve the problem. Let's use a few shortcuts provided by mathematics in order to see exactly how many possibilities there exists within this problem. It may perhaps in a naive way explain why this problem is so difficult.

We tried our hand at solving it... | Photo: singed41

We're going to need to place 8 queens on the board across a board with 64 squares. Intuitively, we may be able understand that this number is quite large, granted it's tough to know exactly how huge without the aid of mathematics. Apologies ahead of time for the lack of mathematical rigor!

Enlisting a little help from mathematicians, we may get a quick and dirty answer. Combinatorial mathematics suggest we must choose k = 8 unique spots to place the queen from the n = 64 squares on the chessboard. Don't worry, all this means is for now is punching numbers into a fancy calculator.

Plugging these numbers into a convenient formula, we get 4,426,165,368 different possibilities!

Mathematicians definitely didn't need computers to figure this out. For more detailed information and to play around with these numbers, visit Wolfram Mathematics.

Out of so many possibilities, only 92 of these positions are valid solutions to the 8 queens puzzle. Let's look at one that's fairly easy to remember and to recreate since it's symmetrical.

The solution in the above diagram appears to be symmetrical if we rotate the queenside and mirror it over onto the kingside. The queen on h4 would be the analog to the queen on a5, the queen on g6 would be the analog to the queen on b3, and so on and so forth.

Two years after the problems proposal, a gentleman by the name of Franz Nauck in 1850 found a solution to the problem. Not too much is known about Nauck but one thing of interest is that he generalized this puzzle to what is called the N-Queens problem.

This puzzle would be transformed from our 8 x 8 sized board to an N x N board. The question then becomes if there exist a solution for every N x N sized chess board (where N is a natural number greater than three). If we made a really large chessboard, the possibilities would be unearthly large!

Just imagine the possibilities... | Source: Unsplash

Only until as recently as 2017, this problem has been proven to be NP-Complete. This class of problem when generalized is one that is used in many fields of scientific study such as mathematics, statistics, and computer science. 

Borrowing from expert Mike James from i-programmer, "NP is the set of problems that are hard to solve but for which it is easy to check a proposed solution, and an NP-Complete problem is one that if you can find a way to solve it quickly then you can solve all (NP) problems in polynomial time".

 A common problem to solve for STEM majors. | Source: Unsplash

While not quite fully qualified to explain what this means, we can appreciate that a lot of interested parties are willing to fork over a lot of cash for the answers in this domain of study.

The proof for solving P vs NP is a long standing question which the Clay Mathematics Institute is willing to reward $1 million USD to its solver. Of course the implications of solving this problem are magnitudes greater than the prize awarded.

Much of the cryptographic functions that are utilized in our day to day devices are predicated on the fact that this can't equation can't be satisfied. Protective mechanisms such as safely logging into chess.com, hiding banking passwords, and privacy for your favorite social media platforms are all protected by many of such algorithms.

Cryptography is protecting your privacy from prying eyes. | Source: Unsplash

Whew! That's quite a historical impact for such a seemingly simple puzzle. Thinkers of the yesteryear could find the solution to this problem without the aid of computers and ponder its implications well into our modern technologically driven society. 

Whether or not that was their intent is another interesting thought experiment to ponder. But for now, let's just appreciate our evergreen game as we continue to marvel at its curiosities in the 21st century!

We're still figuring it out... | Photo: singed41