Satcos

What is 8 Queen Puzzle?
8 chess Queens pieces should be placed in an 8 x 8 chess board such that none of the queen is able to attack any of the other queen. This is one of the hard problems because out of the millions of ways in which these queens can be placed in a chess board only few are valid solution.

Understanding the chess board
Horizontal rows in chess board are called rank and they are identified by numbers 1 to 8, 1 starting from white player. Vertical columns are called file, they are identified by letters a to h, a at the left side of white player.

8 Queen Puzzle Solution
Writing a computer program to solve 8 queens puzzle might sound complicated at first look but if we get simplified representation of chess board, program becomes easy. Let’s take a simple step by step approach to arrive at. the solution.

Rule1:

Queen can move vertically. Since queen can move vertically, there can be only one piece per file. Below image is one valid solution obeying Rule 1. Let’s call these pieces queen1 to queen8 from left to right.

Rule2:

Queen can move horizontally. Since queen can move horizontally, there cannot be more than one queen in same rank. Below image is one valid solution obeying Rule 1 & Rule 2. Let’s compute number of solutions available with these 2 conditions. Let us place the pieces one by one in an empty board. Queen1 at file-a can be placed at any of the 8 ranks. This leaves Queen2 at file-b with only 7 valid ranks because Queen2 cannot be placed at the same rank as that of Queen1. Now Queen3 at file-c get only 6 valid ranks and Queen 4 with 5 valid ranks and so on. Total number of combinations available are 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 8! = 40320. 40K+ combinations are too simple for modern day computers, so technically we can have a program to get the solution. All we have to do is write a program to generate these 40k+ combinations and a verifier checks for the solution criteria if it matches, we got a solution.

Rule3:

Queen can move diagonally. This rule makes our life complicated as well as easy. This renders some solutions from 40K+ candidate solution as invalid. Let’s look at an example, Queen1 is placed at rank4, according to rule2 Queen2 cannot be placed at rank4, now according to rule3 Queen2 cannot be placed at rank3 & rank5 too, so this leave only 5 valid positions for Queen2 reducing the combinations to be explored. The general rule is QueenX eliminates QueenY’s ranks [QueenX’s rank – (Y-X)] & [QueenX’s rank + (Y-X)] provided these values falls between 1 to 8. The above statement can be little confusing, look at a chess board and read it couple of times, you can get it. Below image is one valid solution obeying all 3 rules.


Below Python program finds all 92 solutions, since all conditions are checked in the loop there is no need for seperate verifier. Code might look very lengthy but it is one of the easy to understand version. Download the solution in text format here. The generalized version is neet and elegant without too many nested loops, It can handle the generalized verion of the 8 Queen problem known as n Queen problem of arraning n queens in n x n chessboard without attaching eachother.

Simple version, easy to understand Generalized version to handle n Queen problem