在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）方法”呢？我不想要任何“超级优化”的东西。只是以函数式方式生成“这个对角线已经被使用了吗？”数组的一些方法。

更新：感谢大家的回答！我最初提出这个问题的原因是想解决一个更难的回溯问题。我知道如何在命令式语言中解决它，但无法立即想到一个纯函数数据结构来完成工作。我觉得皇后问题将是一个很好的模型（是回溯问题 :)）来解决整个数据结构问题，但这并不是我的真正问题。

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

我认为sths的解决方案是利用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) 的神话标准:

- DiffArrays 接近但在回溯时会出现问题。它们实际上变得超级慢 :( - STUArrays 与漂亮的函数式回溯方法相冲突，所以被舍弃了。 - 映射和集合只有 O(log n) 的更新时间。

我并不确定是否存在全局解决方案，但这似乎是一个有前途的方向。 更新: 我找到的最有希望的数据结构是 Trailer Arrays。基本上是一个 Haskell DiffArray，但在回溯时它会恢复原样。

- hugomg

---

Haskell中是否有实现用于尾部的数组？ - is7s

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将为您提供命令式数组，使您能够以经典（非函数式）方式实现算法。

- bdonlan

---

我以为数组更新的时间复杂度是O(n)，会破坏算法的复杂度。我错了吗？ - hugomg

更新 - 你是对的，但对于小的N来说仍然更便宜 :) - bdonlan

Answer 2

一般来说，如果要实现一个功能性的非破坏性实现，您可能会被迫支付复杂度为 O(log n) 的“税款”，或者不得不使用 (IO|ST|STM)UArray。严格纯函数语言可能要比非纯函数语言多付出一个 O(log n) 的代价，因为可以通过实现类似于映射结构的引用来写入引用；而懒惰语言有时可以避免这种情况，尽管无法证明懒惰的额外能力是否足以总是避免这种情况——即使强烈怀疑懒惰并不够强大。

在这种情况下，很难找到一种机制来利用延迟计算来避免引用 “税”。毕竟这就是我们首先拥有 ST 单子的原因。 ;)

也就是说，您可能需要调查一下是否可以使用某种棋盘对角线拉链来利用更新的本地性——在拉链中利用本地性是试图消除对数项的常见方式。

- Edward Kmett

Answer 3

我对纯函数通常是O(log n)的说法开始持怀疑态度。请参考Edward Kmett的回答，他提出了这种说法。虽然在理论意义上，这可能适用于随机可变数组访问，但当正确地研究可重复结构时，随机可变数组访问可能不是大多数算法所需的。我认为Edward Kmett在写“利用更新的局部性”时指的就是这一点。

我认为在n皇后问题的纯函数版本中，通过为DiffArray添加一个撤消方法，可以在理论上实现O(1)，该方法请求查看差异以删除重复项并避免重播它们。

如果我对回溯n皇后算法的运行方式的理解是正确的，那么由于保留了不必要的差异，DiffArray引起的减速就是因为它们被保留了下来。

在抽象层面上，“DiffArray”（不一定是Haskell的）具有（或可能具有）一个设置元素方法，该方法返回数组的新副本并存储原始副本的差异记录，包括指向新更改副本的指针。当原始副本需要访问元素时，必须以相反的顺序重放这些差异列表，以撤消当前副本的更改。请注意，甚至必须遍历此单链表到末尾，然后才能重放它。

想象一下，如果将它们存储为双向链接列表，并且有一个撤销操作，会怎样。

从抽象概念层面上看，回溯n皇后算法所做的是递归地操作一些布尔数组，在每个递归级别上逐步向前移动皇后的位置。参见this animation。

我在脑海中思考后发现 DiffArray 很慢的原因是，当皇后从一个位置移动到另一个位置时，原始位置的布尔标志被设为 false，新位置的标志被设置为 true，并记录这些差异，但这些差异是不必要的，因为在反向回放时，数组的值与回放开始前的值相同。因此，需要的不是使用 set 操作将其设回 false，而是需要撤消方法调用，可选地带有输入参数，告诉 DiffArray 在上述差异的双向链表中搜索“撤消至”哪个值。如果在双向链表中的差异记录中找到了该“撤消至”值，则在返回列表搜索时未找到相同数组元素的冲突中间更改，且当前值等于该差异记录中的“撤消自”值，则可以删除该记录并将旧副本重新指向双向链表中的下一个记录。

