[SOLVED] AI tree search. Time complexity of 8-queen, by placeing one by one without attack

AI tree search. Time complexity of 8-queen, by placeing one by one without attack

One approach to achieve goal state is to "add a queen to any square in the leftmost empty column such that it is not attacked by any other queen". And this approach will have a state space of 2057 (also wondering How to compute this?)

What is the time complexity if I am using Depth First search algorithm (which I think is the most suitable one)? How about the space complexity?

I am puzzled because the brunching of the search tree is reducing greatly when goes deep. O(8**8) looks too much for time complexity, even for worst case.

Thanks

Solution

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.