テストの実行

[アーティクル]
06/09/2015

MSF ライブラリを使用して数独パズルを解

James McCaffrey 数独パズルは制約充足問題 (CSP) の一例です。プログラムで CSP を解く 1 つの方法が、Microsoft Solver Foundation (MSF) ライブラリを使用する方法です。通常業務で数独パズルを解くことはまったくなさそうですが、この記事をお読みいただく理由は少なくとも 3 つ考えられます。まず、ここで紹介する手法を、現実の多くの問題解決に当てはめることができます。次に MSF ライブラリとその機能を把握できます。最後に、プログラムで数独パズルを解くこと自体に興味や楽しさを感じていただけるかもしれません。

今回の考え方を把握するために、まずはデモプログラムをご覧ください (図 1 参照)。このデモコンソールアプリケーションは、代表的な数独パズルのデータを設定して表示することから始まります。次に、プログラムですべての数独パズル共通の制約 (必要条件) を定義後、今回の数独パズル固有のデータの制約を設定します。その後、MSF ライブラリを使用してパズルを解き、解答を表示して終了します。

Sudoku Using the Microsoft Solver Foundation
図 1 Microsoft Solver Foundation を使用した数独パズル

今回は、中級レベルのプログラミングスキルを有し、数独パズルについて漠然とした知識をお持ちであることが前提ですが、制約充足問題や MSF ライブラリについてはご存じなくても問題ありません。今回のデモプログラムは C# を使ってコーディングしていますが、他の .NET 言語へのコードのリファクタリングもそれほど難しくありません。ここではすべてのコードを示しますが、付随のコードダウンロード (msdn.microsoft.com/magazine/msdnmag0814、英語) から入手することもできます。中心となる考え方を明瞭にするために、通常のエラーチェックはすべて削除しています。

Microsoft Solver Foundation ライブラリ

MSF バージョン 3.1 ライブラリはコードダウンロードとして個別に入手できます。時間がたつとダウンロードの場所が変わることもありますが、現在は bit.ly/1vayGh1 (英語) からダウンロードできます。今回のテストでは 32 ビットのライブラリを使用するので、こちらのリンクをクリックして、MicrosoftSolverFoundation.msi インストールパッケージを実行または保存します。今回は直接 [実行] するオプションを選択しました。

インストールウィザードは Express Edition をインストールしていることを示します。MSF には本来、無料の Express Edition と有料の Enterprise Edition という 2 つのバージョンがありましたが、Enterprise Edition のダウンロードは終了しています。MSF ライブラリの開発は事実上積極的には行われなくなりましたが、現在の 3.1 バージョンは適切に動作します。高速でも少し重いインストールプロセスが完了すると、主要ライブラリファイルの Microsoft.Solver.Foundation.dll がコンピューターのディレクトリ "C:\Program Files (x86)\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0" にコピーされます。

デモプログラムを作成するには、Visual Studio を起動し、C# コンソールアプリケーションプログラムテンプレートを選択して、「SudokuSolver」という名前を付けます。デモは、Microsoft .NET Framework のバージョンとの大きな依存関係がないので、比較的新しいバージョンの Visual Studio であれば動作します。テンプレートコードが読み込まれたら、ソリューションエクスプローラーウィンドウで Program.cs ファイルの名前を SudokuProgram.cs に変更します。この変更により、Program クラスの名前が Visual Studio によって自動的に変更されます。デモプログラムの全体構造を図 2 に示します (スペースを節約するために少し編集しています)。

図 2 プログラムの全体構造

using System;
using Microsoft.SolverFoundation.Services;
namespace SudokuSolver
{
  class SudokuProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin MS Solver Foundation Sudoku demo");
      Console.WriteLine("The problem is: ");
      int[][] data = new int[9][];
      data[0] = new int[] { 0, 0, 6,
        2, 0, 0,
        0, 8, 0 };
      data[1] = new int[] { 0, 0, 8,
        9, 7, 0,
        0, 0, 0 };
      data[2] = new int[] 
      { 0, 0, 4,
        8, 1, 0,
        5, 0, 0 };
      data[3] = new int[] 
      { 0, 0, 0,
        0, 6, 0,
        0, 0, 2 };
      data[4] = new int[] 
      { 0, 7, 0,
        0, 0, 0,
        0, 3, 0 };
      data[5] = new int[] 
      { 6, 0, 0,
        0, 5, 0,
        0, 0, 0 };
      data[6] = new int[] 
      { 0, 0, 2,
        0, 4, 7,
        1, 0, 0 };
      data[7] = new int[] 
      { 0, 0, 3,
        0, 2, 8,
        4, 0, 0 };
      data[8] = new int[] 
     { 0, 5, 0,
       0, 0, 1,
       2, 0, 0 };
      // all program logic here
      Console.WriteLine("End Solver Foundation Sudoku demo");
      Console.ReadLine();
    }
    static void AddDataConstraints(int[][] data,
      Model model, Decision[][] grid) { . . }
    static int NumberSolutions(SolverContext problem) { . . }
  }
} // ns

