As the title says, I am really really really curious about this.
I've been trying to find the cases where you can't use backtracking to solve them but I can't find them.
Share your knowledge please
If there are too many possibilities to check, backtracking search will be impractical - see e.g. http://en.wikipedia.org/wiki/Lighthill_report. There may also be cases where you cannot state the problem simply and clearly enough to recognize the correct answer when you find it.