Knight.hs

{-# LANGUAGE FlexibleContexts #-}

module Main where

import Control.Monad
import Control.Monad.State
import Data.Set

main :: IO ()
main = print $ solution (1, 1) == allBoard

allBoard :: Set (Int, Int)
allBoard = fromList [ (x, y) | x <- [0..7], y <- [0..7] ]

solution :: (Int, Int) -> Set (Int, Int)
solution = (`execState` empty) . go
  where
    go pos = do
      visited <- member pos <$> get
      when (not visited) $ do
        modify (insert pos)
        mapM_ go $ stepsFrom pos

stepsFrom :: (Int, Int) -> [(Int, Int)]
stepsFrom (x, y) = do
  (dx, dy) <- shifts
  let x' = x + dx
      y' = y + dy
  guard $ x' >= 0 && x' <= 7
  guard $ y' >= 0 && y' <= 7
  pure (x', y')
  where
    shifts = do
      (dx, dy) <- [(2, 1), (1, 2)]
      (sx, sy) <- do
        sx <- [1, -1]
        sy <- [1, -1]
        pure (sx, sy)
      pure (dx * sx, dy * sy)