N-皇后区Haskell不列历

StackOverflow https://stackoverflow.com/questions/1255018

题

我搜索的网用于不同的解决方案的n-皇后区的问题在Haskell，但没有找到任何可能的检查不安全的职位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)

什么是最好的方式来实施这样一个"O(1)办法"，在哈斯克尔?我不是在寻找什么"超级优化".只是某种方式产生的"这是对角线已经使用？"列在功能方式。

更新：

谢谢你所有的答案，人们！我最初的问的问题是因为我想解决一个困难的回溯问题。我知道如何解决它的必要语言，但不能轻易认为的纯粹的功能的数据结构来做这项工作。我想，在皇后区的问题将是一个良好的模型(正在 的 回溯问题：))的总体数据结构问题，但这不是我的 真的 问题虽然。

实际上我想找到一个数据结构，该结构允许O(1)随机存取和保存价值，无论是在"初始"状态(免费线路/角，在n-皇后区的情况)或在一个"最终的"国家(占线/对角线)，与过渡(免费向被占)被O(1)。这可以使用的可变数组在必要的语言，但我感到，限制性的更新值只允许一个不错的纯属功能性的数据结构(而不是快速排序，例如， 真的 希望可变阵列).

我想这sth的解决方案是不如你可以得到使用不可改变的数组在哈斯克尔和"主要的"功能看起来像什么，我想这是：

-- 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)圣杯:

  • DiffArrays来接近，但乱的回溯。他们实际上得到的 超级 慢：(.
  • STUArrays冲突与漂亮的功能性跟踪的方法使它们丢弃。
  • 地图和设置有只O(日志n)更新。

我不是真的一定有一个解决方案的整体，但它 似乎 有希望的。

更新：

最有前途的数据结构，我发现那里拖阵列。基本上是一个Haskell DiffArray但它的变异，当你原路返回。

有帮助吗？

解决方案

一般的你可能会被卡支付 O(log n) 复杂的税收用于功能非破坏性实施，或者你只需要放松和使用 (IO|ST|STM)UArray.

严格的纯语言的可能要付出一个 O(log n) 税收在一种不纯语言，可以引用，通过实施引用通过地图像的结构；懒惰的语言有时可以躲避这个税，虽然没有任何证据证明任何一种方式是否额外的功率提供的懒惰足以总是躲避这个税--即使它们强烈怀疑，懒惰不是足够强大。

在这种情况下，很难看到一种机制，通过这懒惰可能会被利用，以避免的参考税。而且，毕竟，这就是为什么我们有的 ST 单在第一位。;)

这就是说，你可能会调查是否有某种局对角线的拉链可能被用来利用地方的更新--利用当地在一个拉链是一个共同的方法来尽量降对数的术语。

其他提示

也许最直接的方法是使用一个 UArray (Int, Int) Bool 记录安全/不安全的位。尽管复制这个是O(n2)，对于小价值N这是最快的方法提供。

对于较大的N值，主要有三个选项：

  • 数据。DiffArray 消除复制开销 只要你永远不会使用旧的价值观之后再次修改它们.也就是说，如果你总是抛弃旧价值的阵之后的改变，修改O(1)。但是，如果你访问旧价值的阵之后(即使只有一读)，O(N2)是支付，然后在全。
  • 数据。地图 和 数据。设置 允许O(lg n)修改和查找。这改变的算法的复杂性，但是经常的速度不够快。
  • 数据。阵列。圣的 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 它大约有相同的运行时间为该版本在这个问题。

它也可能是值得尝试的其他阵列中的类型标准图书馆看到如果使用他们可以进一步提高的性能。

我越来越怀疑 该权利要求的 那纯粹的功能是一般O(日志n)。也见Edward Kmett的答复，这使得这一要求。虽然可能适用于随机变阵列入在理论意义，但是随机的可变阵列入可能不是什么大多数的算法要求，当它是正确的研究重复性结构，即不是随机的。我认为爱德华Kmett是指这个的时候，他写道，"利用地方的更新"。

我想到的是O(1)是在理论上可能在一个纯粹的功能的版本的n-皇后区的算法，通过增加一个撤消的方法DiffArray，其中请回顾在的差异，以删除重复和避免重放他们。

如果我是正确的我理解的方式回溯n-皇后区的算法操作，则增长放缓造成的DiffArray是因为不必要的差异是被保留。

在摘要中，"DiffArray"(不一定Haskell)具有(或可能)的一组件方法，该方法回报的新副本列和储存有差异的记录的原件，包括针对新的变更副本。当原始副本需要访问一个元素，随后这一清单的差异具有重播在反对撤消该改变在复制目前的副本。注意，甚至有的开销的，这个单一的联名单已经走到年底之前，它可以重播。

想象一下，而不是这些储存作为一个双人联名单，并有一个撤销操作如下。

从一个抽象的概念层次，什么样的回溯n-皇后递归算法没有操作上的一些阵列的布尔，移动皇后的立场逐步向前在这些阵列在每个递归的水平。看看 这个动画.

