See https://github.com/reem/rust-n-queens

NQueues.hs

{-# LANGUAGE BangPatterns #-}
module NQueens where

import Data.Bits
import Control.Parallel

queue n = queensHelper (1 `shiftL` n - 1) 0 0 0

queensHelper :: Int -> Int -> Int -> Int -> Int
queensHelper !allOnes !leftDiag !columns !rightDiags =
    let validSpots = complement (leftDiag .|. columns .|. rightDiags) .&. allOnes
    in go validSpots 0
 where
   go 0 solutions = solutions + fromEnum (columns == allOnes)
   go !validSpots !solutions =
       let spot = negate validSpots .&. validSpots
           validSpots' = validSpots `xor` spot
           leftDiag'   = (leftDiag   .|. spot) `shiftL` 1
           columns'    =  columns    .|. spot
           rightDiags' = (rightDiags .|. spot) `shiftR` 1
           solutions'  = solutions +  queensHelper allOnes leftDiag' columns' rightDiags'
       in go validSpots' solutions'


parallelQueue n = parallelQueensHelper (1 `shiftL` n - 1) 0 0 0

parallelQueensHelper :: Int -> Int -> Int -> Int -> Int
parallelQueensHelper !allOnes !leftDiag !columns !rightDiags =
    let validSpots = complement (leftDiag .|. columns .|. rightDiags) .&. allOnes
    in go validSpots
 where
   go 0 = fromEnum (columns == allOnes)
   go !validSpots =
       let spot = negate validSpots .&. validSpots
           validSpots' = validSpots `xor` spot
           leftDiag'   = (leftDiag   .|. spot) `shiftL` 1
           columns'    =  columns    .|. spot
           rightDiags' = (rightDiags .|. spot) `shiftR` 1
           solutions   = queensHelper allOnes leftDiag' columns' rightDiags' -- Yes, queensHelper
           rest        = go validSpots'
       in solutions `par` rest `pseq` solutions + rest