はじめに
いわゆる川渡り問題です。「狼とヤギとキャベツ」および「宣教師と人食い族」の２つを解きます。再帰の練習としてはほどよい感じですね。もちろん単一SQLクエリです(^^)。MySQLとOracleでそれぞれ記述しています。
狼とヤギとキャベツ問題
オオカミとヤギを連れキャベツを持った農夫がボートを使って対岸に持ち物を運ぼうとしています。ボートを漕げるのは農夫だけで、ボートには農夫のほかはオオカミ、ヤギ、キャベツのどれか一つしか同時には乗せることができません。ただし、農夫がいない岸にオオカミとヤギを置いておくととオオカミがヤギを食べてしまいます。また同じくヤギとキャベツを置いておくとヤギがキャベツを食べてしまいます。すべてを無事に対岸にわたすにはどうすればよいでしょう？
問題の解答
答えは２つですね。以下、アスタリスク"*"が各々の存在を表しています。どちらも７ステップで左側の全てのが右側に移動しています。また農夫が居ないときに「オオカミ、ヤギ」または「ヤギ、キャベツ」の組み合わせは出てきてないですね。ではこの表を出力するクエリを作っていきます。
コーディング
クエリ動きとしては、初期状態からスタートしてすべての動きの可能性を再帰でブルートフォースサーチいきます。したがって、まずはボートでの「移動の動き」のすべてを行としてテーブルに定義しておくのがわかりやすいと思います。この問題では、農夫は必ず移動しますが、単独で移動するか、またはオオカミ、ヤギ、キャベツのいずれかを引き連れていくので、以下のように8つの移動が可能性があります。上半分は右岸への移動、下半分は左岸への移動です。
moves (farmer, wolf, goat, cabbage)
AS (SELECT 1, 0, 0, 0 UNION ALL /* 右岸へ農夫のみ */
SELECT 1, 1, 0, 0 UNION ALL /* 右岸へ農夫とオオカミ */
SELECT 1, 0, 1, 0 UNION ALL /* 右岸へ農夫とヤギ */
SELECT 1, 0, 0, 1 UNION ALL /* 右岸へ農夫とキャベツ */
SELECT -1, 0, 0, 0 UNION ALL /* 左岸へ農夫のみ */
SELECT -1, -1, 0, 0 UNION ALL /* 左岸へ農夫とオオカミ */
SELECT -1, 0, -1, 0 UNION ALL /* 左岸へ農夫とヤギ */
SELECT -1, 0, 0, -1 /* 左岸へ農夫とキャベツ */
),
再帰のパラメータでは、右岸の状態を保持することとします（どちらでもいいですが）。右岸に農夫、オオカミ、ヤギ、キャベツがいない状態である「0,0,0,0」から開始し、すべてが移動して「1,1,1,1」を得たら終了となります。
recur (farmer, wolf, goat, cabbage, step, move, goal, cycle)
AS (/* 右岸になにもないところからスタート */
SELECT 0, 0, 0, 0, 0, CAST('' AS CHAR(20)), 0, CAST('' AS CHAR(500))
UNION ALL
SELECT
再帰の中では、現在の状態をもつrecurに対して上記のmovesを掛け合わせることで移動する状態を作ります。またWHERE句に条件を記述して移動不可の動きをふるい落として移動できる状態のみ再帰の次のステップに進みます。移動可能条件は以下の通りです。
- ゴールしていなこと
- 状態が繰り返しになっていなこと
- 各々の状態が居ない(0)か居る(1)のみであること
- オオカミ、ヤギの組み合わせ違反になっていないこと
- ヤギ、キャベツの組み合わせ違反になっていないこと
FROM recur r, /* 現在の状態(再帰) */
moves m /* すべての動き候補 */
WHERE /* ゴール状態でない */
goal = 0 AND
/* 繰り返し違反でない */
NOT FIND_IN_SET(CONCAT(r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat,
r.cabbage + m.cabbage),
r.cycle) AND
/* 移動条件: 居るか居ないか(0/1)の移動のみ可 */
r.farmer + m.farmer BETWEEN 0 AND 1 AND
r.wolf + m.wolf BETWEEN 0 AND 1 AND
r.goat + m.goat BETWEEN 0 AND 1 AND
r.cabbage + m.cabbage BETWEEN 0 AND 1 AND
/* 違反組み合わせ除外: 農夫、オオカミ、ヤギ 右岸(0,1,1) 左岸(1,0,0) */
(r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat ) NOT IN ((0,1,1), (1,0,0)) AND
/* 違反組み合わせ除外: 農夫、ヤギ、キャベツ 右岸(0,1,1) 左岸(1,0,0) */
(r.farmer + m.farmer,
r.goat + m.goat,
r.cabbage + m.cabbage ) NOT IN ((0,1,1), (1,0,0))
あとは、再帰の次レベルへ渡すパラメータをSELECT句で作ってやれば再帰は完成となります。ゴール判定のフラグ立てはSELECT句で行います。
/* ゴール判定 */
CASE WHEN r.farmer + m.farmer +
r.wolf + m.wolf +
r.goat + m.goat +
r.cabbage + m.cabbage = 4
THEN 1 ELSE 0 /* 右岸に全て揃えばゴール */
END,
最後に再帰で得た情報をもとに出力を行います。再帰中に移動動作をパラメータの文字列に追記していけばゴールした行を出力するだけで終わるのですが、今回は前述のように移動ごとに一行出力して視覚的に検証しやすい表をつくります。このため、まず再帰結果をソートして「深さ優先探索順」で行番号をつけます。
depth_order
AS (SELECT r.*,
ROW_NUMBER() OVER (ORDER BY cycle) search_id
FROM recur r
)
次にゴールまでの経路を取得します。一番内側のサブクエリ(g)は、複数の解答がある場合の解答の番号付けです。それぞれのゴール行の深さ優先探索行番号に対して、それぞれのステップにおいて内輪でもっとも大きい行番号がゴールまでの経路となります。
FROM (SELECT g.grp, r.*,
ROW_NUMBER() OVER (PARTITION BY g.grp, r.step ORDER BY r.search_id DESC) rn
FROM (SELECT search_id, step,
ROW_NUMBER() OVER (ORDER BY step) grp FROM depth_order WHERE goal = 1) g,
depth_order r
WHERE g.search_id >= r.search_id and g.step >= r.step) d
WHERE rn = 1
解答クエリ
MySQL (8.0以降)
以下完成版です。8.0.13で確認しました。
WITH RECURSIVE
/* 動作テーブル */
moves (farmer, wolf, goat, cabbage)
AS (SELECT 1, 0, 0, 0 UNION ALL /* 右岸へ農夫のみ */
SELECT 1, 1, 0, 0 UNION ALL /* 右岸へ農夫とオオカミ */
SELECT 1, 0, 1, 0 UNION ALL /* 右岸へ農夫とヤギ */
SELECT 1, 0, 0, 1 UNION ALL /* 右岸へ農夫とキャベツ */
SELECT -1, 0, 0, 0 UNION ALL /* 左岸へ農夫のみ */
SELECT -1, -1, 0, 0 UNION ALL /* 左岸へ農夫とオオカミ */
SELECT -1, 0, -1, 0 UNION ALL /* 左岸へ農夫とヤギ */
SELECT -1, 0, 0, -1 /* 左岸へ農夫とキャベツ */
),
/*
左岸から右岸へすべてを渡す
farmer, wolf, goat, cabbage 右岸の状態: 0 - 居ない, 1 - 居る
*/
recur (farmer, wolf, goat, cabbage, step, move, goal, cycle)
AS (/* 右岸になにもないところからスタート */
SELECT 0, 0, 0, 0, 0, CAST('' AS CHAR(20)), 0, CAST('' AS CHAR(500))
UNION ALL
/* すべての動作の可能性をチェックしながら再帰 */
SELECT r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat,
r.cabbage + m.cabbage,
r.step + 1,
/* 視覚的な動き */
CONCAT(CASE WHEN m.farmer = 1 THEN '--> ' ELSE '<-- ' end,
CASE WHEN m.wolf <> 0 THEN 'WOLF'
WHEN m.goat <> 0 THEN 'GOAT'
WHEN m.cabbage <> 0 THEN 'CABBAGE'
ELSE ''
END),
/* ゴール判定 */
CASE WHEN r.farmer + m.farmer +
r.wolf + m.wolf +
r.goat + m.goat +
r.cabbage + m.cabbage = 4
THEN 1 ELSE 0 /* 右岸に全て揃えばゴール */
END,
/* 繰り返し判定用にカンマ区切りで状態を保存 */
CONCAT(r.cycle, ',',
r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat,
r.cabbage + m.cabbage)
FROM recur r, /* 現在の状態(再帰) */
moves m /* すべての動き候補 */
WHERE /* ゴール状態でない */
goal = 0 AND
/* 繰り返し違反でない */
NOT FIND_IN_SET(CONCAT(r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat,
r.cabbage + m.cabbage),
r.cycle) AND
/* 移動条件: 居るか居ないか(0/1)の移動のみ可 */
r.farmer + m.farmer BETWEEN 0 AND 1 AND
r.wolf + m.wolf BETWEEN 0 AND 1 AND
r.goat + m.goat BETWEEN 0 AND 1 AND
r.cabbage + m.cabbage BETWEEN 0 AND 1 AND
/* 違反組み合わせ除外: 農夫、オオカミ、ヤギ 右岸(0,1,1) 左岸(1,0,0) */
(r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat ) NOT IN ((0,1,1), (1,0,0)) AND
/* 違反組み合わせ除外: 農夫、ヤギ、キャベツ 右岸(0,1,1) 左岸(1,0,0) */
(r.farmer + m.farmer,
r.goat + m.goat,
r.cabbage + m.cabbage ) NOT IN ((0,1,1), (1,0,0))
),
/* 深さ優先探索順に並び替え */
depth_order
AS (SELECT r.*,
ROW_NUMBER() OVER (ORDER BY cycle) search_id
FROM recur r
)
/* ゴールまでの経路を選択して表示 */
SELECT CASE WHEN step = 0 THEN CONCAT ('(', grp, ')') ELSE '' END answer,
step,
CONCAT(' ', CASE WHEN farmer = 0 THEN '*' ELSE ' ' END, ' : ' ,
CASE WHEN wolf = 0 THEN '*' ELSE ' ' END, ' : ' ,
CASE WHEN goat = 0 THEN '*' ELSE ' ' END, ' : ' ,
CASE WHEN cabbage = 0 THEN '*' ELSE ' ' END) "Farm: Wolf: Goat: Cabb",
move,
CONCAT(' ', CASE WHEN farmer = 1 THEN '*' ELSE ' ' END, ' : ' ,
CASE WHEN wolf = 1 THEN '*' ELSE ' ' END, ' : ' ,
CASE WHEN goat = 1 THEN '*' ELSE ' ' END, ' : ' ,
CASE WHEN cabbage = 1 THEN '*' ELSE ' ' END) "Farm: Wolf: Goat: Cabb"
FROM (SELECT g.grp, r.*,
ROW_NUMBER() OVER (PARTITION BY g.grp, r.step ORDER BY r.search_id DESC) rn
FROM (SELECT search_id, step,
ROW_NUMBER() OVER (ORDER BY step) grp FROM depth_order WHERE goal = 1) g,
depth_order r
WHERE g.search_id >= r.search_id and g.step >= r.step) d
WHERE rn = 1
ORDER BY grp, step
;
Oracle (11gR2以降)
Oracleの再帰には繰り返しを検知するCYCLE句があります。したがって繰り返し検知用のカンマ区切りリストを持つ必要はありません。楽ですね。さらにSEARCH句で深さ優先探索を指定して深さ優先探索での行番号を直接得ることもできます。
COL left HEAD "Farm: Wolf: Goat: Cabb" FOR a23
COL right HEAD "Farm: Wolf: Goat: Cabb" FOR a23
WITH
moves (farmer, wolf, goat, cabbage)
AS (SELECT 1, 0, 0, 0 FROM DUAL UNION ALL
SELECT 1, 1, 0, 0 FROM DUAL UNION ALL
SELECT 1, 0, 1, 0 FROM DUAL UNION ALL
SELECT 1, 0, 0, 1 FROM DUAL UNION ALL
SELECT -1, 0, 0, 0 FROM DUAL UNION ALL
SELECT -1, -1, 0, 0 FROM DUAL UNION ALL
SELECT -1, 0, -1, 0 FROM DUAL UNION ALL
SELECT -1, 0, 0, -1 FROM DUAL
),
recur (farmer, wolf, goat, cabbage, step, move, goal)
AS (SELECT 0, 0, 0, 0, 0, CAST(NULL AS VARCHAR2(20)), 0 FROM DUAL
UNION ALL
SELECT r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat,
r.cabbage + m.cabbage,
r.step + 1,
DECODE(m.farmer, 1, '--> ', '<-- ')
|| DECODE(ABS(m.wolf), 1, 'WOLF')
|| DECODE(ABS(m.goat), 1, 'GOAT')
|| DECODE(ABS(m.cabbage), 1, 'CABBAGE'),
DECODE(r.farmer + m.farmer +
r.wolf + m.wolf +
r.goat + m.goat +
r.cabbage + m.cabbage, 4, 1, 0)
FROM recur r,
moves m
WHERE goal = 0 AND
r.farmer + m.farmer BETWEEN 0 AND 1 AND
r.wolf + m.wolf BETWEEN 0 AND 1 AND
r.goat + m.goat BETWEEN 0 AND 1 AND
r.cabbage + m.cabbage BETWEEN 0 AND 1 AND
(r.farmer + m.farmer,
r.wolf + m.wolf,
r.goat + m.goat ) NOT IN ((0,1,1), (1,0,0)) AND
(r.farmer + m.farmer,
r.goat + m.goat,
r.cabbage + m.cabbage ) NOT IN ((0,1,1), (1,0,0))
)
SEARCH DEPTH FIRST BY step SET search_id
CYCLE farmer, wolf, goat, cabbage SET cycle TO 1 DEFAULT 0
--
SELECT DECODE(step, 0, '('||grp||')') answer,
step,
' ' || DECODE(farmer, 0, '*', ' ') || ' : '
|| DECODE(wolf, 0, '*', ' ') || ' : '
|| DECODE(goat, 0, '*', ' ') || ' : '
|| DECODE(cabbage, 0, '*', ' ') left,
move,
' ' || DECODE(farmer, 1, '*', ' ') || ' : '
|| DECODE(wolf, 1, '*', ' ') || ' : '
|| DECODE(goat, 1, '*', ' ') || ' : '
|| DECODE(cabbage, 1, '*', ' ') right
FROM (SELECT g.grp, r.*,
ROW_NUMBER() OVER (PARTITION BY g.grp, r.step ORDER BY r.search_id DESC) rn
FROM (SELECT search_id, step, ROW_NUMBER() OVER (ORDER BY step) grp
FROM recur
WHERE goal = 1) g,
RECUR r
WHERE g.search_id >= r.search_id and g.step >= r.step)
WHERE rn = 1
ORDER BY grp, step
;
宣教師と人食い族問題
次の問題です。宣教師３人と人食い族３人が同じ川岸にいます。川にはボートが1艘あり誰でも漕ぐことができますが、ボートには最大２人までしか乗ることができません。全員が対岸に渡りたいのですが、どちらかの岸で人食い族の人数が宣教師の人数より多くなると、人食い族は宣教師を襲って食べてしまいます。さて全員無事に対岸に渡るにはどうしたらよいでしょうか？
問題の解答
解答は４つですね。ここで人食い族ってのも最近のポリコレ的にインコレクトな気がするので、わかりやすくなるよう宣教師を「ヒヨコ」、人食い族を「イヌ」に置き換えています。(ヒヨコとイヌはボートを漕ぎます! :-)
コーディング
まず最初に条件を定義したテーブルを作ります。ひよこ３匹とイヌ３匹です。これを元に以降全てを計算で求めていくので、数値をかえて定義の違う問題を解くこともできます。
/* 定義テーブル */
target (prey_name, prey_num, predator_name, predator_num)
AS (SELECT 'Chick', 3, 'Dog', 3
),
次に前問と同様、「移動の動き」テーブルを作成します。単独移動に加えペア移動での組み合わせがあり全部で10種類となりますが、今回は計算で求めます。
/* 単独補助テーブル */
singles (name, prey, predator)
AS (SELECT prey_name, 1, 0 FROM target UNION ALL
SELECT predator_name, 0, 1 FROM target
),
/* ペア補助テーブル */
pairs (pair_name, preys, predators)
AS (SELECT MIN(CONCAT(a.name, ' ', b.name)),
a.prey + b.prey,
a.predator + b.predator
FROM singles a,
singles b
GROUP BY a.prey + b.prey, a.predator + b.predator
),
/* 動作テーブル */
moves (direction, move, preys, predators)
AS (SELECT 'R', name, prey, predator FROM singles UNION ALL
SELECT 'L', name, -prey, -predator FROM singles UNION ALL
SELECT 'R', pair_name, preys, predators FROM pairs UNION ALL
SELECT 'L', pair_name, -preys, -predators FROM pairs
),
以下、Preysかひよこの移動数、Predatorsがイヌの移動数を表しています。
SELECT * FROM moves;
+-----------+-------------+-------+-----------+
| direction | move | preys | predators |
+-----------+-------------+-------+-----------+
| L | Chick | -1 | 0 | -- 左岸へ単独移動 ひよこ
| L | Dog | 0 | -1 | -- 左岸へ単独移動 イヌ
| L | Chick Chick | -2 | 0 | -- 左岸へペア移動 ひよこ ひよこ
| L | Chick Dog | -1 | -1 | -- 左岸へペア移動 ひよこ イヌ
| L | Dog Dog | 0 | -2 | -- 左岸へペア移動 イヌ イヌ
| R | Chick | 1 | 0 | -- 右岸へ単独移動 ひよこ
| R | Dog | 0 | 1 | -- 右岸へ単独移動 イヌ
| R | Chick Chick | 2 | 0 | -- 右岸へペア移動 ひよこ ひよこ
| R | Chick Dog | 1 | 1 | -- 右岸へペア移動 ひよこ イヌ
| R | Dog Dog | 0 | 2 | -- 右岸へペア移動 イヌ イヌ
+-----------+-------------+-------+-----------+
さて、「移動の動き」テーブルができたら再帰でブルートフォースサーチですね。前問同様、右岸にヒヨコもイヌもいない状態「0,0」からスタートして最終的に「3,3」になったら終了です。すべての移動組み合わせのうちWHERE句の条件を満たしたもののみ移動可となります。繰り返しはもちろん不可です。
recur (preys, predators, direction, goal, step, move, cycle)
AS (/* 右岸になにもないところからスタート */
SELECT 0, 0, 'L', 0, 0, CAST('' AS CHAR(20)), CAST('L0:0' AS CHAR(500))
UNION ALL
FROM recur r, /* 現在の状態(再帰) */
moves m, /* すべての動作 */
target t /* 最大人数取得 */
WHERE /* ゴール状態でない */
r.goal = 0 AND
/* 繰り返し違反でない */
NOT FIND_IN_SET(CONCAT(m.direction, r.preys + m.preys, ':',
r.predators + m.predators),
r.cycle) AND
/* 移動は右岸へと左岸へを交互に */
m.direction != r.direction AND
/* ひよこイヌとも最大人数まで移動可 */
r.preys + m.preys BETWEEN 0 AND t.prey_num AND
r.predators + m.predators BETWEEN 0 AND t.predator_num AND
/* 組み合わせ除外: 両岸でひよこがイヌと同数かより多いことただしひよこが0の場合はOK */
(r.preys + m.preys = 0 OR /* 右岸 */
r.preys + m.preys >= r.predators + m.predators) AND
(t.prey_num - (r.preys + m.preys) = 0 OR /* 左岸 */
t.prey_num - (r.preys + m.preys) >= t.predator_num - (r.predators + m.predators))
最後に前問同様、再帰で取得した行から解答ごとに経路を抽出し出力したら完成します。
解答クエリ
MySQL (8.0以降)
WITH RECURSIVE
/* 定義テーブル */
target (prey_name, prey_num, predator_name, predator_num)
AS (SELECT 'Chick', 3, 'Dog', 3
),
/* 単独補助テーブル */
singles (name, prey, predator)
AS (SELECT prey_name, 1, 0 FROM target UNION ALL
SELECT predator_name, 0, 1 FROM target
),
/* ペア補助テーブル */
pairs (pair_name, preys, predators)
AS (SELECT MIN(CONCAT(a.name, ' ', b.name)),
a.prey + b.prey,
a.predator + b.predator
FROM singles a,
singles b
GROUP BY a.prey + b.prey, a.predator + b.predator
),
/* 動作テーブル */
moves (direction, move, preys, predators)
AS (SELECT 'R', name, prey, predator FROM singles UNION ALL
SELECT 'L', name, -prey, -predator FROM singles UNION ALL
SELECT 'R', pair_name, preys, predators FROM pairs UNION ALL
SELECT 'L', pair_name, -preys, -predators FROM pairs
),
recur (preys, predators, direction, goal, step, move, cycle)
AS (/* 右岸になにもないところからスタート */
SELECT 0, 0, 'L', 0, 0, CAST('' AS CHAR(20)), CAST('L0:0' AS CHAR(500))
UNION ALL
/* すべての動作の可能性をチェックしながら再帰 */
SELECT r.preys + m.preys,
r.predators + m.predators,
m.direction,
CASE WHEN r.preys + m.preys + r.predators + m.predators = t.prey_num + t.predator_num
THEN 1 ELSE 0 /* 右岸に全て移動すればゴール */
END,
r.step + 1,
CONCAT(CASE WHEN m.direction = 'R' THEN '--> ' ELSE '<-- ' END, m.move),
CONCAT(r.cycle , ',', m.direction, r.preys + m.preys, ':', r.predators + m.predators)
FROM recur r, /* 現在の状態(再帰) */
moves m, /* すべての動作 */
target t /* 最大人数取得 */
WHERE /* ゴール状態でない */
r.goal = 0 AND
/* 繰り返し違反でない */
NOT FIND_IN_SET(CONCAT(m.direction, r.preys + m.preys, ':', r.predators + m.predators),
r.cycle) AND
/* 移動は右岸へと左岸へを交互に */
m.direction != r.direction AND
/* ひよこイヌとも最大人数まで移動可 */
r.preys + m.preys BETWEEN 0 AND t.prey_num AND
r.predators + m.predators BETWEEN 0 AND t.predator_num AND
/* 組み合わせ除外: ひよこがイヌと同数かより多いことただしひよこが0の場合はOK */
(r.preys + m.preys = 0 OR /* 右岸 */
r.preys + m.preys >= r.predators + m.predators) AND
(t.prey_num - (r.preys + m.preys) = 0 OR /* 左岸 */
t.prey_num - (r.preys + m.preys) >= t.predator_num - (r.predators + m.predators))
),
/* 深さ優先探索順に並び替え */
depth_order
AS (SELECT r.*,
ROW_NUMBER() OVER (ORDER BY cycle) search_id
FROM recur r
)
/* ゴールまでの経路を選択して表示 */
SELECT CASE WHEN step = 0 THEN CONCAT ('(', grp, ')') ELSE '' END answer,
step,
CONCAT(LPAD(SUBSTRING('******', 1, prey_num - preys ), 6, ' '), ' :',
LPAD(SUBSTRING('******', 1, predator_num - predators), 6, ' ')) "Chicks : Dogs",
move,
CONCAT(LPAD(SUBSTRING('******', 1, preys ), 6, ' '), ' :',
LPAD(SUBSTRING('******', 1, predators), 6, ' ')) "Chicks : Dogs"
FROM (SELECT g.grp, r.*,
ROW_NUMBER() OVER (PARTITION BY g.grp, r.step ORDER BY r.search_id DESC) rn
FROM (SELECT search_id, step,
ROW_NUMBER() OVER (ORDER BY step) grp FROM depth_order WHERE goal = 1) g,
depth_order r
WHERE g.search_id >= r.search_id and g.step >= r.step) d,
target t
WHERE rn = 1
ORDER BY grp, step
;
Oracle (11gR2以降)
COL left HEAD " Chicks : Dogs" FOR a15
COL right HEAD " Chicks : Dogs" FOR a15
WITH
target (prey_name, prey_num, predator_name, predator_num)
AS (SELECT 'Chick', 3, 'Dog', 3 FROM DUAL
),
singles (name, prey, predator)
AS (SELECT prey_name, 1, 0 FROM target UNION ALL
SELECT predator_name, 0, 1 FROM target
),
pairs (pair_name, preys, predators)
AS (SELECT MAX(a.name || ' ' || b.name),
a.prey + b.prey,
a.predator + b.predator
FROM singles a,
singles b
GROUP BY a.prey + b.prey, a.predator + b.predator
),
moves (direction, move, preys, predators)
AS (SELECT 'R', name, prey, predator FROM singles UNION ALL
SELECT 'L', name, -prey, -predator FROM singles UNION ALL
SELECT 'R', pair_name, preys, predators FROM pairs UNION ALL
SELECT 'L', pair_name, -preys, -predators FROM pairs
),
recur (preys, predators, direction, goal, step, move)
AS (SELECT 0, 0, 'L', 0, 0, CAST(NULL AS VARCHAR2(20)) FROM DUAL
UNION ALL
SELECT r.preys + m.preys,
r.predators + m.predators,
m.direction,
DECODE(r.preys + m.preys + r.predators + m.predators,
t.prey_num + t.predator_num, 1, 0),
r.step + 1,
DECODE(m.direction, 'R', '--> ', '<-- ') || m.move
FROM recur r,
moves m,
target t
WHERE m.direction != r.direction AND
r.preys + m.preys BETWEEN 0 AND t.prey_num AND
r.predators + m.predators BETWEEN 0 AND t.predator_num AND
(r.preys + m.preys = 0 OR r.preys + m.preys >= r.predators + m.predators) AND
(t.prey_num - (r.preys + m.preys) = 0 OR
t.prey_num - (r.preys + m.preys) >= t.predator_num - (r.predators + m.predators)) AND
r.goal = 0
)
SEARCH DEPTH FIRST BY step SET search_id
CYCLE direction, preys, predators SET cycle TO 1 DEFAULT 0
--
SELECT DECODE(step, 0, '('||grp||')') answer,
step,
LPAD(NVL(SUBSTR('******', 1, prey_num - preys ), ' '), 6, ' ') || ' :' ||
LPAD(NVL(SUBSTR('******', 1, predator_num - predators), ' '), 6, ' ') left,
move,
LPAD(NVL(SUBSTR('******', 1, preys ), ' '), 6, ' ') || ' :' ||
LPAD(NVL(SUBSTR('******', 1, predators), ' '), 6, ' ') right
FROM (SELECT g.grp, r.*,
ROW_NUMBER() OVER (PARTITION BY g.grp, r.step ORDER BY r.search_id DESC) rn
FROM (SELECT search_id, step, ROW_NUMBER() OVER (ORDER BY step) grp
FROM recur
WHERE goal = 1) g,
RECUR r
WHERE g.search_id >= r.search_id and g.step >= r.step),
target t
WHERE rn = 1
ORDER BY grp, step
;
おわりに
どちらの問題でも、まず動きを定義するテーブルを作成し、再帰しながら現在の状態に動作テーブルを掛け合わせて移動候補を作成しつつ移動不可の行を条件で除外していく、という手順になります。まぁSQLの再帰だとだいたいそんな感じになるんでしょうかね。迷路を解く再帰もにたような感じでしたし。
なんにせよMySQLでも文法的に再帰の繰り返し検知ができるようなってほしいところですね。
以上です。