M.Hiroi's Home Page

Functional Programming

お気楽 Standard ML of New Jersey 入門

[ PrevPage | SML/NJ | NextPage ]

レコード

今まで、新しいデータ型を定義する方法として、組と datatype を説明しました。今回は「レコード (record)」を説明します。実をいうと、レコードは SML/NJ の基本的なデータ型の一つで、今まで使ってきた「組」はレコードの特殊な場合なのです。

●レコードの定義

レコードは中カッコ { } で囲み、要素をカンマで区切ります。要素は次の形式で定義します。

ラベル = 値

ラベルは数字または名前です。"ラベル = 値" を「フィールド」、ラベルを「フィールド名」と呼ぶ場合があります。値の部分に式を書いてもかまいません。式の評価結果がラベルの値になります。次の例を見てください。

- {foo=10, bar=20};
val it = {bar=20,foo=10} : {bar:int, foo:int}
- {baz=100, 5=200};
val it = {5=200,baz=100} : {5:int, baz:int}

- {1=10, 2=20, 3=30};
val it = (10,20,30) : int * int * int

- {1=10, 2=20, 4=40};
val it = {1=10,2=20,4=40} : {1:int, 2:int, 4:int}

レコードの型は {ラベル1 : 型式, ラベル2 : 型式, ...} で表されます。{foo=10, bar=20} の型は {bar:int, foo:int} になります。要素の順番は関係ありません。{bar:int, foo:int} も {foo:int, bar:int} も同じ型になります。SML/NJ は要素を昇順に並べて表示します。

組はラベルが 1 から n までの整数で表されている特別な場合です。したがって、レコード {1=10, 2=20, 3=30} は組 (10, 20, 30) と同じです。{1=10, 2=20, 4=40} は 3 が抜けているので組にはなりません。

SML/NJ の場合、コロン ( : ) を使ってデータ型を指定することができます。次の例を見てください。

- fun square x = x * x;
val square = fn : int -> int
- fun square1 x : real = x * x;
val square1 = fn : real -> real

- val a = nil;
val a = [] : 'a list
- val b = nil : int list;
val b = [] : int list

関数 square の型は int -> int になりますが、引数 x の型を指定すると real -> real になります。また、空リスト (nil) の型は 'a list ですが、特定の型を指定することもできます。

レコードの値を参照するには #ラベル を使います。

- val a = {foo=10, bar=20};
val a = {bar=20,foo=10} : {bar:int, foo:int}
- #foo a;
val it = 10 : int
- #bar a ;
val it = 20 : int

レコードに #ラベル を適用すると、ラベルの値を参照することができます。組は番号がラベルのレコードなので #番号 で値を参照できるわけです。

●レコードのパターン

もちろん、レコードでもパターンを使うことができます。次の例を見てください。

- val {foo=x, bar=y} = {foo=100, bar=200};
val y = 200 : int
val x = 100 : int

- val {foo, bar} = {foo=1, bar=2};
val bar = 2 : int
val foo = 1 : int

"ラベル = パターン" とするとラベルの値とパターンがマッチングします。{foo=x, bar=y} は変数 x とラベル foo の値、変数 y とラベル bar の値がマッチングして、x = 100, y = 200 になります。パターンを省略してラベルだけ指定すると、ラベルがパターンの変数になります。{foo, bar} は変数 foo とラベル foo の値がマッチングして foo = 1 になり、変数 bar とラベル bar の値がマッチングして bar = 2 になります。

ただし、ラベルが数字の場合はパターンを省略することができません。次の例を見てください。

- val a = {1=10, bar=20};
val a = {1=10,bar=20} : {1:int, bar:int}
- val {1, bar} = a;
stdIn:23.7-23.13 Error: syntax error: deleting  COMMA ID RBRACE
- val {1=z, bar} = a;
val z = 10 : int
val bar = 20 : int

ラベルが数字の場合、パターンの指定を省略するとエラーになります。必ずパターンを指定してください。

