Understanding Pseudo code for back tracking algorithm

Question

To start back tracking algorithm, the following pseudocode can be called for i=0; X[1..0] represents the empty tuple.

ALGORITHM Backtrack(X[1..i])
   //Gives a template of a generic backtracking algorithm
   //Input: X[1..i] specifies first i promising components of a solution.
   //Output: Alll the tuples representing the problem's solutions
   If X[1..i] is a solution write X[1..i]
   else
     for each element x belongs to Si+1 consistent with X[1..i] and constraints do
        X[i+1] <- x
        Backtrack(X[1..i+1])

I am having difficulty in understanding above logic. I have tried to undestand with 4 queen problem with step thorugh but not. Kindly request your help in understanding above logic with steps of 4 queens problem.

Thanks!

Ali Ali · Accepted Answer · 2012-05-04T12:56:23

look at this PDF file, page 25. it has a step to step description with images about 4 queens solution with backtracking.

http://ce.sharif.edu/courses/90-91/2/ce417-1/resources/root/Lectures/Chapter-6.pdf

In brief:

The algorithm is trying to find an assignment for each element of array X which is consistent with all constraints.

To do this with backtracking, we use a recursive function. In each step we examine all available values for the current variable (domain set S_i+1) and if it is consistent with the constraints, we go to the next variable recursively until we reach a solution.

Understanding Pseudo code for back tracking algorithm

1 Answers