今回は「二分木 (binary tree)」というデータ構造を作ってみましょう。F# のモジュール Map や Set の実装には「平衡木 (balanced binary tree)」が用いられていますが、単純な二分木であれば私達でも簡単にプログラムすることができます。二分木の詳しい説明は、以下に示す拙作のページをお読みくださいませ。
module Tree =
// 型
type 'a tree =
private | Nil
| Node of 'a * 'a tree * 'a tree
// 空の木
val empty: unit -> 'a tree
// 木は空か？
val isEmpty: _arg1: 'a tree -> bool
// データの追加
val add: x: 'a -> _arg1: 'a tree -> 'a tree when 'a: comparison
// データの探索
val contains: x: 'a -> _arg1: 'a tree -> bool when 'a: comparison
// 最小値
val min: _arg1: 'a tree -> 'a
// 最大値
val max: _arg1: 'a tree -> 'a
// 最小値の削除
val deleteMin: _arg1: 'a tree -> 'a tree
// 最大値の削除
val deleteMax: _arg1: 'a tree -> 'a tree
// データの削除
val delete: x: 'a -> _arg1: 'a tree -> 'a tree when 'a: comparison
// 木の巡回
val iter: f: ('a -> unit) -> _arg1: 'a tree -> unit
// 木の畳み込み
val fold: f: ('a -> 'b -> 'a) -> a: 'a -> _arg1: 'b tree -> 'a
//
// tree.fsx : 二分木 (immutable)
//
// Copyright (C) 2022 Makoto Hiroi
//
module Tree
// 二分木の定義
type 'a tree = private Nil | Node of 'a * 'a tree * 'a tree
// 空の木
let empty () = Nil
// 木は空か？
let isEmpty = function
Nil -> true
| _ -> false
// 追加
let rec add x = function
Nil -> Node (x, Nil, Nil)
| (Node (y, _, _)) as node when x = y -> node
| Node (y, l, r) when x < y -> Node (y, (add x l), r)
| Node (y, l, r) -> Node (y, l, (add x r))
// 探索
let rec contains x = function
Nil -> false
| Node (y, _, _) when x = y -> true
| Node (y, l, _) when x < y -> contains x l
| Node (_, _, r) -> contains x r
// 最小値を求める
let rec min = function
Nil -> failwith "empty tree"
| Node (x, Nil, _) -> x
| Node (_, l, _) -> min l
// 最大値を求める
let rec max = function
Nil -> failwith "empty tree"
| Node (x, _, Nil) -> x
| Node (_, _, r) -> max r
// 最小値を削除する
let rec deleteMin = function
Nil -> failwith "empty tree"
| Node (x, Nil, r) -> r
| Node (x, l, r) -> Node (x, (deleteMin l), r)
// 最大値を削除する
let rec deleteMax = function
Nil -> failwith "empty tree"
| Node (x, l, Nil) -> l
| Node (x, l, r) -> Node (x, l, (deleteMax r))
// データの削除
let rec delete x = function
Nil -> failwith "not delete"
| Node(y, l, r) ->
if x = y then
if l = Nil then r
else if r = Nil then l
else
let min_data = min r
Node (min_data, l, (deleteMin r))
else if x < y then
Node (y, (delete x l), r)
else
Node (y, l, (delete x r))
// 二分木の巡回
let rec iter f = function
Nil -> ()
| Node (x, l, r) -> iter f l; f x; iter f r
// 二分木の畳み込み
let rec fold f a = function
Nil -> a
| Node (x, l, r) -> fold f (f (fold f a l) x) r
> open Tree;; > let a = empty() |> add 5 |> add 3 |> add 7 |> add 4 |> add 6;; val a: int tree = Node (5, Node (3, Nil, Node (4, Nil, Nil)), Node (7, Node (6, Nil, Nil), Nil)) > isEmpty a;; val it: bool = false > contains 4 a;; val it: bool = true > contains 2 a;; val it: bool = false > contains 8 a;; val it: bool = false > min a;; val it: int = 3 > max a;; val it: int = 7 > let b = deleteMin a;; val b: int tree = Node (5, Node (4, Nil, Nil), Node (7, Node (6, Nil, Nil), Nil)) > contains 3 b;; val it: bool = false > let c = deleteMax b;; val c: int tree = Node (5, Node (4, Nil, Nil), Node (6, Nil, Nil)) > contains 7 c;; val it: bool = false > let d = a |> delete 3 |> delete 4 |> delete 5 |> delete 6 |> delete 7;; val d: int tree = Nil > isEmpty d;; val it: bool = true > iter (fun x -> printfn "%d" x) a;; 3 4 5 6 7 val it: unit = () > fold (fun a x -> x::a) [] a;; val it: int list = [7; 6; 5; 4; 3]
module Tree1 =
exception EmptyTree
type Tree<'a when 'a: comparison> =
new: unit -> Tree<'a>
member add: x: 'a -> Node<'a>
member contains: x: 'a -> bool
member delete: x: 'a -> Node<'a>
member deleteMax: unit -> Node<'a>
member deleteMin: unit -> Node<'a>
member fold: f: ('a0 -> 'a -> 'a0) -> a: 'a0 -> 'a0
abstract isEmpty: unit -> bool
member iter: f: ('a -> unit) -> unit
member max: unit -> 'a
member min: unit -> 'a
static member empty: unit -> Empty<'a>
abstract Item: 'a
abstract Left: Tree<'a>
abstract Right: Tree<'a>
and Node<'a when 'a: comparison> =
inherit Tree<'a>
new: x: 'a * l: Tree<'a> * r: Tree<'a> -> Node<'a>
override isEmpty: unit -> bool
override Item: 'a
override Left: Tree<'a>
override Right: Tree<'a>
and Empty<'a when 'a: comparison> =
inherit Tree<'a>
new: unit -> Empty<'a>
override isEmpty: unit -> bool
override Item: 'a
override Left: Tree<'a>
override Right: Tree<'a>
//
// tree1.fsx : 二分木 (クラスによる実装, immutable)
//
// Copyright (C) 2022 Makoto Hiroi
//
module Tree1
exception EmptyTree
[<AbstractClass>]
type Tree<'a when 'a: comparison>() =
// 空の木
static let nil = new Empty<'a>()
static member empty() = nil
abstract isEmpty: unit -> bool
abstract Item : 'a with get
abstract Left : Tree<'a> with get
abstract Right : Tree<'a> with get
member this.add(x: 'a) =
if this.isEmpty() then new Node<'a>(x, this, this)
else if x = this.Item then this :?> Node<'a>
else if x < this.Item then new Node<'a>(this.Item, this.Left.add(x), this.Right)
else new Node<'a>(this.Item, this.Left, this.Right.add(x))
member this.contains(x: 'a) =
if this.isEmpty() then false
else if x = this.Item then true
else if x < this.Item then this.Left.contains(x)
else this.Right.contains(x)
member this.min () =
if this.isEmpty() then failwith "empty tree"
else if this.Left.isEmpty() then this.Item
else this.Left.min()
member this.max () =
if this.isEmpty() then failwith "empty tree"
else if this.Right.isEmpty() then this.Item
else this.Right.max()
member this.deleteMin () =
if this.isEmpty() then failwith "empty tree"
else if this.Left.isEmpty() then this.Right :?> Node<'a>
else new Node<'a>(this.Item, this.Left.deleteMin(), this.Right)
member this.deleteMax () =
if this.isEmpty() then failwith "empty tree"
else if this.Right.isEmpty() then this.Left :?> Node<'a>
else new Node<'a>(this.Item, this.Left, this.Right.deleteMax())
member this.delete (x: 'a) =
if this.isEmpty() then failwith "not delete"
else if x = this.Item then
if this.Left.isEmpty() then this.Right
else if this.Right.isEmpty() then this.Left
else let min_data = this.Right.min()
new Node<'a>(min_data, this.Left, this.Right.deleteMin())
else if x < this.Item then new Node<'a>(this.Item, this.Left.delete(x), this.Right)
else new Node<'a>(this.Item, this.Left, this.Right.delete(x))
member this.iter f =
if this.isEmpty() then ()
else (
this.Left.iter f
f this.Item
this.Right.iter f
)
member this.fold f a =
if this.isEmpty() then a
else this.Right.fold f (f (this.Left.fold f a) this.Item)
and Node<'a when 'a: comparison>(x: 'a, l: Tree<'a>, r: Tree<'a>) =
inherit Tree<'a>()
let mutable item = x
let mutable left = l
let mutable right = r
override this.isEmpty () = false
override this.Item with get() = item
override this.Left with get() = left
override this.Right with get() = right
and Empty<'a when 'a: comparison>() =
inherit Tree<'a>()
override this.isEmpty() = true
override this.Item with get() = raise EmptyTree
override this.Left with get() = raise EmptyTree
override this.Right with get() = raise EmptyTree
> open Tree1;;
> let a = Tree<int>.empty();;
val a: Empty<int>
> a.isEmpty();;
val it: bool = true
> let b = a.add(5).add(3).add(7).add(4).add(6);;
val b: Node<int>
> b;;
val it: Node<int> =
FSI_0006.Tree1+Node`1[System.Int32]
{Item = 5;
Left = FSI_0006.Tree1+Node`1[System.Int32];
Right = FSI_0006.Tree1+Node`1[System.Int32];}
> b.iter (fun x -> printfn "%d" x);;
3
4
5
6
7
val it: unit = ()
> b.contains 3;;
val it: bool = true
> b.contains 7;;
val it: bool = true
> b.contains 0;;
val it: bool = false
> b.contains 8;;
val it: bool = false
> b.max();;
val it: int = 7
> b.min();;
val it: int = 3
> let c = b.deleteMax();;
val c: Node<int>
> c.contains 7;;
val it: bool = false
> let d = b.deleteMin();;
val d: Node<int>
> d.contains 3;;
val it: bool = false
> let e = b.delete(3).delete(4).delete(5).delete(6).delete(7);;
val e: Tree<int>
> e.isEmpty();;
val it: bool = true
> b.fold (fun a x -> x::a) [];;
val it: int list = [7; 6; 5; 4; 3]
カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。今回はカッコ列と二分木に関する問題を出題するので、F# で解答プログラムを作ってください。
以下に二分木の定義を示します。
リスト : 二分木の定義 type tree = L | N of tree * tree
N は節を、L は葉を表します。
リスト : 葉の個数を求める let rec countLeaf = function L -> 1 | N (l, r) -> countLeaf l + countLeaf r
> countLeaf L;; val it: int = 1 > countLeaf (N (L, L));; val it: int = 2 > countLeaf (N (N (L, L), N (L, L)));; val it: int = 4 > countLeaf (N (N (L, L), N (L, N (L, L))));; val it: int = 5
countLeaf の引数が葉 L ならば 1 を返します。節 N ならば、countLeaf を再帰呼び出しして、左部分木と右部分木の葉の個数を求め、それを足し算して返すだけです。
リスト : 木の高さを求める
let rec treeHeight = function
L -> 0
| N (l, r) -> let a = treeHeight l
let b = treeHeight r
1 + max a b
> treeHeight L;; val it: int = 0 > treeHeight (N (L, L));; val it: int = 1 > treeHeight (N (N (L, L), L));; val it: int = 2 > treeHeight (N (N (N (L, L), L), L));; val it: int = 3
treeHeight の引数が葉 L ならば 0 を返します。節 N ならば、treeHeight を再帰呼び出しして、右部分木と左部分木の高さを求めます。あとは、大きいほうの値に 1 を足して返すだけです。これで二分木の高さを求めることができます。
リスト : カッコ列の判定
let isKakko s =
let rec iter i l r =
if String.length s = i then l = r
else if s.[i] = '(' then iter (i + 1) (l + 1) r
else if s.[i] = ')' then
if l < r + 1 then false
else iter (i + 1) l (r + 1)
else failwith "illegal charcter"
iter 0 0 0
> isKakko "()";;
val it: bool = true
> isKakko ")(";;
val it: bool = false
> isKakko "((()))";;
val it: bool = true
> isKakko "((())";;
val it: bool = false
> isKakko "((())))";;
val it: bool = false
> isKakko "()()()()";;
val it: bool = true
> isKakko "()(())()";;
val it: bool = true
> isKakko "()()))()";;
val it: bool = false
カッコ列の判定は左右のカッコの個数を調べることで簡単に判定することができます。左カッコの個数を iter の引数 l で、右カッコの個数を引数 r でカウントします。バランスの取れた n 対のカッコ列の場合、l, r, n には r <= l <= n の関係が成り立ちます。
r を +1 したとき、r が l よりも大きくなるとバランスが取れていません。false を返します。文字列を最後まで読み込んだら、l と r の値が等しいかチェックします。そうでなければバランスが取れていない (左カッコが多い) ので false を返します。
リスト : カッコ列の生成
let createKakko f n =
let rec kakkoSub l r a =
if l = r && r = n then f a
else (
if l < n then kakkoSub (l + 1) r (a + "(") else ()
if r < l then kakkoSub l (r + 1) (a + ")") else ()
)
kakkoSub 0 0 ""
> createKakko (fun s -> printfn "%s" s) 1;; () val it: unit = () > createKakko (fun s -> printfn "%s" s) 2;; (()) ()() val it: unit = () > createKakko (fun s -> printfn "%s" s) 3;; ((())) (()()) (())() ()(()) ()()() val it: unit = () > createKakko (fun s -> printfn "%s" s) 4;; (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()() val it: unit = ()
実際の処理は局所関数 kakkoSub で行います。引数 l が左カッコの個数、r が右カッコの個数を表します。l = r = n の場合、カッコ列がひとつ完成しました。引数の関数 f を呼び出します。そうでなければ、kakkoSub を再帰呼び出しします。l < n であれば左カッコを追加し、r < l であれば右カッコを追加します。これでカッコ列を生成することができます。
リスト : 二分木をカッコ列に変換
type tree = L | N * tree * tree
let treeToKakko xs =
let rec toKakko = function
L -> ")"
| N (l, r) -> "(" + (toKakko l) + (toKakko r)
let a = toKakko xs
a.[0 .. (String.length a - 2)]
> N (L, L) |> treeToKakko;; val it: string = "()" > N (N (L, L), L) |> treeToKakko;; val it: string = "(())" > N (L, N (L, L)) |> treeToKakko;; val it: string = "()()" > N (N (N (L, L), L), L) |> treeToKakko;; val it: string = "((()))" > N (N (L, N (L, L)), L) |> treeToKakko;; val it: string = "(()())" > N (N (L, L), N (L, L)) |> treeToKakko;; val it: string = "(())()"
バランスの取れたカッコ列と二分木は 1 対 1 に対応します。二分木を行きがけ順で巡回するとき、途中の節では左カッコ ( を出力して左右の枝をたどり、葉に到達したら右カッコ ) を出力すると、カッコ列を生成することができます。
実際の処理は局所関数 toKakko で行います。引数が節 N の場合、先頭文字が "(" になり、そのあと iter を再帰呼び出しして左部分木 l をたどり、それから右部分木 r をたどります。その結果を演算子 + で連結すればいいわけです。
葉 (要素) の場合は ")" を返します。ただし、このままでは最後に余分な右カッコが付いてくるので、文字列のスライス操作を使って末尾文字を削除します。
リスト : カッコ列を二分木に変換
let treeFromKakko s =
let rec iter i =
if i = String.length s then (L, i)
else if s.[i] = ')' then (L, i + 1)
else if s.[i] = '(' then
let (a, b) = iter (i + 1)
let (c, d) = iter b
(N (a, c), d)
else failwith "illegal character"
iter 0
> treeFromKakko "()";; val it: tree * int = (N (L, L), 2) > treeFromKakko "(())";; val it: tree * int = (N (N (L, L), L), 4) > treeFromKakko "((()))";; val it: tree * int = (N (N (N (L, L), L), L), 6) > treeFromKakko "()()()";; val it: tree * int = (N (L, N (L, N (L, L))), 6) > treeFromKakko "(())()";; val it: tree * int = (N (N (L, L), N (L, L)), 6) > treeFromKakko "(())(())";; val it: tree * int = (N (N (L, L), N (N (L, L), L)), 8) > treeFromKakko "(((())))";; val it: tree * int = (N (N (N (N (L, L), L), L), L), 8)
実際の処理は局所関数 iter で行います。iter は生成した二分木と文字の位置を格納したタプルを返します。i 番目の文字が '(' の場合、iter を再帰呼び出しして左部分木 a を生成し、それから右部分木 c を生成します。あとは (N (a, c), d) を返すだけです。
i 番目の文字が ')' の場合は葉なので、L と i + 1 を返すだけです。ただし、右カッコがひとつ少ないので、i が文字列 s の終端に到達したら、葉 L と i を返すようにします。
下記経路図において、A から G までの経路を深さ優先探索、幅優先探索、反復深化で求めます。アルゴリズムの詳しい説明は、以下の拙作のページをお読みくださいませ。
Ｂ───Ｄ───Ｆ
／│ │
Ａ │ │
＼│ │
Ｃ───Ｅ───Ｇ
図 : 経路図
//
// keiro.fsx : 経路の探索
//
// Copyright (C) 2022 Makoto Hiroi
//
#load "queue.fs"
open Queue
// 隣接リスト (int list array)
let adjacent = [|
[1; 2] // A
[0; 2; 3] // B
[0; 1; 4] // C
[1; 4; 5] // D
[2; 3; 6] // E
[3] // F
[4] |] // G
// 深さ優先探索
let depth_first_search start goal =
let rec dfs p path =
if p = goal then printfn "%A" (List.rev path)
else List.iter (fun x -> if not (List.contains x path) then dfs x (x::path))
adjacent.[p]
dfs start [start]
// 幅優先探索 (Queue のかわりにリストで代用)
let breadth_first_search start goal =
let rec bfs = function
[] -> ()
| path::qs ->
let p = List.head path
if p = goal then (
printfn "%A" (List.rev path)
bfs qs
) else List.fold (fun a x -> if List.contains x path then a else (a @ [x::path]))
qs
adjacent.[p] |> bfs
bfs [[start]]
// モジュール Queue を使用
let breadth_first_search1 start goal =
let rec bfs que =
if is_empty que then ()
else
let path = top que
let p = List.head path
if p = goal then (
printfn "%A" (List.rev path)
bfs (dequeue que)
) else List.fold (fun q x -> if List.contains x path then q else enqueue (x::path) q)
(dequeue que)
adjacent.[p] |> bfs
create |> enqueue [start] |> bfs
// 反復深化
let id_search start goal =
let rec dfs limit p path =
if List.length path = limit then
if p = goal then printfn "%A" (List.rev path)
else List.iter (fun x -> if not (List.contains x path) then dfs limit x (x::path))
adjacent.[p]
for i = 1 to 7 do
printfn "----- move %d -----" (i - 1)
dfs i start [start]
> #load "keiro.fsx";; [読み込み中 /home/mhiroi/fsharp/queue.fs 読み込み中 /home/mhiroi/fsharp/keiro.fsx] namespace FSI_0002.Queue exception Empty type 'a queue = private | Q of 'a list * 'a list val create: 'a queue val enqueue: a: 'a -> _arg1: 'a queue -> 'a queue val dequeue: _arg1: 'a queue -> 'a queue val top: _arg1: 'a queue -> 'a val is_empty: q: 'a queue -> bool when 'a: equality namespace FSI_0002.Keiro val adjacent: int list[] val depth_first_search: start: int -> goal: int -> unit val breadth_first_search: start: int -> goal: int -> unit val breadth_first_search1: start: int -> goal: int -> unit val id_search: start: int -> goal: int -> unit > open Keiro;; > depth_first_search 0 6;; [0; 1; 2; 4; 6] [0; 1; 3; 4; 6] [0; 2; 1; 3; 4; 6] [0; 2; 4; 6] val it: unit = () > depth_first_search 6 0;; [6; 4; 2; 0] [6; 4; 2; 1; 0] [6; 4; 3; 1; 0] [6; 4; 3; 1; 2; 0] val it: unit = () > breadth_first_search 0 6;; [0; 2; 4; 6] [0; 1; 2; 4; 6] [0; 1; 3; 4; 6] [0; 2; 1; 3; 4; 6] val it: unit = () > breadth_first_search 6 0;; [6; 4; 2; 0] [6; 4; 2; 1; 0] [6; 4; 3; 1; 0] [6; 4; 3; 1; 2; 0] val it: unit = () > breadth_first_search1 0 6;; [0; 2; 4; 6] [0; 1; 2; 4; 6] [0; 1; 3; 4; 6] [0; 2; 1; 3; 4; 6] val it: unit = () > breadth_first_search1 6 0;; [6; 4; 2; 0] [6; 4; 2; 1; 0] [6; 4; 3; 1; 0] [6; 4; 3; 1; 2; 0] val it: unit = () > id_search 0 6;; ----- move 0 ----- ----- move 1 ----- ----- move 2 ----- ----- move 3 ----- [0; 2; 4; 6] ----- move 4 ----- [0; 1; 2; 4; 6] [0; 1; 3; 4; 6] ----- move 5 ----- [0; 2; 1; 3; 4; 6] ----- move 6 ----- val it: unit = () > id_search 6 0;; ----- move 0 ----- ----- move 1 ----- ----- move 2 ----- ----- move 3 ----- [6; 4; 2; 0] ----- move 4 ----- [6; 4; 2; 1; 0] [6; 4; 3; 1; 0] ----- move 5 ----- [6; 4; 3; 1; 2; 0] ----- move 6 ----- val it: unit = ()
今回は深さ優先探索の例題として、簡単なパズルを解いてみましょう。
騎士はチェスの駒のひとつで、将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐
│ │●│ │●│ │
├─┼─┼─┼─┼─┤ ┌─┬─┬─┐
│●│ │ │ │●│ │Ｋ│ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│●│ │ │ │●│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│ │●│ │●│ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┘
●：騎士 (K) が動ける位置 問題
図 : 騎士の巡歴
この騎士を動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。大きな盤面を解くのは大変なので、3 行 4 列の盤面で騎士の移動経路を求めてください。プログラムを作る前に、自分で考えてみるのも面白いでしょう。
それではプログラムを作りましょう。次の図を見てください。
┌─┬─┬─┐
│０│１│２│ ０──７──２
├─┼─┼─┤ │ │
│３│４│５│ ５──10──３
├─┼─┼─┤ │ │
│６│７│８│ ６──１──８
├─┼─┼─┤ │ │
│９│10│11│ 11──４──９
└─┴─┴─┘
（Ａ）３行４列盤 （Ｂ）経路図
図 : 騎士の移動
図 (A) のように、3 行 4 列盤の各マスに記号を付けて表します。すると、騎士の移動は図 (B) のようにグラフで表すことができます。これならば、コンピュータを使わなくても解くことができますね。プログラムも隣接リストを定義すれば簡単です。記号は数字 0 - 11 で表せばいいでしょう。あとは単純な深さ優先探索で騎士の経路を探すだけです。
リスト : 騎士の巡歴 (puzzle01.fsx)
// 隣接リスト
let adjacent = [|
[5; 7]
[6; 8]
[3; 7]
[2; 8; 10]
[9; 11]
[0; 6; 10]
[1; 5; 11]
[0; 2]
[1; 3; 9]
[4; 8]
[3; 5]
[4; 6] |]
// 深さ優先探索
let knight start =
let rec dfs n path =
if n = 12 then printfn "%A" (List.rev path)
else
let p = List.head path
List.iter (fun x -> if List.contains x path then () else dfs (n+1) (x::path))
adjacent.[p]
dfs 1 [start]
経路はリストで表します。局所関数 dfs の引数 n が訪れたマスの個数を表し、次の引数 path が経路を表します。n が 12 になったら見つけた経路を printfn で表示します。そうでなければ、騎士を次のマスへ進めます。この処理は経路の探索と同じです。
プログラムはこれだけです。とても簡単ですね。それでは実行してみましょう。
> open Puzzle01;; > knight 0;; [0; 7; 2; 3; 10; 5; 6; 1; 8; 9; 4; 11] [0; 7; 2; 3; 10; 5; 6; 11; 4; 9; 8; 1] val it: unit = ()
2 通りの経路を見つけることができました。
このほかに、どのマスにもちょうど一回ずつ訪れたのち、最初のマスに戻ってくることを条件にする「騎士の周遊」という問題もあります。この場合、3 行 4 列盤には解がありません。また、N 行 M 列の盤面でマスの個数が奇数のときにも、最初のマスに戻ることはできません。これは簡単に証明できるので、息抜きや気分転換に考えてみてください。
皆さんお馴染みのパズル「ナンバープレース (数独)」の解法プログラムです。ナンバープレースは単純な深さ優先探索で簡単に解くことができます。説明は割愛しますので、詳細はプログラムリストをお読みください。
リスト : ナンバープレースの解法
// 盤面の表示
let print_board (board: int array array) =
for y = 0 to 8 do
for x = 0 to 8 do
printf "%d " board.[y].[x]
printfn ""
// 縦横枠に同じ数字がないことを確認する
let check (board: int array array) x y n =
let rec check1 i =
if i = 9 then true
else if board.[y].[i] = n || board.[i].[x] = n then false
else check1 (i + 1)
let x1 = (x / 3) * 3
let y1 = (y / 3) * 3
let rec check2 i j =
if j = 3 then true
else if i = 3 then check2 0 (j + 1)
else if board.[y1 + j].[x1 + i] = n then false
else check2 (i + 1) j
(check1 0) && (check2 0 0)
let number_place board =
let rec dfs x y =
if y = 9 then
print_board board
else if x = 9 then
dfs 0 (y + 1)
else if board.[y].[x] = 0 then
for n = 1 to 9 do
if check board x y n then (
board.[y].[x] <- n
dfs (x + 1) y
board.[y].[x] <- 0
) else ()
else dfs (x + 1) y
print_board board
printfn "--------------------"
dfs 0 0
// 問題 出典: 数独 - Wikipedia の問題例
let q00 = [|
[|5; 3; 0; 0; 7; 0; 0; 0; 0|]
[|6; 0; 0; 1; 9; 5; 0; 0; 0|]
[|0; 9; 8; 0; 0; 0; 0; 6; 0|]
//
[|8; 0; 0; 0; 6; 0; 0; 0; 3|]
[|4; 0; 0; 8; 0; 3; 0; 0; 1|]
[|7; 0; 0; 0; 2; 0; 0; 0; 6|]
//
[|0; 6; 0; 0; 0; 0; 2; 8; 0|]
[|0; 0; 0; 4; 1; 9; 0; 0; 5|]
[|0; 0; 0; 0; 8; 0; 0; 7; 9|] |]
> open Puzzle01;; > number_place q00;; 5 3 0 0 7 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 -------------------- 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 val it: unit = ()
最後に、「マスターマインド」というゲームを解くプログラムを作りましょう。マスターマインドは 0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
[6; 2; 8; 1] : 正解
-------------------------------------
1. [0; 1; 2; 3] : cows 2 : bulls 0
2. [1; 0; 4; 5] : cows 1 : bulls 0
3. [2; 3; 5; 6] : cows 2 : bulls 0
4. [3; 2; 7; 4] : cows 0 : bulls 1
5. [3; 6; 0; 8] : cows 2 : bulls 0
6. [6; 2; 8; 1] : cows 0 : bulls 4
図 : マスターマインドの動作例
今回は、私達が出した問題をコンピュータに答えてもらうことにします。それはちょっと難しいのではないか、と思った人もいるかもしれませんね。ところが、とても簡単な方法があるのです。このゲームでは、10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。コードを生成する処理は順列と同じですから、簡単にプログラムできます。
次に、この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
[6; 2; 8; 1] が正解の場合
[0; 1; 2; 3] => bulls = 0, cows = 2
[0; 1; 2; 3] と比較する
--------------------------------------------------------
[0; X; X; X] 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
[1; 0; 3; 4] cows = 3, bulls = 0 になるので矛盾する
・・・・
[1; 0; 4; 5] cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
[1; 0; 4; 5] => bulls = 0, cows = 1
次は、[0; 1; 2; 3] と [1; 0; 4; 5] に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
[0; 1; 2; 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0; X; X; X] というコードは [0; 1; 2; 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に [1; 0; 3; 4] というコードを考えてみます。[0; 1; 2; 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1; 0; 3; 4] と [0; 1; 2; 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に [1; 0; 4; 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0; 1; 2; 3] と [1; 0; 4; 5] に矛盾しないコードを選択するのです。
リスト : マスターマインドの解法
// 順列の生成
let rec select = function
[] -> []
| [x] -> [(x, [])]
| x::xs -> (x, xs) :: List.map (fun (y, ys) -> (y, x::ys)) (select xs)
let rec permutations n xs =
if n = 0 then [[]]
else List.collect
(fun (y, ys) -> List.map (fun zs -> y::zs) (permutations (n - 1) ys))
(select xs)
// bulls を数える
let count_bulls xs ys =
List.fold2 (fun a x y -> if x = y then a + 1 else a) 0 xs ys
// 同じ数字の個数を数える
let count_same_number xs ys =
List.fold (fun a x -> if List.contains x ys then a + 1 else a) 0 xs
// 質問のチェック
let rec check_query code = function
[] -> true
| (q, bulls, cows)::qs ->
let b = count_bulls q code
let c = count_same_number q code - b
if b = bulls && c = cows then check_query code qs
else false
let master_mind ans =
let rec iter n qs = function
[] -> failwith "not found"
| code::xs ->
if check_query code qs then (
let bulls = count_bulls code ans
let cows = count_same_number code ans - bulls
printfn "%d: %A bulls = %d, cows %d" n code bulls cows
if bulls = 4 then printfn "Good Job!!"
else iter (n+1) ((code,bulls,cows)::qs) xs
) else iter n qs xs
iter 1 [] (permutations 4 [0..9])
> open Puzzle01;; > master_mind [9;8;7;6];; 1: [0; 1; 2; 3] bulls = 0, cows 0 2: [4; 5; 6; 7] bulls = 0, cows 2 3: [5; 4; 8; 9] bulls = 0, cows 2 4: [6; 7; 9; 8] bulls = 0, cows 4 5: [8; 9; 7; 6] bulls = 2, cows 2 6: [9; 8; 7; 6] bulls = 4, cows 0 Good Job!! val it: unit = () > master_mind [9;4;3;1];; 1: [0; 1; 2; 3] bulls = 0, cows 2 2: [1; 0; 4; 5] bulls = 0, cows 2 3: [2; 3; 5; 4] bulls = 0, cows 2 4: [3; 4; 0; 6] bulls = 1, cows 1 5: [3; 5; 6; 1] bulls = 1, cows 1 6: [6; 5; 0; 2] bulls = 0, cows 0 7: [7; 4; 3; 1] bulls = 3, cows 0 8: [8; 4; 3; 1] bulls = 3, cows 0 9: [9; 4; 3; 1] bulls = 4, cows 0 Good Job!! val it: unit = ()