#/***********************************************************
#    cannibals.rb -- 宣教師と人食い人
#***********************************************************/
M = 3  # /* 宣教師の数 */
C = 3  # /* 人食い人の数 */
B = 2  # /* ボートの定員 */

$np = 0; $solutuion = 0
$mb = []; $cb = []; $mh = []; $ch = []
row = Array.new(C+1).fill(0)
$flag = []; (M+1).times { $flag.push(row.dup) }
$mmm = "MMMMMMMMMM", $ccc = "CCCCCCCCCC"

def found( n)  # 解の表示 
    printf("解 %d\n", $solution += 1)
    for i in 0..n
        printf("%4d  %-*.*s %-*.*s  /  %-*.*s %-*.*s\n",\
            i, M, $mh[i], $mmm, C, $ch[i], $ccc,\
               M, M - $mh[i], $mmm, C, C - $ch[i], $ccc)
    end
end

$i = 0
def try  # 再帰的に試す 
    $i += 1
    for j in 1...$np
        if (($i & 1) != 0)   # 奇数回目は向こうに行く 
            m = $mh[$i - 1] - $mb[j];  c = $ch[$i - 1] - $cb[j]
        else          # 偶数回目はこちらに来る 
            m = $mh[$i - 1] + $mb[j];  c = $ch[$i - 1] + $cb[j]
        end
        if (m < 0 || c < 0 || m > M || c > C ||\
                ($flag[m][c] & (1 << ($i & 1))) != 0); next
        end
        $mh[$i] = m;  $ch[$i] = c
        if (m == 0 && c == 0); found($i)
        else 
            $flag[m][c] |= 1 << ($i & 1);  try()
            $flag[m][c] ^= 1 << ($i & 1)
        end
    end
    $i -= 1
end

$np = 0
for m in 0..B
    for c in 0..(B - m)
        if (m == 0 || m >= c) 
            $mb[$np] = m;  $cb[$np] = c;  $np += 1
        end
    end
end
for m in 0..M
    for c in 0..C
        if ((m > 0 && m < c) || (m < M && M - m < C - c))
            $flag[m][c] |= 1 | 2
        end
    end
end
$mh[0] = M;  $ch[0] = C;  $flag[M][C] |= 1
$solution = 0;  try()
if ($solution == 0); printf("解はありません.\n"); end

exit 0