这样做的目的是消除整个数组在回溯时不必要的复制。与算法的命令式版本相比，仍存在一些额外的开销，用于添加和撤消差异记录，但这可以更接近于常数时间，即 O(1)。

如果我正确理解了n皇后算法，那么撤销操作的回溯只有一步，所以不存在行走。因此，在移动皇后位置时，不需要存储集合元素的差异，因为在访问旧副本之前，它将被撤销。我们只需要一种安全地表示这种类型的方法，这很容易做到，但由于这篇文章已经太长了，我将把它留给读者作为练习。

---

更新：我还没有编写完整算法的代码，但是在我的脑海中，n皇后问题可以通过对以下对角线数组进行折叠来实现，其中每个元素是三元组，包括：（占用它的行的索引或None、与左右对角线相交的行索引数组、与右左对角线相交的行索引数组）。可以使用递归或行索引数组的折叠来迭代行（折叠执行递归）。

以下是我设想的数据结构的接口。下面的语法是Copute，但我认为它与Scala非常接近，你应该能够理解意图。

请注意，如果DiffArray是多线程的，则任何DiffArray的实现都会变得不合理地慢，但是n皇后回溯算法不需要DiffArray是多线程的。感谢Edward 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:
//    https://dev59.com/Q3M_5IYBdhLWcg3wt1vD#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.

---

更新：我正在开发Scala实现，与我之前建议的相比，它具有改进的界面。我还解释了如何通过对折叠进行优化，使其拥有与可变数组相同的恒定开销。

- Shelby Moore III

---

我已经有一段时间没有看过这个问题了，但我认为它并不简单... - hugomg

我正在进行一项实现工作，稍后我会在这里汇报。 - Shelby Moore III

回溯 N 皇后算法是一个递归函数，它接受 3 个参数：每个对角线方向（\ 和 /）的数组和行计数。它在该行上迭代列，在数组中移动皇后位置，并在每个列位置上使用 cur_row + 1 递归自身。所以在我描述的情况下，皇后在数组中的移动似乎是可撤销的。看起来太容易了，不是吗？所以请有人告诉我为什么，否则我将在代码实现中找到答案。 - Shelby Moore III

Haskell的DiffArray实现具有非常不幸的性能特征，试图在多个线程中潜在地维护一个焦点需要大量的秘密约会和同步。在算法中使用MVar丢失了2-3个数量级，淹没了其他因素。关于“对数因子”，我只提到它适用于某些情况，但在严格的纯语言中，它肯定适用于某些算法，如并查集。我故意说“可能”，因为也许可以有创造性地分摊更新的总数量以在此处下降。 - Edward Kmett

@ShelbyMooreIII: 我认为你对于使用双向链表的描述与我最初为我的祖先集合设计的相同，但我最终放弃了它，因为实现起来太困难了。问题在于列表中的额外链接使得历史记录永久可达，因此如果您希望您的撤消/重做数据由垃圾收集器收集，则需要使用弱引用。最终，我选择了形成撤销/重做缓冲区的单向链表。结果非常简单但仍然有用。事实上，它非常简单，几乎没有新意。只是明显的DiffList的Set/Map等价物。 - J D

顺便提一下，对此的另一个看法是，算法使用纯函数集合且不利用持久性的情况下，可以线性编写并优化为使用命令式集合，而不会（我认为）牺牲纯度。也许 Rust 可以做到这一点？ - J D

Answer 4

这种方法的基本潜在问题是，每次放置皇后时都需要修改对角线的数组。虽然对角线的常数查找时间略有改善，但不一定值得不断创建新的修改数组所付出的额外工作。

但了解真正的答案最好的方法就是尝试一下，所以我进行了一些实验，并想出了以下解决方案：

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

这个版本比你提到的版本快了大约25％，适用于n = 14。主要的加速来自使用bdonian推荐的非装箱数组。与普通的Data.Array相比，它的运行时间大致相同。

也许值得尝试一下标准库中的其他数组类型，看看是否可以进一步提高性能。

- sth

Answer 5

我有一个解决方案。但是常数可能很大，所以我不指望能打败什么。

这是我的数据结构：

-- | 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％]

请注意，相对于我的解决方案，参考解决方案的减速几乎是线性的，显示了渐近复杂度的差异。

我的解决方案在严格性和类似的事情方面可能很糟糕，必须提供给一些非常好的优化编译器（例如Don Stewart）以获得更好的结果。

无论如何，在这个问题中，我认为O(1)和O(log(n))无法区分，因为log(8)只是3，像这样的常数是微观优化的主题，而不是算法。

- Rotsor