読者です 読者をやめる 読者になる 読者になる

t-hom’s diary

主にVBAネタを扱っているブログです。

VBA 魔方陣を解く

VBA

先日から取り組んでいる以下の本の続き。

Excel VBAでパズルを解こう

Excel VBAでパズルを解こう

今回の課題は魔方陣を作ること。
方陣とは、3×3のマス目に1~9の数字を当てはめてタテ・ヨコ・ナナメの合計がすべて等しくなるようにするというパズルだ。

以下は回答の一例
f:id:t-hom:20150922060829p:plain

上記を含めて、答えは8つある。
自力で挑戦したい方は、以下ネタバレを含むので注意。

方陣を解くためには、順列を使用する。
以下、過去記事。thom.hateblo.jp

今回は記憶をたどりながら順列から自分で書いてみた。一部変数宣言は省略。

Sub 魔方陣()
    Const 列数 = 9, 要素数 = 9
    Dim 順列コレクション As New Collection
    Dim 作業順列コレクション As New Collection
    
    Dim 新順列(1 To 列数)
    
    For i = 1 To 列数
        新順列(i) = i
    Next
    順列コレクション.Add 新順列
    
    For 要素A = 要素数 - 1 To 1 Step -1
        For 要素B = 要素A + 1 To 要素数
            For Each 既存順列 In 順列コレクション
                入替 = False
                For j = 1 To 列数
                    Select Case 既存順列(j)
                        Case 要素A: 新順列(j) = 要素B: 入替 = True
                        Case 要素B: 新順列(j) = 要素A: 入替 = True
                        Case Else: 新順列(j) = 既存順列(j)
                    End Select
                Next
                If 入替 Then 作業順列コレクション.Add 新順列
            Next
        Next
        For Each x In 作業順列コレクション
            順列コレクション.Add x
        Next
        Set 作業順列コレクション = New Collection
    Next
    
    For Each m In 順列コレクション
        If m(1) + m(2) + m(3) = 15 Then
            If m(4) + m(5) + m(6) = 15 Then
                If m(7) + m(8) + m(9) = 15 Then
                    If m(1) + m(4) + m(7) = 15 Then
                        If m(2) + m(5) + m(8) = 15 Then
                            If m(3) + m(6) + m(9) = 15 Then
                                If m(1) + m(5) + m(9) = 15 Then
                                    If m(3) + m(5) + m(7) = 15 Then
                                        Debug.Print m(1); m(2); m(3)
                                        Debug.Print m(4); m(5); m(6)
                                        Debug.Print m(7); m(8); m(9)
                                        Debug.Print "------------------"
                                    End If
                                End If
                            End If
                        End If
                    End If
                End If
            End If
        End If
    Next
    Debug.Print "Fin"
End Sub

順列出力と違うのは最後に魔方陣が成立するかどうかのIf文。
Andでつなげて一つのIfにする方法もあるが、そうすると最初の条件が不成立でも残り全ての条件が評価されてしまうので、計算コストを考えてあえてネストさせている。

1列の合計が15であることは、1~9を全て足して3で割れば求まる。

コードの実行結果はこちら。

 2  7  6 
 9  5  1 
 4  3  8 
------------------
 2  9  4 
 7  5  3 
 6  1  8 
------------------
 4  3  8 
 9  5  1 
 2  7  6 
------------------
 4  9  2 
 3  5  7 
 8  1  6 
------------------
 6  1  8 
 7  5  3 
 2  9  4 
------------------
 6  7  2 
 1  5  9 
 8  3  4 
------------------
 8  3  4 
 1  5  9 
 6  7  2 
------------------
 8  1  6 
 3  5  7 
 4  9  2 
------------------
Fin

さて、よくよく観察すると、真ん中はすべて5、偶数は四隅に散らばっていることが分かる。
f:id:t-hom:20150922064501p:plain

この特性が証明できれば、魔方陣はあてずっぽうではなく論理的に解けるかもしれない。

