Haskell中的N-queens没有列表遍历

Question

我在网上搜索了Haskell中n-queens问题的不同解决方案,但找不到任何可以在O(1)时间内检查不安全位置的解决方案,就像你为/对角线保留一个数组而另一个用于\ diagonals.

我找到的大多数解决方案只是检查了所有以前的新女王.像这样的东西: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)方法"的最佳方法是什么？我不是在寻找任何"超级优化"的东西.只是某种方式来产生"这个对角线已经被使用了吗？" 数组以功能的方式.

更新:

感谢所有答案,伙计们!我最初问这个问题的原因是因为我想解决一个更难回溯的问题.我知道如何用命令式语言解决它,但不能轻易想到一个纯粹的功能数据结构来完成这项工作.我盘算了一下,皇后问题将是一个很好的模式(即在对整个数据结构问题回溯问题:)),但它不是我的真正的,虽然问题.

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

我认为,在Haskell中使用不可变数组可以获得同样好的解决方案,而"main"函数看起来就像我想要的那样:

-- 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 Arrays有O(n)更新.其他不错的建议没有神话般的O(1)圣杯:

• DiffArrays接近但在回溯中陷入困境.他们实际上变得非常慢:(.
• STUArrays与功能强大的回溯方法冲突,因此它们被丢弃.
• 地图和集只有O(log n)更新.

我不确定总体上有解决方案,但看起来很有希望.

更新:

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

Answer 1

可能最直接的方法是使用a 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将为您提供命令式数组,允许您以经典(非功能)方式实现该算法.

Answer 2

通常，您可能会O(log n)为功能性无损实现而支付复杂性税，否则您将不得不放弃并使用(IO|ST|STM)UArray。

严格的纯语言可能不得不为O(log n)一种不纯净的语言缴税，这种不纯净的语言可以通过类似地图的结构来实现引用，从而编写引用。懒惰的语言有时可以避开这项税收，尽管没有任何一种方法可以证明懒惰提供的额外能力是否足以避开这种税收-即使强烈怀疑懒惰还不够强大。

在这种情况下，很难看到一种可以利用懒惰来避免参考税的机制。而且，毕竟这就是为什么我们将STmonad放在首位的原因。;）

就是说，您可能会调查是否可以使用某种板对角拉链来利用更新的局部性-利用拉链中的局部性是尝试删除对数项的一种常见方法。