工作这一点，在我的头上只有我想象的原因DiffArray是如此之慢，是因为当女王是从一个位置移到另一个，然后布尔国旗为原来的位置回到虚假的和新的职位设置为真实，这些差异被记录下来，但他们是不必要的，因为当重播在反，该阵列结束了同样的价值观，它具有以前重开始。因此，而不是使用一套操作设置回来虚假的，所需要的是一个撤销方法的话，可选用的输入参数的告诉DiffArray什么"撤消"值，以寻找在前述双链表的差异。如果，"撤消"价值差异记录在双方联名单，没有冲突的中间上的变化，同样的元件阵列中找到走的时候回来的名单搜索，以及目前价值等于"撤销"价值差异的记录，然后记录可以除去和那个老副本可以重新指出，下一次记录在双方联名单。

这是什么成就是消除不必要的复制的整个列在回溯。还有一些额外的开销，因为相比的，必须版本的算法，对于加入和撤消增加的差异的记录，但这可以接近的恒定时间，即O(1)。

如果我正确理解n-女王算法，回顾对消除操作的只有一个，所以没有走。因此，它甚至不是必要的储存差异的组件在动女王位置，因为它将被撤销之前的旧的副本将访问。我们只是需要一种方式来表达这种类型的安全，这是很容易做到的，但我将把它作为一个运动对于读者，因为这个职位是太长了。

更新：我没有写代码，用于整个算法，但是在我的头n-皇后区可以实现在每一个迭代的排，一倍以下列条对角线，其中每一元的三元组：(指数的排是占据或没有，列行交叉索引左右对角线，列行交叉索引左右斜).行可以迭代用递归或一倍的一系列行指数(折不递归).

在这里遵循的接口数据结构，我设想。下面的语法是Copute，但我认为这足够近，卡拉，你能理解什么是目的。

请注意，任何执行DiffArray将被不合理地缓慢，如果它是多线程，但n-皇后区的回溯算法并不需要DiffArray是多线程的。谢谢爱德华Kmett指出，在评论中对这个答案。

interface Array[T]
{
   setElement  : Int -> T -> Array[T]     // Return copy with changed element.
   setElement  : Int -> Maybe[T] -> Array[T]
   array       : () -> Maybe[DiffArray[T]]// Return copy with the DiffArray interface, or None if first called setElement() before array().
}
// An immutable array, typically constructed with Array().
//
// If first called setElement() before array(), setElement doesn't store differences,
// array will return None, and thus setElement is as fast as a mutable imperative array.
//
// Else setElement stores differences, thus setElement is O(1) but with a constant extra overhead.
// And if setElement has been called, getElement incurs an up to O(n) sequential time complexity,
// because a copy must be made and the differences must be applied to the copy.
// The algorithm is described here:
//    http://stackoverflow.com/questions/1255018/n-queens-in-haskell-without-list-traversal/7194832#7194832
// Similar to Haskell's implementation:
//    http://www.haskell.org/haskellwiki/Arrays#DiffArray_.28module_Data.Array.Diff.29
//    http://www.haskell.org/pipermail/glasgow-haskell-users/2003-November/005939.html
//
// If a multithreaded implementation is used, it can be extremely slow,
// because there is a race condition on every method, which requires internal critical sections.

interface DiffArray[T] inherits Array[T]
{
   unset       : () -> Array[T]        // Return copy with the previous setElement() undone, and its difference removed.
   getElement  : Int -> Maybe[T]       // Return the the element, or None if element is not set.
}
// An immutable array, typically constructed with Array( ... ) or Array().array.

更新：我的工作上 斯卡拉执行情况, ，其中有一个改进的 接口 比什么我有上述建议。我们还解释了如何优化褶皱的办法相同的恒的开销为可变阵列。

我有一个解决方案。然而，该定可能很大，所以我真的不希望打任何东西。

这里是我的数据结构：

-- | Zipper over a list of integers
type Zipper = (Bool,  -- does the zipper point to an item?
               [Int], -- previous items
                      -- (positive numbers representing
                      --   negative offsets relative to the previous list item)
               [Int]  -- next items (positive relative offsets)
               )

type State =
  (Zipper, -- Free columns zipper
   Zipper, -- Free diagonal1 zipper
   Zipper  -- Free diagonal2 zipper
   )

它允许所有需要的行动来加以执行O(1)。

代码可以在这里找到： http://hpaste.org/50707

速度是坏--这是慢于参考方案张贴在该问题上大多数投入。我根据他们对彼此的投入 [1,3 .. 15] 并得到了以下时间的比率((参考解决方案的时间/我的解决方案的时间)中%):

[24.66%, 19.89%, 23.74%, 41.22%, 42.54%, 66.19%, 84.13%, 106.30%]

注意到几乎成线性减缓准解决方案相对于地雷，显示出差异渐近的复杂性。

我的解决方案可能是在可怕的条款的严格性和这样的事情，而且必须被送到一些非常好的优化compiler(像唐*斯图尔特例如)，以获得更好的结果。

无论如何，我认为在这个问题O(1)和O(日志(n))的区分，因为日志(8)只有3和常喜欢这个主题的微优化，而不是的算法。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top