algorithm - Haskell 中的 N 皇后没有列表遍历

Question

我在网上搜索了 Haskell 中 n 皇后问题的不同解决方案，但找不到任何可以在 O(1) 时间内检查不安全位置的解决方案，比如你为/对角线和一个用于\对角线。

我发现的大多数解决方案只是将每个新皇后与之前的所有皇后进行比较。是这样的: http://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

nqueens :: Int -> [[(Int,Int)]]
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
      safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

在 Haskell 中实现这种“O(1) 方法”的最佳方法是什么？我不是在寻找任何“ super 优化”的东西。只是一些产生“这条对角线已经被使用了吗？”的方法以功能方式排列。

更新:

谢谢大家的回答!我最初问这个问题的原因是因为我想解决一个更难的回溯问题。我知道如何用命令式语言解决它，但无法轻易想到一个纯函数式数据结构来完成这项工作。我认为皇后区问题对于整个数据结构问题来说是一个很好的模型( 回溯问题 :) )，但这不是我的真实问题.

我实际上想找到一个允许 O(1) 随机访问并保存处于“初始”状态(自由线/对角线，在 n 皇后情况下)或处于“最终”状态的值的数据结构状态(占用线/对角线)，转换(自由到占用)为 O(1)。这可以在命令式语言中使用可变数组来实现，但我觉得更新值的限制​​只允许一个很好的纯函数数据结构(与快速排序相反，例如，真的想要可变数组).

我认为 sth 的解决方案与您在 Haskell 中使用不可变数组一样好，并且“主”函数看起来像我想要的那样:

-- 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))

主要问题似乎是找到更好的数据结构，因为 Haskell 数组的更新时间为 O(n)。其他不错的建议达不到神话般的 O(1) chalice :

• DiffArrays 接近但在回溯中搞砸了。他们实际上变得 super 慢 :( .
• STUArrays 与漂亮的功能性回溯方法冲突，因此被丢弃。
• Maps 和 Sets 只有 O(log n) 更新。

我不太确定总体上是否存在解决方案，但它似乎很有希望。

更新:

我发现最有前途的数据结构是 Trailer Arrays。基本上是一个 Haskell DiffArray，但当你回溯时它会变异回来。

Answer 1

可能最直接的方法是使用 UArray (Int, Int) Bool记录安全/不安全位。尽管复制它的时间复杂度为 O(n²)，但对于较小的 N 值，这是可用的最快方法。

对于较大的 N 值，主要有以下三种选择:

• Data.DiffArray删除复制开销只要您在修改旧值后不再使用它们。也就是说，如果你总是在改变它之后丢弃数组的旧值，那么修改是 O(1)。但是，如果您稍后访问数组的旧值(即使只是读取一次)，则 O(N²) 将全额支付。
• Data.Map和 Data.Set允许 O(lg n) 修改和查找。这改变了算法的复杂性，但通常足够快。
• Data.Array.ST 的 STUArray s (Int, Int) Bool将为您提供命令式数组，使您能够以经典(非功能性)方式实现算法。