M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Julia Language Programming

簡単なプログラム (6)

[ Home | Light | Julia ]

●コルーチン

複数のコルーチンを使った簡単なサンプルプログラムです。

リスト : 複数のコルーチン

function printcode(code)
    while true
        print(code)
        produce(true)
    end
end

function test_a(n)
    xs = map(x -> Task(() -> printcode(x)), ["h", "e", "y", "!", " "])
    for _ in 1 : n
        for x in xs; consume(x); end
    end
end

function printcode1(code, next)
    while true
        print(code)
        if typeof(next) == Task
            consume(next)
        end
        produce(true)
    end
end

function test_b(n)
    a = @task printcode1(" ", 0)
    b = @task printcode1("!", a)
    c = @task printcode1("y", b)
    d = @task printcode1("e", c)
    e = @task printcode1("h", d)
    for _ in 1 : n
        consume(e)
    end
end

関数 printcode() は引数 code を表示して、produce() で親コルーチンに戻ります。関数 test_a() では、h, e, y, !, 空白を表示するコルーチンを生成し、コルーチンを順番に呼び出すと、指定した回数だけ "hey! " を表示することができます。

関数 printcode1() は code のほかに次に実行するコルーチン next を受け取ります。コルーチンの中では、code を表示したあと next の型が Task であれば、consume() で next の実行を再開します。そのあと、produce() で親コルーチンに戻ります。あとはコルーチンを 5 つ生成して、関数 test_b() で最後に生成したコルーチン e を呼び出します。

julia> test_a(5)
hey! hey! hey! hey! hey!
julia> test_a(10)
hey! hey! hey! hey! hey! hey! hey! hey! hey! hey!
julia> test_b(5)
hey! hey! hey! hey! hey!
julia> test_b(10)
hey! hey! hey! hey! hey! hey! hey! hey! hey! hey!

次は、コルーチンを使って順列を生成するプログラムを示します。

リスト : 順列の生成 (コルーチン版)

function gen_perm(nums)
    function perm(n)
        if n == length(nums)
            produce([])
        else
            for xs in @task perm(n + 1)
                for y in nums
                    if !(y in xs)
                        produce(push!(copy(xs), y))
                    end
                end
            end
        end
    end
    @task perm(0)
end

ジェネレータ gen_perm() の引数 nums は要素を格納した配列です。実際の処理は局所関数 perm() で行います。n は選択した要素の個数を表します。n が nums の要素数と等しい場合は、すべての要素を選択したので produce() で空の配列 [ ] を返します。そうでなければ、@task perm() で生成される値を for 文で受け取ります。そして、その値 xs に要素 y を追加した配列を produce() で返します。このとき、配列 xs をコピーすることに注意してください。これで順列を生成することができます。

julia> for x in gen_perm([1,2,3,4]); println(x); end
Any[1,2,3,4]
Any[1,2,4,3]
Any[1,3,2,4]
Any[1,3,4,2]
Any[1,4,2,3]
Any[1,4,3,2]
Any[2,1,3,4]
Any[2,1,4,3]
Any[2,3,1,4]
Any[2,3,4,1]
Any[2,4,1,3]
Any[2,4,3,1]
Any[3,1,2,4]
Any[3,1,4,2]
Any[3,2,1,4]
Any[3,2,4,1]
Any[3,4,1,2]
Any[3,4,2,1]
Any[4,1,2,3]
Any[4,1,3,2]
Any[4,2,1,3]
Any[4,2,3,1]
Any[4,3,1,2]
Any[4,3,2,1]

また、次のように順列を生成する高い階段関数 permutations() を作成し、それをコルーチンを使ってジェネレータに変換することもできます。

リスト : 順列の生成 (2)

function permutations(f, nums)
    function perm(xs)
        if length(xs) == length(nums)
            f(copy(xs))
        else
            for n in nums
                if !(n in xs)
                    push!(xs, n)
                    perm(xs)
                    pop!(xs)
                end
            end
        end
    end
    perm([])
