こんにちは！
ネクスタで開発エンジニアをしている伊藤です。以前、数理最適化を使って職場の勤務表半自動生成システムを作った経験を生かし、SmartF をより良いものにするというミッションに取り組むことになりました。
この記事では、実際の C# コードを添え、数理最適化をどうやって実際の事例に応用できるのかお伝えします。そこで今回は、Google OR-Toolsというライブラリを使って、「数独（ナンプレ）」を解くアプリを作ります。もちろん、生産管理アプリで数独を解く機会はありません。身近な例から入って、数理最適化とその表現方法について理解してもらうのが今回の記事の狙いになります。
数理最適化とは
数理最適化は、目的を達成するために、制約条件の中で最も良い解を数学的な手法で導き出す技術を指します。数理最適化のビジネス応用例として、シフト勤務職員の勤務表作成や、製品をまとめて作ると効率が良い場合に在庫費用とトレードオフでどれだけまとめて作るかの計画作成（ロットサイズ決定問題と呼ばれる）などがあります。[1]
この記事のゴール
- 数理最適化をコードで表現する方法が分かる
- Google OR-Tools を使って数独を解くコンソールアプリが作れる
実行環境
- .NET 8
- Visual Studio 2022
- Google.OrTools 9.14.6206 (NuGetで取得)
実装内容
まずは動くコードを見てみましょう。
コンソールアプリを作成し、NuGetで Google.OrTools をインストールしてください。
NuGetでGoogle.OrToolsをインストールする画面
そして、Program.cs に以下のコードを貼り付けます。これが数独を解く最小限の実装です。
using Google.OrTools.Sat;
namespace ConsoleApp1
{
public class Program
{
static void Main(string[] args)
{
// 1. 問題データの定義
// 0 は空欄を表します
var initialGrid = new int[9, 9] {
{ 0, 7, 0, 5, 3, 0, 9, 8, 0 },
{ 0, 0, 0, 6, 0, 0, 2, 5, 7 },
{ 5, 4, 0, 8, 2, 0, 6, 1, 0 },
{ 1, 5, 0, 4, 0, 0, 8, 0, 2 },
{ 3, 0, 6, 0, 0, 0, 7, 0, 0 },
{ 0, 0, 4, 0, 0, 3, 1, 0, 0 },
{ 4, 1, 5, 9, 0, 2, 3, 7, 0 },
{ 0, 6, 0, 0, 0, 0, 4, 0, 0 },
{ 0, 0, 8, 0, 7, 0, 0, 6, 0 }
};
Console.WriteLine("--- 数独ソルバー (Google OR-Tools) ---");
Console.WriteLine("問題:");
PrintGrid(initialGrid);
Console.WriteLine("\n[Enter]キーを押すと、AIが数独を解きます...");
Console.ReadLine();
// 2. モデルの作成
var model = new CpModel();
// 3. 変数の定義 (9x9 のグリッド、各マスは 1～9 の整数)
var grid = new IntVar[9, 9];
for (var i = 0; i < 9; i++)
{
for (var j = 0; j < 9; j++)
{
// 「各マスには1~9いずれかの整数が入る」という各マスに対応する変数を定義
grid[i, j] = model.NewIntVar(1, 9, $"grid_{i}_{j}");
// 初期値が設定されているマスはその値で固定する制約を追加
if (initialGrid[i, j] != 0)
{
model.Add(grid[i, j] == initialGrid[i, j]);
}
}
}
// 4. ルールの追加
// 行・列の制約
for (var i = 0; i < 9; i++)
{
// 行に同じ数字を重複させてはならない
//例: i が 1 のとき、grid[1, 0], grid[1, 1], ..., grid[1, 8](2行目全体) が選ばれる
model.AddAllDifferent(Enumerable.Range(0, 9).Select(j => grid[i, j]));
// 列に同じ数字を重複させてはならない
//例: j が 1 のとき、grid[0, 1], grid[1, 1], ..., grid[8, 1](2列目全体) が選ばれる
model.AddAllDifferent(Enumerable.Range(0, 9).Select(j => grid[j, i]));
}
// 3x3 ブロックの制約
for (var row = 0; row < 9; row += 3)
{
for (var col = 0; col < 9; col += 3)
{
var block = new List<IntVar>();
for (var r = 0; r < 3; r++)
{
for (var c = 0; c < 3; c++)
{
block.Add(grid[row + r, col + c]);
}
}
// 3x3 ブロックに同じ数字を重複させてはならない
model.AddAllDifferent(block);
}
}
// 5. 解く
Console.WriteLine("計算中...");
var solver = new CpSolver();
var status = solver.Solve(model);
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
Console.WriteLine("解が見つかりました！:\n");
// 結果を配列に変換して表示
var resultGrid = new int[9, 9];
for (var i = 0; i < 9; i++)
{
for (var j = 0; j < 9; j++)
{
// solver.Value() の結果は long ですが、intで受け取るためキャスト
resultGrid[i, j] = (int)solver.Value(grid[i, j]);
}
}
PrintGrid(resultGrid);
}
else
{
Console.WriteLine("解なし（または計算不能）でした。");
}
// 盤面を見やすく表示するローカル関数
static void PrintGrid(int[,] data)
{
for (var i = 0; i < 9; i++)
{
if (i % 3 == 0 && i != 0) Console.WriteLine("------+-------+------");
for (var j = 0; j < 9; j++)
{
if (j % 3 == 0 && j != 0) Console.Write("| ");
var val = data[i, j];
Console.Write((val == 0 ? "." : val.ToString()) + " ");
}
Console.WriteLine();
}
}
}
}
}
実行すると、一瞬でコンソールに答えが表示されます。
このように、「変数」を定義し、「制約」を与えて、「解く」のが OR-Tools の基本的な流れです。
なぜ CpModel なのか？
Google OR-Tools には複数の制約条件の中で、利益やコストなどの目的を最大化（あるいは最小化）する最適な解を見つけ出す線形計画法（LP:Linear Programming）など複数のソルバーが含まれていますが、今回は CpModel (CP-SAT solver) を使用しました。
なぜなら数独のようなパズルは「コストを最小化する」問題ではなく、「条件（制約）を満たす組み合わせを見つける」問題だからです。CP-SAT ソルバーは、OR-Toolsの中で整数プログラミングの問題（今回で言えば各セルに1~9のうちどの値が入るかを解く）を解く主要なツールの一つです。
添付したコードでは、NewIntVarを使い「各マスには1~9いずれかの整数が入る」という各マスに対応する変数を定義。そしてAddAllDifferentで「各列、各行、各ブロック(3x3)には全て違う数字が入る」という制約を宣言しました。
次のステップ
今回は入門編として、シンプルな数独ソルバーを作りました。なんとなく「制約を与えれば、ライブラリがいい感じに解いてくれる」という感覚が掴めたのではないでしょうか。
私のミッションである「SmartF」への導入提案では、これをさらに発展させてより複雑なビジネス課題に応用する予定です。これらも「制約」の塊ですからね。次は、もう少し実務に近い「勤務表作成」のようなテーマで記事を書いてみます。
皆さんもぜひ、身の回りのパズルや問題を OR-Tools に投げてみてください。
参考資料
-
斉藤努著『データ分析ライブラリーを用いた最適化モデルの作り方』第１章 最適化とは 参照 ↩︎
Discussion