image

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

検索

最近のトラックバック

無料ブログはココログ

« ピックアップ:インターネットで放送されているこの場では公表できません, ユニクロがアンパンと牛乳を無料配布する創業60周年記念セール, etc... | トップページ | ピックアップ:液晶保護シートを微塵の混入もなく貼るコツ, avaScript でリアルタイム 3DCG を実現する WebGL , etc... »

2009-11-19

scala で 8-queen (その2)

ここ数日の勉強を成果で前のプログラムを少し短くすることができた。
(結果を表示する 部分の扱い。配列の値設定、文字列表記生成の部分)

//  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
        }
    }
}

最後の toString 中の var や for ループも無くす事ができそうな気がするが...

« ピックアップ:インターネットで放送されているこの場では公表できません, ユニクロがアンパンと牛乳を無料配布する創業60周年記念セール, etc... | トップページ | ピックアップ:液晶保護シートを微塵の混入もなく貼るコツ, avaScript でリアルタイム 3DCG を実現する WebGL , etc... »

コメント

コメントを書く

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

トラックバック

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

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

« ピックアップ:インターネットで放送されているこの場では公表できません, ユニクロがアンパンと牛乳を無料配布する創業60周年記念セール, etc... | トップページ | ピックアップ:液晶保護シートを微塵の混入もなく貼るコツ, avaScript でリアルタイム 3DCG を実現する WebGL , 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 あわせて読みたい

リンク