Mon Oct 12 01:20:08 JST 2015

N-Queens Problem

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.

このようにして、計算量の上限としては、

\(n \times n * 1 \times n * 2 \times \ldots \times n * (n-1) = n^n * (n-1)!\)

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

上の出力

(4,2)
(5,10)
(6,4)
(7,40)
(8,92)
(9,352)
(10,724)
(11,2680)
(12,14200)
(13,73712)

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

Fast N-Queens

ググったらすぐに見つかった.

  1. A polynomial time algorithm for the N-Queens problem
  2. IEEE Xplore Abstract - Fast search algorithms for the n-queens problem

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")
    }
  }
}

コードはかなり長くなった.

試行回数: 257
._._._._._.q._._._._
._._._.q._._._._._._
._.q._._._._._._._._
._._._._._._._.q._._
._._.q._._._._._._._
._._._._._._.q._._._
._._._._._._._._._.q
.q._._._._._._._._._
._._._._._._._._.q._
._._._._.q._._._._._

確かに動いてるし、試行回数はそこまで大きくないようにも思える. 一回の施行の計算量は \(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")
  }
}

\(n=12\) での試行回数

% for i in `seq 10`; do scala test.scala; done
3955
1754
51
1140
1155
88
2479
307
370
1471

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