n段のハノイの塔を最小回数で移動させるには、まず最小回数でn-1段の円盤を全て中央に移動させてから、左端にある一番大きな円盤を右端に、そして再び最小移動回数で右端に移動させれば良い。a nをn段のハノイの塔の移動回数とするとa n = 2 * a (n - 1) + 1ということになる。また、明らかにn=1のときは1回が最短なので、この漸化式を解けば、最小回数は分かる。

最小の移動回数の数値自体には、今は興味がなくて、最小回数のときに一番小さな円盤をどこへ移動させるかということに興味がある。そこで、上の考え方をそのままHaskellのコードにしてみた。

ソースコード

hanoi.hs

import Control.Monad.Writer

size :: [[a]] -> Int
size = foldr (\ xs n -> length xs + n) 0
move :: [[Int]] -> (Int, Int) -> Writer [String] [[Int]]
move xss (from, to) = return([move_ xs y (from, to) i| (xs, i) <- zip xss [0..]])
                      where (y:_) = xss !! from
move_ :: [Int] -> Int -> (Int, Int) -> Int -> [Int]
move_ [] y (from, to) i = if i == to then [y] else []
move_ (x:xs) y (from, to) i |i == from = xs
                            |i == to   = (y:x:xs)
                            |otherwise = (x:xs)

hanoi :: Int -> Writer [String] [[Int]]
hanoi n = hanoi_ n [[0..(n-1)], [], []] (0, 1, 2)
hanoi_ :: Int -> [[Int]] -> (Int, Int, Int) -> Writer [String] [[Int]]
hanoi_ 0 xss (from, work, to) = return(xss)
hanoi_ n xss (from, work, to) = do xss' <- hanoi_ (n-1) xss (from, to, work)
                                   xss''  <- move xss' (from, to)
                                   tell [show(xss'') ++" (" ++ show(from) ++ " -> " ++ show(to) ++ ")"]
                                   xss''' <- hanoi_ (n-1) xss'' (work, from, to)
                                   return(xss''')
show_hanoi :: Int -> IO ()
show_hanoi n = mapM_ putStrLn $ snd $ runWriter (hanoi n)

test :: Int -> IO ()
test n = mapM_ putStrLn $ take n $ map (head . snd . runWriter . hanoi) [1..]

実行結果

show_hanoi nでn段のハノイの塔の最小回数になる移動方法を示します。テストとしてshow_hanoi 4を実行しましたが、動いているようです。test nは1段からn段までのはじめの1手を標準出力しますが、test 7をした限りだと、『nが奇数ならば右端に、偶数ならば中央へ移動する』というのが答えになりそうです。

証明

『奇数段は右端に、偶数段は中央へ移動する』をn上の帰納法で証明します。まず、n = 1, 2の場合はすでに確認しているので、n段を帰納の仮定として、n+1段の場合を考える。

n+1段

hanoi_の定義からhanoi_ (n+1)..(from, work, to)が呼ばれると(from = 0, work = 1, to = 2)、hanoi_n .. (from, to, work)、hanoi_ (n-1)..(from, to, work)と呼ばれていって、最終的にhanoi_ 1 (from, work', to')が呼ばれ、このときのto'が移動先になる。hanoi_の定義からto'はtoとworkをn回入れ替えたものなので、nが奇数ならばto' = work = 1で中央、nが偶数ならば右端になる。よって(n+1)が奇数ならば右端で、偶数ならば中央。