Backtracking

[oamsath]

I'm sure you all are familiar with the backtracking algorithms. I've studied it theoretically and I'm good at practicing recursion.

I've downloaded and read many examples and now I understand it better, but still cannot write my own backtracking examples. There is where I stop.

I don't know where to study it practically. so I thought I would ask here. Do anyone know a (book, article, site, .... ) that explain this algorithm in detail with problems/solutions so I can get to practice it better?

A book is preferred since it will explain it a lot better than anything.

Thanks.

[jRaskell]

http://www.google.com/search?q=backtracking+algorithm&rls=com.microsoft:en-us&ie=UTF-8&oe=UTF-8&startIndex=&startPage=1

[oamsath]

Didn't you think I've gone through that ?????

Thanks for the criticism anyway :s

[jRaskell]

Perhaps a more specific question then.

If you have a solid understanding of recursion, backtracking is just an extension of that for solving more complex problems that either provide multiple possible solutions (in which case you determine some criteria for selecting the "best" possible solution), and/or dead end scenarios that result in a "failed" path to the solution.

The salesman problem is an example of the first (there may also be dead end scenarios, but the problem usually focuses on a best path solution). The Queens problem is an example of the second (it does also provide multiple possible solutions, but there is no criteria for a "best" solution).

The salesman problem does require some knowledge of graph theory as well though. The Queens problem requires some knowledge of tree structures. A trivial backtracking algorithm can be created for small boards that only reduces the problem set to n! by following the rule of only one Queen per column. That is probably one of the easiest places to start on your first backtracking algorithm.

[oamsath]

thanks... I've made some of them :D