> import Diagrams.Backend.SVG.CmdLine
A relatively well-known puzzle is to find a sequence of moves by which
a knight can visit every square of a chessboard exactly once, without
repeating any squares. This example computes such a tour and
visualizes the solution.
> {-# LANGUAGE NoMonomorphismRestriction #-}
>
> import Data.List (minimumBy, tails, (\\))
> import Data.Ord (comparing)
> import Diagrams.Prelude
First, we compute a tour by a brute force depth-first search (it does
not take very long). This code is adapted from the [code found
here](http://rosettacode.org/wiki/Knight%27s_tour#Haskell).
> type Square = (Int, Int)
>
> board :: [Square]
> board = [ (x,y) | x <- [0..7], y <- [0..7] ]
>
> knightMoves :: Square -> [Square]
> knightMoves (x,y) = filter (`elem` board) jumps
> where jumps = [ (x+i,y+j) | i <- jv, j <- jv, abs i /= abs j ]
> jv = [1,-1,2,-2]
>
> knightTour :: Square -> [Square]
> knightTour sq = knightTour' [sq]
> where
> knightTour' moves@(lastMove:_)
> | null candMoves = reverse moves
> | otherwise = knightTour' $ newSquare : moves
> where newSquare = minimumBy (comparing (length . findMoves)) candMoves
> candMoves = findMoves lastMove
> findMoves s = knightMoves s \\ moves
Now we can go about visualizing a tour. First, let's draw a chessboard:
> boardSq :: Colour Double -> Diagram B
> boardSq c = square 1 # lw none # fc c
>
> chessBoard :: Int -> Diagram B
> chessBoard n
> = vcat . map hcat . map (map boardSq)
> . take n . map (take n) . tails
> $ cycle [antiquewhite, saddlebrown]
Now, we need a way to convert `Square` coordinates (a pair of numbers
in the range 0-7) into actual coordinates on the chessboard. Since
the chessboard ends up with its local origin in the center of the
top-left square, all we need to do is negate the $y$-coordinate:
> squareToPoint :: Square -> P2 Double
> squareToPoint (x,y) = fromIntegral x ^& negate (fromIntegral y)
To draw a knight on a given square, we simply translate the given image appropriately:
> knight :: Square -> Diagram B -> Diagram B
> knight sq knightImg = knightImg # moveTo (squareToPoint sq)
Given a tour, we turn it into a path using `fromVertices`,
and decorate the vertices with dots.
> drawTour :: [Square] -> Diagram B
> drawTour tour = tourPoints <> strokeP tourPath
> where
> tourPath = fromVertices . map squareToPoint $ tour
> tourPoints = atPoints (concat . pathVertices $ tourPath) (repeat dot)
> dot = circle 0.05 # fc black
Finally, we load a knight image, size it to fit a square, and then put all the
previous pieces together:
> example = do
> res <- loadImageEmb "../../doc/static/white-knight.png"
> let knightImg = case res of
> Left _ -> mempty
> Right img -> image img # sized (mkWidth 1)
> return $ mconcat
> [ knight tourStart knightImg
> , knight tourEnd knightImg
> , drawTour tour
> , chessBoard 8
> ]
> where
> tourStart = (1,3)
> tour = knightTour tourStart
> tourEnd = last tour
> main = mainWith (example :: Diagram B)