end

# 高い階段関数をジェネレータに変換
function make_gen(fn, args...)
    @task fn(x -> produce(x), args...)
end

関数 make_gen() の引数 fn は高階関数、そのあとに fn() に渡す引数を可変個引数で受け取ります。なお、fn() は第 1 引数に関数を受け取るものとします。あとは、fn() の第 1 引数に無名関数 x -> produce(x) を渡します。無名関数が呼び出されると、produce() により引数 x を consume() に返して実行が中断されます。

julia> g = make_gen(permutations, [1,2,3])
Task (runnable) @0x052936a0

julia> print(consume(g))
Any[1,2,3]
julia> print(consume(g))
Any[1,3,2]
julia> print(consume(g))
Any[2,1,3]
julia> print(consume(g))
Any[2,3,1]
julia> print(consume(g))
Any[3,1,2]
julia> print(consume(g))
Any[3,2,1]
julia> print(consume(g))
nothing

●エラトステネスの篩

コルーチンを使った「エラトステネスの篩」です。

リスト : コルーチンによるエラトステネスの篩

# n から始まる整数列
function integers(n)
    while true
        produce(n)
        n += 1
    end
end

# フィルター
function filter(f, src)
    Task(() -> while true
                   m = consume(src)
                   if f(m); produce(m); end
               end)
end

function sieve(x)
    nums = @task integers(2)
    for _ in 1 : x
        n = consume(nums)
        print("$n ")
        nums = filter(x -> x % n != 0, nums)
    end
end

sieve(100)

関数 integers() は n から始まる整数列を生成します。関数 filter() は引数 f で渡された述語が偽を返す要素を src から取り除きます。consume() で src から要素を取り出して m にセットします。f(m) が真であれば produce(m) で親コルーチンに m を返します。これで述語が偽を返す要素を取り除くことができます。

素数を求める関数 sieve も簡単です。引数 x は求める素数の個数です。最初に、2 から始まる整数列を @task integers(2) で生成して変数 nums に セットします。nums の先頭要素が素数になります。consume() で nums から素数を取り出して n にセットします。次に n を表示して、n で割り切れる整数を取り除くフィルターを生成して nums にセットします。つまり、x 個の素数を求めるために、x 個のフィルターを重ねていくわけです。

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 
107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 
223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 
337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 
457 461 463 467 479 487 491 499 503 509 521 523 541

●二分木 (immutable)

immutable な二分木です。節を書き換えることができないので、データの挿入や削除で二分木をたどるときは、新しい節を生成していることに注意してください。

リスト : immutable な二分木

abstract Tree

immutable Nil <: Tree
end

immutable Node <: Tree
    item
    left::Tree
    right::Tree
end

const nil = Nil()

# 探索
function search_tree(node::Tree, x)
    while node != nil
        if node.item == x
            return true
        elseif x < node.item
            node = node.left
        else
            node = node.right
        end
    end
    false
end

# 最小値の探索
function search_min(node::Node)
    while node.left != nil
        node = node.left
    end
    node.item
end

# 最大値の探索
function search_max(node::Node)
    while node.right != nil
        node = node.right
    end
    node.item
end

# 挿入
function insert_tree(node::Tree, x)
    if node == nil
        Node(x, nil, nil)
    elseif x == node.item
        node
    elseif x < node.item 
        Node(node.item, insert_tree(node.left, x), node.right)
    else
        Node(node.item, node.left, insert_tree(node.right, x))
    end
end

# 最小値の削除
function delete_min(node::Node)
    if node.left == nil
        node.right
    else
        Node(node.item, delete_min(node.left), node.right)
    end
end

# 最大値の削除
function delete_max(node::Node)
    if node.right == nil
        node.left
    else
        Node(node.item, node.left, delete_max(node.right))
    end
end

