Depth First Search's time depends on how smart the algorithm is to decide which branch to investigate first.
N queens has a cheat: it has a heuristic (see description on wikipedia) which gives a perfect solution in polynomial time. If your Depth First Search's decisions simply mimic that heuristic's decisions, then your Dept First Search is poly time too.