Haskell中8个女王的未知错误 [英] 8 queens unknown error in haskell

问题描述

这个函数没有终止！我试图在8乘8棋盘上为8个皇后生成所有可能的安全组合。我不确定发生了什么问题。我的代码如下。该板被表示为[x1，x2 ... x8]，其中值xi是列，并且所述值的索引是行。

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

safeD函数将比较第一个元素和所有后继元素，以确保没有皇后放置在这个皇后的对角线上（这个元素），所以
$ b $ pre $ code> queens = [[x1，x2，x3，x4，x5，x6，x7，x8] | x1 < - [1..8]，x2 < - [1..8]
，x3 < - [1..8]，x4 < - [1..8]
1，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 le =
if elem el then False
else if length（l）/ = 0 then safeH（tail l）（head l）
else True

safeD le xs n =
if last xs / = e then
if l / = 0 then
如果head l + n == e ||头l - n == e然后假
else safeD（tail l）e xs（n + 1）
else safeD（tail xs）（head xs）xs 1
else True

解决方案

根据Simon的回答评论， ，我会穿过我自己的。我希望对你更好地理解问题并理解Haskell有所帮助。显然，如果这是一个任务，你不应该提交我的代码。

公平的警告 - 我对Haskell也很新，所以我打开来自花生画廊的任何建议！

  import Data.List 
 { -  myNQueens n将解决n皇后对于n个皇后来说，给定棋盘大小nxn 
的问题。每个板由[x1，x2..xn]表示，其中索引
表示列，xi的值表示行。 - } 
 
 --type：该函数接受一个I​​nt并返回一列Ints列表。 
 myNQueens :: Int  - > [[Int]] 
  - 这是一个列表理解，可以消除safeH函数。 
  - 它检查数字[1..n]的所有排列，看它们是否代表
  - 一个合法的董事会。正如你所看到的，皇后安全只检查对角线。水平线
  - 不需要检查，因为生成排列已经花费了
  - 照顾。如果你不想使用Data.List.permutations，它不应该
  - 难以自己手动推出。 
 myNQueens n = [x | x < -  permutations [1..n]，queensSafe x] 
 
 --type：从Ints列表到bool。如果是合法委员会，则返回True，否则为False。 
 queensSafe :: [Int]  - > Bool 
  -  queensSafe是一个递归函数，用于检查第一列
  - 中的皇后是否可以被捕获。如果是这样，它将返回false。如果没有，则再次用板
调用 - 没有第一列。 
 
  -  base case：空板是安全的
 queensSafe [] = True 
  -  l @（x：xs）只是模式匹配。 x是
  -  list的第一个元素，xs是其余元素，l仅仅是
的语法糖 - 引用整个列表。 
 queensSafe l @（x：xs）
  - 这些守卫基本上是if-else语句。 
  - 如果firstQueenSafe l == True，则queensSafe x：xs = queensSafe xs。否则，错误。 
 | firstQueenSafe l == True = queensSafe xs 
 |否则= False 
 
 
 
 firstQueenSafe :: [Int]  - > Bool 
 firstQueenSafe l @（x：xs）= 
  -  unsafe1生成所有不安全对角线向下和向右的列表。 
  -  unsafe2生成所有不安全对角线的列表，并在左边。 
 let unsafe1 = [x，x  -  1 .. x  -  length l] 
 unsafe2 = [x，x + 1 .. x + length l] 
  - 压缩仅对unsafe1和unsafe2与实际板的副本
  - （除了第一个元素）。如果任何元组包含2个相同的值，
  - 那么板是不安全的。 
 zipped = zip（tail unsafe1）（tail l）++ zip（tail unsafe2）（tail l）
  -  countMatches只是检查压缩文件中是否有匹配。 
 countMatches =长度[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>长度$ myNQueens 8  - 在大约一秒钟内运行
 92 
 * Main>长度$ myNQueens 9  - 在约20秒内运行
 352 
 * Main>长度$ myNQueens 10  - 在几分钟内运行
 724 
  

学习你一个Haskell 和真实世界Haskell a>都是非常好的资源。我也在通过 99个Haskell问题，这是我最初的地方看到了这个问题。如果你想看到一些简单的代码来解决其他一些问题，（我没有真的想优化，只是简单易懂的代码，所以我可以学习），你可以fork https://github.com/ostrowr/99-Haskell-Problems

This function isn't terminating! I'm trying to generate all possible safe combinations on an eight by eight chessboard for eight queens. I'm not sure what's going wrong. My code is below. The board is represented as [x1, x2...x8] where the value xi is the column, and the index of said value is the row.

the safeH function should create all the combinations of eight numbers without duplications for example [1,4,3,5,8,6,7,2],[6,4,8,2,5,1,3,7] and so on...

the safeD function will compare the first element with all successors elements to ensure that there is no queen placed on the diagonal of this queen(this element) and so on ..

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

解决方案

As per the comments on Simon's answer, rather than fix your code, I'll step through my own. I hope it's useful for you to get a better understanding of the problem and understand Haskell a little better. Obviously, if this is for an assignment, you shouldn't submit my code.

Fair warning -- I'm very new to Haskell too, so I'm open to any suggestions from the peanut gallery!

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

Obviously, this is non-optimal, but I think it's pretty clear. And quite a short piece of code! Just to show that it works:

*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 and Real World Haskell are both really good resources. I'm also working through 99 Haskell Problems, which is where I originally saw this problem. If you'd like to see some simple code that solves some of these other problems, (I'm not really trying to optimize, just make easy and readable code so I can learn) you can fork https://github.com/ostrowr/99-Haskell-Problems

这篇关于Haskell中8个女王的未知错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！