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

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

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


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


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

ここでは、とにかく全ての数字を当てはめていくという、いわば全数チェックでの解法を使いました。

考察するまでもなく、かなりの無駄がある事は明白です。

しかし、このアルゴリズムは、間違いなく解を得る事ができ、かつ、そのアルゴリズムは非常に簡単なものです。

言わば、より良いアルゴリズムが不明な場合に、最期の手段といえるものでもあります。

さらに、このアルゴリズムは、絶対に不可欠なものでもあります。

少なくとも、数独を解く場合には、最期に複数候補のマスが複数残ってしまった場合には、

この全数チェックを行う事は必然であり、最も確実な方法でもあります。

とはいえ、最初から全数チェックは、いかにも芸がなく、PCのパフォーマンスに全てを委ねてしまっています。

この全数チェックの試行回数が膨大であり、間違いなく無駄だと感じます。

もっと効率的なアルゴリズムがあるはずです。

数独を解く場合のセオリーはいくつかあるようです。

しかし、ここでは、そのような一般的な数独を解くセオリー等は考慮せず、

あくまで、プログラミングのテクニックで、より有効なアルゴリズムを探してみたいと思います。


各マスに入れられる数値は1~9の全てではなく、縦・横・枠内に重複しない数値のみ入れられる訳です。

概ね、1つのマスに入れられる数値の種類は、2~6程度になります。

もちろん、初級問題なら、いきなり1つしか入れられないマスもあったり、

上級問題なら、7つも入れられる可能性のあるマスも存在はするでしょうが・・・


では、全数チェックすると言う事は、その組み合わせは、

入れる事が可能な候補数値の掛け算になってしまいます。

6×6×5×5×4×4×3×3×2×2

10個のマスでも、とんでもない組み合わせ数になってしまいます。

でも、先のアルゴリズムは、本当に全数チェックをしているのでしょうか?

そんな事はありませんね、全数チェックしていたら、とても短時間で解を求めることなど無理ですから。

数値を仮置きし、次のマスに進む、これ繰り返していくと、どこかで破綻します。

つまり、1~9のいずれの数値も入れられなくなってしまう状態が発生します。


その場合は、手前に戻って、数値を入れ直します。

つまり、破綻した時点で、それ以降はチェックしていないのです。


数独(ナンプレ)を解くVBAに挑戦
Option Explicit

Private tryCnt As Long

Sub main()
  Debug.Print Timer
  Dim SuAry(1 To 9, 1 To 9) As Integer
  Dim i1 As Integer
  Dim i2 As Integer
  
  tryCnt = 0
  Erase SuAry
  For i1 = 1 To 9
    For i2 = 1 To 9
      If Cells(i1, i2) = "" Then
        Cells(i1, i2).Font.Color = vbBlue
      Else
        SuAry(i1, i2) = Cells(i1, i2)
      End If
    Next
  Next
  
  Call trySu(SuAry)
  
  Range("A1:I9").Value = SuAry
  Debug.Print Timer
  
  If getBlank(SuAry(), i1, i2) = False Then
    MsgBox "解読成功" & vbLf & tryCnt
  Else
    MsgBox "あれれ・・・"
  End If
End Sub

Function trySu(ByRef SuAry() As Integer) As Boolean
  Dim i1 As Integer
  Dim i2 As Integer
  Dim su As Integer
  If getBlank(SuAry(), i1, i2) = False Then
    trySu = True
    Exit Function
  End If
  For su = 1 To 9
    If chkSu(SuAry(), i1, i2, su) = True Then
      SuAry(i1, i2) = su
      tryCnt = tryCnt + 1
      Cells(i1, i2) = su
      If trySu(SuAry) = True Then
        trySu = True
        Exit Function
      End If
    End If
  Next
  SuAry(i1, i2) = 0
  Cells(i1, i2) = ""
  DoEvents
  trySu = False
End Function

Function getBlank(ByRef SuAry() As Integer, ByRef i1 As Integer, ByRef i2 As Integer) As Boolean
  For i1 = 1 To 9
    For i2 = 1 To 9
      If SuAry(i1, i2) = 0 Then
        getBlank = True
        Exit Function
      End If
    Next
  Next
  getBlank = False
End Function