レコードのパターンは、フィールドの指定に ... を使うことができます。... はワイルドカードで、不要なフィールドの指定を省略することができます。次の例を見てください。

- datatype foo = Bar of {abc:int, def:int, ghi:int};
datatype foo = Bar of {abc:int, def:int, ghi:int}

- val Bar{abc,...} = Bar{abc=1, def=2, ghi=3};
val abc = 1 : int

datatype で新しい型 foo を作成します。レコードはデータ型の一つなので、datatype の型式に使用することができます。データ構成子 Bar の型式は {abc:int, def:int, ghi:int} になります。このレコードからラベル abc の値を取り出したいとき、Bar {abc, ...} のように ... を指定すると、def と ghi の指定を省略することができます。

ただし、フィールド指定の省略は、レコードの型が特定できる場合にのみ可能です。単純に val {abc, ... } と指定すると、レコードの型を特定できずにエラーになります。ご注意くださいませ。

●データの個数を求める

それでは簡単な例題として、データをカウントするプログラムを作ってみましょう。たとえば、入力データが [ "a", "b", "c", "a", "c" ] であれば、"a", "b", "c" の個数を求めます。この場合、"a" が 2 個、"b" が 1 個、"c" が 2 個になります。

一番簡単な方法は連想リストを使うことです。データとその個数を組にし、それをリストに格納にします。連想リストからデータを探索し、データが見つかればその個数を +1 します。見つからなければ、新しい組を生成して連想リストに追加します。

今回はレコードの例題なので、組ではなくレコードを使いましょう。プログラムは次のようになります。

リスト : データの数え上げ

(* カウンタの定義 *)
datatype 'a counter = Cnt of {data:'a, count:int ref}

(* カウントアップ *)
fun countup(Cnt{count, ...}) = count := !count + 1

(* データの探索 *)
fun find_data(w, nil) = NONE
|   find_data(w, (R as Cnt{data, ...})::xs) =
    if w = data then SOME R else find_data(w, xs)

(* データの個数を求める *)
fun data_count(nil, result) = result
|   data_count(x::xs, result) =
    let
      val v = find_data(x, result)
    in
      if isSome v then (countup(valOf v); data_count(xs, result))  
      else data_count(xs, Cnt{data=x, count=ref 1}::result)
    end

最初に datatype で counter を定義します。データ型を限定する必要はないので、'a counter としました。レコードの型は {data:'a, count:int ref} とします。データの個数を書き換えるため、count は参照を使って int ref にします。count の書き換えは関数 countup で行います。

データの探索は関数 find_data で行います。第 1 引数の w が探索するデータ、第 2 引数がレコードを格納しているリスト (連想リスト) です。パターンでレコードの data を取り出し、w と等しいかチェックします。そうであれば、レコード R をoption 型に格納して返します。そうでなければ、find_data を再帰呼び出しして次のレコードを調べます。データが見つからなければ NONE を返します。

関数 data_count はデータの個数を数えて、データと個数を格納した連想リストを返します。第 1 引数が入力データのリストで、第 2 引数の result がレコードを格納する連想リストです。まず、find_data で連想リストからデータ x を探します。関数 isSome で option をチェックし、データがあれば関数 countup で count を +1 します。関数 valOf は option からデータを取り出す関数です。見つからなければ、レコードを生成して result に追加します。

それでは、簡単な実行例を示します。

- data_count(["a", "b", "c", "a", "c"], nil);
val it =
  [Cnt {count=ref 2,data="c"},Cnt {count=ref 1,data="b"},
   Cnt {count=ref 2,data="a"}] : string counter list

- data_count([1, 2, 3, 2, 3, 4, 3, 4, 5], nil);
val it =
  [Cnt {count=ref 1,data=5},Cnt {count=ref 2,data=4},Cnt {count=ref 3,data=3},
   Cnt {count=ref 2,data=2},Cnt {count=ref 1,data=1}] : int counter list

