ここに 175 行 140 列のお絵かきロジックがあるじゃろ？
Japanese crossword #21251 - nonograms.org
これを最適化ソルバーに食わせて…
Google OR-Tools
こうじゃ。
※ お絵かきロジック（a.k.a ピクロス）なんて知らないよって人はこのあたり読んでみてください。一マス塗り間違えると最後に全てが瓦解したりする、なかなか愉快なパズルですぞ。
お絵かきロジックとは - ニコニコ大百科
何をしたの？
こんな感じです。順を追って説明します。
- Selenium で問題をスクレイピング
- 行・列ごとにオートマトンを構築
- オートマトンを制約式として Google OR-Tools に投入
- 解を整形してテキスト出力
※ オートマトンを経由するアルゴリズムは hakank さんが実装していたものをそのまま移植しました。
hakank/google_or_tools/nonogram_regular.py - GitHub
スクレイピング
今回は、お絵かきロジックの投稿サイト nonograms.org から問題を取得することにしました。
Selenium でヘッドレス Chrome を起動して、行のルールを#nmh0_1 > div 列のルールを #nmv2_3 > div といった CSS セレクタで掴んでいます。
コードは Scala で書いていますが、知らなくても雰囲気で読めると思います。
Using(new ChromeDriver(new ChromeOptions().addArguments("--headless"))) { driver =>
driver.get(s"https://www.nonograms.org/nonograms/i/$id")
val nmh = (for (i <- LazyList.from(0)) yield {
(for (j <- LazyList.from(0)) yield {
driver.findElementsByCssSelector(f"#nmh${j}_$i > div").asScala.map(_.getText.toInt)
}).takeWhile(_.nonEmpty).flatten.toVector
}).takeWhile(_.nonEmpty).toVector
val nmv = (for (i <- LazyList.from(0)) yield {
(for (j <- LazyList.from(0)) yield {
driver.findElementsByCssSelector(f"#nmv${i}_$j > div").asScala.map(_.getText.toInt)
}).takeWhile(_.nonEmpty).flatten.toVector
}).takeWhile(_.nonEmpty).toVector
(nmh, nmv)
}(_.close())
ちなみに待望の Scala 2.13 がリリースされたので、さっそく新機能 Using LazyList を使ってますよん。
オートマトンから制約式へ
さて、スクレイピングによって取得したお絵かきロジックのルールを、ソルバーが食える制約式に変換したいわけです。
ここで、お絵かきロジックのルールがどのようなものだったかというと、たとえば行のルールが「1, 2, 3」で 6 列だった場合、その行の埋め方は次のように 6 パターンあるというものでした。
| 行ルール | ||||||
|---|---|---|---|---|---|---|
| 1,2 | ■ | □ | ■ | ■ | □ | □ |
| 1,2 | ■ | □ | □ | ■ | ■ | □ |
| 1,2 | ■ | □ | □ | □ | ■ | ■ |
| 1,2 | □ | ■ | □ | ■ | ■ | □ |
| 1,2 | □ | ■ | □ | □ | ■ | ■ |
| 1,2 | □ | □ | ■ | □ | ■ | ■ |
これって要するに、正規表現「□*■□+■■□*」なのですよね。
正規表現ということは、そうです、対応するオートマトンが作れるということです！
このオートマトンに沿って遷移させれば、その行の塗り方が「□*■□+■■□*」にマッチするかどうか判定できるというわけです。すなわち遷移表はこうなります。
| 状態 | □ | ■ |
|---|---|---|
| 0 (reject) | 0 | 0 |
| 1 (start) | 1 | 2 |
| 2 | 3 | 0 |
| 3 | 3 | 4 |
| 4 | 0 | 5 |
| 5 (accept) | 5 | 0 |
ということで遷移関数を trantision 、 オートマトンの状態を state 、 そしてお絵かきロジックのマスを cell として、次のような制約式に変換します。
\begin{align}
\mathrm{state}[\ 0\ ] &= 1 & \mathrm{start} \\
\mathrm{state}[\ 5\ ] &= 5 & \mathrm{accept} \\
\mathrm{state}[\ i + 1\ ] &= \mathrm{transition}[\ \mathrm{state}[\ i\ ]\ ][\ \mathrm{cell}[\ i\ ]\ ] & i \in \{0, 1, 2, 3, 4\}
\end{align}
コードに落とすとこんな感じになりました。
def addRule(intVars: Seq[IntVar], rule: Seq[Int])(implicit solver: Solver): Unit = {
val transition = Seq(0, 0) ++ (for (((r, s), i) <- rule.zip(rule.scan(0)(_ + _)).zipWithIndex) yield {
Seq(s + i + 1, s + i + 2) ++ (s + i + 3 to s + i + r + 1).flatMap(j => Seq(0, j)) ++ Seq(s + i + r + 2, 0)
}).flatten.dropRight(2) ++ Seq(rule.sum + rule.size, 0)
val states = (0 to intVars.size).map(_ => solver.makeIntVar(0, rule.sum + rule.size))
solver.addConstraint(states.head === 1)
solver.addConstraint(states.last === rule.sum + rule.size)
for (i <- intVars.indices) {
solver.addConstraint(states(i + 1) === ((states(i) * 2) + intVars(i)).of(transition))
}
}
ちなみに === という制約式の演算は solver.makeEquality を読みやすいようにラップした自前の DSL です。このあたりサクッと型安全に実装できるのが Scala の良いところですね。 + * of もそうです。
最適化ソルバー
さて Google OR-Tools ですが、これは名前の通り Google 製のオペレーションズ・リサーチ用ライブラリです。
最適化ソルバーそのものは COIN-OR のものが同梱されていて、今回はそのまま呼んでいます。なので COIN-OR 製の PuLP という Python ライブラリを使っても、ほぼ同じパフォーマンスが出せるはずです。
そして Google OR-Tools は C++ で実装されているのですが、そのインターフェースとして Python C# Java のライブラリも用意されています。インストールは Python のものが pip 一発で入るため楽なのですが、結局 C++ のリファレンスを見ないと引数の仕様が分からないのに C++ の関数名と微妙に異なって（ SWIG でリネームされて）いたりして、入門者にはとっつきにくい印象でした。そのため今回は Java ライブラリを手動でインストールして、同じ JVM 言語の Scala から呼んでいます。
なお Google OR-Tools は自前でビルドすればソルバーを差し替えることができて、商用ソルバーの Gurobi や CPLEX も使えるそうです。どのくらい性能上がるんだろう……。
性能
手元の MacBook Pro (2018) で動かしたところ、ソルバーは 2 秒ちょっとで 175 行 140 列のお絵かきロジックを解きました。
constraints: 147630
solutions: 1
branches: 410
failures: 205
WallTime: 2333 ms
問題ページのコメント欄を見ると 3 時間で解いた上級者がいるみたいなので、これが速いと感じるかどうかは人によると思いますが、汎用ソルバーに 10 万以上の制約式食わせてスッと解いてくるのは中々のものだと私は感じました。少なくともスクレイピングよりは、ずっと速かったですしね。
コード一式
100 行未満に収まりました。わりとコンパクトなのでは……？
import com.google.ortools.constraintsolver.{Constraint, IntExpr, IntVar, Solver}
import org.openqa.selenium.chrome.{ChromeDriver, ChromeOptions}
import scala.jdk.CollectionConverters._
import scala.util.{Failure, Success, Using}
object NonogramsOrgSolver {
implicit class IntExprHelper(i: IntExpr)(implicit solver: Solver) {
def ===(j: Int): Constraint = solver.makeEquality(i, j)
def ===(j: IntExpr): Constraint = solver.makeEquality(i, j)
def +(j: IntExpr): IntExpr = solver.makeSum(i, j)
def *(j: Long): IntExpr = solver.makeProd(i, j)
def of(j: Seq[Int]): IntVar = solver.makeElement(j.toArray, i.`var`()).`var`()
}
def addRule(intVars: Seq[IntVar], rule: Seq[Int])(implicit solver: Solver): Unit = {
val transition = Seq(0, 0) ++ (for (((r, s), i) <- rule.zip(rule.scan(0)(_ + _)).zipWithIndex) yield {
Seq(s + i + 1, s + i + 2) ++ (s + i + 3 to s + i + r + 1).flatMap(j => Seq(0, j)) ++ Seq(s + i + r + 2, 0)
}).flatten.dropRight(2) ++ Seq(rule.sum + rule.size, 0)
val states = (0 to intVars.size).map(_ => solver.makeIntVar(0, rule.sum + rule.size))
solver.addConstraint(states.head === 1)
solver.addConstraint(states.last === rule.sum + rule.size)
for (i <- intVars.indices) {
solver.addConstraint(states(i + 1) === ((states(i) * 2) + intVars(i)).of(transition))
}
}
def main(args: Array[String]): Unit = {
val id = args.head // 21251
System.setProperty("webdriver.chrome.driver", "/path/to/chromedriver")
Using(new ChromeDriver(new ChromeOptions().addArguments("--headless"))) { driver =>
driver.get(s"https://www.nonograms.org/nonograms/i/$id")
val nmh = (for (i <- LazyList.from(0)) yield {
(for (j <- LazyList.from(0)) yield {
driver.findElementsByCssSelector(f"#nmh${j}_$i > div").asScala.map(_.getText.toInt)
}).takeWhile(_.nonEmpty).flatten.toVector
}).takeWhile(_.nonEmpty).toVector
val nmv = (for (i <- LazyList.from(0)) yield {
(for (j <- LazyList.from(0)) yield {
driver.findElementsByCssSelector(f"#nmv${i}_$j > div").asScala.map(_.getText.toInt)
}).takeWhile(_.nonEmpty).flatten.toVector
}).takeWhile(_.nonEmpty).toVector
(nmh, nmv)
}(_.close()) match {
case Success((rowRules, colRules)) =>
System.loadLibrary("jniortools")
implicit val solver: Solver = new Solver("")
val board = rowRules.indices.map(_ => colRules.indices.map(_ => solver.makeIntVar(0, 1)))
for ((row, rowRule) <- board.zip(rowRules)) {
addRule(row, rowRule)
}
for ((col, colRule) <- board.transpose.zip(colRules)) {
addRule(col, colRule)
}
solver.newSearch(solver.makePhase(board.flatten.toArray, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE))
while (solver.nextSolution()) {
println()
val rStrings = rowRules.map(_.mkString(" "))
val rLength = rStrings.map(_.length).max
val rDisplay = rStrings.map(rule => " " * (rLength - rule.length) + rule + " | ")
val cStrings = colRules.map(_.mkString(" "))
val cLength = cStrings.map(_.length).max
val cDisplay = cStrings.map(rule => " " * (cLength - rule.length) + rule + " - ").transpose.map(_.mkString)
for (str <- cDisplay) {
println(" " * (rLength + 3) + str)
}
for ((row, str) <- board.zip(rDisplay)) {
println(str + row.map(v => if (v.value() == 1) "#" else " ").mkString)
}
println()
}
solver.endSearch()
println(s"constraints: ${solver.constraints()}")
println(s"solutions: ${solver.solutions()}")
println(s"branches: ${solver.branches()}")
println(s"failures: ${solver.failures()}")
println(s"WallTime: ${solver.wallTime()} ms")
case Failure(exception) =>
exception.printStackTrace()
}
}
}
name := "nonograms-org-solver"
version := "0.1.0"
javacOptions ++= Seq("-source", "11", "-target", "11")
scalacOptions ++= Seq("-deprecation", "-feature", "-unchecked")
scalaVersion := "2.13.0"
libraryDependencies ++= Seq(
"org.seleniumhq.selenium" % "selenium-chrome-driver" % "3.141.59"
)
fork := true
javaOptions += "-Djava.library.path=lib"
Google OR-Tools のバージョンは v7.1 (2019-05) です。
出力例
Japanese crossword #6250 - nonograms.org
1
2 1
6 2 11 1 2
116 3 4314 1 11 2
1
2 222446 11232 415242
11 1
4221163522416120321542
1521222211111311111221
----------------------
6 2 2 | ###### ## ##
9 1 2 | ######### # ##
9 1 4 | ######### # ####
3 7 2 | ### ####### ##
2 7 1 | ## ####### #
2 5 3 1 1 | ## ##### ### # #
1 1 4 | # # ####
2 5 | ## #####
1 4 3 | # #### ###
4 5 2 2 | #### ##### ## ##
2 16 | ## ################
2 12 3 | ## ############ ###
1 5 3 2 3 | # ##### ### ## ###
2 1 3 4 | ## # ### ####
1 1 2 3 | # # ## ###
1 4 2 | # #### ##
1 1 2 | # # ##
2 1 2 | ## # ##
2 1 2 | ## # ##
2 1 1 2 1 | ## # # ## #
2 4 1 1 3 | ## #### # # ###
4 12 3 | #### ############ ###
constraints: 7484
solutions: 1
branches: 6
failures: 3
WallTime: 128 ms
環境構築手順
- Selenium
- Chrome をインストール
- Chrome Driver をダウンロード
-
webdriver.chrome.driverに Chrome Driver のパスを設定
- Google OR-Tools
- Google OR-Tools (Java) をダウンロード
- 解凍して lib ディレクトリを Scala プロジェクトにコピー
-
java.library.pathに lib ディレクトリのパスを設定 - コード上で最初に
System.loadLibrary("jniortools")を呼びだす