Visual Studio テンプレートが生成したソースコードの先頭にある using ステートメントは、トップレベルの System 名前空間を参照するものを除いてすべて不必要なものとして削除します。次に、MSF ライブラリ DLL ファイルへの参照を追加後、このライブラリをスコープに入れるため、ライブラリを参照する using ステートメントを追加します。

ほぼすべての作業を Main メソッド内で実行します。2 つのヘルパーメソッド AddDataConstraints と NumberSolutions を用意して、コードを若干見やすくしています。デモは、最初に開始メッセージを表示した後、数独パズルのデータを "配列の配列" 形式の行列で設定します。

多くの言語と異なり、C# は真の 2 次元配列をサポートしますが、"配列の配列" を使用する方が作業は簡単になります。経験豊富なプログラマーであっても数式のプログラミングの経験があまりなければ、行列のコーディングテクニックにはなじみがないかもしれません。図 3 に、デモで使用するデータ行列を示します。データには個別のセル単位、または行単位にアクセスできますが、列単位にはアクセスできません。たとえば、data[0][2] は行 0 列 2 のセルを表し、値は 6 です。data[1] は 2 行目全体を指します。列に簡単にアクセスする方法はありません。C# では整数配列のセルがすべて 0 に自動的に初期化されるので、図 3 の空のセルには実際に値 0 が保持されます。

The Problem Data Matrix
図 3 問題データの行列

問題の設定

問題データの行列をしたら、値をシェルに表示します。

for (int r = 0; r < 9; ++r)  {
  for (int c = 0; c < 9; ++c)  {
    if (data[r][c] == 0)
      Console.Write(" _");
    else
      Console.Write(" " + data[r][c]);
  }
  Console.WriteLine("");
}

ここでは、ループの上限 9 をハードコーディングしています。特にデモプログラムの場合、個人的には、コードを汎用化するよりも、シンプルに保つ方が優れていると考えているためです。次に、初めて MSF コードを使用します。

SolverContext problem = SolverContext.GetContext();
Model model = problem.CreateModel();
Decision[][] grid = new Decision[9][];
for (int r = 0; r < 9; ++r)
  grid[r] = new Decision[9];

MSF コードはハイブリッドな研究開発環境で開発されているため、MSF ライブラリの操作はいつもと少し違う感じがするかもしれません。最初の 2 行は CSP オブジェクトを作成するための魔法の呪文と考えてください。通常とは違って、1 つのオブジェクトを操作するのではなく、MSF ライブラリでは problem オブジェクトや model オブジェクトなど、複数のオブジェクトを使用することが多くなります。

grid オブジェクトは、各セルが 1 つの Decision オブジェクトである、配列の配列形式の行列です。1 つの Decision オブジェクトが 1 つの解答をカプセル化すると考えます。つまり、数独パズルを解くには 9 x 9 = 81 個の値を決定する必要があり、これらの各値が 1 つの Decision オブジェクトによって表され、デモはこれらの値を行列に格納します。

この時点で、grid 行列にはインスタンスが作成されていない Decision オブジェクトが複数存在します。デモは、以下のようにして各セルのインスタンスを作成します。

for (int r = 0; r < 9; ++r)
  for (int c = 0; c < 9; ++c)
    grid[r][c] = new Decision(Domain.IntegerRange(1, 9),
      "grid" + r + c);
for (int r = 0; r < 9; ++r)
  model.AddDecisions(grid[r]);