Function chkSu(ByRef SuAry() As Integer, ByVal i1 As Integer, ByVal i2 As Integer, ByVal su As Integer) As Boolean
  Dim ix1 As Integer
  Dim ix2 As Integer
  Dim i1S As Integer
  Dim i2S As Integer
  chkSu = False
  
  '横をチェック
  For ix2 = 1 To 9
    If ix2 <> i2 Then
      If SuAry(i1, ix2) = su Then
        chkSu = False
        Exit Function
      End If
    End If
  Next
  '縦をチェック
  For ix1 = 1 To 9
    If ix1 <> i1 Then
      If SuAry(ix1, i2) = su Then
        chkSu = False
        Exit Function
      End If
    End If
  Next
  '枠内をチェック
  i1S = (Int((i1 + 2) / 3) - 1) * 3 + 1
  i2S = (Int((i2 + 2) / 3) - 1) * 3 + 1
  For ix1 = i1S To i1S + 2
    For ix2 = i2S To i2S + 2
      If ix1 <> i1 Or ix2 <> i2 Then
        If SuAry(ix1, ix2) = su Then
          chkSu = False
          Exit Function
        End If
      End If
    Next
  Next
  chkSu = True
End Function



※赤字の部分は、今回の検証の為に追加した部分になります。
  試行回数をカウントするように変更しました。

これを実行して、じっくり眺めて下さい。


9×9の表の中断あたりで行ったり来たり、時には下段まで行って戻ったりしています。

つまり、下の方の空白マスはほとんどチェックされていないのです。

つまり、候補数値が、

6×6×5×5×4×4・・・ここで破綻

というような事が発生しているのです。


視点を変えて、もし、完全に全数チェックしているならば、

6×6×5×5×4×4×3×3×2×2

2×2×3×3×4×4×5×5×6×7

この2つは同じになります。

しかし、途中までなら、

つまり、

6×6×5×5×4×4

2×2×3×3×4×4

これは、明らかに後者の方が小さくなります。

さらに見方を変えれば、候補数値の少ないマスで破綻が起こりやすいのではないかと想像できます。


処理速度を速くするのなら、試行回数を減らせば良い訳です。

そこで、途中で破綻する事を前提に考えるならば、

このように、小さい数値の方からチェックした方が試行回数が少なくて済むのではないでしょうか。

まずは、これを検証してみます。


№2へ続きます。

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



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



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

アメブロの記事本文をVBAでバックアップする№1
数独(ナンプレ)を解くVBAに挑戦№1
数独(ナンプレ)を解くアルゴリズムの要点とパフォーマンスの検証№1
ナンバーリンク(パズル)を解くVBAに挑戦№1
ナンバーリンクを解くVBAのパフォーマンス改善№1
オセロを作りながらマクロVBAを学ぼう
他ブックへのリンクエラーを探し解除
Excelシートの複雑な計算式を解析するVBA
Excel将棋:マクロVBAの学習用(№1)
Excel囲碁:万波奈穂先生に捧ぐ
Excel囲碁:再起動後も続けて打てるように改造


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

ExcelマクロVBA入門目次|エクセルの神髄(2024-03-20)
VBA10大躓きポイント(初心者が躓きやすいポイント)|VBA技術解説(2024-03-05)
テンキーのスクリーンキーボード作成|ユーザーフォーム入門(2024-02-26)
無効な前方参照か、コンパイルされていない種類への参照です。|エクセル雑感(2024-02-17)
初級脱出10問パック|VBA練習問題(2024-01-24)
累計を求める数式あれこれ|エクセル関数応用(2024-01-22)
複数の文字列を検索して置換するSUBSTITUTE|エクセル入門(2024-01-03)
いくつかの数式の計算中にリソース不足になりました。|エクセル雑感(2023-12-28)
VBAでクリップボードへ文字列を送信・取得する3つの方法|VBA技術解説(2023-12-07)
難しい数式とは何か?|エクセル雑感(2023-12-07)


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

1.最終行の取得(End,Rows.Count)|VBA入門
2.RangeとCellsの使い方|VBA入門
3.セルのコピー&値の貼り付け(PasteSpecial)|VBA入門
4.繰り返し処理(For Next)|VBA入門
5.変数宣言のDimとデータ型|VBA入門
6.ブックを閉じる・保存(Close,Save,SaveAs)|VBA入門
7.並べ替え(Sort)|VBA入門
8.条件分岐(IF)|VBA入門
9.セルのクリア(Clear,ClearContents)|VBA入門
10.マクロとは?VBAとは?VBAでできること|VBA入門




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


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



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