ExcelマクロVBAサンプル集
数独(ナンプレ)を解くアルゴリズムの要点とパフォーマンスの検証№2

ExcelマクロVBAの実用サンプル、エクセルVBA集と解説
最終更新日:2017-11-26

数独(ナンプレ)を解くアルゴリズムの要点とパフォーマンスの検証№2


数独(ナンプレ)を解くアルゴリズムを例に、アルゴリズムの要点と、それによるパフォーマンスを検証します、



候補数値の少ないマスからチェックするように改造します。

変更は、getBlankだけになります。

このプロシージャーで、次に試行するマスを決定しているので、

この時に、候補数値のより少ないマスを返すように変更します。


Function getBlank(ByRef SuAry() As Integer, ByRef i1 As Integer, ByRef i2 As Integer) As Boolean
  Dim i3 As Integer
  Dim cnt As Integer
  Dim tryMin As Integer
  Dim i1Min As Integer
  Dim i2Min As Integer
  tryMin = 10
  For i1 = 1 To 9
    For i2 = 1 To 9
      If SuAry(i1, i2) = 0 Then
        cnt = 0
        For i3 = 1 To 9
          If chkSu(SuAry, i1, i2, i3) = True Then
            cnt = cnt + 1
          End If
        Next
        If tryMin > cnt Then
          i1Min = i1
          i2Min = i2
          tryMin = cnt
        End If
      End If
    Next
  Next
  If tryMin = 10 Then
    getBlank = False
  Else
    i1 = i1Min
    i2 = i2Min
    getBlank = True
  End If
End Function

1~9を回し、chkSuがTrueのカウントをとり、最も小さいマスを返すようにしています。


実際に動かしてやってみて下さい。

違いは歴然です。


当然、問題にもよりますが、一般に上級とされる問題なら、

以前は、試行回数が数万程度だったものが、数百程度に減っています。

当然、処理時間も激減しています。

数種類の問題で、セルへの途中表示をコメントアウトし試したところ、

№1のアルゴリズムは、1万~7万の試行回数で、0.2秒~0.8秒

№2のアルゴリズムは、90~800の試行回数で、0.1秒~0.4秒


いきなり、大幅に改善されてしまいました。

まさに、ここがアルゴリズムの要点だったのです。

ここに手を付けずに、他の箇所をいろいろ工夫したところで、

労多くして実り少ない事になるでしょう。

どうしても、全数チェックではダメだと考えた時、

数独を解くセオリーを調べ、それをプログラミングしようとしてしまいます。

しかし、生半可なアルゴリズムでは、結局複数候補のマスが多く残ってしまい、

最期は全数チェックに頼らざる負えなくなります。

つまり、この全数チェックのアルゴリズムは避けて通れないのです。

ならば、この全数チェックを、より有効なアルゴリズムにする事が、

パフォーマンスを上げる一番の近道だと考える事も出来ます。


この時、アルゴリズムの要点をどう見つけるか・・・

これには、経験と勘が必要であり、

また、実際の動きを注意深く観察する事も重要なのです。

理論と実践、この繰り返しになります。


№3へ続きます。

数独を解くアルゴリズムの要点とパフォーマンスの検証 №1 №2 №3 №4



こちらの最終完成版のダウンロード



同じテーマ「マクロVBAサンプル集」の記事

エクセルでファイル一覧を作成
アメブロの記事本文をVBAでバックアップする№6
数独(ナンプレ)を解くVBAに挑戦№5
数独(ナンプレ)を解くアルゴリズムの要点とパフォーマンスの検証№4
ナンバーリンク(パズル)を解くVBAに挑戦№8
ナンバーリンクを解くVBAのパフォーマンス改善№3
オセロを作りながらマクロVBAを学ぼう№9
他ブックへのリンクエラーを探し解除するマクロ(変更前)
Excelシートの複雑な計算式を解析するVBAの関数構文


新着記事NEW ・・・新着記事一覧を見る

CSVの読み込み方法(ジャグ配列)|VBAサンプル集(7月15日)
その他のExcel機能(グループ化、重複の削除、オートフィル等)|VBA入門(7月14日)
オートフィルタ退避回復クラスを複数シート対応させるVBAクラス|VBA技術解説(7月6日)
オートフィルタを退避回復するVBAクラス|VBA技術解説(7月6日)
IfステートメントとIIF関数とMax関数の速度比較|VBA技術解説(6月23日)
Withステートメントの実行速度と注意点|VBA技術解説(6月6日)
VBA+SeleniumBasicで検索順位チェッカー(改)|VBA技術解説(6月2日)
マクロでShift_JIS文字コードか判定する|VBA技術解説(6月1日)
Shift_JISのテキストファイルをUTF-8に一括変換|VBAサンプル集(5月31日)
「VBAによる解析シリーズその2 カッコ」をやってみた|エクセル(5月21日)


アクセスランキング ・・・ ランキング一覧を見る

1.最終行の取得(End,Rows.Count)|VBA入門
2.セルのコピー&値の貼り付け(PasteSpecial)|VBA入門
3.RangeとCellsの使い方|ExcelマクロVBA入門
4.変数とデータ型(Dim)|ExcelマクロVBA入門
5.Range以外の指定方法(Cells,Rows,Columns)|VBA入門
6.繰り返し処理(For Next)|ExcelマクロVBA入門
7.マクロって何?VBAって何?|ExcelマクロVBA入門
8.ひらがな⇔カタカナの変換|エクセル基本操作
9.ExcelマクロVBAの基礎を学習する方法|エクセルの神髄
10.空白セルを正しく判定する方法(IsEmpty,IsError,HasFormula)|VBA技術解説



  • >
  • >
  • >
  • 数独(ナンプレ)を解くアルゴリズムの要点とパフォーマンスの検証№2

  • このサイトがお役に立ちましたら「シェア」「Bookmark」をお願いいたします。


    記述には細心の注意をしたつもりですが、
    間違いやご指摘がありましたら、「お問い合わせ」からお知らせいただけると幸いです。
    なお、掲載のVBAコードは自己責任で使ってください。万一データ破損等の損害が発生しても責任は負いません。




    このサイトがお役に立ちましたら「シェア」「Bookmark」をお願いいたします。
    本文下部へ