Wednesday, July 8, 2009

N Queens in Scala

Its been a while since I blogged. Even this is not a blog entry, its just a scala code snippet to solve the N queen problem. Its not particularly efficient, but by using lazy lists, we can run it on large numbers and get the first few results. Right now, not so lazy version:

object q extends Application {
def check(a: Tuple2[Int, Int], b: Tuple2[Int, Int]) =
a._1 == b._2 || (a._1+a._2 == b._1+b._2) || (a._2-a._1 == b._1-b._2)

def safe(p: List[Int], n: Int) = p.zipWithIndex.forall(!check(_, (p.size, n)))

def queens(m: Int)(n: Int): List[List[Int]] =
if (m == 0) List(Nil) else for (p <- queens(m-1)(n); i <- (0 until n); if (safe(p, i))) yield p ::: List(i)

println(queens(8)(8)) //Test code