Decision コンストラクターは 2 つのパラメーターを受け取ります。最初のパラメーターは解答のデータ型を表します。ここは、各解答は 1 ～ 9 までの整数です。2 つ目のパラメーターは文字列型の名前で省略できません。名前は一意になる必要があるため、プログラムでは "grid00"、"grid01" といった名前を 81 個の Decision オブジェクトそれぞれに割り当てています。Decision オブジェクトのインスタンスを作成したら、そのインスタンスを Model オブジェクトに追加します。AddDecisions メソッドは 1 つの Decision オブジェクトまたは Decision オブジェクトの配列を受け取ることができるので、デモでは grid 行列の 9 行を渡します。以下のように、入れ子にした 2 つのループを使用する方法もあります。

for (int r = 0; r < 9; ++r)
    for (int c = 0; c < 9; ++c)
      model.AddDecisions(grid[r][c]);

全般的な制約の追加

すべての数独パズルに共通の全般的な制約が 3 つあります。まず、各行の値はすべて異なる値にならなければなりません。次に各列の値もすべて異なる値にならなければなりません。最後に、3 x 3 のサブキューブに含まれる値もすべて異なる値にならなければなりません。最初の制約は、以下のように簡単に対処できます。

Console.WriteLine("Creating generic row constraints");
for (int r = 0; r < 9; ++r)
  model.AddConstraint("rowConstraint" + r, 
  Model.AllDifferent(grid[r]));

AddConstraint メソッドは、制約名と制約を受け取ります。ここでの名前は、"rowConstraint0"、"rowConstraint1" などになります。このデモでは AllDifferent メソッドを使用して制約を作成します。つまり、各行の値はすべて異なる値を持たなければならないという制約を、9 つの行それぞれに追加します。

列に関する全般的な制約を追加するのはちょっと面倒です。

Console.WriteLine("Creating generic column constraints");
for (int c = 0; c < 9; ++c)
{
  for (int first = 0; first < 8; ++first)
    for (int second = first + 1; second < 9; ++second)
      model.AddConstraint("colConstraint" + c + first + second,
        grid[first][c] != grid[second][c]);
}

列全体に直接アクセスすることはできないので、個別に各列を操作します。列 0 の場合、入れ子になった内側の 2 つのループを最初に処理するときに、 "colConstraint001" という名前で grid[0][0] != grid[1][0] という制約を設定します。2 回目の繰り返しでは、"colConstraint002" という名前で grid[0][0] != grid[2][0] という制約を設定します。つまり、AllDifferent メソッドは一連の Decision オブジェクトを配列として受け取り、明示的な不等式を生成します。Decision オブジェクトを配列にしない場合 (列の値の場合) は、明示的に不等式を生成する必要があります。

最も複雑なのは、9 個ある 3 x 3 のサブキューブに含まれる値がすべて異なる値になるという制約の設定です。図 4 にこのコードを示します。頑張りましょう。見かけほど複雑ではありません。

図 4 サブキューブの制約の設定

Console.WriteLine("Creating generic sub-cube constraints");
for (int r = 0; r < 9; r += 3) {
  for (int c = 0; c < 9; c += 3) {
    for (int a = r; a < r + 3; ++a) {
      for (int b = c; b < c + 3; ++b) {
        for (int x = r; x < r + 3; ++x) {
          for (int y = c; y < c + 3; ++y) {
            if ((x == a && y > b) || (x > a))
            {
              model.AddConstraint("cubeConstraint" + a + b + x + y,
                grid[a][b] != grid[x][y]);
            }
          } // y
        } // x
      } // b
    } // a
  } // c
} // r

図 3 の左下隅のサブキューブについて考えます。このサブキューブに必要な制約は以下のとおりです。

grid[6][0] != grid[6][1]
grid[6][0] != grid[6][2]
grid[6][0] != grid[7][0]
...
grid[8][1] != grid[8][2]

このサブキューブには 8 + 7 + 6 + … + 1 = 36 個の制約があることになるため、9 個あるサブキューブの制約は総計 9 * 36 = 324 個の不等式になります。根気よくコピーして貼り付ければそれぞれの不等式を記述できますが、プログラムによるアプローチの方が高速です。

コードでは、2 つの外側のループで各サブキューブの左上隅を決めます。最も内側の 4 つのループでは、各セルに grid[a][b] != grid[x][y] という不等式を設定します。インデックスだけを使って考えると以下のようになります。

60 and 61
60 and 62
...
81 and 82