正常に動作していますね。ところで、このプログラムはデータの種類が増えると実行速度が遅くなります。実は、データの種類が増えると、データを探索する find_data の処理に時間がかかるのです。find_data は列の先頭から順番に要素を比較してデータを探します。これを「線形探索」といいます。

データ数が少なければ線形探索でも何とかなりますが、データ数が多くなると探索に時間がかかるようになります。このような場合、あらかじめデータを整理整頓しておくことで、特定のデータを高速に見つけることができるようになります。この代表的なアルゴリズムが「ハッシュ法」と「二分探索木」です。これらのアルゴリズムは次節以降で取り上げることにします。


初版 2005 年 5 月 28 日
改訂 2020 年 8 月 9 日

バックトラック法

複雑な問題を厳密に解こうとするときや、条件を満たす解をすべて求める必要があるとき、可能性のあるパターンをすべて生成して、条件を満たしているかチェックするしか方法がない場合があります。このようなとき用いる手法に「バックトラック法 (backtracking)」があります。

たとえば、簡単な例として迷路を考えてみましょう。ある地点 A で道が左右に分かれているとします。ここで、左の道を選んで先へ進むと、行き止まりになってしまいました。この場合は A 地点まで戻って右の道へ進まないといけません。

このように、失敗したら元に戻って別の選択枝を選ぶ、という試行錯誤を繰り返して解を見つける方法がバックトラック法なのです。バックトラック法は、いろいろな分野の問題に応用できる方法です。そして、再帰定義を使うと簡単にプログラムを作ることができます。今回は簡単な例題として、バックトラック法でパズルを解いてみましょう。

●小町算

パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。123456789 とか 321654987 のような数字が小町数です。「小町算」というものもあり、123 + 456 + 789 とか 321 * 654 + 987 のようなものです。今回は小町算の中でも特に有名なパズルを解いてみましょう。

[問題] 小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。なお、1 の前に符号 - は付けないものとします。

例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

●データ型の定義

それではプログラムを作りましょう。この問題は演算子が + と - だけしかないので、式はリストで表すことにします。SML/NJ の場合、異なるデータ型をリストに格納することはできないので、+ と - と数値を表すデータ型を定義します。

リスト : データ型の定義

datatype term =  Plus | Minus | Num of int  

term を使うと数式は次のように表すことができます。

1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
=> [Num 1, Plus, Num 2, Plus, Num 3, Minus, Num 4, Plus, 
    Num 5, Plus, Num 6, Plus, Num 78, Plus, Num 9]

あとは、式を生成して値を計算するだけです。式を生成するとき、リストを逆順で管理すると簡単です。次の図を見てください。

[Num 1] => [Num 2, Plus, Num 1]  => [Num 3, Plus, Num 2, Plus, Num 1]
                                 => [Num 3, Minus, Num 2, Plus, Num 1]
                                 => [Num 23, Plus, Num 1]
        => [Num 2, Minus, Num 1] => [Num 3, Plus, Num 2, Minus, Num 1]
                                 => [Num 3, Minus, Num 2, Minus, Num 1]
                                 => [Num 23, Minus, Num 1]
        => [Num 12]              => [Num 3, Plus, Num 12]
                                 => [Num 3, Minus, Num 12]
                                 => [Num 123]

式を生成するとき、リストに数字と演算子を順番に追加していきます。Numと Plus, Minus を追加する処理は簡単です。プログラムのポイントは数字を連結する処理、たとえば 1 と 2 を連結して一つの数値 12 にする処理です。この処理はリストの先頭の数字 Num 1 を Num 12 (= 1 * 10 + 2) に置き換えることで実現できます。リストが [Num 2, Plus, Num 1] であれば、Num 2 を Num 23 (= 2 * 10 + 3) に置き換えます。

●式の生成

式を生成するプログラムは次のようになります。

リスト : 式の生成

