🔙 Back to Top

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

čĢ–æ–‡ãŽčĄ¨ã ã¨ã‚‚ãŖã¨å°‘ãĒãã‚„ãŖãĻるãŊいけお. äŊ•ãŒé•ãŖãŸã‹ãĒ.