Is that not what's happening here? Except GHC has the recursive backtracking built in? The code looks a lot like the equivalent Prolog implementation.

I'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

Though 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)