fun make_expr(10, expr) = 
  let
    val expr1 = rev expr
  in
    if calc_expr expr1 = 100 then print_expr expr1 else ()
  end
|   make_expr(n, expr as Num x :: xs) =
  (make_expr(n + 1, Num(n)::Plus::expr);
   make_expr(n + 1, Num(n)::Minus::expr);
   make_expr(n + 1, Num(x * 10 + n)::xs))

式の生成はバックトラックを使うと簡単です。make_exp の引数 n が追加する数字、expr が生成する式(リスト)です。n が 10 になったら式が完成したので値を計算します。関数 rev で式を元に戻し、calc_expr で式 expr1 を計算します。その結果が 100 になれば関数 print_expr で式を出力します。

n が 10 より小さい場合は数値と演算子をリストにセットします。最初に Num(n) と Plus をセットして make_expr を再帰呼び出しします。その次に、Num(n) と Minsu をセットして make_expr を呼び出します。最後に、Num(x) を Num(x * 10 + n) に置き換えてから make_expr を呼び出します。これで、全部の数式を生成することができます。

●式の計算

次は式を計算する calc_exp を作ります。今回の問題は演算子に + と - しかないので、リストで表現した式を計算することは簡単です。次のプログラムを見てください。

リスト : 式の計算

fun calc_expr (Num n :: expr) =
  let
    fun calc_expr_sub(nil, sum) = sum
    |   calc_expr_sub(Plus::Num(x)::xs, sum) = calc_expr_sub(xs, sum + x)
    |   calc_expr_sub(Minus::Num(x)::xs, sum) = calc_expr_sub(xs, sum - x)
  in
    calc_expr_sub(expr, n)
  end

実際の計算処理は関数 calc_expr_sub で行います。第 1 引数が数式 (リスト) で、第 2 引数が計算結果です。calc_expr は先頭の数値 n を取り出し、残りの数式を calc_expr_sub の第 1 引数に、n を第 2 引数に渡します。すると、数式の先頭は Plus か Minus になります。calc_expr_sub では、Plus の場合は次の数値 x を sum に加算し、Minus の場合は sum から減算します。あとは calc_expr_sub を再帰呼び出しするだけです。

あとのプログラムは簡単なので説明は省略いたします。詳細は プログラムリスト1 をお読みください。

●実行結果

プログラムをコンパイルすると Warning: match nonexhaustive が表示されます。この Warning は、すべての場合についてパターンを定義していないときに表示されます。このプログラムはパターンが限定されているので、Warning を無視しても大丈夫です。

それでは実行結果を示します。

fun solver() = make_expr(2, [Num(1)])

- solver();
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 23 - 4 + 56 + 7 + 8 + 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
123 + 4 - 5 + 67 - 89
123 + 45 - 67 + 8 - 9
123 - 4 - 5 - 6 - 7 + 8 - 9
123 - 45 - 67 + 89
val it = () : unit

全部で 11 通りの解が出力されます。この他にも、いろいろな解き方があると思います。興味のある方は、もっとクールな方法を考えてみてください。

●プログラムリスト1

(* 
 * komachi.sml : 小町算の解法
 *
 *               Copyright (C) 2005-2020 Makoto Hiroi
 *)

datatype term =  Plus | Minus | Num of int

fun print_item Plus =  print " + "
|   print_item Minus = print " - "
|   print_item (Num x) = print (Int.toString x)

fun print_expr nil = print "\n"
|   print_expr (x::xs) = (print_item x; print_expr xs)

fun calc_expr (Num n :: expr) =
  let
    fun calc_expr_sub(nil, sum) = sum
    |   calc_expr_sub(Plus::Num(x)::xs, sum) = calc_expr_sub(xs, sum + x)
    |   calc_expr_sub(Minus::Num(x)::xs, sum) = calc_expr_sub(xs, sum - x)
  in
    calc_expr_sub(expr, n)
  end

