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

公開日：2013年5月以前　最終更新日：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でバックアップする№1

後日追記アメブロの仕様変更が度々あり、ここで紹介しているコードで取得できないものもあります、いつ仕様変更されるかわかりませんので、都度変更するのは結構大変です。あくまで、WEBページの取得技術方法として参考にしてください。アメブロにはバックアップ機能がありません。

数独（ナンプレ）を解くVBAに挑戦№1

数独は、一般に「ナンバープレース（ナンプレ）」と呼ばれ、外国では「sudoku」と呼ばれているようです、この数独をExcelマクロVBAで解いてみようと言う事です。解き方は、とにかく片っ端から数字を当てはめていくという、なんとも芸の無い方法です。

数独（ナンプレ）を解くアルゴリズムの要点とパフォーマンスの検証№1
ナンバーリンク(パズル)を解くVBAに挑戦№1

ナンバーリンクというパズルがあります、これをエクセルVBAで解いてみようと思います、数独(ナンプレ)に続くパズルVBA解法の第二弾です。ナンバーリンクをご存じない方は、、ウィキペディアナンバーリンクのおためし問題このあたりをお読みください。

ナンバーリンクを解くVBAのパフォーマンス改善№1

「ナンバーリンク(パズル)を解くVBAに挑戦」で作成したVBAでナンバーリンクを解く事には成功しました、しかし、10×10なら数分で解けるものの、10×18でやったところ、4時間半もかかってしまいました。12×12では、待ちきれずに途中で止めてしまいました。

オセロを作りながらマクロVBAを学ぼう

ExcelマクロVBAでオセロ（リバーシ）を作っていきながら、マクロVBAを学んで行きましょう。目的は、マクロVBAの学習であり、思考を整理しVBAでプログラミングする学習です。従って、強いソフトを作ることが目的ではありませんので、最近流行のAIなんちゃら…なんていうのは考えるつもりはありません。

他ブックへのリンクエラーを探し解除

リンクエラーが見つけられない… 「リンクの編集」で、「リンクの解除」を選択してもリンクが削除できない… こんな経験をした人は多いのではないでしょうか。エクセルをいろいろと操作していると、意図せずに参照先が別ブックになってしまい、かつ、その参照先のブックが無くなってしまっている… こんな場合に、リンクエラーとなります。

Excelシートの複雑な計算式を解析するVBA

・複雑な計算式を解析するVBAの概要・複雑な計算式を解析する全VBAコード・複雑な計算式を解析した結果の表示・最後に

Excel将棋：マクロVBAの学習用(№1)

・Excel将棋の要件定義・Excel将棋のシート作成・Excel将棋の目次

Excel囲碁：万波奈穂先生に捧ぐ

・Excel囲碁の動作・全体の処理流れ・Excel囲碁の全VBAコード・Excel囲碁のダウンロード

Excel囲碁：再起動後も続けて打てるように改造

・Excel囲碁の今回の改造のきっかけ・Excel囲碁の今回の改造点・Excel囲碁の全VBAコード・Excel囲碁のダウンロード

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

1.最終行の取得（End,Rows.Count）｜VBA入門
2.セルのコピー&値の貼り付け（PasteSpecial）｜VBA入門
3.RangeとCellsの使い方｜VBA入門
4.ひらがな⇔カタカナの変換｜エクセル基本操作
5.繰り返し処理（For Next)｜VBA入門
6.変数宣言のDimとデータ型｜VBA入門
7.ブックを閉じる・保存（Close,Save,SaveAs）｜VBA入門
8.並べ替え（Sort）｜VBA入門
9.セルのクリア（Clear,ClearContents）｜VBA入門
10.Findメソッド（Find,FindNext,FindPrevious）｜VBA入門

ホーム
マクロVBA応用編
マクロVBAサンプル集
数独（ナンプレ）を解くアルゴリズムの要点とパフォーマンスの検証№2

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

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

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