Watsonで数独を解く! Decision Optimizationを使ってみた

# はじめに
まだ、あまり知られていないのですが、クラウドのWatson Studioでは、**CPLEX**と呼ばれる、**最適化問題を解くツール**がPythonから使えるようになっています。
(クラウド上のサービスの正式名称が**Decision Optimaization**です。)
その機能の紹介をします。
題材としては、日本人ならみんな知っていると思われるパズル「**数独**」を取りあげます。

[2020-03-16 githubのリポジトリ移動]
[2020-04-25 セットアップ手順変更]

# Decision Optimizationの動作原理
もともとあった製品としてのCPLEXでは、Eclipse上の開発ツール(**IBM ILOG CPLEX Optimization Studio**（**COS**)を使って、**Optimization Programming Language**(**OPL**)という言語によるモデル定義を生成します。
クラウド上の**Decision Optimization**は、これと同等のモデルをPythonのAPIによって呼び出すスタイルになります。クラウド上でOPLによるモデルを取り込んで使える機能は近々サポートされる予定です。
今回は、**Python APIでCLPEXを呼び出す**やりかたを取ることにします。

# APIの利用方法
クラウドのWatson Studio上で、このPython APIを呼び出すのはとても簡単です。
Notebook作成時のEnvironment設定で、「**Python 3.6x+DO**」となっているものを選ぶだけです。そう、**DO**とは**Decision Optimization**の略だったのですね。(私もつい最近知りました)

# サンプルコード
Jupyter Notebookで動くサンプルコードは
https://github.com/IBMDecisionOptimization/docplex-examples
に公開されています。
今回はここに入っていた``sudoku``を、コメントを日本語化して、コードを一部わかりやすくしたものを私のgithubにアップしておきました。

コード全体は、
https://github.com/makaishi2/sample-notebooks/blob/master/cplex/sudoku-aka.ipynb
にあります。