fun make_expr(10, expr) = 
  let
    val expr1 = rev expr
  in
    if calc_expr expr1 = 100 then print_expr expr1 else ()
  end
|   make_expr(n, expr as Num x :: xs) =
  (make_expr(n + 1, Num(n)::Plus::expr);
   make_expr(n + 1, Num(n)::Minus::expr);
   make_expr(n + 1, Num(x * 10 + n)::xs))

fun solver() = make_expr(2, [Num(1)])

●8 クイーン

もう一つ、有名なパズルを解いてみましょう。「8 クイーン」はコンピュータに解かせるパズルの中でも特に有名な問題です。8 クイーンは、8 行 8 列のチェスの升目に、8 個のクイーンを互いの利き筋が重ならないように配置する問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を次に示します。


       図 : 8 クイーンの解答例

8 クイーンを解くには、すべての置き方を試してみるしか方法はありません。最初のクイーンは、盤上の好きなところへ置くことができるので、64 通りの置き方があります。次のクイーンは 63 通り、その次は 62 通りあります。したがって、置き方の総数は 64 から 57 までの整数を掛け算した 178462987637760 通りもあります。

ところが、解答例を見ればわかるように、同じ行と列に 2 つ以上のクイーンを置くことはできません。上図の解答例をリストを使って表すと、 次のようになります。

  1  2  3  4  5  6  7  8    <--- 列の位置
---------------------------
 [1, 7, 5, 8, 2, 4, 6, 3]   <--- 要素が行の位置を表す  


        図 : リストでの行と列の表現方法

列をリストの位置に、行番号を要素に対応させれば、各要素には 1 から 8 までの数字が重複しないで入ることになります。すなわち、1 から 8 までの順列の総数である 8! = 40320 通りの置き方を調べるだけでよいのです。パズルを解く場合は、そのパズル固有の性質をうまく使って、調べなければならない場合の数を減らすように工夫することが大切です。

順列を生成するプログラムは 順列と組み合わせ で作成しました。あとは、その順列が 8 クイーンの条件を満たしているかチェックすればいいわけです。このように、正解の可能性があるデータを作りそれをチェックするという方法を「生成検定法 (generate and test)」といいます。

可能性のあるデータをもれなく作る場合、「バックトラック (backtrack)」が適しています。バックトラックは再帰定義で簡単にプログラムを作ることができます。順列を生成するプログラムもバックトラックを使っています。バックトラックはパズルの解法だけではなく、いろいろな分野の問題に応用できる方法です。ただし、「生成するデータ数が多くなると時間がとてもかかる」という弱点があるので注意してください。

●プログラムの作成

それでは、プログラムを作りましょう。次のリストを見てください。

リスト : 8 クイーンの解法

(* 衝突のチェック *)
fun attack(x, xs) = 
  let
    fun attack_sub(_, _, nil) = true
    |   attack_sub(x, n, y::ys) =
      if x = y + n orelse x = y - n then false
      else attack_sub(x, n + 1, ys)
  in
    attack_sub(x, 1, xs)
  end

(* 8 クイーンの条件を満たしているか *)
fun safe nil = true
|   safe (x::xs) = if attack(x, xs) then safe xs else false

(* 8 クイーンの解法 *)
fun queen(f, nil, board) =
    if safe board then f (rev board) else ()
|   queen(f, nums, board) =
  app (fn x => queen(f, remove(x, nums), x::board)) nums

関数 queen は順列を生成するプログラムと同じです。順列を一つ生成したら、述語 safe で 8 クイーンの条件を満たしているかチェックします。そうであれば関数 f を呼び出します。引数 f に print_initlist を渡せば、盤面 (リスト) を表示することができます。

