先日から取り組んでいる以下の本の続き。
- 作者: 坪崎誠司
- 出版社/メーカー: 株式会社プレスティージ
- 発売日: 2010/07/06
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
今回の課題は魔方陣を作ること。
魔方陣とは、3×3のマス目に1～9の数字を当てはめてタテ・ヨコ・ナナメの合計がすべて等しくなるようにするというパズルだ。
以下は回答の一例
上記を含めて、答えは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、偶数は四隅に散らばっていることが分かる。
この特性が証明できれば、魔方陣はあてずっぽうではなく論理的に解けるかもしれない。
真ん中が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
