3 ms·
People like Criss who ask this question in interviews are looking for a brute force solution with recursive backtracking.
by lmartel 9y ago
People like Criss who ask this question in interviews are looking for a brute force solution with recursive backtracking.
- proaralyst 9y agoIs that not what's happening here? Except GHC has the recursive backtracking built in? The code looks a lot like the equivalent Prolog implementation.
- sp332 9y agoI think you're supposed to show that you know how to do that yourself, instead of just using an existing implementation.
- Tarean 9y agoThough I don't think I would use backtracking for an actual haskell solution. Probably something like: import Data.List (permutations) solve :: Int -> [[Int]] solve i = filter (valid . zip [1..]) (permutations [1..i]) valid :: [(Int, Int)] -> Bool valid [] = True valid (x:xs) = singleValid x xs && valid xs where singleValid x xs = all (pairwiseValid x) xs pairwiseValid (x1, y1) (x2, y2) = abs (x1-x2) /= abs (y1-y2)
- andrewem 9y agoI'm a fan of the min-conflicts heuristic for this problem. See eg section 5.3 of http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf