Top > 数独〔SUDOKU:ナンバープレイス〕 解を求めるアルゴリズム

数独(ナンバープレース)

数独(ナンバープレース)
問題から解を求めるアルゴリズム(コンソール版)
.NET Framework 2.0 with Visual Studio 2005 C++, C#. VB
VB6,VC++,VJ(Java)

1998年にオブジェクト指向、クラスなどを勉強するために作ったものです。
GUIの部分はありません。

ルールは以下の通り

ゲームは、全てのマスに下記の条件に合う1~9の数字を埋め込む
縦9列のマスに1~9までの数字を1個ずつ重複することなく配置される。
横9列のマスに1~9までの数字を1個ずつ重複することなく配置される。
3×3の枠内も1~9までの数字を1個ずつ重複することなく配置される。

 

アルゴリズムの解説

  1. すべての未確定のマスを対象に、関連する縦・横・3*3のマスからなり得る数値群「可能数一覧」を求める。
  2. 「可能数一覧」で、なり得る数値が1個の場合、そのマスはその数値で確定することになる。
  3. 確定したマスに関連する縦・横・3*3のそれぞれのマスが持つ「可能数一覧」から、確定した数値を削除する。
  4. 削除した結果、「可能数一覧」がなり得る数値が1個になった場合、そのマスはその数値で確定することになる。
  5. これを左上から1マス毎に順に繰り返すことで解を求めている。

 技術的には再帰を使い、自分のマスが解決すると、他の関連するマスを確認し、それが解決するとまた、他の関連するマスを確認・・・ これを最後のマスまで行うと、はじめのマスから繰り返します。

 旧VC++による、プログラミングとアルゴリズムの勉強のために作ったもの。他の言語での移植性をみるためにVB6,JAVAへ移植しました。今回、Visual Studio 2005 の 新旧の互換性と移植性をみるため、VC6(C++)を元に、C++, C#, VB へ移植しました。基本的なコードはそのままで、コンパイルが通るための若干の修正を加えています。(2006/7/7)

【ルール】

 次のルールに従ってマスに1~9の数字を書きこむ
(1)縦の9列、横の9列のどの列にも1~9の数字が1つずつ入る。
(2)線で囲まれた9つの3×3マスのどのブロックにも1~9の数字が1つずつ入る。

【前提条件】

マス・グループ

 一つのマスを取って見たときに、そのマス自身の値を確定するための条件要素として3つのグループがある。
 縦グループと横グループそして3×3グループである。それぞれのグループは、そのマス自身を含めた9個のマスで構成される。
 一グループにおいて調査した結果値が確定すると他のグループにおいても必ず一致するはずである。もし、一致しない場合はデータに矛盾が有る。

【方法】

  1.  未確定の各マスに自分自身がなりえる数値「未確定数値郡」を抽出する。これは、ルールでも明らかなように該当マスが属している「縦・横・3×3」の全グループ内で唯一の数値を求めるのだから、そのグループ内で確定している数値をすべて除けばいい。
     但し、「未確定数値郡」の結果、可能性のある数値が1個しかない場合はその数値で確定する。(「未確定数値郡」の結果が0個になることはない)
     
  2. マスの数値が確定する条件は以下の通りである。
    1. 初めから「未確定数値郡」の個数が1個の場合(上記1.項参照)
    2. 自分自身の「未確定数値郡」の中から一つ数値を取り出し、各グループ内で重複していないか確認する。
      重複していなければ、その数値が自分自身の値として確定する(一グループ内でその数値になり得る他のマスはない)。と同時に、他のグループ(縦グループで確定された場合は、横グループと3×3グループ)のマス「未確定数値郡」に同一の数値は削除する。重複していた場合は、「未確定数値郡」のいずれかの数値が上記条件に一致するか全て判定する。
    3. 他のマスが確定することで、自身の「未確定数値郡」が1個になったとき。
       
  3. 全マスが確定するまで2.項を繰り返す。
    (9×9の81マス)
     
  4. また、直接アルゴリズムとは関係ないが、データの整合性チェック(同一グループ内において同じ数値が確定されている等)を行うかどうかは他の要因で決定されるだろう。その際のチェック項目の抽出は試行錯誤的にならざるをえない。論理的矛盾を回避するためのものだから、すべての手順を考察した後で現れてくる。
     データによっては、答えがおかしかったり、無限ループになってしまい終了できなくなる可能性もあり得る。

