Почему рыцарь не покрывает весь стол?

Question

Я хочу, чтобы рыцарь начал с (1,1) и попытался двигаться по всему столу. Это мой код:

canMove :: (Int -> Int) -> (Int -> Int) -> [(Int,Int)] -> Bool 

canMove (x) (y) list 
     | (x (fst lastMove),y (snd lastMove)) `elem` list = False 
     | newX> 8 || newY> 8 || newX<=0 || newY<=0 = False 
     | otherwise = True 
     where lastMove = last list 
       newX = x (fst lastMove) 
       newY = y (snd lastMove) 

move :: [(Int, Int)] -> [(Int, Int)] 
move list 
    | length list == 64 = list 
    | canMove (+1) (+2) list = move (list ++ [(x+1,y+2)]) 
    | canMove (+2) (+1) list = move (list ++ [(x+2,y+1)]) 
    | canMove (subtract 1) (+2) list = move (list ++ [(x-1,y+2)]) 
    | canMove (subtract 2) (+1) list = move (list ++ [(x-2,y+1)]) 
    | canMove (subtract 1) (subtract 2) list = move (list ++ [(x-1,y-2)]) 
    | canMove (subtract 2) (subtract 1) list = move (list ++ [(x-2,y-1)]) 
    | canMove (+1) (subtract 2) list = move (list ++ [(x+1,y-2)]) 
    | canMove (+2) (subtract 1) list = move (list ++ [(x+2,y-1)]) 
    | otherwise = list 
    where lastMove = last list 
     x = fst lastMove 
     y = snd lastMove 

y=length (move [(1,1)]) 

main = print $ y 

Почему рыцарь после остановки 34 шагов?

Answer 1

Я предполагаю, что вы пытаетесь решить проблему knight's tour в Haskell. В этом случае ваша проблема заключается в том, что вы используете жадный алгоритм, который не удается решить проблему рыцаря. Если вы удалите length из своей функции y, вы увидите путь, выбранный вашим алгоритмом.

[(1,1),(2,3),(3,5),(4,7),(6,8),(5,6),(7,7),(5,8),(4,6),(6,7), 
(8,8),(7,6),(5,7),(7,8),(6,6),(8,7),(7,5),(6,3),(8,4),(6,5), 
(8,6),(7,4),(5,5),(3,6),(4,8),(2,7),(1,5),(3,4),(2,6),(3,8), 
(1,7),(2,5),(3,7),(1,8)] 
-- From (1,8), we can go to either (4,6) or (3,5). 
-- But we've already been to both of those positions. 

Проще говоря, ваш рыцарь сделал «неправильный» поворот на какой-то момент и получил сам застрял в положении, когда она не могла выйти без повторения позиции. Чтобы обойти это, вам нужно использовать какой-то алгоритм обратного отслеживания, так что, когда рыцарь допустит такую ​​ошибку, он может отменить свои действия и попробовать что-то еще. К счастью для вас, Haskell делает это относительно легко с монадой списка. Если вы не знакомы с монадами, они неотъемлемы от Haskell, и вы можете узнать о них here.