haskell 的骑士巡回演出获得循环

Question

我正在编写 knight 的巡回功能的代码，到目前为止我在我的 ghci 中得到了一个无限循环：

type Field = (Int, Int)

nextPositions:: Int -> Field -> [Field]
nextPositions n (x,y) = filter onBoard  
    [(x+2,y-1),(x+2,y+1),(x-2,y-1),(x-2,y+1),(x+1,y-2),(x+1,y+2),(x-1,y-2),(x-1,y+2)]  
    where onBoard (x,y) = x `elem` [1..n] && y `elem` [1..n]

type Path = [Field]

knightTour :: Int -> Field -> [Path]
knightTour n start = [posi:path | (posi,path) <- tour (n*n)]
                         where tour 1 = [(start, [])]
                               tour k = [(posi', posi:path) | (posi, path) <- tour (k-1), posi' <- (filter (`notElem` path) (nextPositions n posi))]

F.e。 knightTour 10 (4,4) 没有输出！有什么建议吗？

Answer 1

我认为主要问题之一是检查您是否去过某个广场。这需要太多时间。您应该寻找一种可以提高效率的数据结构。

对于小板，例如最大 8×8，您可以使用 64 位整数。一个64位可以看做是64个布尔值，每个布尔值代表骑士是否已经到过那个地方。

因此我们可以通过以下方式实现：

{-# LANGUAGE BangPatterns #-}

import Data.Bits(testBit, setBit)
import Data.Word(Word64)

testPosition :: Int -> Word64 -> (Int, Int) -> Bool
testPosition !n !w (!r, !c) = testBit w (n*r + c)

setPosition :: Int -> (Int, Int) -> Word64 -> Word64
setPosition !n (!r, !c) !w = setBit w (n*r + c)

nextPositions :: Int -> Word64 -> (Int, Int) -> [(Int, Int)]
nextPositions !n !w (!x, !y) = [ c
  | c@(x', y') <- [(x-1,y-2), (x-1,y+2), (x+1,y-2), (x+1,y+2), (x-2,y-1), (x-2,y+1), (x+2,y-1), (x+2,y+1)]
  , x' >= 0
  , y' >= 0
  , x' < n
  , y' < n
  , not (testPosition n w c)
  ]

knightTour :: Int -> (Int, Int) -> [[(Int, Int)]]
knightTour n p0 = go (n*n-1) (setPosition n p0 0) p0
    where go 0 _ _ = [[]]
          go !k !w !ps = [
              (ps':rs)
            | ps' <- nextPositions n w ps
            , rs <- go (k-1) (setPosition n ps' w) ps'
            ]

main = print (knightTour 6 (1,1))

如果我使用 -O2 标志和运行在本地编译这个马从 (1,1) 开始的 5×5 棋盘，所有的解决方案都在 0.32 秒内生成.对于 6×6 的板，打印第一个解决方案需要 2.91 秒，但要找到从 (1,1) 开始的所有解决方案需要很长时间。对于 8×8 的板，第一个解决方案在 185.76 秒内找到：

[(0,3),(1,5),(0,7),(2,6),(1,4),(0,2),(1,0),(2,2),(3,0),(4,2),(3,4),(4,6),(5,4),(6,2),(5,0),(3,1),(2,3),(3,5),(2,7),(0,6),(2,5),(1,3),(0,1),(2,0),(3,2),(2,4),(0,5),(1,7),(3,6),(4,4),(5,6),(7,7),(6,5),(7,3),(6,1),(4,0),(5,2),(7,1),(6,3),(7,5),(6,7),(5,5),(4,7),(6,6),(7,4),(5,3),(7,2),(6,0),(4,1),(3,3),(2,1),(0,0),(1,2),(0,4),(1,6),(3,7),(4,5),(5,7),(7,6),(6,4),(4,3),(5,1),(7,0)]

然而，用蛮力方法解决这个问题并不是一个好主意。如果我们假设平均分支因子为 ~6 步，那么对于 6×6 的棋盘，我们已经有 1.031×10²⁸ 个可能的序列，我们必须检查 6×6 的棋盘。

最好分而治之。很容易将一块 8×8 的木板分成四块 4×4 的木板。然后确定可以从一块板跳到另一块板的位置，然后解决 4×4 板的子问题。对于小板，您可以轻松存储解决方案以从 4×4 板上的任何正方形到任何其他正方形，然后 对所有象限重复使用 这些，从而节省计算量，通过不计算第二次，特别是因为您不需要多次存储对称查询。如果您知道如何在 4×4 板上从 (1,0) 转到 (2,3)，您可以轻松地使用它在同一块板上从 (3,0) 转到 (2,3)，只需通过镜像。

haskell 的骑士巡回演出获得循环

Knights tour in haskell getting a loop

loops

haskell

knights-tour