アプローチ

  1. 個々のマスを一オブジェクトとし、81個のマス・オブジェクトを作成する。
     
  2. マス・オブジェクトは、マス自身が各グループのマスとの比較を行う。そのために、「未確定数値郡」と自身が属している各グループのマス・オブジェクト(自身を除く8個のマス×3グループ)へのポインタを持つ。メリットとしては確定処理の際、マス№やグループ№および各グループ内のマス№を意識しないですむ。
     
  3. 9×9の81個のマスと3×3グループの関係は以下の通りとする。

    マス№:0-80(左から右への一方向、上から下へ:左上を0とし、右下を80とする)

    00 01 02 | 03 04 05 | 06 07 08
    09 10 11 | 12 13 14 | 15 16 17 (3×3グループは左から、0、1、2)
    18 19 20 | 21 22 23 | 24 25 26
    ---------+----------+---------
    27 28 29 | 30 31 32 | 33 34 35
    36 37 38 | 39 40 41 | 42 43 44 (3×3グループは左から、3、4、5)
    45 46 47 | 48 49 50 | 51 52 53
    ---------+----------+---------
    54 55 56 | 57 58 59 | 60 61 62
    63 64 68 | 66 67 68 | 69 70 71 (3×3グループは左から、6、7、8)
    72 73 74 | 75 76 77 | 78 79 80
    マス№から3×3グループ№を求める計算式
    (マス№ / 27) * 3 + ((マス№ / 3) % 3)
    
    マス№から縦グループの先頭のマス№を求める計算式
    マス№ % 9;
    
    マス№から横グループの先頭のマス№を求める計算式
    (マス№ / 9) * 9;
    
    3×3グループ№からマス№を求める計算式
    for (int Count = 0; Count < 9; Count++)
        ThirdAndThirdGroupOffset[グループ№] + ((Count / 3) * 9) + (Count % 3);
    
    ThirdAndThirdGroupOffset[] =
    {
        0, 3, 6, 27, 30, 33, 54, 57, 60,
    };
  4. 確定と確定後に関連するマスの「未確定数値郡」から各定数値を削除し他結果1個になるのは連動するので、この処理を再帰する。(9×9の81個のマス走査回数が削減できる(あるパターンにおいて、再帰にしない場合は6回だが再帰にした場合4回の走査で完了した)。
     
  5. マス・オブジェクトの変数とメソッド(関数)は以下の通り。
パブリック変数 なし
プライベート変数
CMeasure *m_HeightNoGroup[8]; // 縦グループ(自分自身は除く)
CMeasure *m_WidthNoGroup[8]; // 横グループ(自分自身は除く)
CMeasure *m_ThirdAndThird[8]; // 3×3グループ(自分自身は除く)
int m_GroupNo; // 3×3グループ№
int m_MeasureNo; // 自分自身の位置:0-80(左から右への一方向、
                 // 上から下へ:左上を0、右下を80)
int m_Data; // 自分自身の値(1-9:0は未確定)
int m_MyElementCount; // 自分自身の未定義時における可能性のある数値データ件数
int m_MyElements[9]; // 自分自身の未定義時における可能性のある数値データ郡

パブリックメソッド(関数)
CMeasure(); // コンストラクタ
int IsData(void); // 数値要求(自身の数値データを返す。未確定の場合は0が返る)
// マス・オブジェクトの初期化
BOOL MeasureInitialization(int Data, int MeasureNo, CMeasure AllMeasure[]);
void MakeElements(); // 「未確定数値郡」の作成
int MeasureCheckStart(); // 「未確定数値郡」の一意な数値検索と確定処理
プライベートメソッド(関数)
BOOL IsSettlement(void); // 確定確認(確定していた場合TRUEを返す)
int ElementsUniqueCheck(int OneElement);// 「未確定数値郡」の重複確認
int ElementDelete(int OneElement);          // 「未確定数値郡」の確定済み数値の削除
void ElementSettlement(int OneElement);     // 確定とグループの要素データ整理

※上記アルゴリズムは、各マスが1個になることを前提にしています。例えば、ある2つマスに、2個の数値が残ったとします。どちらかを選択すれば解が求まる場合もありますが、それには対応していません。

ソースコード(プロジェクト一式)
C# NineAndNineCS.zip
VB NineAndNineVB.zip
C++ NineAndNineCpp.zip

※ロジックのみでUIはありません。コンソール版です。

旧版(VC++,VB6,JAVA)

C++ NineAndNineforC++.ZIP VC++プロジェクトで作っているが、MFCは使っていない。main()関数から始まるノーマルなC++のみで作成。結果はprintfで出力。
Java NineAndNineforJAVA.ZIP 上記VC++をJavaへ移植したもの。
VB NineAndNineforVB.ZIP 上記VC++をVBへ移植したもので、当然ながらクラスを用いている。

 

SUDOKU数独サイト Web上で楽しめます。

数独(SUDOKU・ナンプレ) - 無料フラッシュゲーム -

 〔数独〕のアルゴリズムに関するサイト紹介。 ナンバープレイス解法教室もご参照ください。

▲ページトップに戻る