//  See http://booksites.artima.com/programming_in_scala/examples/html/ch23.html#sec2
package scalaapplication

object Queen extends Application {

    val MinQueen = 1 // 1
    val MaxQueen = 4 // 8

    for (size <- MinQueen to MaxQueen ) {
        def print(sols: List[List[(Int, Int)]]) = {
            Console.println(size.toString + " Queen: " +
                            (if (sols.isEmpty) "no solution"
                             else sols.length + " solution(s)"))
            sols.zipWithIndex.foreach( q =>
                Console.println("No." + (q._2 + 1) + "\n" +
                                Board(size, q._1))
            )
        }
        print(solve(size))
    }
    //--------------------------
    def solve(n: Int): List[List[(Int, Int)]] = {
        def placeQueens(k: Int): List[List[(Int, Int)]] = {
            if (k == 0) List(List())
            else
            for {queens <- placeQueens(k - 1)
                 column <- 1 to n
                 queen = (k, column)
                 if isSafe(queen, queens)
            } yield queen :: queens
        }
        placeQueens(n)
    }
    private def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = {
        queens forall (q => !inCheck(queen, q))
    }
    private def inCheck(q1: (Int, Int), q2: (Int, Int)) = {
        q1._1 == q2._1 ||  // same row
        q1._2 == q2._2 ||  // same column
        (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal
    }
    //--------------------------
    case class Board(size: Int, qs: List[(Int, Int)]) {
        private val board = Array.fromFunction((x,y) => qs.exists(_ == (x,y)))(size + 1, size + 1)

        override def toString = {
            var str: String = ""
            for (x <- 1 to size) {
                str += board(x).map(if(_) "*" else ".").mkString(" ") + "\n"
            }
            str
        }
    }
}