99 problems in Haskell, 88-91

connected_components :: (Eq a, Show a) => Graph a -> [[a]]
connected_components (Graph vs es) = foldr f [] vs
    where
        -- Flatten the accumulator in order to determine if `v` belongs to a connected
        -- component which we already enumerated:
        f v acc = if v `elem` (concat acc)
                then acc
                else dfs (Graph vs es) v : acc

bipartite :: (Eq a, Ord a, Show a) => Graph a -> Bool
bipartite g = 2 == (maximum $ map snd $ wpcolor g)

import Data.List (permutations)

queens :: Int -> [[Int]]
-- All permutations, i.e. queens' placements must be "safe":
-- This test is slow-ish. To do better, I would write a list comprehension that generates
-- permutations and incorporates the `safe` test as a guard, to fail as early as possible:
queens n = filter test (permutations [1..n])
    where
        test [] = True
        test (q : qs) = safe q qs && test qs
        -- A placement of queens is "safe" iff there are no two queens in the same row or
        -- in the same diagonal:
        safe p ps = not (p `elem` ps || same_diagonal p ps)

        -- Two pieces (r1, c1) and (r2, c2) are on the same diagonal iff abs(r2 - r1) ==
        -- abs (c2 - c1), i.e. the distance between their columns is equal to the distance
        -- between their rows.
        -- Columns are given the same numbering as the rows, i.e. [1..n] (n is omitted for
        -- no reason):
        same_diagonal p ps = any (\(distance, row) -> abs (row - p) == distance) $ zip [1..] ps

main = print $ queens 8

import Data.Ord (comparing)
import Data.List ((\\), minimumBy)

type Square = (Int, Int)

-- Is a square part of a NxN board?
on_board :: Int -> Square -> Bool
on_board n (x, y) = 1 <= x && x <= n && 1 <= y && y <= n

-- Valid moves for a knight for a given square, on a NxN board:
valid_moves :: Int -> Square -> [Square]
valid_moves n (x, y) = filter (on_board n) [(x+1, y+2), (x+1, y-2),
                                            (x+2, y+1), (x+2, y-1),
                                            (x-1, y+2), (x-1, y-2),
                                            (x-2, y+1), (x-2, y-1)]

knights_to :: Int -> Square -> [Square]
knights_to n finish = knights' [finish]
    where
        -- Our search ends when there's no more moves:
        knights' moves | next_choices == [] = moves
        -- Otherwise we keep going by picking a `next` move:
                       | otherwise = knights' (next : moves)
            where
                -- The choice for our next move is a heuristic by Warnsdorf, which says
                -- to prefer squares with fewer onward moves. We won't be concerned with
                -- how to break possible ties:
                next = minimumBy (comparing (length . choices)) next_choices

                -- We pick valid moves from the last move taken, which is the head of
                -- `moves`:
                next_choices = choices (head moves)

                -- All the valid moves from a given square, to which we haven't been to
                -- yet:
                choices square = valid_moves n square \\ moves