CODEWITHSUNDEEP
c#pythonalgorithmsearch
Rob P.
Rob P.

Reputation: 15071

Backtracking Search Algorithms

My real question is, 'Why doesn't backtracking speed up my search?' But I'm not sure if that makes any sense without more context...

This question is really just academic - the code 'works' and my program finds the solutions I'm expecting....but I want to make sure I understand the terminology. To help illustrate things, let's use a specific example where we'd need a search algorithm - the n-Queens problem.

n-queens problem - Placing n queens on an n×n chessboard in such a way that no queen can attack another.

One Solution

Example Solution

There are lots of example code on the internet that can be found searching for, 'N-queens backtracking', and Wikipedia's article on backtracking even uses N-Queens in their explanation of what backtracking is (http://en.wikipedia.org/wiki/Backtracking). The idea, as I understand it, is that given a board configuration that is invalid - let's say two places queens that can attack each other, the algorithm disregards all board configurations that would be made by adding additional pieces.

I've also implemented a (non-recursive/non-backtracking) Depth-first and Breadth-first version of my search. As expected, both variations test the exact same number of states. I expected that a recursive, depth-first with backtracking algorithm should test fewer states. But I'm not seeing that.

Depth First
    Found 92 solutions in 10.04 seconds
    Tested 118969 nodes (1.2k nodes per second)
    Largest Memory Set was 64 nodes
BackTracking
    Found 92 solutions in 9.89 seconds
    Tested 118969 nodes (1.2k nodes per second)
    Largest Memory Set was 170 nodes
Breadth First
    Found 92 solutions in 12.52 seconds
    Tested 118969 nodes (0.95k nodes per second)
    Largest Memory Set was 49415 nodes

My actual implementation is intended be generic, so I'm not taking advantage of board mirrors/rotations or anything else clever.

I feel like I must be misunderstanding, but I don't see what benefit backtracking gives me?

Wikipedia's explains that once a given state is found to be invalid, it's sub-tree is skipped (pruned), but placing the queens rationally (avoiding Q1 in a8 and Q2 in a7) seems to prevent any situations that can be pruned?

What board configurations should my breath-first implementation consider that backtracking avoids?

Upvotes: 5

Views: 4361

Answers (3)

Antti Huima
Antti Huima

Reputation: 25522

Vanilla backtracking is the same thing as depth-first search. You get deeper and deeper on your branch, and when you can't proceed further (because no more queens can be put on the board) you track your path backwards towards the root, and try some other branch of the tree --- hence "backtracking".

Your depth first search and "backtracking search" are likely the same algorithm with just a cosmetic difference. When you have 6 queens on the board and no more queens fit there, you can't "rationally" proceed with the search, so likely your depth first search stops there anyway (instead of enumerating through all the invalid configurations you get from adding 7th and 8th queen anywhere on the board).

Upvotes: 1

David Eisenstat
David Eisenstat

Reputation: 65458

Wikipedia's description of backtracking conflates (i) revisiting nodes to consider the unvisited branches and (ii) pruning nodes, e.g., by algorithms that enforce local consistency. If you don't do (ii), then the visited node count won't decrease.

Upvotes: 0

ethan
ethan

Reputation: 790

Backtracking is one of several ways to avoid searching down bad paths. Heuristics, like placing the queens "rationally" is another. Your non-backtracking solutions must have had good enough heuristics to avoid searching all the invalid paths. A solution with no pruning at all would have tested every (64 choose 8) arrangement of queens on the board.

Upvotes: 4

Related Questions