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 · Accepted Answer · 2012-05-04 12:56:23Z

1

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.

answered May 4, 2012 at 12:56

Ali

7,0184 gold badges41 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Understanding Pseudo code for back tracking algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related