# 削除
function delete_tree(node::Tree, x)
    if node == nil
        node
    elseif node.item == x
        if node.left == nil; return node.right; end
        if node.right == nil; return node.left; end
        Node(search_min(node.right), node.left, delete_min(node.right))
    elseif x < node.item
        Node(node.item, delete_tree(node.left, x), node.right)
    else
        Node(node.item, node.left, delete_tree(node.right, x))
    end
end

# 木の巡回
function for_each_tree(f, node::Tree)
    if node != nil
        for_each_tree(f, node.left)
        f(node.item)
        for_each_tree(f, node.right)
    end
end

# コルーチンによるジェネレータの生成
function make_gen(node::Tree)
    @task for_each_tree(x -> produce(x), node)
end

# テスト
root = nil
for x in [5,6,4,7,3,8,2,9,1]
    root = insert_tree(root, x)
end

for x in 0 : 10
    println(search_tree(root, x))
end

println(search_min(root))
println(search_max(root))

g = make_gen(root)
for _ in 1 : 9
    x = consume(g)
    print("$x ")
end
println("")

root = delete_min(root)
for_each_tree(x -> print("$x "), root)
println("")

root = delete_max(root)
for_each_tree(x -> print("$x "), root)
println("")

for x in 2 : 8
    root = delete_tree(root, x)
    for_each_tree(x -> print("$x "), root)
    println("")
end
false
true
true
true
true
true
true
true
true
true
false
1
9
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
2 3 4 5 6 7 8
3 4 5 6 7 8
4 5 6 7 8
5 6 7 8
6 7 8
7 8
8

●ナンバープレース (2)

ナンバープレース (1) をビット操作で高速化したプログラムです。解法アルゴリズムの説明は拙作のページ C言語超入門 数独の解法 をお読みください。

リスト : ナンバープレースの解法 (ビット操作版)

# 定数
const SIZE = 9

# 大域変数
const board = Array(Int, (9, 9))
const xflag = Array(Int, 9)
const yflag = Array(Int, 9)
const zflag = Array(Int, 9)

# ブロック番号を求める
block_number(x, y) = div(y - 1, 3) * 3 + div(x - 1, 3) + 1

# 置くことができる数字を求める
get_number(x, y) = xflag[x] & yflag[y] & zflag[block_number(x, y)]

# 数字を置く
function put_number(x, y, n)
    board[x, y] = n
    xflag[x] $= n
    yflag[y] $= n
    zflag[block_number(x, y)] $= n
end

# 数字を削除する
function del_number(x, y)
    n = board[x, y]
    board[x, y] = 0
    xflag[x] $= n
    yflag[y] $= n
    zflag[block_number(x, y)] $= n
end

# 盤面とフラグの初期化
function init_board(q)
    fill!(xflag, 0x3fe)
    fill!(yflag, 0x3fe)
    fill!(zflag, 0x3fe)
    fill!(board, 0)
    for x in 1 : SIZE
        for y in 1 : SIZE
             n = q[x, y]
             if n > 0
                 put_number(x, y, 1 << n)
             end
        end
    end
end

# 盤面の表示
function print_board()
    for x in 1 : SIZE
        for y in 1 : SIZE
            n = count_ones(board[x, y] - 1)
            print("$n ")
        end
        println("")
    end
    println("")
end

# 解法
function solver(x, y)
    if y > SIZE
        print_board()
    elseif x > SIZE
        solver(1, y + 1)
    elseif board[x, y] > 0
        solver(x + 1, y)
    else
        m = get_number(x, y)
        while m > 0
            n = m & (-m)
            put_number(x, y, n)
            solver(x + 1, y)
            del_number(x, y)
            m &= m - 1
        end
    end
end

function solver1(q)
    init_board(q)
    solver(1, 1)
end

