Home arrow Development Cycles arrow Page 3 - The Backtracking Algorithm Technique
DEVELOPMENT CYCLES

The Backtracking Algorithm Technique


Every so often during our software development endeavors we might face situations where the solution(s) can be found easily or the job can be done quickly using typical well-known algorithms that can be implemented routinely. This is the first part of a multi-segment series on programming techniques where we briefly present algorithm methods one by one. This time we are going to cover backtracking.

Author Info:
By: Barzan "Tony" Antal
Rating: 4 stars4 stars4 stars4 stars4 stars / 31
September 16, 2008
TABLE OF CONTENTS:
  1. · The Backtracking Algorithm Technique
  2. · The Theory
  3. · Problem and Solution
  4. · Taking a Break

print this article
SEARCH DEVARTICLES

The Backtracking Algorithm Technique - Problem and Solution
(Page 3 of 4 )

Before we begin, we need to phrase the "Puzzle of N Queens." How can we place N queens on an N x N chessboard such that neither of them will attack each other? Of course, we know that such a placement is possible only when no two queens are to be found in the same row, column, or diagonal. Also, we won't stop right after the first solution. Our scope is to find all of the possible placements of those N queens on the board.

In order to maintain the clarity of this article, we'll consider only a 4 x 4 board; thus, we have minimized our task to only 4 queens. As we discussed in the earlier section, we need to find a way to codify a series of candidates and ultimately the solution into vectors. In this case, it is pretty straightforward. There is no need to allocate the chessboard in its entirety (4 x 4 matrices) since we only need to know the positions of queens. We can do this only with a single-dimensional array (vector). Here's how.

Simply, the index of the vector will serve as the row of the chess board, while the actual number within the X[index] vector is going to represent the column. Therefore, this is how the placement of the queen is going to be codified. Therefore, if X[1] = 3, that means there is a queen located on the first row and third column. Simple, right?

We are going to move on using the previously mentioned system of standards. In this case (4 x 4) the possible candidates (columns) can be digits from 1 to 4. That means all four of those A1, A2, A3, A4 arrays contain the {1, 2, 3, 4} elements. Due to this, we don't actually need to allocate and use those arrays. Any plain loop from 1 until 4 will do it, right? Yes. That's right. Level (n) must also be <= 4 (since we're using 4 queens).

In order to implement this algorithm, we need the follow the de facto standard style of the backtracking algorithm. Check out the following pseudo-code. It is all about having a basic recursive method, which we'll call back(), a possible() function that analyzes the likelihood of the next candidate, and ultimately the solution() function, which does nothing but check the final criteria in order to finalize the validation.

function backtracking (current depth)

if solution is valid

return / print the solution

else

for each element from A[] source array

let X[current depth] ß element

if possible candidate (current depth + 1)

backtracking (current depth + 1)

end if

end for

end if

end function

Now it's time for us to write the actual program in ANSI C. We'll begin with the possible() function because that's where possible candidates are picked. Basically, each time we are "planning" to place another queen, we need to check and verify that the specific location isn't attacked by any other queens. We need to take care of the following three factors: we cannot place the queens on the same row and column, nor the same diagonal. 

int possible(int k)

{

for (int i = 1; i < k; i++)

if (x[i] == x[k] || abs(x[i] - x[k]) == k - i)

return 0;

return 1;

}

Since our X[] is a single-dimension array we can only place one element on each index, that means X[1], for example, can only contain one number. Knowing this, the first criteria is met (it is impossible to place two queens on the same row). Next, using the x[i] == x[k] condition we can bypass those solutions where queens would be located on the same column. Ultimately, that last condition eliminates the possibilities where queens are to be placed on a position that would be already diagonally attacked.

The solution function in this particular queen's puzzle is easy. Since we analyze the fact that queens cannot attack each other right before placing a queen on the table (we do this within the possible() function), the solution function does nothing but checks whether or not we placed all of the necessary queens. This is done by returning either 1 (yes) or 0 (no).

int solution(int k)

{

return k == n;

}

The print() function prints out the elements of the X[] array until the k-nth level.

void print(int k)

{

for (int i = 1; i < k + 1; i++)

printf("%d ", x[i]);

printf("n");

}

And here's the recursive implementation of the backtracking algorithm. It is based on all of the previously presented functions. With the for loop it "tries" to place the queens on the table, trying out each column placement possibility on each row. We get the result from the possible(k + 1) which checks whether the next move is possible; if so, we "validate" that part by moving further/forward, otherwise it tries the next candidate.

void back(int k)

{

if (solution(k))

print(k);

else

for (x[k+1] = 1; x[k+1] <= n; x[k+1]++)

if (possible(k + 1))

back(k + 1);

}

Running this little application, of course, assuming you complete it with the required main() function, we get the following result on a 4 x 4 chessboard with 4 queens.

2 4 1 3

3 1 4 2

That's right. We have two possible placements in total. Remember what we said about the position of the queens? 2 4 1 3 means that X[1] = 2; X[2] = 4; X[3] = 1; X[4] = 3, meaning that first queen is located on (1,2), second on (2,4), third on (3,1), and the final fourth queen on (4,3). Try it out. It is valid. The same thing goes for the second result. 

If you want to see another visual example, check out the following diagram. In it you can see how the so-called "tree" is built if we approach backtracking from our tree analogy. Notice that the first node, the root node, is empty.

Additionally, I'd like to point out that in our above code we store only one number in our X[] vector, but as I mentioned, its index represents the row on which we place the queen. Thus, the index of X[] is basically the level (index-nth row) of the tree. That's why we will skip the root node, the 0-nth level; there's no zero row/index on the chess board. The tree exemplifies why only two solutions can be found.

You see, that's how backtracking works. Consider the first (1,1) node, that's X[1]=1 in our codified way, if the queen is placed there, on the next row the queen can be placed on (2,4), which stands for X[2]=4. Half of the problem is done. Now the third queen's only valid position is (3,2) meaning X[3]=4. The problem is almost solved.

However, here comes the bummer. The fourth queen cannot be placed in this combination. None of the four columns satisfy the condition (not to attack each other). What does the backtracking algorithm do? It steps back, moving further, and trying other alternative combinations using the possible candidates. Ultimately, it finds a solution on (1,2), (2,4), (3,1), and (4,3). It surely should make sense by now!

If you'd like to download the source code of this problem, then click below.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2014 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials