Depth First Search Basics

Posted by cam on Stack Overflow See other posts from Stack Overflow or by cam
Published on 2010-04-24T11:46:39Z Indexed on 2010/04/24 11:53 UTC
Read the original article Hit count: 330

I'm trying to improve my current algorithm for the 8 Queens problem, and this is the first time I'm really dealing with algorithm design/algorithms. I want to implement a depth-first search combined with a permutation of the different Y values described here: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

I've implemented the permutation part to solve the problem, but I'm having a little trouble wrapping my mind around the depth-first search. It is described as a way of traversing a tree/graph, but does it generate the tree graph? It seems the only way that this method would be more efficient only if the depth-first search generates the tree structure to be traversed, by implementing some logic to only generate certain parts of the tree.

So essentially, I would have to create an algorithm that generated a pruned tree of lexigraphic permutations. I know how to implement the pruning logic, but I'm just not sure how to tie it in with the permutation generator since I've been using next_permutation.

Is there any resources that could help me with the basics of depth first searches or creating lexigraphic permutations in tree form?

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about tree