Puzzle Generater Japan にある Java版標準問題集 より問題 8-a, 8-b, 9-a, 9-b, 10-a, 10-b と Java版超難問集 の超難問 849 と 1122 を試してみたところ、実行時間は次のようになりました。

  表 : 実行結果 (単位 : 秒)

  問題 : Hint :  (1)  |  (2)
 ------+------+-------+-------
   8-a :  20  : 0.207 : 0.061 
   8-b :  20  : 0.043 : 0.015
   9-a :  20  : 0.046 : 0.010
   9-b :  21  : 0.023 : 0.007
  10-a :  22  : 0.019 : 0.006
  10-b :  22  : 0.024 : 0.010
   849 :  24  : 0.037 : 0.010
  1122 :  24  : 0.027 : 0.008
-------+------+-------+-------
  全体 :      : 0.440 : 0.137

実行環境 : Windows 7, Core i7-2670QM 2.20GHz

実行時間はどの問題でも速くなりました。全体では約 3.2 倍速くなっているので、ビット操作の効果は十分に出ていると思います。

●川渡りの問題

  1. 狼とヤギとキャベツの問題

    農夫が狼と山羊とキャベツを持って川の左岸にいます。農夫はこれらを川の右岸へ運ばなければいけませんが、ボートにはそのうちのひとつしか乗せることができません。狼は山羊を好んで食べるため、この 2 つを同じ岸に残すことはできません。また、山羊はキャベツを好んで食べるため、この 2 つも同じ岸に残すことはできません。この条件で、荷物をすべて右岸へ運ぶ手順を求めてください。

  2. 嫉妬深い夫の問題

    三組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、六人ともボートをこぐことができます。この条件で、三組の夫婦が川を渡る最短手順を求めてください。

  3. 宣教師と先住民

    3 人の宣教師と 3 人の先住民が川を渡ることになりました。川には 2 人乗りのボートが 1 そうしかありません。どのような時でも先住民の数が宣教師の数よりも多いと、宣教師は襲われてしまいます。6 人が安全に川を渡る最短手順を求めてください


●解答1

リスト : 狼とヤギとキャベツの問題 (反復深化)

# 定数
const farmer  = 1
const cabbage = 2
const goat = 4
const wolf = 8
const all  = 15

# ボートに乗せる組み合わせ
const boat_list = [farmer, farmer + cabbage, farmer + goat, farmer + wolf]

# 失敗か?
function isfail(st)
    bad1 = cabbage + goat
    bad2 = goat + wolf
    st & bad1 == bad1 || st & bad2 == bad2
end

# 表示
function print_state(st)
    print("[ ")
    if st & farmer > 0;  print("farmer ");  end
    if st & cabbage > 0; print("cabbage "); end
    if st & goat > 0;    print("goat ");    end
    if st & wolf > 0;    print("wolf ");    end
    print("]")
end

function print_answer(left, right)
    for i in 1 : length(left)
        print_state(left[i])
        print_state(right[i])
        println("")
    end
end

# 同一局面があるか?
function check_same_state(st, xs)
    for x in xs
        if x == st; return true; end
    end
    false
end

# 反復深化
function ids(n, limit, src, dst)
    if n == limit
        if src[end] == all
            print_answer(dst, src)
            throw("found!")
        end
    else
        for boat in boat_list
            if boat & src[end] == boat
                new_src = src[end] - boat
                new_dst = dst[end] + boat
                if !isfail(new_src) && !check_same_state(new_src, src)
                    push!(src, new_src)
                    push!(dst, new_dst)
                    ids(n + 1, limit, dst, src)
                    pop!(src)
                    pop!(dst)
                end
            end
        end
    end
end

try
    limit = 1
    while true
        println("----- $limit -----")
        ids(0, limit, [all], [0])
        limit += 2
    end
catch e
    println(e)
