99 questions/Solutions/90 - Revision history
http://www.haskell.org/haskellwiki/index.php?title=99_questions/Solutions/90&action=history
Revision history for this page on the wikienMediaWiki 1.19.5-1+deb7u1Tue, 29 Jul 2014 15:19:27 GMTWapcaplet at 17:05, 15 July 2010
http://www.haskell.org/haskellwiki/index.php?title=99_questions/Solutions/90&diff=36207&oldid=prev
http://www.haskell.org/haskellwiki/index.php?title=99_questions/Solutions/90&diff=36207&oldid=prev<p></p>
<p><b>New page</b></p><div>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.<br />
<br />
The simplest solution is a composition of separate functions to generate the list of candidates and to test each candidate:<br />
<br />
<haskell><br />
queens :: Int -> [[Int]]<br />
queens n = filter test (generate n)<br />
where generate 0 = [[]]<br />
generate k = [q : qs | q <- [1..n], qs <- generate (k-1)]<br />
test [] = True<br />
test (q:qs) = isSafe q qs && test qs<br />
isSafe try qs = not (try `elem` qs || sameDiag try qs)<br />
sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs<br />
</haskell><br />
<br />
By definition/data representation no two queens can occupy the same column.<br />
<hask>try `elem` alreadySet</hask> checks for a queen in the same row, <hask>abs (try - q) == col</hask> checks for a queen in the same diagonal.<br />
<br />
This is easy to understand, but it's also quite slow, as it generates and tests N^N possible N-queen configurations.<br />
The key to speeding it up is to fuse the composition <hask>filter test . generate</hask> into a semantically equivalent function <hask>queens'</hask> that does the tests as early as possible.<br />
If a list already contains two queens in a line, there's no point in considering all the possible ways of adding more queens.<br />
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.<br />
This yields the following version, which is much faster:<br />
<br />
<haskell><br />
queens :: Int -> [[Int]]<br />
queens n = map reverse $ queens' n<br />
where queens' 0 = [[]]<br />
queens' k = [q:qs | qs <- queens' (k-1), q <- [1..n], isSafe q qs]<br />
isSafe try qs = not (try `elem` qs || sameDiag try qs)<br />
sameDiag try qs = any (\(colDist,q) -> abs (try - q) == colDist) $ zip [1..] qs<br />
</haskell><br />
<br />
If you approach this problem with an imperative mindset, you might be tempted to use an accumulating parameter for the list of candidates.<br />
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.</div>Thu, 15 Jul 2010 17:05:05 GMTWapcaplethttp://www.haskell.org/haskellwiki/Talk:99_questions/Solutions/90