Revision as of 17:05, 15 July 2010
This is a classical problem in computer science. The objective is to place eight queens on a chessboard so that no two queens are attacking each other; i.e., no two queens are in the same row, the same column, or on the same diagonal.
The simplest solution is a composition of separate functions to generate the list of candidates and to test each candidate:
queens :: Int -> [[Int]] queens n = filter test (generate n) where generate 0 = [] generate k = [q : qs | q <- [1..n], qs <- generate (k-1)] test  = True test (q:qs) = isSafe q qs && test qs isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs
By definition/data representation no two queens can occupy the same column.
This is easy to understand, but it's also quite slow, as it generates and tests N^N possible N-queen configurations.The key to speeding it up is to fuse the composition
If a list already contains two queens in a line, there's no point in considering all the possible ways of adding more queens. Now that the recursive call incorporates testing, we avoid recomputing it by interchanging the two generators, and reverse each answer at the end to obtain the original order. This yields the following version, which is much faster:
queens :: Int -> [[Int]] queens n = map reverse $ queens' n where queens' 0 = [] queens' k = [q:qs | qs <- queens' (k-1), q <- [1..n], isSafe q qs] isSafe try qs = not (try `elem` qs || sameDiag try qs) sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs
If you approach this problem with an imperative mindset, you might be tempted to use an accumulating parameter for the list of candidates. This would make the function harder to understand, and would not help much (if at all): the important thing here is the breadth of the search tree, not its depth.