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セットアップガイド
を参照して下さい。

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

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

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

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

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

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

コード解説

問題データの定義

この部分は、通常のPythonのコードなので、説明は省略します。

# 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呼出しの本質的な部分です。
行単位で、コメントをいれておきましたので、それを読むとだいたいの様子はわかるかと思います。

# ライブラリインポート
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関数を呼び出すと数独の問題を解いてくれます。

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

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

結果の確認

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

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)

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

おまけ

上で紹介した数独より実業務に近い問題である「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