NQueen.scala

object NQueen {
  def nq1(n:Int) = {
    def _nq(n:Int, x:Int, xs:Set[Int], ys:Set[Int], us:Set[Int], ls:Set[Int]):Int = {
      def collision(x:Int, y:Int) = xs(x) || ys(y) || us(y + x) || ls(y - x)  
      if (n == x) 1
      else {
        var cnt = 0
        for(y <- 0 to n - 1) {
          if ( !collision(x, y) ) {
            cnt += _nq(n, x+1, xs + x, ys + y, us + (y + x), ls + (y - x))
          }
        }
        cnt
      }
    }
    _nq(n, 0, Set(), Set(), Set(), Set())
  }
  
  def nq2(n:Int) = {
    def _nq(n:Int, x:Int, xs:Set[Int], ys:Set[Int], us:Set[Int], ls:Set[Int]):Int = {
      def collision(x:Int, y:Int) = xs(x) || ys(y) || us(y + x) || ls(y - x)  
      
      if (n == x) 1
      else (0 to n - 1)
        .filter(y => !collision(x, y))
        .map(y => _nq(n, x+1, xs + x, ys + y, us + (y + x), ls + (y - x)))
        .foldLeft(0)(_+_)
    }
    _nq(n, 0, Set(), Set(), Set(), Set())
  }  

  def main(args : Array[String]) = {
    import scala.testing.Benchmark
    def benchmark(f:Int=>Int, n:Int) = { 
      val xs = (new Benchmark { def run = f(n) }).runBenchmark(5)
      xs.sort((x, y) => x > y)(xs.length / 2)
    }
    def run(name:String, f:Int => Int) = {
      println(name)
      for(n <- List(8,10,11)) printf("n=%2d => %d \t %d ms\n", n, f(n), benchmark(f, n))       
      println("---\n")
    }
    
    run("Procedural", nq1)
    run("Functioanl", nq2)
  }
}