Skip to content

Instantly share code, notes, and snippets.

@MgaMPKAy
Created April 27, 2014 02:32
Show Gist options
  • Save MgaMPKAy/11336339 to your computer and use it in GitHub Desktop.
Save MgaMPKAy/11336339 to your computer and use it in GitHub Desktop.
{-# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment