状態遷移図を作成するようなプログラムを書ければ (A, B) の全状態を把握する事ができそうだ。
  では、どうやって状態遷移図を作成するプログラムが書けるのか？

  ある状態以上の状態を持たない条件 (終了) を規定できれば、再帰的に状態遷移図を手繰るプログラムができそうである。
  では、ある状態以上を持たない条件とはどんなものか？

  既知の全ての状態に対して、上述の各アクションを行ったときに、新たな状態が一つでも見つけられない時、既知の状態は全ての状態である、ということが帰納的に言えるだろう。
  このアルゴリズムを擬似コードで表すと次のようになる。

  (0) |  初期状態 を 既知の状態 に設定
  (1) |
  (2) |  次の状態 = 全ての 既知の状態 に対してアクションを行う
  (3) |  if (次の状態 is 未知の状態) {
  (4) |    次の状態 を 既知の状態 に設定
  (5) |    goto (2)
  (6) |  }
  (7) |  終了

  それではこれをプログラムに直してみる。
  まずは Perl で作ってみた [1] 。以下はコードの一部を抜粋したもの。

     1  &searchStates(\@states, BASIC_STATE, \@actions);
     2  
     3  (略)
     4  
     5  sub searchStates
     6  {
     7    my $states_ref = shift;
     8    my $crnt_state = shift; # current_state has been known yet.
     9    my $actions_ref = shift;
    10  
    11    for(@$actions_ref){
    12      my $after = $_->($crnt_state);
    13  
    14      my $check = &checkState($states_ref, $after);
    15      if($check == UNKNOWN){
    16        push @$states_ref, $after;
    17  
    18        &searchStates($states_ref, $after, $actions_ref);
    19      }
    20    }
    21  }

  何も考えずに書いたので、いかにも関数型言語に慣れていない人間が書いた、副作用満載なコードであるが。(苦しい言い訳だが) Haskell との比較対象としてはこのくらいがいいのではないだろうか。

  中身は $states_ref が既知の状態配列のリファレンスを、$actions_ref がアクションの無名関数配列のリファレンスをそれぞれ表している。そして 12 行目で取得した次状態が未知か既知かを 14 行目でチェックし、未知ならば次状態を既知の状態配列に追加して、searchStates を再帰的に呼び出す。
  全てのアクションに対して得られる次状態が全て既知の時、それが全状態なので @states に全ての状態が格納される。
  Perl で書いたこのプログラムは全体で 136 行になる。
  また、出力は次のようになる。

$ perl water_pitcher01.pl
(0, 0)
(4, 0)
(0, 3)
(4, 3)
(3, 3)
(3, 0)
(4, 2)
(2, 3)
(4, 1)
(1, 3)
(0, 1)
(1, 0)
(0, 2)
(2, 0)

  それでは、これを Haskell で書いてみる [2]。
  以下がコードの全体である。

     1  import List
     2  
     3  basicState = (0,0)
     4  actions = let {xmax = 4; ymax = 3}
     5            in [(\(x, y) -> (xmax, y)),
     6              (\(x, y) -> (x, ymax)),
     7              (\(x, y) -> (0, y)),
     8              (\(x, y) -> (x, 0)),
     9              (\(x, y) -> if (x + y > xmax) then (xmax, y+x-xmax) else (x+y, 0)),
    10              (\(x, y) -> if (x + y > ymax) then (x+y-ymax, ymax) else (0, x+y))]
    11  
    12  main = print $ searchStates [basicState]
    13  
    14  searchStates :: [(Int, Int)] -> [(Int, Int)]
    15  searchStates states = let nexts = filter (not . (checkState states)) $ concat $ map (execSeek actions) states
    16                        in if length nexts > 0
    17                           then searchStates $ states ++ (nub nexts)
    18                           else states
    19  
    20  execSeek :: [((Int, Int) -> (Int, Int))] -> (Int, Int) -> [(Int, Int)]
    21  execSeek (f:fs) crnt | null fs = (f crnt : [])
    22                       | True    = (f crnt : []) ++ execSeek fs crnt
    23  
    24  checkState :: [(Int, Int)] -> (Int, Int) -> Bool
    25  checkState states (crnt_x, crnt_y) = any isSameState states
    26    where
    27      isSameState :: (Int, Int) -> Bool
    28      isSameState (x, y) = if (x == crnt_x && y == crnt_y) then True else False

  全体でわずか 28 行。
  熟練プログラマが書けば更に短くなるのだろうが。Haskell 素人の自分でも Perl のコードの 1/5 程度の規模で作成できた。

  コード中では (A, B) の各状態をタプルで表現している。
  21 行目の execSeek 関数で、ある状態 (crnt) に各アクション関数を適応させ、次状態となりうる全ての状態のリストを取得している。
  そして 25 行目の checkState では、現在までの既知の状態リストとある状態を受け、その状態が未知か既知かを判定している。

  Haskell では副作用を排除する為に値の再代入ができないので、幅優先探索のような処理ができない。つまり、ある再起から戻ってきて、別の再起を呼び出したときに、前の再起の状態を保存しておく事ができないので、現在の状態を記憶した状態でバックトラックして、別の経路を探索することができない。
  スタック上での値のやりとりのみによって、全状態のリストを作成しなければならない。
  15 行目の searchStates では、execSeek 関数によって次状態リストを取得し、checkState 関数によってこのうち、未知の状態のみのリストを取得する。ただし、checkState 関数は受け取った状態が未知の場合に False になるので、not との関数合成によって未知の状態のリストのみを得る。
  そして、未知の状態が一つでもある場合には、未知の状態を既知の状態に追加して、searchStates を再び呼び出す。ここで、execSeek によって別アクションによる同一の次状態を取得するケースがある為、List モジュールの nub 関数によって重複排除を行っている。
  もし、未知の状態が一つも無い場合には、現在までの状態リストが全状態な為、states を返す。

  このプログラムの実行結果は次のようになる。

  $ ./a.out 
  [(0,0),(4,0),(0,3),(4,3),(1,3),(3,0),(1,0),(3,3),(0,1),(4,2),(4,1),(0,2),(2,3),(2,0)]

  よさそうである。

[1] http://dev.ariel-networks.com/Members/ohyama/stuff/water_pitcher01.pl/download
[2] http://dev.ariel-networks.com/Members/ohyama/stuff/water_pitcher01.hs/download


・おわりに

  この問題を解くのに、今日一日使ってしまった。特に、前半で述べた定理にたどりつくまでと、Haskell のプログラム作成にめちゃめちゃ時間がかかったが。とてもいい勉強になった。
  普段、あまり数学に触れる習慣が無いので、こういったアルゴリズム問題を考えて、定理を導き、プログラムを書いて、動かして、答えが出たとき。あまりの達成感に驚喜した。脳内はアドレナリンが大量分泌している事まちがいない。