N皇后Haskell中没有列表的遍历 [英] N-queens in Haskell without list traversal

问题描述

我在网上搜索不同的解决方案，在Haskell N皇后问题，但找不到任何可以为O检查不安全的位置（1）的时间，这样的一个你保持一个数组用于/对角线和一个用于\对角线

I searched the web for different solutions to the n-queens problem in Haskell but couldn't find any that could check for unsafe positions in O(1) time, like that one that you keep an array for the / diagonals and one for the \ diagonals.

大多数解决方案，我发现刚才检查每一个新的女王对所有的previous的。事情是这样的： http://www.reddit.com/r/programming/评论/ 62j4m / nqueens％5Fin％5Fhaskell /

Most solutions I found just checked each new queen against all the previous ones. Something like this: http://www.reddit.com/r/programming/comments/62j4m/nqueens%5Fin%5Fhaskell/

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）办法的最佳方法是什么？ 我不是在寻找什么超优化。只是一些方法，以生产这是对角已被使用？阵列以功能性方式。

What would be the best way to implement such an "O(1) approach" in Haskell? I am not looking for anything "super-optimized". Just some way to produce the "is this diagonal already used?" array in a functional manner.

更新：

感谢所有的答案，乡亲们！我之所以当初问的问题是，因为我想解决一个困难回溯问题。我知道如何解决它的命令式语言，但不能轻易认为纯功能数据结构来完成这项工作的。我想，在皇后问题将是一个很好的模式（是的在的回溯问题:)），为整体数据结构的问题，但它不是我的真正的问题，但

Thanks for all the answers, folks! The reason I originally asked the question is because I wanted to solve a harder backtracking problem. I knew how to solve it in an imperative language but could not readily think of a purely functional data structure to do the job. I figured that the queens problem would be a good model (being the backtracking problem :) ) for the overall data-structure problem, but it isn't my real problem though.

其实我是想找到一个数据结构，使O（1）随机访问，认为是无论是在初始状态值（免费线/对角线，在N皇后的情况下），或在最终状态（占据线/对角线），与转换（随意占用）为O（1）。 这可以通过使用可变数组在命令式语言来实现，但我觉得，更新值的限制​​，只允许一个不错的纯函数的数据结构（相对于快速排序，例如，的真正的希望可变阵列）。

I actually want to find a data structure that allows O(1) random access and holds values that are either on a "initial" state (free line/diagonal, in the n-queens case) or in a "final" state (occupied line/diagonal), with transitions (free to occupied) being O(1). This can be implemented using mutable arrays in an imperative language but I feel that the restriction of updating values only allows for a nice purely functional data structure (as opposed to Quicksort, for example, that really wants mutable arrays).

我想某事的解决方案是一样好，你可以得到使用哈斯克尔不变的阵列和主的功能看起来像什么，我想它是：

I figure that sth's solution is as good as you can get using immutable arrays in Haskell and the "main" function looks like what I wanted it to be:

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

主要的问题似乎是，虽然找到一个更好的数据结构，哈斯克尔数组有O（n）的更新。 另外还有个不错的建议功亏一篑神话中澳（1）圣杯：

The main problem seems to be finding a better data structure though, as Haskell Arrays have O(n) updating. Other nice suggestions fall short of the mythical O(1) holy grail:

• DiffArrays进来回溯接近，但陷入困境。他们实际上得到的超的慢:(。
• 与pretty的功能回溯的方式，使他们被丢弃STUArrays冲突。
• 地图及套装只有O（log n）的更新。

• DiffArrays come close but mess up in the backtracking. They actually get super slow :( .
• STUArrays conflict with the pretty functional backtracking approach so they are discarded.
• Maps and Sets have only O(log n) updating.

我真的不知道有一个整体的解决方案，但它的似乎的有前途的。

I am not really sure there is a solution overall, but it seems promising.

更新：

最有前途的数据结构，我发现，其中拖车阵列。基本上一个Haskell DiffArray但它发生变异回来时，你原路返回。

The most promising data structure I found where Trailer Arrays. Basically a Haskell DiffArray but it mutates back when you backtrack.

推荐答案

在一般的你可能会被卡住支付 O（log n）的的复杂性税款，但功能非破坏性的执行，或者你将不得不松口，并使用（IO | ST | STM）UArray 。

In general you are probably going to be stuck paying the O(log n) complexity tax for a functional non-destructive implementation or you'll have to relent and use an (IO|ST|STM)UArray.

严格的纯语言可能需要支付 O（log n）的税收过，可以通过实现通过地图状结构引用写入引用不纯的语言;懒惰的语言有时会躲过此税，虽然目前还没有证据证明任何一种方式被惰性所提供的额外的电源是否足以总是躲闪这种税收 - 即使它强烈怀疑懒惰不够强大。

Strict pure languages may have to pay an O(log n) tax over an impure language that can write to references by implementing references through a map-like structure; lazy languages can sometimes dodge this tax, although there is no proof either way whether or not the extra power offered by laziness is sufficient to always dodge this tax -- even if it is strongly suspected that laziness isn't powerful enough.

在此情况下，它是很难看到通过该懒惰可能被利用，以避免参考税的机制。而且，毕竟这就是为什么我们有 ST 单子摆在首位。 ;）

In this case it is hard to see a mechanism by which laziness could be exploited to avoid the reference tax. And, after all that is why we have the ST monad in the first place. ;)

这就是说，你可能会探讨一些板斜拉链与否可以被用来利用更新的地方 - 一个拉链利用地方是一种常见的方式来尝试删除一个对数项

That said, you might investigate whether or not some kind of board-diagonal zipper could be used to exploit locality of updates -- exploiting locality in a zipper is a common way to try to drop a logarithmic term.

这篇关于N皇后Haskell中没有列表的遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！