c# - Backtracking Search Algorithms -

my real question is, 'why doesn't backtracking speed search?' i'm not sure if makes sense without more context...

this question academic - code 'works' , program finds solutions i'm expecting....but want make sure understand terminology. illustrate things, let's use specific example we'd need search algorithm - n-queens problem.

n-queens problem - placing n queens on n×n chessboard in such way no queen can attack another.

one solution

there lots of example code on internet can found searching for, 'n-queens backtracking', , wikipedia's article on backtracking uses n-queens in explanation of backtracking (http://en.wikipedia.org/wiki/backtracking). idea, understand it, given board configuration invalid - let's 2 places queens can attack each other, algorithm disregards board configurations made adding additional pieces.

i've implemented (non-recursive/non-backtracking) depth-first , breadth-first version of search. expected, both variations test exact same number of states. expected recursive, depth-first backtracking algorithm should test fewer states. i'm not seeing that.

depth first     found 92 solutions in 10.04 seconds     tested 118969 nodes (1.2k nodes per second)     largest memory set 64 nodes backtracking     found 92 solutions in 9.89 seconds     tested 118969 nodes (1.2k nodes per second)     largest memory set 170 nodes breadth first     found 92 solutions in 12.52 seconds     tested 118969 nodes (0.95k nodes per second)     largest memory set 49415 nodes  

my actual implementation intended generic, i'm not taking advantage of board mirrors/rotations or else clever.

i feel must misunderstanding, don't see benefit backtracking gives me?

wikipedia's explains once given state found invalid, it's sub-tree skipped (pruned), placing queens rationally (avoiding q1 in a8 , q2 in a7) seems prevent situations can pruned?

what board configurations should breath-first implementation consider backtracking avoids?

backtracking 1 of several ways avoid searching down bad paths. heuristics, placing queens "rationally" another. non-backtracking solutions must have had enough heuristics avoid searching invalid paths. solution no pruning @ have tested every (64 choose 8) arrangement of queens on board.