Mon Oct 12 01:20:08 JST 2015

Scala の練習として、リストのない方表記の練習として、 10.1 N クィーン問題 (The N-Queens Problem) をやってた. 大部分はそこに書いてあるとおりだけど、自分の解答として

import scala.math._
import scala.collection.mutable.{Queue, Set}
import scala.collection.immutable._
import scala.util.Random
 
object Main {

  def queens(n: Int): List[List[Int]] = {
    def isSafe(c: Int, qs: List[Int], d: Int): Boolean = {
      qs match {
        case List() => true
        case q::qs if c+d == q || c-d == q || c == q => false
        case q::qs => isSafe(c, qs, d+1)
      }
    }
    def sub(k: Int): List[List[Int]] = {
      if (k == 0) return List(List())
      for { qs <- sub(k-1)
          c <- Range(0, n)
        if isSafe(c, qs, 1) }
        yield c::qs
    }
    sub(n)
  }

  def show(n: Int, qs: List[Int]) {
    for (i <- Range(0, n)) {
      for (j <- Range(0, n)) {
        print('.')
        if (qs(i) == j) print('q')
        else print('_')
      }
      println("")
    }
  }

  def main(args: Array[String]) {
    for (n <- Range(4, 16)) {
      val ans = queens(n)
      println(n, ans.length)
    }
    /*
    for (ls <- ans) {
      for (x <- ls) print(x + " ")
      println("")
      show(n, ls)
    }
    */
  }
}

模範解答だと思う. 古典問題だし. 計算量の上限を測ってみることにした.

長さ n のリストの末尾から作っていくことに成る. 末尾の要素は n 通りある (制約がないので 0..(n-1) の何がきても良い). 末尾から2つ目の要素については、末尾の要素 n 通りそれぞれについて、やはり 0..(n-1) の n 通りを isSafe によって試して、問題ないものを次に通す. isSafe は長さに比例する計算量だから、ここでは 1.

ってな具合. 実際には、isSafe の部分で枝狩って行くことになるので、もっと小さい. 実際、最終的に得られる答えの数はもっとずっと小さい.

上の出力

とはいえ n=13 あたりからきつくなるので、適当な体感でいうと O(n!) かなって思っちゃう.

Fast N-Queens

2つめは家からアクセスできなかったんで、 1つめを読んでみた. 流し読みで読んだけど、要するに Figure 1 ということらしい.

Figure 1 の実装

答えは確かにどうせ [0 .. n-1] の置換である. アルゴリズムは簡単に

愚直に実装すると以下通り. ただし、無限ループ部分は1000回の上限をつけた. List[Int] は Array[Int] にした.

import scala.math._
import scala.collection.mutable.{Queue, Set}
import scala.collection.immutable._
import scala.util.Random
 
object Main {

  def queens(n: Int, uplimit: Int = 1000): Option[Array[Int]] = {

    def collision(qs: Array[Int]): Int = { // 衝突の数を数える
      var c = 0
      for (i <- Range(0, n-1)) {
        for (j <- Range(i+1, n)) {
          val d = j - i
          if (qs(i) == qs(j) || qs(i) == qs(j) - d || qs(i) == qs(j) + d) c += 1
        }
      }
      c
    }

    var tryNumber = 0
    for (t <- Range(0, uplimit)) {
      tryNumber = t + 1
      val qs = Random shuffle Range(0, n) toArray;
      var c = collision(qs)
      for (i <- Range(0, n-1)) {
        val tmp = qs(i)
        for (j <- Range(i+1, n)) {
          qs(i) = qs(j)
          qs(j) = tmp
          val c2 = collision(qs)
          if (c2 >= c) { // when swap doesn't reduce
            qs(j) = qs(i)
            qs(i) = tmp
          } else {
            c = c2
          }
        }
      }
      if (c == 0) {
        println("試行回数: " + tryNumber)
        return Some(qs)
      }
    }
    return None
  }

  def show(n: Int, qs: Array[Int]) {
    for (i <- Range(0, n)) {
      for (j <- Range(0, n)) {
        print('.')
        if (qs(i) == j) print('q')
        else print('_')
      }
      println("")
    }
  }

  def main(args: Array[String]) {
    val n = 10;
    val ans = queens(n)
    ans match {
      case Some(qs) => show(n, qs)
      case None => println("no answers")
    }
  }
}

確かに動いてるし、試行回数はそこまで大きくないようにも思える. 一回の施行の計算量は \(O(n^4)\) だけどな. \(n=12\) くらいから、1000回のループでは怪しくなってきた.

Figure 2

一つの、ランダムに生成した置換について、 swap を一度でも行ったものを、もう少し続けて試すというヒューリスティクスを導入する.

import scala.math._
import scala.collection.mutable.{Queue, Set}
import scala.collection.immutable._
import scala.util.Random
 
object Main {

  def queens(n: Int, uplimit: Int = 1000): Option[Array[Int]] = {

    def collision(qs: Array[Int]): Int = { // 衝突の数を数える
      var c = 0
      for (i <- Range(0, n-1)) {
        for (j <- Range(i+1, n)) {
          val d = j - i
          if (qs(i) == qs(j) || qs(i) == qs(j) - d || qs(i) == qs(j) + d) c += 1
        }
      }
      c
    }

    var tryNumber = 0
    for (t <- Range(0, uplimit)) {
      val qs = Random shuffle Range(0, n) toArray;
      var c = collision(qs)
      var grad = true
      while (grad) {
        tryNumber += 1
        var performed = 0
        for (i <- Range(0, n-1)) {
          val tmp = qs(i)
          for (j <- Range(i+1, n)) {
            qs(i) = qs(j)
            qs(j) = tmp
            val c2 = collision(qs)
            if (c2 >= c) { // when swap doesn't reduce
              qs(j) = qs(i)
              qs(i) = tmp
            } else {
              c = c2
              performed += 1
            }
          }
        }
        if (performed == 0) grad = false
        if (c == 0) {
          println(tryNumber)
          return Some(qs)
        }
      }
    }
    return None
  }

  def show(n: Int, qs: Array[Int]) {
    for (i <- Range(0, n)) {
      for (j <- Range(0, n)) {
        print('.')
        if (qs(i) == j) print('q')
        else print('_')
      }
      println("")
    }
  }

  def main(args: Array[String]) {
    val n = 12;
    val ans = queens(n, 1000000)
    if (ans == None) println("None")
  }
}

論文の表だともっと少なくやってるぽいけど. 何が違ったかな.