{- |
Description: Find all solutions to the \(n\) queens problem
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P90" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P90 (queens) where

-- | Solve the extended eight queens problem for arbitrary \(n\).
--
-- Represent the positions of the queens as a list of numbers from 1 to \(n\).
queens :: Int -> [[Int]]
queens :: Int -> [[Int]]
queens Int
n = [(Int, Int)] -> Int -> [Int] -> [[Int]]
enumerate [] Int
1 [Int
1..Int
n]

enumerate :: [(Int, Int)] -> Int -> [Int] -> [[Int]]
enumerate :: [(Int, Int)] -> Int -> [Int] -> [[Int]]
enumerate [(Int, Int)]
assigned Int
_ [] = [((Int, Int) -> Int) -> [(Int, Int)] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, Int) -> Int
forall a b. (a, b) -> b
snd [(Int, Int)]
assigned]
enumerate [(Int, Int)]
assigned Int
column [Int]
remainingRows = (Int -> [[Int]]) -> [Int] -> [[Int]]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Int -> [[Int]]
expand [Int]
possibleRows
  where expand :: Int -> [[Int]]
expand Int
r = [(Int, Int)] -> Int -> [Int] -> [[Int]]
enumerate ((Int
column, Int
r) (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
forall a. a -> [a] -> [a]
: [(Int, Int)]
assigned) (Int
columnInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int -> [Int]
rowExcluded Int
r)
        rowExcluded :: Int -> [Int]
rowExcluded Int
r = (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Int
r /=) [Int]
remainingRows
        possibleRows :: [Int]
possibleRows = (Int -> Bool) -> [Int] -> [Int]
forall a. (a -> Bool) -> [a] -> [a]
filter (Bool -> Bool
not (Bool -> Bool) -> (Int -> Bool) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, Int)] -> Int -> Int -> Bool
attacksPrevious [(Int, Int)]
assigned Int
column) [Int]
remainingRows

attacksPrevious :: [(Int, Int)] -> Int -> Int -> Bool
attacksPrevious :: [(Int, Int)] -> Int -> Int -> Bool
attacksPrevious [(Int, Int)]
assigned Int
column Int
row = ((Int, Int) -> Bool) -> [(Int, Int)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (Int, Int) -> Bool
attacks [(Int, Int)]
assigned
  -- Due to how rows are extracted to be assigned at each column,
  -- no queen can attack another via row or column.
  where attacks :: (Int, Int) -> Bool
attacks (Int
c, Int
r) = Int -> Int
forall a. Num a => a -> a
abs (Int
column Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
c) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int -> Int
forall a. Num a => a -> a
abs (Int
row Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
r)