1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ $O(8^8) = O(1)$ -- don't use Landau notation when you don't let $n\to\infty$. $\endgroup$
    – Raphael ♦
    Feb 22, 2014 at 9:24
  • $\begingroup$ Thank you @Raphael, this is a mistake should be avoided, thanks $\endgroup$
    – Wendy
    Feb 22, 2014 at 22:22

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you so mush for the great explanation. The number 2057 is from "Artificial Intelligence -- a modern approach 3rd edition", page 72. If using incremental formulation -- from column left to right, place queens one by one avoiding column row and diagonal attack against queens already on board, there is 2057 states (including not complete state like 5 or 6 queen on boards, but all legal state). I am not using backtracking, just know it's a better way for less memory. But I am just practicing analyzing such problem where branching decrease heavily, with some path abandoned halfway. Thank you! $\endgroup$
    – Wendy
    Feb 22, 2014 at 0:01
  • $\begingroup$ If you're not using backtracking you are only trying one potential solution: at each point you're placing the queen in a fixed spot, and you might get stuck. Backtracking is a way of exploring more than one solution. $\endgroup$
    – Yuval Filmus
    Feb 22, 2014 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.