TCS Papers: Sample Questions 194 - 194 of 502

Examrace Placement Series prepares you for the toughest placement exams to top companies.

Question number: 194

» Basic CS » Data Structures

Essay Question▾

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 ith column but cannot find solution for (i + 1) th queen, then going backwards we will try to find other admissible solution for the ith 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

The backtracking algorithm

The Backtracking Algorithm

Given the image is define the backtracking algorithm