パズルを解く制約プログラミング

このような１０枚の板を、四角に組み合わせるというパズル。

行き当たりばったりでは、簡単には解けない。
パソコンに解かせようと探したところ、こんなプログラムを見つけた。

* Coprisによる制約プログラミング入門
>> http://bach.istc.kobe-u.ac.jp/copris/docs/intro-ja.html

“制約プログラミング”とは、制約条件をコンピュータに入れると、コンピュータが条件に合った答をはじき出す、というもの。
Coprisの場合、条件を整数の数式の形で入力すると、答にあてはまるパターンが次々と出てくる。
この感覚を口で説明するのは、なかなか難しい。
たとえば上のパズルを解くプログラムは、こんな感じになる。

* まず答が入る容れ物となる、５ｘ５の変数を用意する。
　この全部で25個の変数は、それぞれ -1, 0, +1 の値のいずれかを取るものとする。
　+1 は長い切れ込み、-1 は短い切れ込み、0 は普通の長さの切れ込みを表すことにする。

* １０枚の板には +1 と -1 が１個ずつ入っている。
　[条件1] ５ｘ５の変数の、それぞれ縦の列の合計 = 0 となる。
　[条件2] ５ｘ５の変数の、それぞれ横の行の合計 = 0 となる。
　[条件3] ５ｘ５の変数の、それぞれ縦の列の絶対値の合計 = 2 となる（+1 と -1 の２個が入っている）。
　[条件4] ５ｘ５の変数の、それぞれ横の行の絶対値の合計 = 2 となる（+1 と -1 の２個が入っている）。

* １０枚の板のパターンが全部異なっている。
　板を裏返しに差し込むこともできるが、それらのパターンも全て異なる。
　[条件5] ５カ所の切れ込みを２進数と見なしたとき、２進数の値が縦横全部で異なる。
　　２進数は、切れ込みを右から左へ読んだパターンと、左から右に読んだパターンの全てが異なる。

* Scala ソースコードはこちら・・・
>> http://brownian.motion.ne.jp/memo/Copris/CrossBoard.scala
>> http://brownian.motion.ne.jp/memo/Copris/CrossBoardMain.scala

このような制約条件をセットして、答を探せ(find)と命令すると、Coprisが次々と答を出してくる。
試したところ、176パターンの答が出てきた。
このパターンの中には上下左右前後をひっくり返しただけの答も含まれているので、実質的には 176÷8=22 パターンの答があるようだ。
１パターンだけ示すと、こんな風になる。

0 -1 0 0 1
-1 1 0 0 0
0 0 1 -1 0
1 0 0 0 -1
0 0 -1 1 0

* 全ての解はこちら・・・
>> http://brownian.motion.ne.jp/memo/Copris/CrossBoardSol.txt

■ 班分け問題

パズルを解くプログラムなんて、ピンポイントでマニアックなものかと思いきや、これが案外役に立つ。
実際、私の役に立ったのは“相性のあるグループ分け問題”だった。
４０名ほどのメンバーを、５〜６名×７グループに班分けしたかったのだが、
メンバー同士には相性があって、この人と組みたい、この人とは一緒になりたくない、といった希望がある。
これが４０人分ともなると、いちいち希望を聞いて班分けするのは実に面倒くさい。
場合によっては、あっちの希望はかなったのに、なぜこっちの希望はかななわないのか、など、不平不満になりかねない。
そこで制約プログラミングの出番である。

* まず答が入る容れ物となる、(メンバー数)ｘ(グループ数)の変数を用意する。
　これらの変数は、それぞれ 1, 0 のいずれかの値を取るものとする。
　1 は、そのメンバーがそのグループに属していることを意味する。

* [条件1] 各メンバーは、どこかのグループに属する。
　変数の、メンバー行の合計 = 1。

* [条件2] 各グループに属する人数は決まっている。
　変数の、グループ列の合計 = (所定の人数)。

* [条件3] 仲良し同士は同じグループ。
　仲良し同士について、変数をグループ列方向に掛け算した合計 = 1（どこかのグループで１×１となる）。

* [条件4] 嫌い同士は異なるグループ。
　嫌い同士について、変数をグループ列方向に掛け算した合計 = 0（すべてのグループで１×１とはならない）。

* Scala ソースコードはこちら・・・
>> http://brownian.motion.ne.jp/memo/Copris/Groups.scala

好き、嫌いの条件をたくさん入れすぎると、解無しになってしまう。
そうなったとき、１つずつ条件を減らしてゆくと、どこかで解が出てくる。
つまり、誰が我慢すれば丸く収まるのか試すことができる。

■ 環境設定

制約プログラミングのソフトウェアはいくつかあるが、Coprisの良いところは敷居が低いことだと思う。
とにかくScalaさえ動かせれば、Copris自体で覚えるべきことはかなり少ない。
なので、「制約プログラミングとは何ぞや」を知るにはベストなのではないかと思う。
ただ、この「Scalaさえ動かせれば」のところでつまずく人も多いと思うので、Windows上での簡単な導入方法を以下にメモっておく。
（実際「Scala インストール」で検索すると、やれ開発ツールを入れろ、sbtを入れろ、
といった方法がヒットするので、目的に到達する前に息切れしてしまう。スタートはもっと簡単でよい。）

(1). Java runtime version 1.8 以降をインストールする >> http://www.java.com
（もちろんJDKでもかまわない。試しにコマンドプロンプト上で、
　　> java -version
　と入力してみて、version 8 以上と出てきたらインストールは不要。）

(2). Scala version 2.11 をインストールする
* Scala Download >> https://www.scala-lang.org/download/
　『CoprisはScala version 2.11で動作する (他のバージョンでは動作しない)．』
　とあるので、現在の最新版ではなく、前のバージョンを入手する。
　Scalaダウンロードページの下の方に「Other Releases」「Scala 2.11.12」とあるので、そちらをクリック。
　SCALA 2.11.12ダウンロードページには「DOWNLOAD INTELLIJ」「DOWNLOAD SBT」とあるのだが、
　それぞれ本格的開発向けなので、そこはパスする。
　ページ下の方にある「Other resources」「scala-2.11.12.zip」から、直接zipファイルをダウンロード入手する。

(3). Javaと Scalaにパスを通す。coprisにクラスパスを通す。
作業するコマンドプロンプト上で、以下のように入力するか、以下のようなバッチファイルを作っておく。
（"C:\MyWork"といった箇所は、各人の環境に応じて適切な場所をセットする。）

SET JAVA_HOME=C:\MyWork\java\10
SET SCALA_HOME=C:\MyWork\Scala\scala-2.11.12
PATH=%PATH%;%JAVA_HOME%\bin;%SCALA_HOME%\bin
SET CLASSPATH=.
SET CLASSPATH=%CLASSPATH%;C:\MyWork\Scala\copris-v2-2-8\build\copris-all-v2-2-8.jar

この状況で > scala と入力すると、scala対話プロンプト(REPL)が立ち上がる。

C:\MyWork\Scala>scala
Welcome to Scala 2.11.12 (Java HotSpot(TM) 64-Bit Server VM, Java 10).
Type in expressions for evaluation. Or try :help.
　
scala>

(4). 以降の操作は、Copris入門ページにある通り。
* Coprisによる制約プログラミング入門
>> http://bach.istc.kobe-u.ac.jp/copris/docs/intro-ja.html