真ん中が5というのはなんとなく分かる。
全ての数は、真ん中を通して15を作るので、真ん中が大小どちらかに偏ると、ある値では15に満たないか、超えてしまうことになる。
従って1~9の中央値である5を真ん中に据えることになる。

では、上記以外のパターンを考えてみよう。

偶数をこのように並べることは可能か。

 
   
     

これはできない。
まず、角に偶数を置いた時点で、対角線上も偶数になる。

   
   
   

なぜなら、合計値15のうち5は真ん中なので、残り10を作るために片方を偶数としたら、もう一方も偶数とする必要がある為だ。
同じく、上中央を偶数とした場合、下中央も偶数になる。

 
   
 

ここで4つ使い果たしてしまったので、あとは奇数しかない。

すると、縦列の左右が奇数+奇数+偶数=偶数となる。
作りたい15は奇数なので、これは間違い。

これも、

   
 
     

これも、

     
   
 

前述のパターンを回転・反転させただけで、同じ結論になる。

つまり、外周では偶数どおしが隣に並ぶことは無いといえる。
偶数が横に並ばないということは、間に必ず奇数が入るということであるから、奇数もまた横並びになることはありえない。

つまりこの理屈ではパターンはこれか、

これしかないということ。

しかし、後者の方は中央を通る線はクリアできてもそれ以外の外周が偶数になってしまうので15は作れない。
従って、正解パターンであるコレしか魔方陣は作れないということ。

ここまで魔方陣の性質が分かれば、プログラムはもっとスマートにできるし、紙と鉛筆でも全パターン書き出せるだろう。

このように、コンピューターによる力技でまず全パターン試してみて、出てきた結果から特性を探るというアプローチは非常に合理的だ。

コンピューターに計算させてしまったら楽しくないと思う方もいるかもしれないが、答えを知った上でなぜそうなるのか検証する作業もまた楽しいものである。

追記

方陣の性質を踏まえて改良したコード。
順列の要素が9から4に減ったのでかなりスピードアップした。

Sub 魔方陣改()
    Const 列数 = 4, 要素数 = 4
    Dim 順列コレクション As New Collection
    Dim 作業順列コレクション As New Collection
    
    Dim 新順列(1 To 列数)
    
    For i = 1 To 列数
        新順列(i) = i
    Next
    順列コレクション.Add 新順列
    
    For 要素A = 要素数 - 1 To 1 Step -1
        For 要素B = 要素A + 1 To 要素数
            For Each 既存順列 In 順列コレクション
                入替 = False
                For j = 1 To 列数
                    Select Case 既存順列(j)
                        Case 要素A: 新順列(j) = 要素B: 入替 = True
                        Case 要素B: 新順列(j) = 要素A: 入替 = True
                        Case Else: 新順列(j) = 既存順列(j)
                    End Select
                Next
                If 入替 Then 作業順列コレクション.Add 新順列
            Next
        Next
        For Each x In 作業順列コレクション
            順列コレクション.Add x
        Next
        Set 作業順列コレクション = New Collection
    Next
    
    '1,2,3,4を二倍して偶数順列 2,4,6,8を作成
    Dim 偶数順列コレクション As New Collection
    For Each m In 順列コレクション
        For k = 1 To 4
            新順列(k) = m(k) * 2
        Next
        
        '対角の合計が10になる場合のみ追加。
        If 新順列(1) + 新順列(4) = 10 Then 偶数順列コレクション.Add 新順列
    Next
    
    '奇数値は計算で求まる。
    For Each m In 偶数順列コレクション
        Debug.Print m(1); 15 - (m(1) + m(2)); m(2)
        Debug.Print 15 - (m(1) + m(3)); 5; 15 - (m(2) + m(4))
        Debug.Print m(3); 15 - (m(3) + m(4)); m(4)
        Debug.Print "------------------"
    Next
    Debug.Print "Fin"
End Sub

当ブログは、amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、 Amazonアソシエイト・プログラムの参加者です。