ATSプログラミング入門:
Prev	Chapter 3. 関数	Next

例: エイト・クイーンパズル

エイト・クイーンパズルは 8x8 のチェスボードの上に8つのクイーンのコマを、他のコマを取れるようなコマが全くないように配置する問題です。 ATS でこのパズルの解法を次に示すことで、これまで紹介してきたプログラミングの機能のいくつかを復習します。特にこの章で実装する全ての再帰関数は末尾再帰であることに注意してください。

まずはじめに、次のように整数の定数8に名前を付けます:

#define N 8

この宣言の後では、名前 N は8に置換されます。ボードの配置を表現するために、次のような int8 型を定義します:

typedef int8 =
(
  int, int, int, int, int, int, int, int
) // end of [int8]

int8 型の値は8つの整数のタプルです。 1番目の整数は1番目の行 (row 0) 上のクイーンの列の位置を表現していて、 2番目の整数は2番目の行 (row 1) 上のクイーンの列の位置を表現していて、などと続きます。

ボードの配置を印字するために、次の関数群を定義します:

fun print_dots (i: int): void =
  if i > 0 then (print ". "; print_dots (i-1)) else ()
// end of [print_dots]

fun print_row (i: int): void =
(
  print_dots (i); print "Q "; print_dots (N-i-1); print "n";
) // end of [print_row]

fun print_board (bd: int8): void =
(
  print_row (bd.0); print_row (bd.1); print_row (bd.2); print_row (bd.3);
  print_row (bd.4); print_row (bd.5); print_row (bd.6); print_row (bd.7);
  print_newline ()
) // end of [print_board]

関数 print_newline は改行記号を印字して、標準出力のバッファをフラッシュします。読者がバッファのフラッシュに詳しくない場合には、 print_newline のこの側面を無視してかまいません。

例として、 @(0, 1, 2, 3, 4, 5, 6, 7) で表わされたボード配置に print_board を呼び出すと、次の8行が印字されます:

Q . . . . . . . 
. Q . . . . . . 
. . Q . . . . . 
. . . Q . . . . 
. . . . Q . . . 
. . . . . Q . . 
. . . . . . Q . 
. . . . . . . Q

ボードとボード上に行の数だけクイーンのコマが与えられた時、次の関数 board_get は列のコマの数を返します:

fun board_get
  (bd: int8, i: int): int =
  if i = 0 then bd.0
  else if i = 1 then bd.1
  else if i = 2 then bd.2
  else if i = 3 then bd.3
  else if i = 4 then bd.4
  else if i = 5 then bd.5
  else if i = 6 then bd.6
  else if i = 7 then bd.7
  else ~1 // end of [if]
// end of [board_get]

ボードと行の数 i と列の数 j が与えられた時、次の関数 board_set は、行 i のクイーンの列の数が j である点を除いて元のボードと同じ新しいボードを返します:

fun board_set
  (bd: int8, i: int, j:int): int8 = let
  val (x0, x1, x2, x3, x4, x5, x6, x7) = bd
in
  if i = 0 then let
    val x0 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 1 then let
    val x1 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 2 then let
    val x2 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 3 then let
    val x3 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 4 then let
    val x4 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 5 then let
    val x5 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 6 then let
    val x6 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else if i = 7 then let
    val x7 = j in (x0, x1, x2, x3, x4, x5, x6, x7)
  end else bd // end of [if]
end // end of [board_set]

関数 board_get と board_set の定義はいくらか不恰好です。これはタプルをボード配置の表現に使っていることに由来します。ボード配置の表現に配列を使うことができるようになったら、この実装はより単純に明解になるでしょう。けれども、ここではまだ配列を紹介していません。

2つのテスト関数 safety_test1 と safety_test2 を次のように実装しましょう:

fun safety_test1
(
  i0: int, j0: int, i1: int, j1: int
) : bool =
(*
** [abs]: the absolute value function
*)
  j0 != j1 andalso abs (i0 - i1) != abs (j0 - j1)
// end of [safety_test1]

fun safety_test2
(
  i0: int, j0: int, bd: int8, i: int
) : bool =
  if i >= 0 then
    if safety_test1 (i0, j0, i, board_get (bd, i))
      then safety_test2 (i0, j0, bd, i-1) else false
    // end of [if]
  else true // end of [if]
// end of [safety_test2]

これら2つの関数の機能は次のように表現できます:

関数 safety_test1 は、行 i0 列 j0 にあるクイーンが、行 i 列 j にあるクイーンを取ることができるかどうかテストします。
関数 safety_test2 は、行 i0 列 j0 にあるクイーンが、与えられたボード上の i 以下の行番号にあるどれかのクイーンを取ることができるかどうかテストします。

これで、深さ優先探索 (DFS) アルゴリズムを使って、次のような関数 search を実装する準備が整いました:

fun search
(
  bd: int8, i: int, j: int, nsol: int
) : int = (
//
if
(j < N)
then let
  val test = safety_test2 (i, j, bd, i-1)
in
  if test
    then let
      val bd1 = board_set (bd, i, j)
    in
      if i+1 = N
        then let
          val () = print! ("Solution #", nsol+1, ":nn")
          val () = print_board (bd1)
        in
          search (bd, i, j+1, nsol+1)
        end // end of [then]
        else (
          search (bd1, i+1, 0(*j*), nsol) // positioning next piece
        ) (* end of [else] *)
      // end of [if]
    end // end of [then]
    else search (bd, i, j+1, nsol)
  // end of [if]
end // end of [then]
else (
  if i > 0
    then search (bd, i-1, board_get (bd, i-1) + 1, nsol) else nsol
  // end of [if]
) (* end of [else] *)
//
) (* end of [search] *)

search の返値はエイト・クイーンパズルの解の総数です。 search の本体の中のシンボル print! は ATS における特別な識別子です: この識別子は任意の数の引数を取り、それぞれの引数に print を適用します。これは search 関数を呼び出すと印字される最初の解です:

Q . . . . . . . 
. . . . Q . . . 
. . . . . . . Q 
. . . . . Q . . 
. . Q . . . . . 
. . . . . . Q . 
. Q . . . . . . 
. . . Q . . . .

解の総数は92になります。

この章で紹介した全コードと追加のテストコードはオンラインから入手できます。

Prev	Home	Next
末尾呼出と末尾再帰	Up	相互再帰関数