述語 safe はリストの先頭の要素からチェックしていきます。衝突のチェックは斜めの利き筋を調るだけです。端にあるクイーンから順番に調べるとすると、斜めの利き筋は次のように表せます。

    1 2 3    --> 調べる方向
  *-------------
  | . . . . . .
  | . . . -3. .  5 - 3 = 2
  | . . -2. . .  5 - 2 = 3
  | . -1. . . .  5 - 1 = 4
  | Q . . . . .  Q の位置は 5  
  | . +1. . . .  5 + 1 = 6
  | . . +2. . .  5 + 2 = 7
  | . . . +3. .  5 + 2 = 8
  *-------------


    図 : 衝突の検出

図を見てもらえばおわかりのように、Q が行 5 にある場合、ひとつ隣の列は 4 と 6 が利き筋に当たります。2 つ隣の列の場合は 3 と 7 が利き筋に当たります。このように単純な足し算と引き算で、利き筋を計算することができます。これをプログラムすると次のようになります。

リスト : 衝突の検出

fun attack(x, xs) = 
  let
    fun attack_sub(_, _, nil) = true
    |   attack_sub(x, n, y::ys) =
      if x = y + n orelse x = y - n then false
      else attack_sub(x, n + 1, ys)
  in
    attack_sub(x, 1, xs)
  end

attack は、斜めの利き筋に当たった場合に false を返し、利き筋に当たらない場合は true を返します。実際の処理は関数 attack_sub で行います。attack_sub は、リストの先頭から斜めの利き筋に当たるか調べます。第 1 引数がクイーンの位置、第 2 引数が位置の差分、第 3 引数がリストになります。

最初の定義がクイーンを全て調べた場合です。クイーンは衝突していないので true を返します。次の定義で、リストから先頭の要素 y を取りだし、利き筋に当たるか調べます。これは、y + n または y - n が x と等しいかチェックするだけです。衝突している場合は false を返します。そうでなければ、attack_sub を再帰呼び出しして次のクイーンを調べます。このとき、差分 n の値を +1 することをお忘れなく。

●実行結果

これでプログラムは完成です。それでは実行してみましょう。

- queen(print_intliist, [1, 2, 3, 4, 5, 6, 7, 8], nil);
1 5 8 6 3 7 2 4
1 6 8 3 7 4 2 5
1 7 4 6 8 2 5 3

・・・省略・・・

8 2 5 3 1 7 4 6
8 3 1 6 2 5 7 4
8 4 1 3 6 2 7 5
val it = () : unit

解は全部で 92 通りあります。ところで、このプログラムはクイーンの個数を増やすと極端に遅くなります。クイーンの個数を増やして試してみたところ、実行時間は次のようになりました。

リスト : N Queens Problem

(* 整数列の生成 *)
fun iota(n, m) =
  if n > m then nil
  else n :: iota(n + 1, m)

(* 時間計測 *)
fun queen_solver f n =
  let
    val a = Timer.startRealTimer()
    val c = ref 0
  in
    f(fn _ => c := !c + 1, iota(1, n), nil);
    print (Int.toString (!c) ^ "\n");
    Timer.checkRealTimer(a)
  end
- queen_solver queen 9;
352
val it = TIME {usec=62392} : Time.time
- queen_solver queen 10;
724
val it = TIME {usec=515461} : Time.time
- queen_solver queen 11;
2680
val it = TIME {usec=5686201} : Time.time
- queen_solver queen 12;
14200
val it = TIME {usec=70936481} : Time.time

実行環境 : Windows 10, SML/NJ ver 110.98, Intel Core i5-6200U 2.30GHz

クイーンの個数が 12 の場合、解の総数は 14200 通りありますが、実行時間は約 72 秒もかかります。実はこのプログラム、とても非効率なことをやっているのです。

●8 クイーンの高速化

実行速度が遅い理由は、失敗することがわかっている順列も生成してしまうからです。

たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を発生させてからチェックする方法では、このような無駄を省くことができません。

そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。

リスト : 8 クイーン (改良版)