end
----- 1 -----
----- 3 -----
----- 5 -----
----- 7 -----
[ farmer cabbage goat wolf ][ ]
[ cabbage wolf ][ farmer goat ]
[ farmer cabbage wolf ][ goat ]
[ wolf ][ farmer cabbage goat ]
[ farmer goat wolf ][ cabbage ]
[ goat ][ farmer cabbage wolf ]
[ farmer goat ][ cabbage wolf ]
[ ][ farmer cabbage goat wolf ]
found!

●解答2

リスト : 嫉妬深い夫の問題 (反復深化)

# 定数
const Boat = 1
const Ha   = 2
const Hb   = 4
const Hc   = 8
const Wa   = 16
const Wb   = 32
const Wc   = 64
const MAN  = 14
const ALL  = 127

# ボートに乗る組み合わせ
const boat_list = [
    Ha, Hb, Hc,
    Wa, Wb, Wc,
    Ha | Hb, Ha | Hc, Hb | Hc,
    Wa | Wb, Wa | Wc, Wb | Wc,
    Ha | Wa, Hb | Wb, Hc | Wc
]

# 安全か?
function safep(st)
    for (w, h) in [(Wa, Ha), (Wb, Hb), (Wc, Hc)]
        # 婦人 w がいて、夫 h がいなくて、他の夫がいる場合はダメ
        if st & w > 0 && st & h == 0 && st & MAN > 0
            return false
        end
    end
    true
end

# 手順の表示
function print_state(st)
    print("[ ")
    if st & Boat > 0; print("Boat "); end
    if st & Ha > 0; print("Ha "); end
    if st & Hb > 0; print("Hb "); end
    if st & Hc > 0; print("Hc "); end
    if st & Wa > 0; print("Wa "); end
    if st & Wb > 0; print("Wb "); end
    if st & Wc > 0; print("Wc "); end
    print("]")
end

function print_answer(left, right)
    for i in 1 : length(left)
        print_state(left[i])
        print_state(right[i])
        println("")
    end
end

# 同一局面のチェック
function check_same_state(st, xs)
    for x in xs
        if x == st; return true; end
    end
    false
end

# 反復深化
function ids(n, limit, src, dst)
    if n == limit
        if src[end] == ALL
            print_answer(dst, src)
            throw("found!")
        end
    else
        for b in boat_list
            x = b | Boat
            if src[end] & x != x; continue; end
            new_src = src[end] - x
            new_dst = dst[end] + x
            if safep(new_src) && safep(new_dst) && !check_same_state(new_dst, dst)
                push!(src, new_src)
                push!(dst, new_dst)
                ids(n + 1, limit, dst, src)
                pop!(src)
                pop!(dst)
            end
        end
    end
end

try
    limit = 1
    while true
        println("----- $limit -----")
        ids(0, limit, [ALL], [0])
        limit += 2
    end
catch e
    println(e)
end
----- 1 -----
----- 3 -----
----- 5 -----
----- 7 -----
----- 9 -----
----- 11 -----
[ Boat Ha Hb Hc Wa Wb Wc ][ ]
[ Ha Hb Hc Wc ][ Boat Wa Wb ]
[ Boat Ha Hb Hc Wa Wc ][ Wb ]
[ Ha Hb Hc ][ Boat Wa Wb Wc ]
[ Boat Ha Hb Hc Wa ][ Wb Wc ]
[ Ha Wa ][ Boat Hb Hc Wb Wc ]
[ Boat Ha Hb Wa Wb ][ Hc Wc ]
[ Wa Wb ][ Boat Ha Hb Hc Wc ]
[ Boat Wa Wb Wc ][ Ha Hb Hc ]
[ Wc ][ Boat Ha Hb Hc Wa Wb ]
[ Boat Hc Wc ][ Ha Hb Wa Wb ]
[ ][ Boat Ha Hb Hc Wa Wb Wc ]
found!

●解答3

リスト : 宣教師と先住民

# 状態はタプルで表す
# (ボート 左宣 左先 右宣 右先)

