ハノイの塔

Coq

久しぶりにCoqで遊ぼうかと思って、いい問題はないかと考えたところ、ハノイの塔あたりが面白いんじゃなかろうかということで証明してみた。

証明したいことはハノイの塔を完成させる最短手数は2^n-1であること…

と思って少し書いてみたんだけど、これはかなり大変だということになって、ハノイの塔の解等を計算する関数が正しく解になっていることを証明することを最初の目標としてみた。

問題設定は以下の通り

Inductive pos : Set := pos1 | pos2 | pos3.
Inductive move : Set :=
| from_to (from to: pos):  move.

Definition tower := list pos.
Definition moves := list move.

Fixpoint single_tower (t: tower) (p: pos) : Prop.

Definition legal_move (t: tower) (m: move) : Prop. 
Definition make_move (t:tower) (m:move) : tower.

Fixpoint legal_moves (m:moves) (t:tower) :=
match m with
| hd::tl => legal_move t hd /\ legal_moves tl (make_move t hd)
| nil => True
end.

Definition make_moves (m:moves) (t:tower) :=
  fold_left make_move m t.

Fixpoint answer (n: nat) (from to rest: pos) {struct n} :=
match n with
| O => nil
| S m =>  answer m from rest to ++ (from_to from to::nil) ++ answer m rest to from
end.

Theorem hanoi: forall (n:nat) (t: tower) (from to rest: pos),
  from <> to -> from <> rest -> to <> rest ->
  length t = n ->
  single_tower t from ->
  legal_moves (answer n from to rest) t
   /\ single_tower (make_moves (answer n from to rest) t) to.

塔をどのようにlist posで表現するかで泥沼がまっているぞ！

とりあえず、清書してない300行ある証明は http://github.com/kik/sandbox/blob/c1b16b684feb7482f0582480a43b2db4a9be3ce0/coq/Hanoi.v にあるけど、自分で証明したい人は見ないように。

Coq 8.1でやったから新しいのだと問題があるかも