Backtracking Search Algorithms
algorithm, c#, python, search
Solution
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.
Problem
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 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?