# ボートに乗る人数の組み合わせ (宣教師, 先住民)
const boat_list = [
    (1, 0), (0, 1), (1, 1), (2, 0), (0, 2)
]

# 安全か?
function safep(b, lm, le, rm, re)
    (lm >= le || lm == 0) && (rm >= re || rm == 0)
end

# 移動
function move_boat(st, boat)
    b, lm, le, rm, re = st
    m, e = boat
    if b == :left
        if lm >= m && le >= e
            new_st = (:right, lm - m, le - e, rm + m, re + e)
        else
            ()
        end
    else
        if rm >= m && re >= e
            new_st = (:left, lm + m, le + e, rm - m, re - e)
        else
            ()
        end
    end
end

# 同一局面のチェック
function check_same_state(st, xs)
    for x in xs
        if x == st; return true; end
    end
    false
end

# 反復深化
function ids(n, limit, moves)
    if n == limit
        if moves[end] == (:right, 0, 0, 3, 3)
            for st in moves; println(st); end
            throw("found!")
        end
    else
        for b in boat_list
            new_st = move_boat(moves[end], b)
            if new_st != () && safep(new_st...) && !check_same_state(new_st, moves)
                push!(moves, new_st)
                ids(n + 1, limit, moves)
                pop!(moves)
            end
        end
    end
end

try
    limit = 1
    while true
        println("----- $limit -----")
        ids(0, limit, [(:left, 3, 3, 0, 0)])
        limit += 2
    end
catch e
    println(e)
end
----- 1 -----
----- 3 -----
----- 5 -----
----- 7 -----
----- 9 -----
----- 11 -----
(:left,3,3,0,0)
(:right,2,2,1,1)
(:left,3,2,0,1)
(:right,3,0,0,3)
(:left,3,1,0,2)
(:right,1,1,2,2)
(:left,2,2,1,1)
(:right,0,2,3,1)
(:left,0,3,3,0)
(:right,0,1,3,2)
(:left,1,1,2,2)
(:right,0,0,3,3)
found!

●ペグ・ソリティア

ペグ・ソリテアは盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは、次のルールに従って移動し、除去することができます。

  1. ペグは隣にあるペグをひとつだけ跳び越して、空き場所へ着地する。
  2. 跳び越されたペグは盤上から取り除かれる。
  3. 移動方向はふつう縦横のみの 4 方向だが、ルールによっては斜め方向の移動を許す場合もある。
  4. 同じペグの連続跳び越しは 1 手と数える。

参考文献 1 によると、最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、最初の空き位置が盤の中央で、なおかつ、補償型の解がある場合を「中央補償型の解」と呼ぶそうです。

-- 参考文献 --------
1. 橋本哲, 『特集コンピュータパズルへの招待 ペグ・ソリテア編』, C MAGAZINE 1996 年 2 月号, ソフトバンク

問題1 Hoppers

Hoppers は芦ヶ原伸之氏が考案されたペグ・ソリテアです。次の図を見てください。

●───●───●  
│\  /│\  /│  
│  ●  │  ●  │  
│/  \│/  \│  
●───○───●  
│\  /│\  /│  
│  ●  │  ●  │  
│/  \│/  \│  
●───●───●  

   図 : Hoppers

Hoppers は穴を 13 個に減らしていて、遊ぶのに手頃な大きさになっています。上図に示したように、最初に中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。

解答


問題2 変形三角盤

下図は「変形三角盤」と呼ばれるペグ・ソリテアです。21 個のマスが少し変わった三角形に並んでいて、そこにペグを配置します。ペグは別のペグをひとつだけ跳び越えることで、任意の方向へ移動することができます。もちろん、着地する地点が空いていなければ、跳び越すことはできません。

                    ●───●
                      \  /
                        ●
                      /  \
                    ●───●
                  /  \  /  \
                ●───○───●
              /  \  /  \  /  \
            ●───●───●───●
          /  \  /  \  /  \  /  \
