Backtracking and N-Queens
One of the problem-solving techniques that comes up at least reasonably often in algorithmics is backtracking. It is, in essence, a mechanism for creating all permutations of a given set that satisfy some constraint. Having never written a backtracking algorithm before and given its popularity and in fact arguable dominance in some of our local competitions, I figured it was time to sit down and bang one out.
#My internet is down and I've never written one of these so... N-QUEENS import time def is_complete(candidate, size): """Given the candidate and the size of the board we are solving for, returns a boolean value indicating whether this is a valid solution.""" return len(candidate) == size def is_valid_candidate(candidate, size): """Given the candidate and the size, ensure that the latest addition to the candidate solution is legal. Takes candidate and size, returns boolean.""" if len(candidate) == 1: return True for i in candidate[:-1]: #Check to see if any queens share a column. if i == candidate[-1]: return False #Check to see if any queens share a diagonal. horiz_distance = abs(candidate[-1] - i) vert_distance = abs(len(candidate) - 1 - candidate.index(i)) if horiz_distance == vert_distance: return False return True def process_solution(candidate): """Given a final candidate, output the results.""" for i in candidate: line = '' for j in range(i-1): line += '.' line += '*' line += '.' * (len(candidate) - i) print line print "" def backtrack(candidate, size): """The meat of the algorithm. Builds a candidate, checks it, recurses to build final sol'n""" for i in range(1, size + 1, 1): candidate[-1] = i if is_valid_candidate(candidate, size): if is_complete(candidate, size): process_solution(candidate) return new_candidate = candidate[:] new_candidate.append(0) backtrack(new_candidate, size) return candidate = [0] x = time.time() backtrack(candidate, 8) print time.time() - x
The classic problem used to explain backtracking is N-Queens, which is defined thus: given a chess board that is n squares in height and n in width, how many ways can n queens be placed upon the board such that none of them is able to capture each other?
The way backtracking works is by using partial solutions or candidates to construct a full solution. The algorithm runs through each possibility for that candidate and, if they are valid, uses them to build a more complete candidate and so on until a complete solution is formed.
Because the solution is recursive, it implicitly constructs a tree of all of the candidates. Any candidate that is rejected is omitted, and we're left with an interesting situation where all of the remaining leaves of that tree are solutions.
Once again Python steps up with a short, sweet answer that was fun to write and (i hope) easy to read.
