Haskell: Knight Tour nie zu Ende, wenn ich mehr als 55 Schritte versuche?

Question

Dies ist mein Code:

maxX=8; maxY=8; 
maxSteps=60 -- If I change maxSteps=55 I get an answer 
move :: [(Int, Int)] -> [(Int, Int)] 
move list 
    | lastX>maxX || lastY>maxY || lastX<=0 || lastY<=0 = [] 
    | lastMove `elem` (init list) = [] 
    | length list == maxSteps = list 
    | length m1 == maxSteps = m1 
    | length m2 == maxSteps = m2 
    | length m3 == maxSteps = m3 
    | length m4 == maxSteps = m4 
    | length m5 == maxSteps = m5 
    | length m6 == maxSteps = m6 
    | length m7 == maxSteps = m7 
    | length m8 == maxSteps = m8 
    | otherwise = [] 
    where lastMove = last list 
     lastX = fst lastMove 
     lastY = snd lastMove 
     m1 = move (list ++ [(lastX+1,lastY+2)]) 
     m2 = move (list ++ [(lastX+2,lastY+1)]) 
     m3 = move (list ++ [(lastX-1,lastY+2)]) 
     m4 = move (list ++ [(lastX-2,lastY+1)]) 
     m5 = move (list ++ [(lastX+1,lastY-2)]) 
     m6 = move (list ++ [(lastX+2,lastY-1)]) 
     m7 = move (list ++ [(lastX-1,lastY+2)]) 
     m8 = move (list ++ [(lastX-2,lastY-1)]) 
y = move [(1,1)] 
main = print $ y 

Wissen Sie, warum es nie zu Ende (Vielleicht kann ich mehr warten ...)? Haben Sie eine andere Lösung, um den gleichen Brute-Force-Algorithmus zu implementieren, aber schneller?

Answer 1

Es beendet (es läuft für etwa 1 Minute auf meinem Computer) und produziert eine richtige Antwort.

Ein einfacher Weg, um es zu beschleunigen, ist eine neue Bewegung an der Vorderseite der Liste hinzufügen (und das Ergebnis vor dem Drucken umkehren). Das Hinzufügen des ersten Elements dauert konstant, während ein Element an der Rückseite der Liste linear in seiner Größe angefügt wird.

Es gibt auch einen Fehler in Ihrem Code: m3 und m7 sind gleich. diesen Fehler und das Hinzufügen der neuen Bewegung zu der Vorderseite der Liste Nach dem Fixieren wird der Code in unter einmal pro Sekunde:

maxX = 8 
maxY = 8 
maxSteps = 60 

move :: [(Int, Int)] -> [(Int, Int)] 
move list 
    | lastX > maxX || lastY > maxY || lastX <= 0 || lastY <= 0 = [] 
    | lastMove `elem` (tail list) = [] 
    | length list == maxSteps = list 
    | length m1 == maxSteps = m1 
    | length m2 == maxSteps = m2 
    | length m3 == maxSteps = m3 
    | length m4 == maxSteps = m4 
    | length m5 == maxSteps = m5 
    | length m6 == maxSteps = m6 
    | length m7 == maxSteps = m7 
    | length m8 == maxSteps = m8 
    | otherwise = [] 
    where lastMove = head list 
     lastX = fst lastMove 
     lastY = snd lastMove 
     m1 = move ((lastX + 1, lastY + 2) : list) 
     m2 = move ((lastX + 2, lastY + 1) : list) 
     m3 = move ((lastX - 1, lastY + 2) : list) 
     m4 = move ((lastX - 2, lastY + 1) : list) 
     m5 = move ((lastX + 1, lastY - 2) : list) 
     m6 = move ((lastX + 2, lastY - 1) : list) 
     m7 = move ((lastX - 1, lastY - 2) : list) 
     m8 = move ((lastX - 2, lastY - 1) : list) 
y = move [(1, 1)] 
main = print $ reverse y  

Ich habe ein machte ein paar weitere Änderungen. Zuallererst wurde ich "manuell" los und fügte bei jedem Schritt 8 mögliche Züge hinzu. Dafür können wir eine Liste verwenden. Dieser Ansatz hilft, solche Fehler zu vermeiden. Es stellt sich auch heraus, dass die Ausführungszeit von der Reihenfolge abhängt, in der neue Bewegungen untersucht werden. Diese Version findet eine offene Tour in etwa einer Minute (und meiner Meinung nach ist es lesbarer als der ursprüngliche Code):

maxX = 8 
maxY = 8 
maxSteps = 64 
shifts = [-1, 1, -2, 2] 

move :: [(Int, Int)] -> [(Int, Int)] 
move path 
    | lastX > maxX || lastY > maxY || lastX <= 0 || lastY <= 0 = [] 
    | lastMove `elem` tail path = [] 
    | length path == maxSteps = path 
    | not (null validNewPaths) = head validNewPaths 
    | otherwise = [] 
    where lastMove@(lastX, lastY) = head path 
     newPaths = [(lastX + x, lastY + y) : path | x <- shifts, y <- shifts, abs x /= abs y] 
     validNewPaths = filter (\xs -> length xs == maxSteps) (map move newPaths) 

main = print $ reverse (move [(1, 1)])