fun queen_f(f, nil, board) = f (rev board)
|   queen_f(f, nums, board) = 
    app (fn x => if attack(x, board)
                 then queen_f(f, remove(x, nums), x::board) else ()) nums

匿名関数の中で、追加したクイーンが board 内のクイーンと衝突していないか関数 attack でチェックします。順列を生成している途中でチェックを入れることで、無駄な順列を生成しないようにするわけです。この場合、safe は必要ありません。

このように、できるだけ早い段階でチェックを入れることで、無駄なデータをカットすることを「枝刈り」と呼びます。バックトラックを使って問題を解く場合、この枝刈りのよしあしによって実行時間が大きく左右されます。ところが、枝刈りの方法はパズルによって違います。パズル固有の性質をよく調べて、適切な枝刈りを考えることが重要なのです。パズル自体はコンピュータに解かせるのですが、枝刈りの条件は私達が考えるのです。これも「パズルの解法」の面白いところでしょう。解を求めるだけでなく、いかに効率の良い条件を見つけて実行時間を短縮するか、ということでも楽しむことができます。

それでは実行してみましょう。

- queen_solver queen_f 11;
2680
val it = TIME {usec=31250} : Time.time
- queen_solver queen_f 12;
14200
val it = TIME {usec=140590} : Time.time
- queen_solver queen_f 13;
73712
val it = TIME {usec=874835} : Time.time
- queen_solver queen_f 14;
365596
val it = TIME {usec=5334862} : Time.time

クイーンの個数が 13 以下の場合、1 秒もかからずに解を求めることができました。しかしながら、クイーンの個数をこれ以上増やすと、このプログラムでも時間がかかるようになります。さらなる高速化が必要になります。興味のある方は拙作のページ Puzzle DE Programming N Queens Problem をお読みください。

ところで、今回は単純にリストを出力するだけなので、ちょっと面白くありません。興味のある方は、解答例のような図を出力するプログラムを作ってみてください。

●プログラムリスト2

(*
 * queen.sml : 8 クイーンの解法
 *
 *             Copyright (C) 2005-2020 Makoto Hiroi
 *)

(* 要素の削除 *)
fun remove(_, nil) = nil
|   remove(n, x::xs) =
  if x = n then xs else x::remove(n, xs)

(* int list の表示 *)
fun print_intlist nil = print "\n"
|   print_intlist (x::xs) =
  (print(Int.toString(x) ^ " "); print_intlist xs)

(* 衝突のチェック *)
fun attack(x, xs) = 
  let
    fun attack_sub(_, _, nil) = true
    |   attack_sub(x, n, y::ys) =
      if x = y + n orelse x = y - n then false
      else attack_sub(x, n + 1, ys)
  in
    attack_sub(x, 1, xs)
  end

(* 8 クイーンの条件を満たしているか *)
fun safe nil = true
|   safe (x::xs) = if attack(x, xs) then safe xs else false

(* 8 クイーンの解法 *)
fun queen(f, nil, board) =
    if safe board then f (rev board) else ()
|   queen(f, nums, board) =
  app (fn x => queen(f, remove(x, nums), x::board)) nums

(* 高速版 *)
fun queen_f(f, nil, board) = f (rev board)
|   queen_f(f, nums, board) = 
    app (fn x => if attack(x, board)
                 then queen_f(f, remove(x, nums), x::board) else ()) nums

(* 整数列の生成 *)
fun iota(n, m) =
  if n > m then nil
  else n :: iota(n + 1, m)

(* 時間計測 *)
fun queen_solver f n =
  let
    val a = Timer.startRealTimer()
    val c = ref 0
  in
    f(fn _ => c := !c + 1, iota(1, n), nil);
    print (Int.toString (!c) ^ "\n");
    Timer.checkRealTimer(a)
  end

初版 2005 年 5 月 28 日
改訂 2020 年 8 月 9 日

Copyright (C) 2005-2020 Makoto Hiroi
All rights reserved.

[ PrevPage | SML/NJ | NextPage ]