●───●───●───●───●───●───●
  \  /                                  \  /
    ●                                      ●

                 図 : 変形三角盤

今回は上図のように 21 個のペグの中からひとつのペグを取り除き、最初の空き位置と最後に残ったペグの位置が同じになる「補償型の解」の最短手数を求めることにします。

解答


解答1

リスト : Hoppers (反復深化)

#=

●───●───●    1───2───3  
│\  /│\  /│    │\  /│\  /│  
│  ●  │  ●  │    │  4  │  5  │  
│/  \│/  \│    │/  \│/  \│  
●───○───●    6───7───8  
│\  /│\  /│    │\  /│\  /│  
│  ●  │  ●  │    │  9  │  10  │  
│/  \│/  \│    │/  \│/  \│  
●───●───●    11───12───13  
 
  (1) Hoppers             (2) 座標

=#

# 定数
const SIZE = 13
const HOLE = 7
const MAX_JUMP = 11

# 跳び先表 (del, to)
const jump_table = Array{Tuple{Int,Int}, 1}[
    [(2, 3), (4, 7), (6, 11)],    # 1
    [(4, 6), (7, 12), (5, 8)],    # 2
    [(2, 1), (5, 7), (8, 13)],    # 3
    [(7, 10)],                    # 4
    [(7, 9)],                     # 5
    [(4, 2), (7, 8), (9, 12)],    # 6
    [(4, 1), (5, 3), (9, 11), (10, 13)], # 7
    [(5, 2), (7, 6), (10, 12)],   # 8
    [(7, 5)],                     # 9
    [(7, 4)],                     # 10
    [(6, 1), (9, 7), (12, 13)],   # 11
    [(9, 6), (7, 2), (10, 8)],    # 12
    [(8, 3), (10, 7), (12, 11)]   # 13
]

# 盤面
const board = Array(Bool, SIZE)

# 手順の表示
function print_moves(moves)
    print("($(moves[1][1]),$(moves[1][2])")
    for i in 2 : MAX_JUMP
        if moves[i - 1][2] == moves[i][1]
            print(",$(moves[i][2])")
        else
            print(")($(moves[i][1]),$(moves[i][2])")
        end
    end
    println(")")
end

# 反復深化
function ids(n, limit, jc, moves)
    if n == MAX_JUMP
        if board[HOLE]
            print_moves(moves)
            throw("found!")
        end
    else
        for from in 1 : SIZE
            if !board[from]; continue; end
            for (del, to) in jump_table[from]
                if !board[del] || board[to]; continue; end
                jc1 = jc + (from == moves[end][2] ? 0 : 1)
                if jc1 <= limit
                    board[from] = false
                    board[del] = false
                    board[to] = true
                    push!(moves, (from, to))
                    ids(n + 1, limit, jc1, moves)
                    pop!(moves)
                    board[to] = false
                    board[del] = true
                    board[from] = true
                end
            end
        end
    end
end

# 実行
try
    fill!(board, true)
    board[1] = false
    board[4] = false  # 初手 1 -> 4 -> 7
    for limit in 2 : MAX_JUMP
        println("----- $limit -----")
        ids(1, limit, 1, [(1, 7)])
    end
catch e
    println(e)
end
----- 2 -----
----- 3 -----
----- 4 -----
----- 5 -----
----- 6 -----
----- 7 -----
(1,7)(10,4)(3,1,7)(12,2)(11,1,3,7)(9,5)(13,3,7)
found!

解答2

リスト : 変形三角盤 (反復深化 + 下限値枝刈り法)

#=
                    1───2
                      \  /
                        3
                      /  \
                    4───5
                  /  \  /  \
                6───7───8
              /  \  /  \  /  \
            9───10───11───12
          /  \  /  \  /  \  /  \
13───14───15───16───17───18───19
  \  /                                  \  /
    20                                      21

