数独〔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個ずつ重複することなく配置される。 |
アルゴリズムの解説
- すべての未確定のマスを対象に、関連する縦・横・3*3のマスからなり得る数値群「可能数一覧」を求める。
- 「可能数一覧」で、なり得る数値が1個の場合、そのマスはその数値で確定することになる。
- 確定したマスに関連する縦・横・3*3のそれぞれのマスが持つ「可能数一覧」から、確定した数値を削除する。
- 削除した結果、「可能数一覧」がなり得る数値が1個になった場合、そのマスはその数値で確定することになる。
- これを左上から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個のマスで構成される。
一グループにおいて調査した結果値が確定すると他のグループにおいても必ず一致するはずである。もし、一致しない場合はデータに矛盾が有る。
【方法】
-
未確定の各マスに自分自身がなりえる数値「未確定数値郡」を抽出する。これは、ルールでも明らかなように該当マスが属している「縦・横・3×3」の全グループ内で唯一の数値を求めるのだから、そのグループ内で確定している数値をすべて除けばいい。
但し、「未確定数値郡」の結果、可能性のある数値が1個しかない場合はその数値で確定する。(「未確定数値郡」の結果が0個になることはない)
- マスの数値が確定する条件は以下の通りである。
- 初めから「未確定数値郡」の個数が1個の場合(上記1.項参照)
-
自分自身の「未確定数値郡」の中から一つ数値を取り出し、各グループ内で重複していないか確認する。
重複していなければ、その数値が自分自身の値として確定する(一グループ内でその数値になり得る他のマスはない)。と同時に、他のグループ(縦グループで確定された場合は、横グループと3×3グループ)のマス「未確定数値郡」に同一の数値は削除する。重複していた場合は、「未確定数値郡」のいずれかの数値が上記条件に一致するか全て判定する。 -
他のマスが確定することで、自身の「未確定数値郡」が1個になったとき。
-
全マスが確定するまで2.項を繰り返す。
(9×9の81マス)
-
また、直接アルゴリズムとは関係ないが、データの整合性チェック(同一グループ内において同じ数値が確定されている等)を行うかどうかは他の要因で決定されるだろう。その際のチェック項目の抽出は試行錯誤的にならざるをえない。論理的矛盾を回避するためのものだから、すべての手順を考察した後で現れてくる。
データによっては、答えがおかしかったり、無限ループになってしまい終了できなくなる可能性もあり得る。
アプローチ
- 個々のマスを一オブジェクトとし、81個のマス・オブジェクトを作成する。
-
マス・オブジェクトは、マス自身が各グループのマスとの比較を行う。そのために、「未確定数値郡」と自身が属している各グループのマス・オブジェクト(自身を除く8個のマス×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, };
- 確定と確定後に関連するマスの「未確定数値郡」から各定数値を削除し他結果1個になるのは連動するので、この処理を再帰する。(9×9の81個のマス走査回数が削減できる(あるパターンにおいて、再帰にしない場合は6回だが再帰にした場合4回の走査で完了した)。
- マス・オブジェクトの変数とメソッド(関数)は以下の通り。
パブリック変数 なし プライベート変数 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)
|
SUDOKU数独サイト Web上で楽しめます。
数独(SUDOKU・ナンプレ) - 無料フラッシュゲーム -
〔数独〕のアルゴリズムに関するサイト紹介。 ナンバープレイス解法教室もご参照ください。