単一SQLクエリでハノイの塔を解いてみよう

## はじめに
再帰演習の定番である「[ハノイの塔](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%8E%E3%82%A4%E3%81%AE%E5%A1%94)」をSQLで解きます。基本**Oracle**のSQLで記述していますが、特別なことをしているわけではないので、再帰が使えるSQLであればすこしの手直しで簡単に書き換えらます。ということで最後に**PostgreSQL**版と**MySQL**版も載せています。

## ハノイの塔の再帰アルゴリズム
ハノイの塔には非常に有名な再帰記述アルゴリズムがあります。「複雑そうな動きも再帰で記述するとこんなに簡単になるんだよ」と言える代表格みたいなやつですね。

```C:ハノイの塔(C言語)
		Hanoi (n, orig, free, dest) {
			if (n > 1) Hanoi (n - 1, orig, dest, free);
			printf("%s -> %s\n", orig, dest);
			if (n > 1) Hanoi (n - 1, free, orig, dest);
		}
```

アルゴリズム等の詳しい解説に関しては下記のサイト等を参考にしてください。他にも「ハノイの塔」で検索すればたくさん出てくると思いますのでここでは簡潔に説明します。

> [ハノイの塔を攻略せよ](http://www13.plala.or.jp/kymats/study/C++/Hanoi/Hanoi.html)

まず上記のHANOI関数ですが、『第一引数(N)個のタイルの山を第二引数(ORIG)から第四引数(DEST)にまとめて移動する』ものであると考えてください。例えば４つのタイルの山がORIGにある状態でHANOI関数を呼ぶと、タイルの山がそのままDESTに移動して帰ってくるイメージです。ルール等は一旦置いておいてHANOI関数はそういう動きをするものだと定義します。

次に内部の再帰コールを見ていきます。先程の4つのタイルの山でHANOI関数を呼んだとしましょう。ここで行われるのは、以下の３つです。

**#1.**  4つ目のタイルを除いた上3つのタイルの山(N - 1)を『まとめて』ORIGから一旦FREEへ移動する
**#2.**  4つ目のタイルをORIGからDESTへ移動する。これが実際の動き（出力）となります。
**#3.**  上記#1でFREEに移動した3つのタイルを『まとめて』FREEからDESTへ移動する。

最後の一つのタイルを除いて、残り３つのタイルをまとめて移動するところがポイントです。これで一番下のタイルを目的地に動かすことができます。そしてさらに移動した残りの３つのタイルをその上に移動して、めでたく完成です。そんなんルール違反だろって思うかもしれませんが、この『まとめて移動』自体が再帰コールなので、またその中で今度は対象となった３つのタイルのうち上２つをまとめて動かし、またそのなかの再帰コールで２つの内上のひとつだけを動かして、最終的に正しく一つずつ動かしているというわけですね。

## SQLの再帰クエリでの記述

### そのままSQLへ置換

さて、これをSQLの再帰クエリに書き換えてみます。タイルの数を変更するには、SQLコードの二行目の``４``を変更するだけです。

```sql:
WITH hanoi (tiles, ln, orig, free, dest) AS (
SELECT  4,   -- タイルの数
        0,   -- ライン番号
       'Left', 'Center', 'Right' -- 場所の定義
FROM   dual
UNION ALL
SELECT 
        r.tiles - 1,
        r.ln * 2 + m.n,
        -- n = 0 のとき (orig, dest, free) : orig -> free
        -- n = 1 のとき (free, orig, dest) : free -> dest
        DECODE(n, 0, orig, free),
        DECODE(n, 0, dest, orig),
        DECODE(n, 0, free, dest)
FROM 
        hanoi r, 
        (SELECT 0 n FROM dual UNION ALL SELECT 1 FROM dual) m
WHERE
        r.tiles > 1
)
SELECT * FROM hanoi;


     TILES         LN ORIG   FREE   DEST
---------- ---------- ------ ------ ------
         4          0 Left   Center Right
         3          0 Left   Right  Center
         3          1 Center Left   Right
         2          0 Left   Center Right
         2          1 Right  Left   Center
         2          2 Center Right  Left
         2          3 Left   Center Right
         1          0 Left   Right  Center
         1          1 Center Left   Right
         1          2 Right  Center Left
         1          3 Left   Right  Center
         1          4 Center Left   Right
         1          5 Right  Center Left
         1          6 Left   Right  Center
         1          7 Center Left   Right
```

ここでポイントは２つ。ひとつは再帰の各レベル（Cの場合は一回の関数コール）で２回再帰コールしなければならないため、0と1を持つインラインビューを作って結合し、0のときは上記#1の最初の再帰``(ORIG, DEST, FREE)``、1のときは#3の２つ目の再帰``(FREE, ORIG, DEST)``をしています。そしてもうひとつ。SQLではC言語のように再帰コールの途中で結果を出力することができないため、計算後に並び替えてタイルを移動する順番に出力する必要があります。そのためライン番号(LN)をつけて、(TILES, LN)で各行をユニークに識別できるようにしています。

### ユニーク番号からステップ番号への置換

そしてその並び替えです。まずは正しいタイルの動きの順番（ステップ番号）をコメントでいれてみます。

```
     TILES         LN ORIG   FREE   DEST       ステップ番号
---------- ---------- ------ ------ ------
         4          0 Left   Center Right          <--  #8
         3          0 Left   Right  Center         <--  #4
         3          1 Center Left   Right          <-- #12
         2          0 Left   Center Right          <--  #2
         2          1 Right  Left   Center         <--  #6
         2          2 Center Right  Left           <-- #10
         2          3 Left   Center Right          <-- #14
         1          0 Left   Right  Center         <--  #1
         1          1 Center Left   Right          <--  #3
         1          2 Right  Center Left           <--  #5
         1          3 Left   Right  Center         <--  #7
         1          4 Center Left   Right          <--  #9
         1          5 Right  Center Left           <-- #11
         1          6 Left   Right  Center         <-- #13
         1          7 Center Left   Right          <-- #15
```

はい、規則性がさっぱりわかりませんね。では理解しやすようにTILESとLNをツリー図に置き換えてみます。横軸がTILES、縦軸がLNです。それぞれにステップ番号を追加しています。

```
   4      3     2     1          <-- TILES
---------------------------
                    /  0 <#1>    <-- LN <ステップ番号#>
               0 <#2>
             /      \  1 <#3>
            /
         0 <#4>
         /  \       /  2 <#5>
        /    \ 1 <#6>
      /             \  3 <#7>
     /   
  0 <#8>             / 4 <#9>
     \         2 <#10>
      \     /        \ 5 <#11>
       \   /
        1 <#12>
           \         / 6 <#13>
            \  3 <#14>
                     \ 7 <#15>
ステップ番号の規則性
------------------------------
    <#8>   <#4>   <#2>   <#1>     <-- 各TILESでLN=0     = 2 ^ (tiles - 1)
            +      +      +
            8      4      2       <-- LN増加に対する増加 = 2 ^ tiles
```

(TILES,LN)とステップ番号の関連性が見えてきました。TILES 4, 3, 2, 1それぞれにおいてLNが0であるときにスッテプ番号が8, 4, 2, 1となっています。これは、2 ^ (TILES - 1)で表されます。さらに各TILESでLNが一つ増えるとステップ番号がそれぞれ、TILESが1では2の増加、TILESが2では4の増加、TILESが3では8の増加となります。つまり(2 ^ TILES)の増加です。したがって(TILES, LN)からステップ番号の変換をSQLで表すと、``POWER(2, tiles - 1) + LN * POWER (2, tiles)``となります。(追記:表記の間違い訂正しました)

以上の計算を最後の表示に組み込んでハノイの塔の解法ができあがります。

```sql:ハノイの塔（動きのみ）
WITH hanoi (tiles, ln, orig, free, dest) AS (
SELECT  
        4, 0, 'Left', 'Center', 'Right'
FROM   dual
UNION ALL
SELECT 
        r.tiles - 1,
        r.ln * 2 + m.n,
        DECODE(n, 0, orig, free),
        DECODE(n, 0, dest, orig),
        DECODE(n, 0, free, dest)
FROM 
        hanoi r, 
        (SELECT 0 n FROM dual UNION ALL SELECT 1 FROM dual) m
WHERE
        r.tiles > 1
)
SELECT POWER(2, tiles - 1) + ln * POWER (2, tiles) step,   -- ステップ番号
       tiles                                       tile,
       orig || ' -> ' || dest                      action  -- タイルの移動
FROM hanoi
ORDER BY step;


      STEP       TILE ACTION
---------- ---------- ----------------
         1          1 Left -> Center
         2          2 Left -> Right
         3          1 Center -> Right
         4          3 Left -> Center
         5          1 Right -> Left
         6          2 Right -> Center
         7          1 Left -> Center
         8          4 Left -> Right
         9          1 Center -> Right
        10          2 Center -> Left
        11          1 Right -> Left
        12          3 Center -> Right
        13          1 Left -> Center
        14          2 Left -> Right
        15          1 Center -> Right
```

### 視覚図への置換

これで一応完成といえば完成なんですか、やっぱり動きの指示だけだといまいち分かりにくいので、さらに再帰クエリを追加して視覚的な図にしてみましょう。

```sql:ハノイの塔（タイル図）
col left   for a21 jus right
col center for a21 jus right
col right  for a21 jus right

WITH
-- ハノイの塔の再帰
hanoi (tiles, ln, orig, free, dest) AS (
SELECT  -- タイル数
        4, 0, 'Left', 'Center', 'Right'
FROM    dual
UNION ALL
SELECT
        r.tiles - 1,
        r.ln * 2 + m.n,
        DECODE(n, 0, orig, free),
        DECODE(n, 0, dest, orig),
        DECODE(n, 0, free, dest)
FROM    hanoi r, 
        (SELECT 0 n FROM dual UNION ALL SELECT 1 FROM dual) m
WHERE   r.tiles > 1
),
-- 開始時のタイルの山を作成 e.g. 1-2-3-4-
pile(n, s, m) AS (
SELECT 
        1, CAST('1-' AS VARCHAR2(100)), MAX(tiles)
FROM    hanoi
UNION ALL
SELECT 
        n + 1, s || TO_CHAR(n + 1) || '-', m
FROM    pile
WHERE   n < m
),
-- 各行でのタイルの移動に応じたタイルの山の再生成
display (step, left, center, right, target) AS (
SELECT 
        0,
        s,
        CAST(NULL as VARCHAR2(100)),  -- CASTしないと意図しない動きになることがある
        CAST(NULL as VARCHAR2(100)),  -- なんとなくオラクルのバグっぽい
        CAST(NULL as VARCHAR2(10))
FROM    pile
WHERE   n = m
UNION ALL
SELECT
        p.step,
        CASE -- LEFT
        WHEN p.orig = 'Left' THEN REGEXP_REPLACE(left, '^\d+-', '')
        WHEN p.dest = 'Left' THEN p.tile_no || '-' || left
        ELSE left
        END,
        CASE -- CENTER
        WHEN p.orig = 'Center' THEN REGEXP_REPLACE(center, '^\d+-', '')
        WHEN p.dest = 'Center' THEN p.tile_no || '-' || center
        ELSE center
        END,
        CASE -- RIGHT
        WHEN p.orig = 'Right' THEN REGEXP_REPLACE(right, '^\d+-', '')
        WHEN p.dest = 'Right' THEN p.tile_no || '-' || right
        ELSE right
        END,
        p.dest
FROM display d,
     (SELECT  -- 並び順の計算
              POWER(2, tiles - 1) + ln * POWER(2, tiles) step,
              tiles tile_no, orig, dest, ln
      FROM    hanoi) p
WHERE d.step + 1 = p.step
)
-- タイルの山を右寄せで出力 (タイル数が10を超える場合はサイズを広げる)
SELECT
        step,
        LPAD(DECODE(target, 'Left',   '*') || RTRIM(left,   '-'), 21, ' ') left,
        LPAD(DECODE(target, 'Center', '*') || RTRIM(center, '-'), 21, ' ') center,
        LPAD(DECODE(target, 'Right',  '*') || RTRIM(right,  '-'), 21, ' ') right
FROM display
ORDER BY step;
```

以下が出力となります。ついでなので、確認しやすいように移動したタイルには＊をつけてみました。かなり視覚的にわかりやすくなったのではないでしょうか。小さな数の上に大きな数が来ることなく左の山を右に移動できていますね。


```:出力（*は移動したタイル）
      STEP                  LEFT                CENTER                 RIGHT
---------- --------------------- --------------------- ---------------------
         0               1-2-3-4
         1                 2-3-4                    *1
         2                   3-4                     1                    *2
         3                   3-4                                        *1-2
         4                     4                    *3                   1-2
         5                  *1-4                     3                     2
         6                   1-4                  *2-3
         7                     4                *1-2-3
         8                                       1-2-3                    *4
         9                                         2-3                  *1-4
        10                    *2                     3                   1-4
        11                  *1-2                     3                     4
        12                   1-2                                        *3-4
        13                     2                    *1                   3-4
        14                                           1                *2-3-4
        15                                                          *1-2-3-4
```

## PostgreSQLとMySQL

PostgreSQLとMySQLにも書き換えてみました。大きな変更はありません。せいぜい文字連結をCONCATにしたりDECODEをCASE WHENにしたり。ただ、CASTしないとエラーになる場所がデータベースによって異なるというのが面白いところですね。

### PostgreSQL版

PostgreSQL 11.0で確認しました。

```sql:PostgreSQL
WITH RECURSIVE hanoi (tiles, ln, orig, free, dest) AS (
SELECT  
        4, 0, 'Left', 'Center', 'Right'
UNION ALL
SELECT 
        r.tiles - 1,
        r.ln * 2 + m.n,
        CASE WHEN n = 0 THEN orig ELSE free END,
        CASE WHEN n = 0 THEN dest ELSE orig END,
        CASE WHEN n = 0 THEN free ELSE dest END
FROM 
        hanoi r, 
        (SELECT 0 n UNION ALL SELECT 1) m
WHERE
        r.tiles > 1
),
pile(n, s, m) AS (
SELECT 
        1, '1-', MAX(tiles)
FROM    hanoi
UNION ALL
SELECT 
        n + 1, s || n + 1 || '-' , m
FROM    pile
WHERE   n < m
),
display (step, left_, center_, right_, target) AS (
SELECT 
        0, s, '', '', ''
FROM    pile
WHERE   n = m
UNION ALL
SELECT
        p.step,
        CASE -- LEFT
        WHEN p.orig = 'Left' THEN REGEXP_REPLACE(left_, '^\d+-', '')
        WHEN p.dest = 'Left' THEN p.tile_no || '-' || left_
        ELSE left_
        END,
        CASE -- CENTER
        WHEN p.orig = 'Center' THEN REGEXP_REPLACE(center_, '^\d+-', '')
        WHEN p.dest = 'Center' THEN p.tile_no || '-' || center_
        ELSE center_
        END,
        CASE -- RIGHT
        WHEN p.orig = 'Right' THEN REGEXP_REPLACE(right_, '^\d+-', '')
        WHEN p.dest = 'Right' THEN p.tile_no || '-' || right_
        ELSE right_
        END,
        p.dest
FROM display d,
     (SELECT
              CAST(POWER(2, tiles - 1) + ln * POWER(2, tiles) AS INTEGER) step,
              tiles tile_no, orig, dest, ln
      FROM    hanoi) p
WHERE d.step + 1 = p.step
)
SELECT
        step,
        LPAD(CASE WHEN target = 'Left'   THEN '*' ELSE '' END || RTRIM(left_,   '-'), 21, ' ') left_,
        LPAD(CASE WHEN target = 'Center' THEN '*' ELSE '' END || RTRIM(center_, '-'), 21, ' ') center_,
        LPAD(CASE WHEN target = 'Right'  THEN '*' ELSE '' END || RTRIM(right_,  '-'), 21, ' ') right_
FROM display
ORDER BY step;
```

### MySQL版

MySQL 8.0.13で確認しました

```sql:MySQL

WITH RECURSIVE hanoi (tiles, ln, orig, free, dest) AS (
SELECT  
        4, 0, 
        CAST('Left'   as char(10)),
        CAST('Center' as char(10)),
        CAST('Right'  as char(10))
UNION ALL
SELECT 
        r.tiles - 1,
        r.ln * 2 + m.n,
        CASE WHEN n = 0 THEN orig ELSE free END,
        CASE WHEN n = 0 THEN dest ELSE orig END,
        CASE WHEN n = 0 THEN free ELSE dest END
FROM 
        hanoi r, 
        (SELECT 0 n UNION ALL SELECT 1) m
WHERE
        r.tiles > 1
),
pile(n, s, m) AS (
SELECT 
        1, CAST('1-' AS CHAR(100)), MAX(tiles)
FROM    hanoi
UNION ALL
SELECT 
        n + 1, CONCAT(s, n + 1, '-'), m
FROM    pile
WHERE   n < m
),
display (step, left_, center_, right_, target) AS (
SELECT 
        0,
        s,
        CAST('' AS CHAR(100)),
        CAST('' AS CHAR(100)),
        CAST('' AS CHAR(100))
FROM    pile
WHERE   n = m
UNION ALL
SELECT
        p.step,
        CASE -- LEFT
        WHEN p.orig = 'Left'   THEN CAST(REGEXP_REPLACE(left_,   '^[0-9]+-', '') AS CHAR(100))
        WHEN p.dest = 'Left'   THEN CONCAT(p.tile_no, '-', left_)
        ELSE left_
        END,
        CASE -- CENTER
        WHEN p.orig = 'Center' THEN CAST(REGEXP_REPLACE(center_, '^[0-9]+-', '') AS CHAR(100))
        WHEN p.dest = 'Center' THEN CONCAT(p.tile_no, '-', center_)
        ELSE center_
        END,
        CASE -- RIGHT
        WHEN p.orig = 'Right'  THEN CAST(REGEXP_REPLACE(right_,  '^[0-9]+-', '') AS CHAR(100))
        WHEN p.dest = 'Right'  THEN CONCAT(p.tile_no, '-', right_)
        ELSE right_
        END,
        p.dest
FROM display d,
     (SELECT
              POWER(2, tiles - 1) + ln * POWER(2, tiles) step,
              tiles tile_no, orig, dest, ln
      FROM    hanoi) p
WHERE d.step + 1 = p.step
)
SELECT
        step,
        LPAD(CONCAT(CASE WHEN target = 'Left'   THEN '*' else '' END, TRIM('-' from left_)),   21, ' ') left_,
        LPAD(CONCAT(CASE WHEN target = 'Center' THEN '*' else '' END, TRIM('-' from center_)), 21, ' ') center_,
        LPAD(CONCAT(CASE WHEN target = 'Right'  THEN '*' else '' END, TRIM('-' from right_)),  21, ' ') right_
FROM display
ORDER BY step;
```

##おわりに

SQL言語の再帰は他の言語と比べると細かい制御はできないですが、再帰のなかったころに比べてSQL単体でできることが相当に広がりました。いわゆる再帰パズルを解くことによってSQLでも再帰に親しめるのではないかと思います。

以上です。