この記事は Google Apps Script Advent Calendar 2021 の 13 日目の記事となります。
はじめに
Apps Script には LinearOptimizationService という 線形計画問題 を解くためのユーティリティサービスがあります。 特殊な目的で使用する機能なので、存在を知っている方は少ないんじゃないかと思います。
今回この LinearOptimizationService が使い物になるのかの検証を兼ねて、以前作った Python と PuLP を使って実装した数独を線形計画法で解くプログラム を Apps Script に移植してみようと思います。
作ったプログラムは ↓ に置いています。 解説では一部のコードのみを抜粋しているので、コードの全体はこちらでご確認ください。
LinearOptimizationService を触ってみる
先ずは簡単な問題から実装してみます。
適当に次のような問題を考えました。
問題: 「227 円の商品 x と 497 円の商品 y と 723 円の商品 z を、10,000 円からのお釣りがなるべく少なくなるように買うには、それぞれ何個ずつ買えばよいか」
この問題を解くプログラムを LinearOptimizationService を用いて、次のように実装しました。
function example() { const engine = LinearOptimizationService.createEngine(); engine.addVariable('x', 0, 100, LinearOptimizationService.VariableType.INTEGER); engine.addVariable('y', 0, 100, LinearOptimizationService.VariableType.INTEGER); engine.addVariable('z', 0, 100, LinearOptimizationService.VariableType.INTEGER); const constraint = engine.addConstraint(0, 10000); constraint.setCoefficient('x', 227); constraint.setCoefficient('y', 497); constraint.setCoefficient('z', 723); engine.setObjectiveCoefficient('x', 227); engine.setObjectiveCoefficient('y', 497); engine.setObjectiveCoefficient('z', 723); engine.setMaximization(); const solution = engine.solve(); Logger.log('x: ' + solution.getVariableValue('x')); Logger.log('y: ' + solution.getVariableValue('y')); Logger.log('z: ' + solution.getVariableValue('z')); }
プログラムは次のような流れになっています。
- 変数の宣言
- 制約式の追加
- 目的関数の定義
- 実行と結果の表示
それぞれの内容について詳しく見ていきましょう。
変数の宣言
engine.addVariable('x', 0, 100, LinearOptimizationService.VariableType.INTEGER); engine.addVariable('y', 0, 100, LinearOptimizationService.VariableType.INTEGER); engine.addVariable('z', 0, 100, LinearOptimizationService.VariableType.INTEGER);
ここでは x と y と z を商品の個数を入れる変数として定義し、それぞれ値のとる範囲を 0 ~ 100 としています。 値の上限値はとりあえず十分な値である 100 を指定しています。
また、商品の個数は整数値である必要があるので、変数のタイプに LinearOptimizationService.VariableType.INTEGER を指定しています。
制約式の追加
const constraint = engine.addConstraint(0, 10000); constraint.setCoefficient('x', 227); constraint.setCoefficient('y', 497); constraint.setCoefficient('z', 723);
今回必要な制約は、「合計金額が 10,000 円以下であること」なので、式で表すと次のようになります。
engine.addConstraint(0, 10000) で制約式を追加し、最大値及び最小値を指定しています。また、constraint.setCoefficient('変数名', 係数) で各変数の係数を指定しています。
目的関数の定義
engine.setObjectiveCoefficient('x', 227); engine.setObjectiveCoefficient('y', 497); engine.setObjectiveCoefficient('z', 723); engine.setMaximization();
今回は合計金額をなるべく多くしたいので、目的関数は次のようになります。
制約式と同じ要領で engine.setObjectiveCoefficient('変数名', 係数) で各変数の係数を指定しています。
金額を最大化したいため、engine.setMaximization() を呼び出しています。
実行と結果の取得
const solution = engine.solve(); Logger.log('x: ' + solution.getVariableValue('x')); Logger.log('y: ' + solution.getVariableValue('y')); Logger.log('z: ' + solution.getVariableValue('z'));
engine.solve() を呼び出して、設定した線形計画問題の答えを得ています。
各変数の値は solution.getVariableValue('x') のように呼び出すことで取得できます。
実行結果
実行してみると、次のような結果になりました。
計算してみると 227 * 13 + 497 * 4 + 723 * 7 = 10000 となります。今回はちょうどぴったしな解（最適解）があったようです。
数独を解く
ここまで LinearOptimizationService の簡単な使い方を解説してきましたが、ここからが本題の数独です。
変数の宣言
線形計画法で問題を解くには、変数どう設定するかが重要となります。 今回、数独の i 行 j 列目に値 v が使用されるかどうかを 0, 1 で持つ変数を定義します（この変数の値が 1 であれば i 行 j 列目には値 v が入るものとする）。
この定義方法では 9×9×9 = 729 個の変数が必要となります。数が多いため for 文を使って次のように定義します。
function variable(i, j, v) { return "x_" + i + "_" + j + "_" + v; } const engine = LinearOptimizationService.createEngine(); for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { for (let v = 1; v < 10; v++) { engine.addVariable(variable(i, j, v), 0, 1, LinearOptimizationService.VariableType.INTEGER); } } }
variable(i, j, v) を定義して、i と j と v の値を連結した文字列 x_i_j_v (i, j, v には具体的な数字が入る)を変数として定義しています。
変数のとる値は 0 と 1 だけであり、整数値をとる必要があるので LinearOptimizationService.VariableType.INTEGER を指定しています。
制約式の追加
数独で必要な制約は次の 4 種類になります。
- 各マスに 1~9 のいずれかの数字がちょうど一つ割り当てられるための制約
- 各行に 1~9 の数字がそれぞれ一回ずつ割り当てられるための制約
- 各列に 1~9 の数字がそれぞれ一回ずつ割り当てられるための制約
- 各 3x3 ブロックに 1~9 の数字がそれぞれ一回ずつ割り当てられるための制約
全部を説明すると長くなるため、一つ目の 「各マスに 1~9 のいずれかの数字がちょうど一つ割り当てられるための制約」についてのみ説明をします。
この制約を満たすためには、各 i, j についてちょうど一つの v についてのみ変数 x_i_j_v の値が 1（それ以外の v では 0）になるようにする必要があります。 そこで各 i, j について次の条件が満たされるようにします。
これをプログラムで表現すると次のようになります。
for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { const constraint = engine.addConstraint(1, 1); for (let v = 1; v < 10; v++) { constraint.setCoefficient(variable(i, j, v), 1); } } }
残りの制約については解説を省略しますが、同じような感じでやってます。
問題を制約式として表現
前述の制約だけだと、数独としてありうる問題の答えが一つ得られるだけなので、所望の数独の問題に対する答を得るために制約を追加します。
const p = [ [6, 5, 0, 0, 0, 0, 0, 0, 9], [0, 0, 2, 0, 8, 0, 0, 0, 0], [0, 0, 1, 9, 3, 2, 6, 0, 0], [0, 0, 0, 8, 0, 0, 2, 0, 0], [0, 0, 0, 4, 5, 0, 0, 0, 0], [0, 0, 9, 0, 0, 3, 0, 0, 7], [0, 9, 0, 0, 0, 0, 7, 0, 0], [4, 0, 0, 0, 0, 0, 3, 8, 0], [0, 0, 7, 0, 1, 0, 9, 0, 0] ];
9×9 の配列 p を数独の問題とし、p[i][j] が 0 の i, j については空欄で、それ以外の i, j についてはその数字が入っているものとします。 p の答えを得るために、p[i][j] が 0 以外の値をとる i, j とそのときの v = p[i][j] について次の条件を追加します。
これをプログラムで表現すると次のようになります。
for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { const v = p[i][j]; if (v != 0) { const constraint = engine.addConstraint(1, 1); constraint.setCoefficient(variable(i, j, v), 1); } } }
目的関数の定義
ここまでで追加した制約が満たされれば数独の答えとなるため、今回は目的関数は設定しません。
実行結果
以上の内容で実行した結果を次のようにして取得・表示してみました。
const solution = engine.solve(); for (let i = 0; i < 9; i++) { let line = ''; for (let j = 0; j < 9; j++) { for (let v = 1; v < 10; v++) { const value = solution.getVariableValue(variable(i, j, v)); if (value != 0) { line += " " + v; break; } } } Logger.log(line); }
得られた結果は次のようになります。
うーん。。。ぱっと見大丈夫そうです。
まとめ
LinearOptimizationService を使って実際に数独を解くことが出来ました。 今回は数独という実用性のない例でしたが、スプレッドシートなどと組み合わせるともっと実用的なアプリケーションが作れるかもしれません。
使ってみた感想としては...
Python で使った PuLP と比べ機能は少ないものの、その分とっつきやすかったです（雰囲気で書いたら動いた）。一方で、制約式を間違えたときに謎のサーバーエラーになり、エラーの詳細が分からずデバッグに苦労する場面もありました。実行環境も特殊なので、あまり初心者にはおすすめできないかなという感じです。
Apps Script については他にもいくつか記事を書いているので、良かったらご覧ください。