=#

# 定数
const SIZE = 21
const HOLE = 7
const MAX_JUMP = 19

# コーナーペグ
const corner = [
                true,true,
                  false,
               false,false,
            false,false,false,
         false,false,false,false,
 true,false,false,false,false,false,true,
    true,                        true
]

# 跳び先表
# 6 個のコーナーペグがジャンプするには
# 3, 6, 8, 14, 16, 18 の 6 つのペグが必要になる。
# これらのペグがコーナー以外のペグから跳び越されると、
# コーナーペグの移動が不可能になる
const jump_table = Array{Tuple{Int,Int}, 1}[
    [(3, 5)],                             # 1
    [(3, 4)],                             # 2
    [(4, 6), (5, 8)],                     # 3
    [(7, 11)],                            # 4 (3, 2), (6, 9) は禁止
    [(7, 10)],                            # 5 (3, 1), (8, 12) は禁止 
    [(4, 3), (7, 8), (9, 14), (10, 16)],  # 6
    [(10, 15), (11, 17)],                 # 7
    [(5, 3), (7, 6), (11, 16), (12, 18)], # 8
    [(10, 11)],                           # 9 (6, 4), (14, 20) は禁止
    [(7, 5), (11, 12)],                   # 10
    [(7, 4), (10, 9)],                    # 11
    [(11, 10)],                           # 12 (8, 5), (18, 21) は禁止
    [(14, 15)],                           # 13
    [(9, 6), (15, 16)],                   # 14
    [(10, 7)],                            # 15 (14, 13), (16, 17) は禁止
    [(10,6), (11,8), (15,14), (17,18)],   # 16
    [(11, 7)],                            # 17 (16, 15), (18, 19) は禁止
    [(12, 8), (17, 16)],                  # 18
    [(18, 17)],                           # 19
    [(14, 9)],                            # 20
    [(18, 12)]                            # 21
]

# 盤面
const board = Array(Bool, SIZE)

# 手順の表示
function print_moves(moves)
    print("($(moves[1][1]),$(moves[1][2])")
    for i in 2 : MAX_JUMP
        if moves[i - 1][2] == moves[i][1]
            print(",$(moves[i][2])")
        else
            print(")($(moves[i][1]),$(moves[i][2])")
        end
    end
    println(")")
end

# 反復深化 + 下限値枝刈り法
function ids(n, limit, jc, moves, lower)
    if n == MAX_JUMP
        if board[HOLE]
            print_moves(moves)
            throw("found!")
        end
    else
        for from in 1 : SIZE
            if !board[from]; continue; end
            for (del, to) in jump_table[from]
                if !board[del] || board[to]; continue; end
                jc1 = jc + (from == moves[end][2] ? 0 : 1)
                # コーナーに着地するペグは無い
                lower1 = corner[from] ? lower - 1 : lower
                if jc1 + lower1 <= limit
                    board[from] = false
                    board[del] = false
                    board[to] = true
                    push!(moves, (from, to))
                    ids(n + 1, limit, jc1, moves, lower1)
                    pop!(moves)
                    board[to] = false
                    board[del] = true
                    board[from] = true
                end
            end
        end
    end
end

# 実行
try
    fill!(board, true)
    board[15] = false
    board[10] = false  # 初手 15 -> 10 -> 7
    for limit in 7 : MAX_JUMP
        println("----- $limit -----")
        ids(1, limit, 1, [(15, 7)], 6)
    end
catch e
    println(e)
end
----- 7 -----
----- 8 -----
----- 9 -----
----- 10 -----
----- 11 -----
----- 12 -----
(15,7)(12,10)(4,11)(2,4)(8,3)(1,5)(13,15,7)(6,3,8,6,14)(21,12,10)(16,18)(20,9,11)(19,17,7)
found!

Copyright (C) 2016 Makoto Hiroi
All rights reserved.

[ Home | Light | Julia ]