2
$\begingroup$

I have seen many posts which were related to algorithms for solving an N⨯N puzzle, but I could not figure out the time complexity or memory complexity in these algorithms, especially when we want to apply DFS and BFS for solving our puzzle.

For example, if we assume that at first, the elements are not at their place, but the desired state would be like the below picture. What would be the time and memory complexity, if we want to show them by using Big O notation? enter image description here In this link, it has been told that we can not always find a solution using DFS and it is not complete, and also there is an explanation on how to solve the puzzle using BFS, but nothing is said about the time and memory complexity.

I will be grateful for a more detailed explanation of these algorithms when they are used for solving a puzzle because I am just a beginner in this field.

$\endgroup$
1
  • 2
    $\begingroup$ By the way, Manhattan distance is an efficient and safe heuristic for A* search, with time and memory complexity at least as good as BFS. $\endgroup$
    – Pseudonym
    Oct 10, 2022 at 5:51

1 Answer 1

8
$\begingroup$

The complexity of the BFS and DFS algorithms depend heavily on the graph being analyzed, and the search strategy being used. If we have a method to consistently get "closer" to a solution, then the search can be much more efficient than if we blindly stumble everywhere hoping to find what we need. In this case, I'm going to ignore heuristics for simplicity, and assume that by a BFS solution you mean "blindly try every combination of moves from the start until we find a solution."

The complexity of a BFS over an arbitrary tree with branching factor $b$ and maximum depth $m$ is $O(b^m)$. A branching factor is how many (on average) neighbors there are for every position. The maximum depth is how far we can possibly be from the target position. Some more information on where this fact comes from is available over on StackOverflow.

In this case, the complexity depends on understanding a few things about the puzzle, and the tree that is being searched.

To compute the complexity of a breadth-first search on an $n\times n$ 15-puzzle, we need to know these values.

The branching factor is easier, it's the number of moves we have available. The position can have either 2, 3, or 4 neighbors depending on whether the empty slot is in the center, edge, or corner. There's an exact formula for the branching factor based on how many of these there are. For an $n\times n$ puzzle:

$$\frac{2\cdot 4+3\cdot 4(n-2)+4(n-2)^2}{n^2}=4\frac{n-1}{n}$$

The maximum depth is a little more complicated. The big idea is that for an $n\times n$ puzzle, each individual piece can be at most $2n-1$ positions away from its destination (on opposite corners). On average, if you randomly place pieces on the board, you will get some linear proportion of this value* for each of the $n^2-1$ positions. Multiplying these, we get something on the order of $O(n^3)$.

Putting these two values together, we get that the complexity is:

$$O\left((4\tfrac{n-1}{n})^{n^3}\right)\in O\left(4^{n^3}\right)$$

In practice you can reduce this complexity a bit by choosing a smarter algorithm. For instance, keeping track of visited states to avoid repeated effort will at worst hit the $O(n^2!)$ positions, which is a considerable improvement (at the cost of much worse memory complexity). Heuristic searching reduces this bound by even more, and if we permit finding any solution rather than the best solution, there are algorithms that hit the $O(n^3)$ move bound directly*.

* More information on this can be found in Chris Calabro, Solving the 15-Puzzle, 2005

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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