scala で 8-queen 問題

こんなサイトを見つけた

- http://en.literateprograms.org/LiteratePrograms:Welcome
> LiteratePrograms:Welcome - LiteratePrograms

ちょっとした小さなプログラムの問題をいろいろな言語で処理する例が示されている。

scala で　８−クイーンを解く例があったので、試してみた。

$ scala -version
Scala code runner version 2.7.1.final -- Copyright 2002-2008, LAMP/EPFL

$ cat 8queen.scala
// See http://en.literateprograms.org/Eight_queens_puzzle_(Scala)

object EightQueens extends Application {
  def isSafe(queens: List[Int], column: Int, delta: Int): Boolean =
    queens.isEmpty ||
      ((queens.head != column) &&
      (Math.abs(queens.head - column) != delta) &&
      isSafe(queens.tail, column, delta+1))

  def queens(n: Int): List[List[Int]] = {
    def placeQueens(k: Int): List[List[Int]] =
      if (k == 0) List(List())
      else for { queens <- placeQueens(k - 1)
                 column <- (1 to n)
                 if isSafe(queens, column, 1) } yield column :: queens
    placeQueens(n)
  }
  queens(8).foreach(println(_))
}

$ calac 8queen.scala
$ time scala -cp . EightQueens | wc
      92     736    2668

real    0m0.484s
user    0m0.342s
sys    0m0.083s

これで N-queen の swi-prolog, ruby, scala, java での例を入手できたことになる。
速度やメモリ使用量を比較したり、N の増加に対するスケーラビリティを比較したりしてみたい。
また、言語に応じた解法はどれなのかについても調べていきたい。