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

问题描述

我在网络上搜索了Haskell中的n-queens问题的不同解决方案，但是在O（1）时间里找不到任何可以检查不安全的位置的东西，就像那个保存/对角线的阵列一样，一个用于\对角线。

大多数解决方案，我发现刚刚检查每个新的女王对所有以前的。这样的：
http://www.reddit.com / r / programming / comments / 62j4m / nqueens_in_haskell /

  nqueens :: Int  - > [[（Int，Int）]] 
 nqueens n = foldr qu [[]] [1..n] 
其中qu k qss = [（（j，k）：qs）| qs<  -  qss，j<  -  [1..n]，all（safe（j，k））qs] 
 safe（j，k）（l，m）= j / & k / = m&& abs（jl）/ = abs（km）
  

什么是实现这样一个 O（1）方法在Haskell？
我不寻找任何超优化。只是一些方法来产生这个对角线已经被使用了吗？

更新：

感谢所有的答案，伙计！我原来问这个问题的原因是因为我想解决一个更难的回溯问题。我知道如何用强制性的语言来解决它，但是不能容易地想到一个纯功能的数据结构来完成这项工作。我认为皇后问题对于整体数据结构问题来说将是一个很好的模式（正在 回溯问题:)），但这并不是我真正的问题，

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

我认为sth的解决方案与在Haskell中使用不可变数组一样好，main函数看起来像我想要的成为：

   - 尝试排列n-1中的女王的所有职位
 place :: BoardState  - > ; Int  - > [[（Int，Int）]] 
 place _ 0 = [[]] 
 place bn = concatMap place_（freefields b（n-1））
 where place_ p = map :)（place（占用bp）（n-1））
  

主要问题似乎是找到更好的数据结构，因为Haskell数组有O（n）更新。
其他不错的建议不符合神圣的O（1）圣杯：

• DiffArrays接近但在回溯中混乱。他们实际上得到超级慢:(。


• STUArrays与相当功能的回溯方法冲突，所以它们被丢弃。


• 地图和集只有O（log n）更新。

我不太确定总体上有一个解决方案， >似乎承诺。

更新：

最有希望数据结构我发现Trailer Arrays在哪里，基本上是Haskell DiffArray，但是当你回溯时，它会变回。

解决方案

将被困在支付 O（log n）复杂性税的功能非破坏性实现，否则您将不得不放弃并使用（ IO | ST | STM）UArray 。

严格的纯语言可能需要支付 O（log n） / code>通过使用类似地图的结构实现引用来写入引用的不纯的语言税收;懒惰语言可能有时躲避这个税，虽然没有任何一种证明，无论懒惰提供的额外权力是否足以总是避免这种税 - 即使强烈怀疑懒惰不够强大。

在这种情况下，很难看到可以利用懒惰避免引用税的机制。而且，这就是为什么我们首先有 ST monad。 ;）

这样说，你可能会调查是否可以使用某种板对角拉链来利用更新的位置 - 利用拉链中的地点是通常的方式来尝试删除一个对数项。

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.

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

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.

UPDATE:

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.

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

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

UPDATE:

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

解决方案

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.

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.

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.

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