GoはProlog - ハノイの塔

ハノイの塔はエドゥアール・リュカが考案したパズルで、３本の杭のうち左の杭に刺さった大きさの異なる円盤を、小さい円盤の上に大きい円盤を刺すことなく右の杭まで移動させるもの。あるいは、VimとEmacs、間違った方のエディタを使っていた者が死んだ後、賽の河原でさせられることで知られる罰。

GoはPrologなので、以下のようにハノイの塔を解くプログラムが書ける:

package main

import (
	"flag"
	"fmt"

	"github.com/ichiban/prolog"
	"github.com/ichiban/prolog/nondet"
	"github.com/ichiban/prolog/term"
)

func main() {
	var n int
	flag.IntVar(&n, "n", 3, "円盤の枚数")
	flag.Parse()

	i := prolog.New(nil, nil)
	if err := i.Exec(`
hanoi(N) :- move(N, '左', '右', '中央').

move(0, _, _, _) :- !.
move(N, X, Y, Z) :-
  M is N - 1,
  move(M, X, Z, Y),
  actuate(X, Y),
  move(M, Z, Y, X).
`); err != nil {
		panic(err)
	}

	i.Register2("actuate", func(x, y term.Interface, k func(*term.Env) *nondet.Promise, env *term.Env) *nondet.Promise {
		fmt.Printf("%sから%sに円盤を動かす\n", env.Resolve(x), env.Resolve(y))
		return k(env)
	})

	sols, err := i.Query(`hanoi(?).`, n)
	if err != nil {
		panic(err)
	}

	_ = sols.Next()
}

$ go run examples/hanoi/main.go -n 4
'左'から'中央'に円盤を動かす
'左'から'右'に円盤を動かす
'中央'から'右'に円盤を動かす
'左'から'中央'に円盤を動かす
'右'から'左'に円盤を動かす
'右'から'中央'に円盤を動かす
'左'から'中央'に円盤を動かす
'左'から'右'に円盤を動かす
'中央'から'右'に円盤を動かす
'中央'から'左'に円盤を動かす
'右'から'左'に円盤を動かす
'中央'から'右'に円盤を動かす
'左'から'中央'に円盤を動かす
'左'から'右'に円盤を動かす
'中央'から'右'に円盤を動かす

書いてから気づいたんだが、別にPrologにする必要はなかった。