8 Queen Puzzle

Introduction

In this blog post, we will look at the solution for 8 Queen Puzzle.

Problem Statement

8 Queen Puzzle is the problem of placing eight queens on an 8 x 8 chessboard, so that no two queens threaten each other. The queen can be moved any number of unoccupied squares in a straight line vertically, horizontally, or diagonally, thus combining the moves of the rook and bishop. So the answer for 8 queen puzzle is to find a solution which requires that no two queens share the same row, column, or diagonal.

Trial and Error

Trial and Error is a fundamental method of problem solving. It is characterized by repeated, varied attempts which are continued until success, or until the practicer stops trying. If we had to solve the 8 Queen Puzzle by Trial and Error, the number of possible ways that we can place 8 queens occupying every row on the board is 16777216 which makes it very hard for a human being to try out all these possible positions on the board to arrive at the solution.

In software engineering, whenever we use open source libraries to design and build our solutions, and if we uncover a bug in their library, be it functional defect, (or) unrecoverable errors like Out of Memory Errors, we will try to explain the problem in the simplest possible code outside the context of our application, so that the open source community can look at the essence of the problem and provide a solution. Similarly, we can reduce the problem space by choosing to solve the 8 queen puzzle​ using  4 queens which will reduce the number of possible ways to 256 which is 99.99% reduction of the number of possible ways when compared to 8 queens on the board, but still keeping the essence of the problem intact.

In humans, our short term memory has a fairly limited capacity. So in effect, reducing the problem space circumvents the limited nature of our short term memory. Also, the other most important benefit of shrinking the problem space is, it will help us probe the question much more deeper. One of my favorite quote of J Krishnamurti is :

If we can really understand the problem, the answer will come out of it, because the answer is not separate from the problem – J Krishnamurti

We will use Trial and Error method to solve the 4 Queen Puzzle using which we can extrapolate the solution for 8 queens on the board. If we follow the trail and error approach, we will find that we have 2​ fully valid positions which are: [[.Q.., …Q, Q…, ..Q.], [..Q., Q…, …Q, .Q..]].

Power of elimination

The insight from the above picture is, if we find a partially invalid position, then all the corresponding fully invalid positions which involve those partially invalid position will automatically be invalid. From the above 4 positions in the image we have eliminated 36 fully invalid positions. By following the same approach, by traversing just 44​ invalid positions, either partial or full out of 256 possible positions, roughly 17%, we will eliminate 254​ fully invalid positions which will help us actually find 2​ fully valid positions. The beauty of this approach is, as the board size increases, the number of fully invalid positions that we eliminate will be significantly higher, by just inspecting a handful of invalid positions, either partial or full. For instance, if we take 8 queen, we will traverse only 13664 invalid positions, either partial or full out of 16777216​ possible positions, roughly 0.08%, we will eliminate 16777124, which is almost 99.99% of all possible solutions. The power of elimination shines as the board size n increases, as the power of n which gives the total possible positions also increases significantly.

To understand the significance of power​ on any number, lets look at compound interest for example. We all know the formula to calculate compound interest, which is,

A = P(1 + r/n)^nt

where “A” is the ending amount, “P” is the beginning amount (or “principal”), “r” is the interest rate, “n” is the number of compounding in a year, and “t” is the total number of years. For discussion purposes, we will assume that the number of compounding in a year n is equal to one. So, the formula becomes:

A = P(1 + r)^t

We can see that, t is in exponent position in the compound interest formula. If we allow compounding to work over a longer time period, the ending amount “A” will be significantly higher as opposed to compounding over a shorter time period, due to the magic of t which is in the exponent position., higher the number greater is the end result A.

For example, if we compound 1$ at 12% for 30 yrs,  we can clearly see in the below diagram, that compounding is backloaded where significant gains are achieved in the final years.

Generalization

Generalization is the formulation of general concepts from specific instances by abstracting common properties. If we can capture the essence of our problem solving approach that we have followed so far in a generic fashion outside of the specifics of 8 Queens puzzle, we can define it as follows:

An algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. This approach is formerly known as “Backtracking”.

We can apply Backtracking approach to solve problems involving Sudoku  , Crosswords etc.,

Solution

As we place the queens in each of the n rows, we need to make sure NO queens intersect each other after every time we place one additional queen in its own row. For queens, not to intersect each other they should satisfy the below constraints:

• No queens should be in the same column
• No queens in diagonal 1 i.e from top left to bottom right.
  • From the below diagram we can see that,  for queens intersecting in diagonal 1 , the value of  row - col of queen currently being placed on the board should be equal to row - col of any other queen already placed on the board.
• No queens in diagonal 2 i.e from bottom left to top right
  • From the below diagram we can see that,  for queens intersecting in diagonal 2 , the value of  row + col of queen currently being placed on the board should be equal to row + col of any other queen already placed on the board.

Recursive solution using Backtracking approach can be found here.

Intuition

To summarize our overall logic,

We know the truth table for AND operator which is:

In the above use case, we simply fail fast if we find partial invalid solution along the way, which can be nicely captured using AND operator. Every time we fail fast, we simply ignore all the other fully invalid positions which involve these partial invalid positions and this number increases significantly as the board size n increases. The OR operator does the exact opposite, where it helps us to succeed fast the moment one of the OR conditions becomes true.

AND and OR are powerful primitive operators, which helps us to make logical decisions  accurately and swiftly when 2 or more variables are involved.

Conclusion

In this blog post, by solving the 8 queen puzzle, we looked at trial and error approach, elimination techniques, power of exponent, generalization, backtracking, AND/OR operator.