N-королевы в Haskell без обхода списка

Вероятно, наиболее простым способом было бы использовать UArray (Int, Int) Bool для записи безопасных / небезопасных битов. Хотя для копирования это O (n ² ), для малых значений N это самый быстрый из доступных методов.

Для больших значений N есть три основных варианта:

• Data.DiffArray удаляет накладные расходы на копирование до тех пор, пока вы больше никогда не будете использовать старые значения после их изменения . То есть, если вы всегда выбрасываете старое значение массива после его изменения, модификация будет O (1). Если, однако, вы получите доступ к старому значению массива позже (даже только для чтения), O (N ² ) оплачивается полностью.
• Data.Map и Data.Set разрешает O (lg n) модификации и поиск. Это меняет алгоритмическую сложность, но часто бывает достаточно быстро.
• Data.Array.ST ' s STUArray s (Int, Int) Bool предоставит вам императивные массивы, позволяющие реализовать алгоритм классическим (нефункциональным) способом.

Основная потенциальная проблема этого подхода состоит в том, что массивы диагоналей необходимо изменять каждый раз, когда ставится ферзь. Небольшое улучшение постоянного времени поиска диагоналей не обязательно стоит дополнительной работы по постоянному созданию новых модифицированных массивов.

Но лучший способ узнать настоящий ответ - это попробовать, поэтому я немного поигрался и пришел со следующим:

import Data.Array.IArray (array, (//), (!))
import Data.Array.Unboxed (UArray)
import Data.Set (Set, fromList, toList, delete)

-- contains sets of unoccupied columns and lookup arrays for both diagonals
data BoardState = BoardState (Set Int) (UArray Int Bool) (UArray Int Bool)

-- an empty board
board :: Int -> BoardState
board n
   = BoardState (fromList [0..n-1]) (truearr 0 (2*(n-1))) (truearr (1-n) (n-1))
   where truearr a b = array (a,b) [(i,True) | i <- [a..b]]

-- modify board state if queen gets placed
occupy :: BoardState -> (Int, Int) -> BoardState
occupy (BoardState c s d) (a,b)
   = BoardState (delete b c) (tofalse s (a+b)) (tofalse d (a-b))
   where tofalse arr i = arr // [(i, False)]

-- get free fields in a row
freefields :: BoardState -> Int -> [(Int, Int)]
freefields (BoardState c s d) a = filter freediag candidates
   where candidates = [(a,b) | b <- toList c]
         freediag (a,b) = (s ! (a+b)) && (d ! (a-b))

-- try all positions for a queen in row n-1
place :: BoardState -> Int -> [[(Int, Int)]]
place _ 0 = [[]]
place b n = concatMap place_ (freefields b (n-1))
   where place_ p = map (p:) (place (occupy b p) (n-1))

-- all possibilities to place n queens on a n*n board
queens :: Int -> [[(Int, Int)]]
queens n = place (board n) n

Это работает и для n = 14 примерно на 25% быстрее, чем версия, которую вы упомянули. Основное ускорение достигается за счет использования массивов без упаковки , рекомендованных bdonian . С обычным Data.Array он имеет примерно такое же время выполнения, что и версия, о которой идет речь.