1

この関数は終了していません! 8 x 8 のチェス盤で 8 つのクイーンに対して、考えられるすべての安全な組み合わせを生成しようとしています。何が問題なのかわかりません。私のコードは以下です。ボードは [x1, x2...x8] として表されます。ここで、値 xi は列であり、その値のインデックスは行です。

safeH 関数は、[1,4,3,5,8,6,7,2],[6,4,8,2,5,1,3,7] のように、8 つの数値のすべての組み合わせを重複なく作成する必要があります。等々...

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にも取り組んでいます。これは、私が最初にこの問題を見た場所です。これらの他の問題のいくつかを解決する簡単なコードを見たい場合は (私は実際に最適化しようとしているわけではありません。学習できるように簡単で読みやすいコードを作成してください)、https://github.com/をフォークできます。 ostrowr/99-Haskell-問題

于 2013-08-21T17:36:28.990 に答える