TCS Papers: Sample Questions 194  194 of 502
Examrace Placement Series prepares you for the toughest placement exams to top companies.
Question number: 194
Describe in Detail
What is the algorithm used in solving the 8 queen’s problem?
Explanation

Backtracking algorithm used in solving the 8 queens problem

Backtracking is modified brute force approach.

Technique systematically searches for a solution to problem among all available options by assuming that the solutions are represented by vectors () of values and by traversing through the domains of the vectors until the solutions is found.

For example: for 8 queens problems, queen Q1 attacks some positions, therefore queen Q2 has to comply with these constraints and be placed so that it is not directly attacked by Q1. Placing queen Q3 is harder, since we have to satisfy constraints of both Q1 and Q2.

Upon reaching a point, where the constraints make the placement of the next queen impossible, we relax the constraints and find new solution this is done by going backwards and finding new admissible solution by following simple rule: last placed, first displaced.

In other words if we place successfully queen on the i^{th} column but cannot find solution for (i + 1) ^{th} queen, then going backwards we will try to find other admissible solution for the i^{th} queen first. This process is called backtrack

Algorithm: 

Start with one queen at the first column first row

Continue with second queen from the second column first row

Go up until find a permissible situation

Continue with next queen