Skip to content

Instantly share code, notes, and snippets.

@tronje
Last active October 10, 2019 18:54
Show Gist options
  • Save tronje/cf1ec8f05b854ff488760dce396a1f5f to your computer and use it in GitHub Desktop.
Save tronje/cf1ec8f05b854ff488760dce396a1f5f to your computer and use it in GitHub Desktop.
Eight Queens puzzle in Haskell
#!/usr/bin/env runhaskell
{-
0 1 2 3 4 5 6 7
0 □ ■ □ ■ □ ■ □ ■
1 ■ □ ■ □ ■ □ ■ □
2 □ ■ □ ■ □ ■ □ ■
3 ■ □ ■ □ ■ □ ■ □
4 □ ■ □ ■ □ ■ □ ■
5 ■ □ ■ □ ■ □ ■ □
6 □ ■ □ ■ □ ■ □ ■
7 ■ □ ■ □ ■ □ ■ □
-}
import System.Environment (getArgs)
-- a Queen has two coordinates
data Queen = Queen { x :: Int
, y :: Int
} deriving (Eq)
-- make string representation of Queens a bit more
-- readable, especially if we were to print a list of 'em
instance Show Queen where
show (Queen x y) = " Q (" ++ show x ++ "," ++ show y ++ ") "
-- see if two Queens are attacking one another
attacking :: Queen -> Queen -> Bool
attacking (Queen x1 y1) (Queen x2 y2)
-- same row or column
| (x1 == x2) || (y1 == y2) = True
-- same diagonal
| abs (x1 - x2) == abs (y1 - y2) = True
| otherwise = False
-- a Queen can be placed if no other queens are attacking its position
placeable :: Queen -> [Queen] -> Bool
placeable try [] = True
placeable try (q:qs) = if try `attacking` q
then False
else placeable try qs
-- generate all configurations of n Queens on an nxn chessboard,
-- where no two Queens are attacking one another
nQueens :: Int -> [[Queen]]
nQueens n = map reverse $ nQueens' n where
nQueens' 0 = [[]]
nQueens' k =
let prevQs = nQueens' (k - 1)
legalQs = [Queen (k - 1) y | y <- [0 .. n - 1]]
in [q:qs | qs <- prevQs, q <- legalQs, placeable q qs]
-- print a list of lists (of Queens) in a more readable fashion
printQs :: [[Queen]] -> IO ()
printQs [] = putChar '\n'
printQs (q:qs) = do
putStrLn $ show q
printQs qs
-- assume first arg can be interpreted as an integer, and use that as `n`
-- for the nQueens computation
main :: IO ()
main = do
args <- getArgs
let n = read $ head args
printQs $ nQueens n
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment