相关疑难解决方法(0)

功能,声明和命令式编程这两个术语是什么意思？

我在网上搜索了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 -> …