# 試してみよう
論より証拠、とにかく試してみましょう。
まだ、IBM Cloudのアカウントを持っていない方は、この機会に大至急アカウントを取得して下さい。
クレジットカードなしに、無期限で利用可能なLiteアカウントがあります。
手順は、
[無料でなんでも試せる! Watson Studioセットアップガイド](https://qiita.com/makaishi2/items/b666f847a98c2e42dfbb)
を参照して下さい。

ここに書かれた手順の登録が一通り終わったら、次のリンクから今作ったWatson Studioのプロジェクトを選択します。

https://dataplatform.cloud.ibm.com/projects

プロジェクト管理の画面になったら、画面上部の「**Add to project**」をクリックします。

![スクリーンショット 2019-08-07 11.21.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206130/5943b457-c19d-ab33-d331-fbba956b8b24.png)

下の画面になったら**Notebook**を選択します。

![スクリーンショット 2019-08-07 11.21.26.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206130/4f244f10-605f-07f8-6273-b092e3432f82.png)

次のNotebook作成画面になったら次の操作をします。
①「**From URL**」タブをクリック
② Nameの入力。なんでもいいですが、仮に**SUDOKU**としています。
③ Select runtime を「**Default Python 3.6XS + DO**」に変更します(重要)
④ Notebook URLの欄に下記URLを入力
⑤ 画面右下の「Create Notebook」ボタンをクリック

![スクリーンショット 2019-08-07 11.23.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206130/9849202b-4c66-6d34-dcc6-fc4db2be3087.png)

https://github.com/makaishi2/sample-notebooks/raw/master/cplex/sudoku-aka.ipynb

下の画面になったら、`shift + enter`でセルを上から順に実行していきます。
ちなみに、SUDOKU_PROPLEM_X が問題の定義です。ここを差し替えれば、あなた自身の数独を解かせることもできます。

![スクリーンショット 2019-08-07 11.32.44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206130/709af9ac-e689-8349-8556-a39efdc16a4b.png)

うまくいくと、最後にこんな結果が表示されるはずです。

![スクリーンショット 2019-08-07 11.24.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206130/b792d2c1-8d4f-c9e5-9bb1-09c567ac916d.png)

# コード解説

## 問題データの定義
この部分は、通常のPythonのコードなので、説明は省略します。

```py3
# GRNG: Grid Range
GRNG = range(9)

SUDOKU_PROBLEM_X = ( (0, 0, 0,  0, 1, 5,  0, 7, 0),
                     (6, 3, 0,  8, 0, 0,  0, 0, 0),
                     (0, 0, 8,  0, 4, 0,  0, 0, 0),
                     (0, 2, 5,  0, 0, 0,  0, 4, 0),
                     (3, 0, 0,  4, 7, 0,  2, 0, 0),
                     (1, 0, 0,  0, 0, 0,  0, 6, 0),
                     (8, 0, 0,  0, 0, 6,  0, 0, 0),
                     (0, 0, 0,  0, 2, 0,  0, 0, 0),
                     (0, 7, 2,  1, 0, 0,  0, 9, 0)
                    )

import numpy as np
import matplotlib.pyplot as plt

# 表示用関数
def draw_grid(values):
    %matplotlib inline
    fig, ax = plt.subplots(figsize =(4,4))
    min_val, max_val = 0, 9
    R =  range(0,9)
    for l in R:
        for c in R:
            v = values[c][l]
            s = " "
            if v > 0:
                s = str(v)
            ax.text(l+0.5,8.5-c, s, va='center', ha='center')
        ax.set_xlim(min_val, max_val)
    ax.set_ylim(min_val, max_val)
    ax.set_xticks(np.arange(max_val))
    ax.set_yticks(np.arange(max_val))
    ax.grid()
    plt.show()

# 問題の表示
draw_grid(SUDOKU_PROBLEM_X)
```

## CPLEXによる問題定義
ここが、CPLEX呼出しの本質的な部分です。
行単位で、コメントをいれておきましたので、それを読むとだいたいの様子はわかるかと思います。

```py3
# ライブラリインポート
from docplex.cp.model import *

# モデルの生成
mdl = CpoModel(name="Sudoku")

# 決定変数の定義

# 9 x 9 の配列に Clc という名前のCPLEX変数を定義します (C00, C01,.. C88)
# それぞれの変数は1から9までの整数値を取ります

grid = [[integer_var(min=1, max=9, name="C" + str(l) + str(c)) for l in GRNG] for c in GRNG]

# 制約の定義

# 制約条件を定義していきます

# 同一行に同じ整数値をもってはいけない
# all_diff は「すべての要素が同じではいけない」という意味の制約を表現する関数です
for l in GRNG:
    mdl.add(all_diff([grid[l][c] for c in GRNG]))

# 同一列に同じ整数値をもってはいけない
for c in GRNG:
    mdl.add(all_diff([grid[l][c] for l in GRNG]))    
    
# 3 x 3 の矩形領域に同じ整数値があってはいけない
ssrng = range(0, 9, 3)
for sl in ssrng:
    for sc in ssrng:
        mdl.add(all_diff([grid[l][c] for l in range(sl, sl + 3) for c in range(sc, sc + 3)]))

# 初期条件の設定

# C00からC88までのCPLEX変数に初期条件をとて与えられている値を設定していきます
# 設定は set_domainという関数で行います。
# 例えばマス目の値が7の場合該当する変数に対して 
# Cxx.set_domain(7, 7) (７以上7以下の値を設定) という設定を行います。

for l in GRNG:
    for c in GRNG:
        v = problem[l][c]
        if v > 0:
            grid[l][c].set_domain((v, v))
            # 設定した変数名と値の表示
            print(grid[l][c])
```

最後のprint文の結果は次のようになります。

```
C40 = intVar(1, 1)
C50 = intVar(5, 5)
C70 = intVar(7, 7)
C01 = intVar(6, 6)
C11 = intVar(3, 3)
C31 = intVar(8, 8)
C22 = intVar(8, 8)
C42 = intVar(4, 4)
C13 = intVar(2, 2)
C23 = intVar(5, 5)
C73 = intVar(4, 4)
C04 = intVar(3, 3)
C34 = intVar(4, 4)
C44 = intVar(7, 7)
C64 = intVar(2, 2)
C05 = intVar(1, 1)
C75 = intVar(6, 6)
C06 = intVar(8, 8)
C56 = intVar(6, 6)
C47 = intVar(2, 2)
C18 = intVar(7, 7)
C28 = intVar(2, 2)
C38 = intVar(1, 1)
C78 = intVar(9, 9)
```

## CPLEXによる解の取得
これで準備は整いました。後はモデルのslove関数を呼び出すと数独の問題を解いてくれます。

```py3
print('Solving model....')
msol = mdl.solve(TimeLimit=10)
print('Solved!')
```

さすがCPLEXです。「難問」を選んだつもりだったのですが、あっという間に答えを出してくれました。

## 結果の確認
最後に結果を確認してみます。

```py3
draw_grid(problem)
sol = [[msol[grid[l][c]] for c in GRNG] for l in GRNG]
print('Solve time: ',  msol.get_solve_time())
draw_grid(sol)
```

こんな結果がでてくれば成功です。

![スクリーンショット 2019-08-07 11.51.16.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/206130/075afbcb-2a16-7b0c-4ba4-1e1896c990fb.png)

# おまけ
上で紹介した数独より実業務に近い問題である「**oil blending**」もコメント日本語化をしてみました。使い方は上の例と同じです。

ソースをブラウザで見る場合のURL
https://github.com/makaishi2/sample-data/blob/master/notebooks/oil-blendung.ipynb

Watson StudioのJupyterにロードする場合のURL
https://raw.githubusercontent.com/makaishi2/sample-data/master/notebooks/oil-blendung.ipynb