Problem Detail: I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing 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.
Asked By : Wendy
Answered By : Yuval Filmus
Let’s tackle your questions one by one:
- State space: I have no idea where you got this number from. The state space is ostensibly $binom{64}{8} approx 2^{48}/8! approx 2^{32}$.
- Your approach: What backtracking is involved here? Your algorithm as stated could either succeed or not, but it will do so very fast.
- Time complexity: It is in general difficult to estimate the time it takes a backtracking algorithm to find a solution. You can try to estimate the total time it takes to go over the entire space in various ways, for example you can estimate the branching factor at each step.
- Space complexity: Backtracking algorithms have very small space complexity. You’re basically keeping track of one partial solution.
- The estimate $O(8^8)$: Actually $8^8 = 2^{24}$ is very small. You can probably go over this search space in under a second on a modern computer.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21905
