image

  • フォト Amazonギフト券
    ※この時計の時刻は、閲覧しているパソコンのものであり、必ずしも正確な時間とは限りません

検索

最近のトラックバック

無料ブログはココログ

« Scala スケーラブルプログラミング | トップページ | ピックアップ:綾瀬はるかが同世代の女優をぶっちぎり始めた理由, 150年の謎 リーマン予想, etc... »

2009-11-15

scala で 8-queen

書籍中のサンプルコードに コンソール出力を追加してみた。
なるべく scala らしく書こうとしたが、まだまだ...

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

import scala.collection.mutable.HashMap

object Queen extends Application {

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

    for (size <- 1.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).putQueens(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) {
        private val board = new Array[Array[Boolean]](size + 1)
        for (y <- 0.to(size)) {
            board.update(y, new Array[Boolean](size + 1))
        }
        def putQueens(qs: List[(Int, Int)]) = {
            qs.foreach(q =>  board(q._2).update(q._1, true))
            this
        }
        override def toString = {
            var str: String = ""
            for (y <- 1.to(size)) {
                for (x <- 1.to(size)) {
                    str += (if (board(x)(y)) "* " else ". ")
                }
                str += "\n"
            }
            str
        }
    }
}

netbeans 上でrun させると
init:
deps-jar:
compile:
run:
1 Queen: 1 solution(s)
No.1
*

2 Queen: no solution
3 Queen: no solution
4 Queen: 2 solution(s)
No.1
. . * .
* . . .
. . . *
. * . .

No.2
. * . .
. . . *
* . . .
. . * .

構築成功 (合計時間: 0 秒)

となる。

« Scala スケーラブルプログラミング | トップページ | ピックアップ:綾瀬はるかが同世代の女優をぶっちぎり始めた理由, 150年の謎 リーマン予想, etc... »

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/184434/46772720

この記事へのトラックバック一覧です: scala で 8-queen:

« Scala スケーラブルプログラミング | トップページ | ピックアップ:綾瀬はるかが同世代の女優をぶっちぎり始めた理由, 150年の謎 リーマン予想, etc... »

mokuji

2013年12月
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

google

  • twitter
  • __
  • _
    Googleボットチェッカー

合わせて読む

  • 合わせて読む
    フィードメーター - katoy: cocolog あわせて読みたい

リンク