各ケースを見てみると、ab < xy になるときに、不等式の制約が存在します。最も内側の 4 つのループでは、a、b、x、y を反復して、可能性のあるすべてのインデックスのペアを生成し、if-then 条件によって ab < xy のときだけ grid[a][b] と grid[x][y] に制約を作成します。

問題固有の制約の追加

全般的な制約を作成してモデルに追加したら、問題とする数独パズルを定義する制約を追加します。今回の問題では 27 個の値が決まっているため、以下のようにこの 27 個の値を 1 つずつ設定していくのも 1 つの方法です。

model.AddConstraint("v02", grid[0][2] == 6);
model.AddConstraint("v03", grid[0][3] == 2);
...
model.AddConstraint("v86", grid[8][6] == 2);

この方法でもかまいませんが、このデータは既に行列に含まれているので、プログラムでヘルパーメソッドを定義し、これを呼び出して値を変換すれば簡単です。

AddDataConstraints(data, model, grid);
where the helper is defined as:
static void AddDataConstraints(int[][] data, Model model, 
  Decision[][] grid)
{
  for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      if (data[r][c] != 0) {
        model.AddConstraint("v" + r + c,
          grid[r][c] == data[r][c]);
      }
    }
  }
}

Model オブジェクトと Decision オブジェクト間の奇妙な関係があることがわかります。開発者によって作成された開発者のためのライブラリコードは、おそらく model.grid[r][c] の行に従って Decision (解答) オブジェクトを参照していることになります。ここまでの 3 つの例で、MSF ライブラリの独特なスタイルに慣れたのではないでしょうか。

パズルを解く

すべての準備が整ったので、次のコードを使用してパズルを解きます。

Console.WriteLine("Solving. . . ");
int numSolutions = NumberSolutions(problem);
Console.WriteLine("There is/are " + 
  numSolutions + " Solution(s)");
Solution solution = problem.Solve();

NumberSolutions メソッドはプログラムで定義したヘルパーメソッドで、これを呼び出して、解がない (定義された制約が競合している) か、1 個以上あるかをチェックします。

static int NumberSolutions(SolverContext problem)
{
  int ct = 0;
  Solution soln = problem.Solve();
  while (soln.Quality == SolverQuality.Feasible) {
    ++ct;
    soln.GetNext();
  }
  return ct;
}

MSF の Solve メソッドは、SolverContext オブジェクトへの参照によって関連付けられる Model オブジェクトに含まれた Decision オブジェクトに実際の解を配置するだけです。Solution オブジェクトには、Feasible や Infeasible など、8 つの値のうちの 1 つを含む Quality フィールドがあります。Solution の GetNext メソッドは明示的な値を返すのではなく、Quality フィールドを変更します。これは MSF の仕様です。

数独デモは、grid 行列内部の Decision オブジェクトに格納されている解を表示して完了します。

for (int r = 0; r < 9; ++r) {
    for (int c = 0; c < 9; ++c) {
      double v = grid[r][c].GetDouble();
      Console.Write(" " + v);
    }
    Console.WriteLine("");
  }
  Console.WriteLine("End Solver Foundation Sudoku demo");
  Console.ReadLine();
} // Main

GetDouble メソッドは Decision オブジェクトから解の値を抽出します。解は 1 ～ 9 の範囲の整数値になるように定義しました。ただ、GetInteger メソッドは存在しないので、解の値を Double 型に暗黙のうちにキャストします。解の値に小数点以下はないので、Double 型であっても整数値として表示されます。

まとめ

今回紹介した特定の CSP は、組み合わせ最適化問題です。つまり、制約エラーが最も少ない値の組み合わせを探すのが目標です。ここに記載した情報を活用して、多くの実践的な組み合わせ最適化問題を、MSF ライブラリを使って解くことができるようになります。

実は、数年前、妹のボーイフレンドがパームスプリングスへの家族旅行の際に数独を教えてくれました。数独やクロスワードパズルなどをどちらが先に解けるかを競うと、いつも負けてしまいます。ただ、彼はこのコードを使用して数独パズルを解けることを知らないので、次の家族旅行が楽しみです。ノート PC を持っていくつもりです。

Dr. James McCaffrey は、ワシントン州レドモンドにある Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。連絡先は donnm@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれた以下の技術スタッフの Kirk Olynyk (Microsoft Research) に心より感謝いたします。