[Solved]: Time complexity of 8-queen, by placeing one by one without attack

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:

1. 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}$.

2. Your approach: What backtracking is involved here? Your algorithm as stated could either succeed or not, but it will do so very fast.

3. 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.

4. Space complexity: Backtracking algorithms have very small space complexity. You're basically keeping track of one partial solution.

5. 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