1

此功能不会终止！我正在尝试为八个皇后在八乘八棋盘上生成所有可能的安全组合。我不确定出了什么问题。我的代码如下。棋盘表示为 [x1, x2...x8]，其中值 xi 是列，该值的索引是行。

safeH 函数应该创建八个数字的所有组合而不重复，例如 [1,4,3,5,8,6,7,2],[6,4,8,2,5,1,3,7]等等...

safeD 函数会将第一个元素与所有后继元素进行比较，以确保没有皇后放置在该皇后（该元素）的对角线上，依此类推..

queens = [ [x1,x2,x3,x4,x5,x6,x7,x8] | x1 <- [1..8], x2 <- [1..8]
                                     , x3 <- [1..8], x4 <- [1..8]
                                     , x5 <- [1..8], x6 <- [1..8]
                                     , x7 <- [1..8], x8 <- [1..8]
                                     , safeH [x2,x3,x4,x5,x6,x7,x8] x1
                                     , safeD [x2,x3,x4,x5,x6,x7,x8] x1
                                             [x1,x2,x3,x4,x5,x6,x7,x8] 1 ]

safeH l e =
  if elem e l then False
  else if length (l)/=0 then safeH(tail l)(head l)
       else True

safeD l e xs n =
  if last xs /= e then
    if length l /= 0 then
      if head l + n == e || head l - n == e then False
      else safeD (tail l) e xs (n + 1)
    else safeD (tail xs) (head xs) xs 1
  else True
4

2 回答 2

4

根据对西蒙回答的评论，我不会修复您的代码，而是逐步完成我自己的。我希望它对您更好地理解问题并更好地理解 Haskell 有所帮助。显然，如果这是为了作业，您不应该提交我的代码。

公平警告——我对 Haskell 也很陌生，所以我愿意接受花生画廊的任何建议！

import Data.List
{- myNQueens n will solve the n-queens problem for the given board-size nxn 
   for n queens. Each board is represented by [x1, x2..xn] where the index
   represents the column and the value of xi represents the row. -} 

--type: this function takes an Int and returns a list of lists of Ints.
myNQueens :: Int -> [[Int]]
-- here is a list comprehension that does away with your safeH function.
-- it checks all permutations of the numbers [1..n] to see if they represent
-- a legal board. As you'll see, queensSafe only checks diagonals. Horizontals
-- do not need to be checked because generating the permutations already takes
-- care of that. If you'd prefer not to use Data.List.permutations, it shouldn't
-- be too hard to hand-roll your own.
myNQueens n = [x | x <- permutations [1..n], queensSafe x]

--type: from list of Ints to bool. Returns True if legal board, else False.
queensSafe :: [Int] -> Bool
-- queensSafe is a recursive function that checks if the queen in the first column
-- can be captured. If so, it returns false. If not, it is called again with the board
-- without the first column.

-- base case: the empty board is safe
queensSafe [] = True
-- l@(x:xs) is just pattern matching. x is the first element of the
-- list, xs is the remaining elements, and l is just syntactic sugar for
-- referencing the whole list.
queensSafe l@(x:xs)
-- these "guards" are basically if-else statements.
-- if firstQueenSafe l == True then queensSafe x:xs = queensSafe xs. else, False.
    | firstQueenSafe l == True = queensSafe xs
    | otherwise = False



firstQueenSafe :: [Int] -> Bool
firstQueenSafe l@(x:xs) =
    -- unsafe1 generates a list of all of the unsafe diagonals down and to the right.
    -- unsafe2 generates a list of all of the unsafe diagonals up and to the left.
    let unsafe1 = [x, x - 1 .. x - length l]
        unsafe2 = [x, x + 1 .. x + length l]
        -- zipped just pairs unsafe1 and unsafe2 with copies of the actual board 
        -- (except the first element.) If any of tuples contain 2 of the same values,
        -- then the board is unsafe.
        zipped = zip (tail unsafe1) (tail l) ++ zip (tail unsafe2) (tail l)
        -- countMatches just checks if there are any matches in zipped.
        countMatches = length [x | x <- zipped, fst x == snd x]
    in if countMatches == 0 then True else False

显然，这是非最佳的，但我认为这很清楚。还有很短的一段代码！只是为了证明它有效：

*Main> head $ myNQueens 8
[6,4,7,1,3,5,2,8]
*Main> head $ myNQueens 9
[6,3,5,8,1,4,2,7,9]
*Main> head $ myNQueens 10
[7,5,8,2,9,3,6,4,1,10]
*Main> length $ myNQueens 8 -- runs in about a second
92
*Main> length $ myNQueens 9 -- runs in about 20 seconds
352
*Main> length $ myNQueens 10 -- runs in a couple of minutes
724

Learn You a Haskell和Real World Haskell都是非常好的资源。我也在处理99 Haskell Problems，这是我最初看到这个问题的地方。如果你想看一些简单的代码来解决其他一些问题，（我并不是真的在尝试优化，只是制作简单易读的代码以便我可以学习）你可以 fork https://github.com/ ostrowr/99-Haskell-问题

于 2013-08-21T17:36:28.990 回答
3

为了计算queens，必须遍历 8^8 = 16777216 个案例，每个案例都受safeH和的约束safeD。这需要相当长的时间。

queens = [ [x1,x2,x3,x4,x5,x6,x7,x8] | x1 <- [1..8], x2 <- [1..8]
                                     , x3 <- [1..8], x4 <- [1..8]
                                     , x5 <- [1..8], x6 <- [1..8]
                                     , x7 <- [1..8], x8 <- [1..8]

您可以查看其他人如何解决Haskell 中的 8-queens 问题。

于 2013-08-20T18:28:40.180 回答