魔方陣をよろしく
Mr. Shigeaki Iwamura
「魔方陣」をよろしく
昔からの有名な数学パズルに「魔方陣」というのがあります。１からｎ２までの
自然数をｎ行ｎ列の正方形に並べて行・列・対角線ともその和が一定数になる方陣
です。ただし、ｎ＝１の場合は意味がなく、ｎ＝２の場合は存在しません。通常は
ｎ＝３の場合が例としてあげられ、この場合には下図のように和が１５となり、相
対的な位置は代わっても、１通りしか存在しません。
4 9 2
3 5 7
8 1 6
３次の場合には紙と鉛筆の力仕事でもこれを見つけることはそんなに難しくあ
りません。問題は ｎ≧４の４次以上の場合です。
実はこんなことを考えさせられたのは、ある先輩が中学生のお孫さんに数学に興
味をもたせようと数学パズルの本を買ってあげたところ、自分が魔方陣に夢中にな
り、「本に出ている魔方陣の作り方はあまり論理的でない。ただ４次の魔方陣は８
８０個で、５次の場合には２７５，３０５，２２４個あるとあるが、その根拠がわ
からない。君のボケ予防のため、一緒に考えてくれ」というＥメ－ルをもらった次
第。この数字はいかにもコンピュータがはじきだした数字のようです。
魔方陣の最初の記録は、水力工学者として名声を博したという中国伝説の夏の禹
王の統治時代にまでさかのぼります。治水のカメによって人間にもたらされた、と
中国の漢王朝（Ｂ．Ｃ．２００年）の頃の「九章算術」という書物に書いてあるそ
うです。それ以来、高次の魔方陣は主として東洋で研究され、日本でも、かの関孝
和が考えていた、とのことです。そんな歴史のある魔方陣を今さらという感じもし
ますが、先輩のいうボケ防止のため、私も考えることにしました。そしたら実は私
もはまったのです。
先ず、ｎ次の方陣の一列（行）の和を求めます。
ｎ2個の自然数の和は１からｎ２までの自然数の数列の和がｎ2（１＋ｎ２）／２で
あることからこれをnで割り、n（1+n2）／2であることがわかります。つまり、３
次の場合は１５、４次の場合は３４、５次の場合は６５です。
そこで今４次（ｎ＝４）の場合を以下の順序で考え、方陣をつぎのようにあらわ
すことにします。
ａ11 ａ12 ａ13 ａ14
ａ21 ａ22 ａ23 ａ24
ａ31 ａ32 ａ33 ａ34
ａ41 ａ42 ａ43 ａ44
（１） １から１６までの自然数のうち、４個を選び出す選び方は順列１６Ｐ４＝
４３６８０通りある。
（２） ｘ＋ｙ＋ｚ＋ｕ＝３４
の不定方程式にｘ，ｙ，ｚ，ｕは１から１６までの自然数である、という条件を入
れて解
く。これは紙と鉛筆ではとても無理で、コンピュ－タの力を借りなくては出来ない
。それでも、まだかなり大きな数の４個の数の組合せになるだろうが、４３６８０
通りよりは大分しぼられるはずである。
（３） （２）の組合せのなかから要素、ａ11が共通になることを条件にした不定
方程式を解く。１から１６の場合の数がある。
（４） （３）の場合の数からａ44が共通になることを条件にした不定方程式を解
く。１から１５の場合の数がある。
同様の操作を他の２つの角の要素、ａ14、ａ41についても漸化する。
（５） つぎに眞中の小行列
ａ22 ａ23
ａ22 ａ23
の要素について考える。これらの要素はもとの２つの対角線の両端、ａ11�ａ14、
ａ41、ａ44の場合の数が決っており、対角線の和が３4であることを条件にした不
定方程式になる。これを解けばかなり絞られることになる。
（６）４つの周辺の眞中の要素についても同じことがいえる。
このように、その都度、不定方程式の条件を厳しくして、繰り返すことにより、
４次の魔方陣は解けることになります。８８０通りの場合の数が検証出来るばかり
でなく、間違っていなければ、そのものずばりの８８０個が得られるはずです。
しかし、数え上げ方式で、いかにもダサイ。コンピュータ頼みの、アタマの悪さ
をさらけ出した方法です。
コンピュータのアルゴリズムを前提に、もっとエレガントな方法がありましたら
教えてください。
プログラミング：
私はＢＡＳＩＣが搭載されている古い９８を今でも愛用しています。それを何年
かぶりにＢＡＳＩＣモードにして、３次の場合の簡単なプログラムを作りました。
ところが、最初の不定方程式がうまく処理できません。宣言文に原因がありそうな
ので、一から勉強しなおさないとダメみたいです。あーあ！
こんな調子ではとても４次のプログラミングなど、おぼつかないでしょう。イン
ターネットのＴｅｌｎｅｔでＵｎｉｘ環境のコンピュータに接続できる、というの
に・・・。
ーーー君い、そんなことをやって何か役に立つの？
ーーー何の役にも立ちゃーしません。もともとパズルですから。先輩の心ずかいに
は悪いけれど、ボケ予防もあやしいものです。
ーーーでは、もの好きだな。
ーーーまあそうです。ほら漫才にあったでしょう。「地下鉄の車両をどうやって地
下に入れるかを考えてたら、眠れなくなった」という・・・。
ーーーうん、あった、あった。
ーーーそれなんですよ。私も魔方陣を考え出したら眠れなくなっちゃって、睡眠不
足でかえってボケそう。
ーーー厄介だな。
ーーーでも、私も好きですから、先輩を恨むなんて、とんでもない。
という次第で、魔方陣の考え方をもっとすっきりさせるヒントがありましたら教
えてください。また、プログラミングについてもアドバイスがありましたらお願い
いたします。私のボケ防止のためにも。・・・
参考：「数学歴史パズル」 藤村幸三郎 田村三郎 講談社ブルーバックス
［註］本文では数式のベキやサフィックス等の添字がうまく表現できません。ご
判読をお願いします。
--
Shigeaki Iwamura
http://pweb.aix.or.jp/~shigea-i/
shig...@aix.or.jp
STJ3...@pcvan.or.jp
Hiroshi OHKAWA
大川です。魔法陣について詳しくはないですが。
Mr. Shigeaki Iwamuraさん：
>「魔方陣」をよろしく
（大幅に省略）
> 先ず、ｎ次の方陣の一列（行）の和を求めます。
>ｎ2個の自然数の和は１からｎ２までの自然数の数列の和がｎ2（１＋ｎ２）／２で
「n2」は「n^2」と書いたほうがわかりやすいです。一瞬何事かと思ってしまった。
> ａ11 ａ12 ａ13 ａ14
> ａ21 ａ22 ａ23 ａ24
> ａ31 ａ32 ａ33 ａ34
> ａ41 ａ42 ａ43 ａ44
このへんもたとえば「a_{12}」とか書いたらいいかなとか思うのですが。
>（１） １から１６までの自然数のうち、４個を選び出す選び方は順列１６Ｐ４＝
>４３６８０通りある。
TeX風に「{}_{16}P_4」とか。これはわかりにくいな。やめとこう。
> ［註］本文では数式のベキやサフィックス等の添字がうまく表現できません。ご
>判読をお願いします。
べき乗や添え字は今回フォローしたようにするのがわかりやすいと思います。
＃MS-INなんかを使ってるとHTMLで書くとかっていう裏技もありそうですが。
役にたたないフォローでしたが。では。
--
名古屋大学ミステリ研究会「自称」会長 大川 博
ta...@mars.dtinet.or.jp
f940...@eds.ecip.nagoya-u.ac.jp
Mr. Shigeaki Iwamura
岩村です。
In article <199701061...@mars.dtinet.or.jp>,
ta...@mars.dtinet.or.jp (Hiroshi OHKAWA) wrote:
> 大川です。魔法陣について詳しくはないですが。
>
>とありますが、関心をもってくださったことは事実、数式の記述に対するご忠告
ありがとうございます。
ところで、私は使ったことがないので、お尋ねしますが、あのような不定方程式を
解くのに”Mathematica"に限りませんが、市販の数学ソフトが使えるものなのでし
ょうか？
もし、数学ソフト使用の経験がありましたら教えてください。
LAING Haisheng
梁 海声と申します．
「魔方陣」を少し説明します．
> 魔方陣の最初の記録は、水力工学者として名声を博したという中国伝説の夏の禹
> 王の統治時代にまでさかのぼります。治水のカメによって人間にもたらされた、と
> 中国の漢王朝（Ｂ．Ｃ．２００年）の頃の「九章算術」という書物に書いてあるそ
［易経］の”洛書”が最初の記録です．亀が川に浮かべ，背には，方陣が書かれた．
"方陣"に関して，研究結果を以下に載せた：
http://free.websight.com/CHANGE/
http://free.websight.com/HappyBirthday/
4 2 9
8 6 1
3 7 5
上下左右にを繰り返すと
4 2 9 4 2 9 4 2 9
8 6 1 8 6 1 8 6 1
3 7 5 3 7 5 3 7 5
4 2 9 4 2 9 4 2 9
8 6 1 8 6 1 8 6 1 (C) 1996 LIANG
3 7 5 3 7 5 3 7 5
4 2 9 4 2 9 4 2 9
8 6 1 8 6 1 8 6 1
3 7 5 3 7 5 3 7 5
となり，左上がりに
1 2 3
4 5 6
7 8 9
の配列ができる．十字と斜め十字の和が１５である．
以下は，方陣により，小生の誕生日をデザインした模様である．
勿論，誕生日以外に，電話番号もデザインできる．
自作ｇａｍｅソフトを用意しておる．必要な方がご連絡して下さい！
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
¥ / | ¥ / | ¥ / | ¥ / | ¥ / |
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
/ | / | / | / | / |
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
| | | | |
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
¥ / | ¥ / | ¥ / | ¥ / | ¥ / |
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
/ | / | / | / | / |
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
| | | | |
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
¥ / | ¥ / | ¥ / | ¥ / | ¥ / |
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
/ | / | / | / | / |
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
| | | | |
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
¥ / | ¥ / | ¥ / | ¥ / | ¥ / |
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
/ | / | / | / | / |
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
| | | | |
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
¥ / | ¥ / | ¥ / | ¥ / | ¥ / |
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
/ | / | / | / | / |
6 4 5 6 4 5 6 4 5 6 4 5 6 4 5
| | | | |
9 7 8 9 7 8 9 7 8 9 7 8 9 7 8
¥ / | ¥ / | ¥ / | ¥ / | ¥ / |
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
(C) 1993 LIANG
"." for double numbers.
"o" for zero.
N.IRIYAMA
入山です
４方陣についての総数算出について
思い付いた方法（単なるしらみつぶし）を述べます．
内容はともあれ，プログラミングが容易で実施可能と思います．
４方陣については，１列の和以外に，下記の同記号の部分の総和も３４に
等しいことが知られています．これは１列の項の和が等しい事から得られる
１０本（各行・各列・各対角線の和＝３４）の連立方程式から算出されます．
A B B A
C D D C
C D D C
A B B A
対称性を考慮すれば 隅,辺,中央の３通りいずれかに１が配置されます．
下図のように，あと残り6個(a-f)を選択すれば，残りは自動的に算出されます．
（６個でなく５個で十分なのかも知れませんが..??どなたか考えてみて下さい）
1 a b ? 1 a b (34-a-b-1)
? c d e ==> (34-c-d-e) c d e
? ? f ? 略 (34-c-d-f) f 略
? ? ? ? 略 略 (34-b-d-f) (34-f-c-1)
そこで，算出された結果が１から１６まで，すべて重複なく得られたか
チェックすれば良いということになります．
a-fの６種類について15*14*13*12*11*10＝3,603,600回の試行となります．
各1msecを要したとして約１時間かかります．
１の配置について３通りですから，約３時間でできますね(^O^)！？
東北大学鈴木先生の魔方陣データベース
http://www.pse.che.tohoku.ac.jp/~msuzuki/magicsquare-j.html
を自分で見つけておきながら，中身をまだよく読んでないので
申し訳ないのですが，多分もっと洗練された解法があると思います．
＃ぜひ鈴木先生のフォローが欲しいです．
--
N.Ir...@konica.co.jp
N.IRIYAMA
入山と申します． 私も,はまった者です．
小学時代：４方陣から始まって（この頃から２進数に親しんでいた！？）
中学時代：４の（準）立方陣を作成．（完全な４立方陣は不可能）
高校時代：８立方陣をプログラム電卓の助けを借りて作成．
（思えばこれが，やくざな世界(COMPUTER)に，はまったきっかけ）
大学時代：ｂｉｔに投稿．
といった具合です．
参考文献が極端に少ない状況下，かえって自力で，
作り方を発見していけた点は良かったと思います．
４方陣については，２進数との関連から当時のｂｉｔのナノピコ教室に
出題，解答記事を載せておりますので下記バックナンバーを参照してください．
（ｂｉｔ：1984年９月号（解答編：当然6月号の出題内容が示されています））
同年10月号（立方陣の一部誤記訂正））
他にｂｉｔナノピコ教室をまとめた本も共立出版からでています（初巻に掲載）．
また，検索エンジンで探したところ，魔方陣に造詣の深い先生が東北大学に
いらっしゃいました． （"魔法陣"で探してはいけません..^^;;;;.guruguru）
詳細はこちら↓（魔方陣データベース）
http://www.pse.che.tohoku.ac.jp/~msuzuki/magicsquare-j.html
私がbitに投稿した内容は，２進数の補助方陣として
0,0,1,1 1,0,1,0 1,1,0,0 1,1,0,0 1,0,1,0
1,1,0,0 0,1,0,1 0,0,1,1 1,0,1,0 0,0,1,1
0,0,1,1 0,1,0,1 0,0,1,1 0,1,0,1 1,1,0,0
1,1,0,0 1,0,1,0 1,1,0,0 0,0,1,1 0,1,0,1
といったパターンを４種類組み合わせ，それらを２進数４桁の各位に割り当て，
0000～1111 (0～15)からできる魔方陣(＋１で通常の１～１６までの魔方陣）を
得る組み合わせを求めるというもので，
上記５種類のパターンとその回転形,反転形から作れる５２４通りの組合わせを
N88BASICで，悉く作成した結果をファイルに納めるといった回答もありました．
他に７通りの２進補助方陣パターンを組み合わせれば，８８０通りすべてを
作成することができることや，同様のパターンの立体的組合わせで８立方陣が
作成できるといったことを述べています．
以上，Ｎ方陣の総数算出方法については不案内ですが御参考まで．
--
N.Ir...@konica.co.jp
Hironobu Suzuki
>>>>> "%" == Shigeaki Iwamura <shig...@aix.or.jp> writes:
In article <shigea-i-050...@ppp235067.aix.or.jp> shig...@aix.or.jp (Mr. Shigeaki Iwamura) writes:
%> 洋で研究され、日本でも、かの関孝和が考えていた、とのことです。そん
%> な歴史のある魔方陣を今さらという感じもしますが、
ご存知かと存じますが、魔法陣に関しては、関孝和よりも、同世代の久留島義
太という和算家が、すごいです。フェルマーよりも良いものを作っています。
マイナーな情報ですいません。
ひろのぶ
N.IRIYAMA
入山です．
東北大学の鈴木睦先生に問い合わせたところ，下記メールをいただきました．
許可を受け，ここに掲載いたします．
先生は，”ネットワーク活動もいろいろ有りすぎて、身を慎んでいるもので”
ということで，fjにはアクセスされてないそうです．
下記内容，最後のパラグラフは，先行するメールにでてきた話題で，先生は
７次の不規則型の完全方陣の探索を考えているとのことです．
何か情報ありましたら次行のアドレスへメールしてください．
1997/01/08 Mutsumi Suzuki<msu...@eleph.pse.che.tohoku.ac.jp>さんは書きました：
｜私が使った代数的方法とは以下のようなものです。簡単のために 3x3 を
｜例にして説明します。
｜
｜ a b c
｜ d e f
｜ g h i
｜
｜において、
｜ a+b+c = 15 ---> c = 15-a-b
｜ d+e+f = 15 ---> f = 15-d-e
｜ c+f+i = 15 ---> i = 15-c-f = 15-(15-a-b)-(15-c-f)
｜ = -15+a+b+c+d
｜ a+d+g = 15 ---> g = 15-a-d
｜ b+e+h = 15 ---> h = 15-b-e
｜
｜ g+h+i = 15 ---> same result ; i = -15+a+b+d+e
｜
｜ a+e+i = 15 ---> 2a+b+d+2e = 30 ---> 2a+b+d = 30 -2e
｜ c+e+g = 15 ---> (15-a-b)+e+(15-a-d) = 15
｜ ---> e = -15 + 2a+b+d = -15+(30-2e)
｜ ---> e = 5,
｜ ---> 2a+b+d=20 ---> d = 20-2a-b
｜
｜となって、最終的に適当な２変数を独立変数に選べば（例えばa,b）
｜ c = 15-a-b
｜ d = 20-2a-b
｜ e = 5
｜ f = -10+2a+b
｜ g = -5+a+b
｜ h = 10-b
｜ i = 10-a
｜を得ます。
｜ただし、この解法には整数の条件や互いに重複しない条件が入って
｜いませんから a,b が不適当だと通常の（1-9の整数）魔方陣にはな
｜りません。そこで a と b を種々（システマティックに）変更して
｜条件に合う場合を探索すればよいことになります。
｜
｜ for a := 1 to 9 do for b := 2 to 9 do ....
｜
｜と繰り返すのです。
｜
｜類似の操作を 5x5 の完全方陣で行なうと独立変数が 8こ必要になり
｜ます。それをじょうずに選ぶと繰り返しの回数を倹約できて10年前の
｜旧式パソコン（自宅用）でも１０分程度で144の基本型完全方陣をす
｜べてチェックすることができました。
｜お尋ねの 4x4 の単純な方陣なら独立変数が７こになります。
｜
｜同じプログラムを大学で動かしたら3秒でした。そろそろ買い換えの
｜時期と思いつつ、先立つ物の手配に手間取っていて、、、
｜
｜大正年代に寺村周太郎氏が半年かかって 4x4 の網羅計算を手計算で
｜やったことを思うと計算機の有り難みがわかります。
｜
｜最初は正月の酒を醒す目的で手計算で代数方程式を解きました。
｜次に、昔の muMATH を引っ張り出して解いてみました。
｜最後に、研究室のWSと mathematica を利用して解いてみました。
｜さすが mathematica の威力はすごいもので 7x7 の代数方程式も実に
｜やすやすと解いてくれます。あとはこの結果を探索プログラムに書き
｜込んで計算すればよいのですが、独立変数が多すぎて、多分計算時間
｜がかかりすぎることでしょう。どれを独立変数に選ぶべきか、計算時
｜間短縮の工夫などを凝らしている段階です。
｜ 以上
｜
Akira Hatakeyama
畠山＠ＳＲＡと申します。
From article <shigea-i-050...@ppp235067.aix.or.jp>
by shig...@aix.or.jp
> 実はこんなことを考えさせられたのは、ある先輩が中学生のお孫さんに数学に興
> 味をもたせようと数学パズルの本を買ってあげたところ、自分が魔方陣に夢中にな
> り、「本に出ている魔方陣の作り方はあまり論理的でない。ただ４次の魔方陣は８
> ８０個で、５次の場合には２７５，３０５，２２４個あるとあるが、その根拠がわ
> からない。君のボケ予防のため、一緒に考えてくれ」というＥメ－ルをもらった次
> 第。この数字はいかにもコンピュータがはじきだした数字のようです。
昔、わたしもはまりました。丁度、そのころ「魔方陣」という本が
出ていまして、解法が載っていました。実家に置いたままで、出版社、
著者等が不明ですが、表紙にデューラーのメランコリアの絵（魔方陣
が背景になっています）が使われていました。
> コンピュータのアルゴリズムを前提に、もっとエレガントな方法がありましたら
> 教えてください。
このあたりはうろ覚えなのですが、ｎ次の魔方陣は、２桁のｎ進数が
配置されたものとして考え、上位／下位の各桁毎に０．．（ｎ－１）の
数による（直交する？）方陣を二つ作り、それらを合成すると目的の
魔方陣になる、といった方法だったと思います。たとえば、３次の
魔方陣ですと
１ ２ ０ ０ ２ １
０ １ ２ と ２ １ ０
２ ０ １ １ ０ ２
の二つのマトリクスから
１０ ２２ ０１ ３ ８ １ ４ ９ ２
０２ １１ ２０ －＞ ２ ４ ６ ＋１ ３ ５ ７
２１ ００ １２ ７ ０ ５ ８ １ ６
という魔方陣が生成されるわけです。
なんでも、このような計算は実験計画法で使うそうなので、前出の
「魔方陣」の本が入手できなくても、実験計画法の参考書でも読めば、
関連した情報が入手できるのではないかと思います。
PS. 他に情報が入らないようでしたら、「魔方陣」の本の
出版元、著者等も調べますので、連絡ください。
---
Akira Hatakeyama E-Mail: ak...@sra.co.jp
tsuzuki, yokohama, japan
N.IRIYAMA
I入山です．
昨日にひきつづき鈴木様よりメールが届きました．ここに掲載いたします．
３～５までの魔方陣しか総数がわかっていないという事は初めて知りました．
どなたか，６以上の魔方陣の総数算出に一番のりの手柄を立ててください．
岩村様いかかですか？
鈴木先生には，直接fjに投稿していただくようお願いして，私はそろそろ，
おいとましようと思います．
鈴木先生は魔方陣に関するメーリングリストに所属していらっしゃると思います．
興味のある方は次行のアドレスへお問い合わせ下さい．
1997/01/09 10:12:35 Mutsumi Suzuki <msu...@eleph.pse.che.tohoku.ac.jp>さんは
書きました：
｜入山様
｜偶然ですが昨日イギリス人からメイルが来て
｜
｜｜ I have calculated the number of unique 5 by 5 magic squares and got the
｜｜same result as Mr Matsumato of 275 305 224 this number was also obtained
｜｜by Rich Schroeppel in Arizona.
｜｜
｜Seamus Bellew
｜
｜とのことでした。この数は既に何度も確認されていたのですが、実行するのは
｜意外に大変です。6x6 以上はまだです。わが国から一番乗りがでると良いので
｜すが如何ですか？
｜東北大；鈴木 睦
｜
--
N.Ir...@konica.co.jp
Yokoyama Takehiro
In article <5b2487$g...@srashc.sra.co.jp>,
ak...@sra.co.jp (Akira Hatakeyama) wrote:
>昔、わたしもはまりました。丁度、そのころ「魔方陣」という本が
>出ていまして、解法が載っていました。実家に置いたままで、出版社、
>著者等が不明ですが、表紙にデューラーのメランコリアの絵（魔方陣
>が背景になっています）が使われていました。
「新編 魔方陣」大森清美著、冨山房、ISBN4-572-00696-2、3500円。
これは1992年の発行ですが、20年ほど前に、旧版を図書館で借りて
読みふけったことがあります。
新版には魔方陣をみつけるプログラム例も載っています。
--
横山岳浩
am...@po.iijnet.or.jp
http://www.iijnet.or.jp/amris/index.html
LIANG Haisheng
梁 海声です． 自己フォロ－させて頂きます．
この何日魔法陣にはまられました．超初心者ですが，以下の魔方陣を作りました．
既に有るものと思いますが，情報をご提供してくれれば幸いと存じます．
宜しくお願い致します．
１・連続魔方陣
数字自身と行、列、斜め線上の数字の和が
自然数である方陣。
13 12 14
2 4 5 11
3 1 6 10
8 7 9
２・四角和 魔方陣
方陣の中にはすべての近傍四角の四つ数字の和が
ある同じ定数になる場合、四角和 方陣と言う。
以下は小生の”発見”した ５種類 四角和 方陣です。
O が四角和の定数。 X が 対角の値である。
**************************************
O = 16, X = 17
8 5 6
16 16
1 2 3
16 16
9 4 7
*************************************
O = 18, X = 11
8 4 7
18 18
5 1 6
18 18
3 9 2
*************************************
O = 20, X = 13
6 9 2
20 20
1 4 5
20 20
7 8 3
*************************************
O = 18, X = 15
8 6 7
18 18
1 3 2
18 18
5 9 4
*************************************
O = 23, X = 17
7 4 2
23 23
3 9 8
23 23
6 5 1
LIANG Haisheng
梁 海声です． 自己フォロ－させて頂きます．
この何日魔法陣にはまられました．超初心者ですが，以下の魔方陣図形を作
りました．
既に存在されたものと思いますが，情報をご提供してくれれば幸いと存じます．
宜しくお願い致します．
魔方陣の線図形
M4 M4 M4 ...
M4 M4 M4 ...
M4 M4 M4 ...
.
.
.
****************************************
1 2 15 16
13 14 3 4
12 7 10 5
8 11 6 9
15＿ 1＿2
13__／ 16 ＼＿4
｜14 10 7 3 | UFO
12＼／＼＿／＼／5
11 9 8 6
****************************************
1 14 15 4
8 11 10 5
12 7 6 9
13 2 3 16
__
1／ ＼
__ | GLASSES
／ ＼／＼__／
| 16
＼__／
****************************************
16 13 1 4
3 2 14 15
10 11 7 6
5 8 12 9
i = 1‾8
7__6
／ ＼5
8 4／ 1 Ying-Yang
＼__／
3 2
i = 1‾8
j = 17 - i
7__6
／ ＼5
8 4／ 1
＼__／
3 2
****************************************
Yuzuru Hiraga
平賀＠図書館情報大学です。
魔方陣と似たような話なのですが。
# fj.rec.games にもふりますが、Followup-To は fj.sci.math
数独（別名ナンバープレース）というパズルをご存じなら話が早いです。
9*9 の盤面で、各マス（合計 81 個）に 1-9 の数字をいれます。
ただし、各行、各列、及び 3*3 の小正方形の各々について、
1-9 の数字が揃っていることが条件です。
別の言い方をすれば、各行、各列、各小正方形には同じ数字が
１つずつあります。
下に例を示します（見やすいように、3*3 の小正方形の区切りに罫線が
いれてあります）。
+-----------+ +-----------+
|674|913|582| |123|456|789|
|538|726|419| |768|291|354|
|192|584|763| |549|783|216|
|---+---+---| |---+---+---|
|246|839|175| |931|864|527|
|915|472|638| |457|329|168|
|387|165|924| |682|517|493|
|---+---+---| |---+---+---|
|753|698|241| |276|148|935|
|421|357|896| |395|672|841|
|869|241|357| |814|935|672|
+-----------+ +-----------+
問題は、このような数字の並べ方が何通りあるかです。
まずすぐわかるように、1-9 という数字自体には意味がなく、
互いに区別できる記号ならなんでもかまいません。
またこの数字（記号）の間に置換を行えば、最初のとは異なる並べ方が
できます（ただし回転・鏡映により同一になる場合は考えない：
もっともこれは現実には起こらないかな）。
たとえば上の右側の配置は、左側の配置に数字の置換を施して、
上１行が 123456789 と並ぶようにしたものです。
置換は 9! = 362880 通りありますから、１つの盤面からこれだけ通りの
配置が生み出せます。
以下ではこのような数字の置換により得られる配置はすべて同一視します。
（それには上のように、上１行を固定しまった場合だけを考えることに
すれば十分）。
この並べ方の総数について、何かご存じの方がいらっしゃいましたら
お教えください（すでに答はわかっている、こういう方法で調べられる等々）。
ちなみに現在のところ、総数は約 2 * 10^16 通り（つまり２京）という
見積りができています。ただしこれは部分的な数え上げの結果から外挿した
推定値ですから、正確な評価ではありません（といっても、そう大きく
狂ってもいないはず：正解はたかだかこの数倍（ないし数分の１）の
範囲にあると思う）。
ちなみに上記のように１行固定をしてしまえば、回転・鏡映により重なる
場合は生じません（問題：なぜでしょう？）。
=====
一般化すれば、N に対して一辺 N^2 の正方形に 1...N^2 の数字を、
各行・列、N*N 小正方形に各々１つずついれる問題になります。
上は N=3 の場合です。
N=2 の場合は 12 通りあります（上記のように置換を除く、またこれらは
回転・鏡映はすべて互いに異なる：上で「重なる場合は生じない」といったのは
N が奇数である特性を利用したので、N が偶数の場合どうなるかは不明）。
N=3 で、上記のように膨大な数になります。
N>3 の場合は考える気にもならない（ならなくなった）。
=====
群論などを適用する可能性も考えられますが、やはり似たような問題の
N-queens の場合にうまい数え上げの方法がないことを考えると、
おそらく難しいでしょう（変換群を少し調べてはいますが）。
しかし 10^16 というオーダーを考えると、単純な数え上げでは
絶望的です。
（平賀＠図書館情報大学）
KANOU Hiroki
狩野＠わせだと申します。
In article <E4Cq0...@ulis.ac.jp> hir...@ulis.ac.jp (Yuzuru Hiraga) writes:
>数独（別名ナンバープレース）というパズルをご存じなら話が早いです。
知っています。
> +-----------+ +-----------+
1> |674|913|582| |123|456|789|
2> |538|726|419| |768|291|354|
3> |192|584|763| |549|783|216|
> |---+---+---| |---+---+---|
4> |246|839|175| |931|864|527|
5> |915|472|638| |457|329|168|
6> |387|165|924| |682|517|493|
> |---+---+---| |---+---+---|
7> |753|698|241| |276|148|935|
8> |421|357|896| |395|672|841|
9> |869|241|357| |814|935|672|
> +-----------+ +-----------+
行に番号を振りました。
>問題は、このような数字の並べ方が何通りあるかです。
行と列にある種の置換を施しても、数独の問題としての本質は
変わりませんが、それは同一視するのでしょうか？
例えば、数独の問題図において行1,2,3を任意の順番に入れ換えて、
問題を解いて、また行1,2,3に逆の置換を施せば、元の問題を
そのまま解いたのと同じ解答図が得られます。
また、行4,5,6のグループと行7,8,9のグループを入れ換えるような
操作も任意に行なうことができます。
この置換は、グループ内3個、グループ間1個について行なうことが
でき、行列合わせて6^8 = 1679616通りの異なるパターンを生み出す
ことができます(重複が無ければ、の話ですが)。
これを同一視すれば、
>ちなみに現在のところ、総数は約 2 * 10^16 通り（つまり２京）という
>見積りができています。ただしこれは部分的な数え上げの結果から外挿した
>推定値ですから、正確な評価ではありません（といっても、そう大きく
>狂ってもいないはず：正解はたかだかこの数倍（ないし数分の１）の
>範囲にあると思う）。
10^10 のオーダーに入り、検索可能な範囲に入ると思います。
>ちなみに上記のように１行固定をしてしまえば、回転・鏡映により重なる
>場合は生じません（問題：なぜでしょう？）。
1行目を固定すれば、列に関する置換は同一視したことになります。
行に関しては、2,3行目と、4,5,6 行目と、7,8,9 行目をそれぞれ
左端(1列目)の数字でソートし、4,7行目も大小関係が成り立つように
すれば、検索量が節約できるはずです。
このようにすれば、「本質的に異なる解答図の種類」は求められますが、
各解答図に(6^8 * 9! * 8)通りの変換を施して得られた物の中には、
重複するものが大量にあるでしょうから、「最終的に求めたい物」が
別物だと、このような節約は無意味かも知れません。
私の場合、「最終的に求めたい物」が「数独の問題を成立させる(すなわち、
解答図が1通りしか存在しない)ために、問題図に表出している必要がある
数字の最小値」なのですが、求めることを半分諦めてます。
#18個で問題を作れることは実証されています。
--
狩野 宏樹 g92k...@mn.waseda.ac.jp
(cfi.waseda.ac.jpのaccountは3月迄)
Yuzuru Hiraga
平賀＠図書館情報大学です。
狩野さん、ありがとうございます。
In article <G92K0323.97...@wise22.mn.waseda.ac.jp> g92k...@mn.waseda.ac.jp (KANOU Hiroki) writes:
>狩野＠わせだと申します。
...
>In article <E4Cq0...@ulis.ac.jp> hir...@ulis.ac.jp (Yuzuru Hiraga) writes:
>>数独（別名ナンバープレース）というパズルをご存じなら話が早いです。
...
>行と列にある種の置換を施しても、数独の問題としての本質は
>変わりませんが、それは同一視するのでしょうか？
前に記事においては、同一視していませんでした。
この点については後述。
>例えば、数独の問題図において行1,2,3を任意の順番に入れ換えて、
>問題を解いて、また行1,2,3に逆の置換を施せば、元の問題を
>そのまま解いたのと同じ解答図が得られます。
>
>また、行4,5,6のグループと行7,8,9のグループを入れ換えるような
>操作も任意に行なうことができます。
はい、それは承知しています。
「変換群云々」といったのは、そういったことを含んでいます。
>この置換は、グループ内3個、グループ間1個について行なうことが
>でき、行列合わせて6^8 = 1679616通りの異なるパターンを生み出す
>ことができます(重複が無ければ、の話ですが)。
N=2（つまり 4*4 の盤面）で調べたところでは、かなりの重複が生じます。
またおっしゃるような行・列交換で何がカバーできるか（逆に何ができないか）、
さらにどういう変換が可能かもある程度調べてあります。
N=3 ではもっと事情が悪化するでしょう。
>これを同一視すれば、
>
>>ちなみに現在のところ、総数は約 2 * 10^16 通り（つまり２京）という
>>見積りができています。...
>
>10^10 のオーダーに入り、検索可能な範囲に入ると思います。
2 * 10^16 という見積りは、9! = 362880 通りの数字間の置換を同一視
した場合の話です（これは操作的には、既述のように上１行固定、一般には
ある１行・列ないし 3*3 の小正方形を固定することで実現できる）。
行交換、列交換を施すとこれが崩れますから、上の計算は
2 * 10^16 * 9! / 6^8
としなければならないでしょう。
>1行目を固定すれば、列に関する置換は同一視したことになります。
ちょっとここのところはこちらに誤解があるのかもしれませんが、
１行目を固定するというのは、「列に関する置換」＝列（あるいは列グループ）
どうしの交換を同一視したことにはなりませんよ。
たとえば：
123456789
4........
...
という配置で第 4,5 列を交換しても、２行目左端の 4 はそのまま
変わらないわけですから、4<->5 という数字の置換を施すと、
別物になってしまう。
>行に関しては、2,3行目と、4,5,6 行目と、7,8,9 行目をそれぞれ
>左端(1列目)の数字でソートし、4,7行目も大小関係が成り立つように
>すれば、検索量が節約できるはずです。
このように１行目にさわらない行だけの交換なら安全であり、
それが引き起こす変換群も、おっしゃるようにはっきりしています。
ただこれによる節約は、
2! * (3!)^2 * 2! = 144
ですから、まだ不十分でしょう。
（まあ、この場合は重複が生じませんから、組み合わせ総数が
144 で割り切れるということはわかるわけですが）。
一方、行・列両方の交換を交えると、上述のように、重複するケースが
生じます。また重複の仕方も、出発点とする盤面によって異なると
思われますので、事情は複雑になります。
>このようにすれば、「本質的に異なる解答図の種類」は求められますが、
>各解答図に(6^8 * 9! * 8)通りの変換を施して得られた物の中には、
>重複するものが大量にあるでしょうから、「最終的に求めたい物」が
>別物だと、このような節約は無意味かも知れません。
ちょっとここの意味がわかりません。
「このようにすれば」というのは何を指すのでしょうか？
6^8 は行・列交換、9! は数字の置換、8 は回転・鏡映変換のことと思いますが、
少なくとも上の記述では行交換は部分的に組み込まれていても、
列交換は組み込まれていませんが。
それに「本質的に異なる」というのが well-defined ではありません。
１つには、おっしゃるように重複を除去する必要があります。
しかしそれより、これはあくまで「数字の置換は同一視して」とか
「行・列交換は同一視して」という限定がついての話でしかありえず、
そういった限定をはずして何が「本質的に異なる」かは問題です。
極端な話、出発点となる盤面からすべての盤面を生成しうる変換群が
特定できてしまえば、「本質的に異なる」盤面は１つしかないことに
なってしまいます。
前の記事で「数字による置換（だけ）を同一視」としたのは、それが安全、
かつわかりやすく、はっきりした限定になっているからです。
>私の場合、「最終的に求めたい物」が「数独の問題を成立させる(すなわち、
>解答図が1通りしか存在しない)ために、問題図に表出している必要がある
>数字の最小値」なのですが、求めることを半分諦めてます。
>#18個で問題を作れることは実証されています。
ここで中心的な問題となるのは、
: :
... a ... b ...
: :
... b ... a ...
: :
のような配置があって、この a,b を交換して（他は変えない）：
: :
... b ... a ...
: :
... a ... b ...
: :
としても正しい盤面になっているような場合です。
（なお、「どんな盤面でも」上のような a,b は必ず存在します（はず：
N=3 ではちゃんと確かめてありませんが、N=2 では成り立つ。
たぶん、簡単な組み合わせ論と「鳩の巣原理」で示せるはず。））。
解の一意性を保証するにはこの両義性をつぶす必要がありますから、
aabb の 1 つは問題図に書かなければなりません。
上は単に２つの数字の場合の話ですが、玉突式にもっと大規模に、
上のような両義性が生じる場合もあるはずです。
おそらくこの現象の現れ方は盤面によって違うでしょうから、
「必要な数字の最小値」も盤面によって異なるはずです。
もちろん求めたいのは、「各盤面での最小値」の、そのまたすべての
盤面にわたる最小値でしょうが。
（平賀＠図書館情報大学）
KANOU Hiroki
>In article <G92K0323.97...@wise22.mn.waseda.ac.jp> g92k...@mn.waseda.ac.jp (KANOU Hiroki) writes:
>>行と列にある種の置換を施しても、数独の問題としての本質は
>>変わりませんが、それは同一視するのでしょうか？
>
>前に記事においては、同一視していませんでした。
ご説明を聞いて、理由が分かりました。
>>10^10 のオーダーに入り、検索可能な範囲に入ると思います。
>
>2 * 10^16 という見積りは、9! = 362880 通りの数字間の置換を同一視
>した場合の話です（これは操作的には、既述のように上１行固定、一般には
>ある１行・列ないし 3*3 の小正方形を固定することで実現できる）。
>行交換、列交換を施すとこれが崩れますから、上の計算は
> 2 * 10^16 * 9! / 6^8
>としなければならないでしょう。
それだと、ほとんど検索量は変わりませんね。数字の入れ換えと
違って、「上1行固定」のような、組合せ生成前に設定できる簡単な
正規化条件が無さそうなので、実際にプログラムを組むのは難しい
と思います。
>>1行目を固定すれば、列に関する置換は同一視したことになります。
>
>ちょっとここのところはこちらに誤解があるのかもしれませんが、
>１行目を固定するというのは、「列に関する置換」＝列（あるいは列グループ）
>どうしの交換を同一視したことにはなりませんよ。
この点は、まったく勘違いしていました。
>それに「本質的に異なる」というのが well-defined ではありません。
問題を作る立場から見れば自明だと思って安易に使ってしまいました。
>しかしそれより、これはあくまで「数字の置換は同一視して」とか
>「行・列交換は同一視して」という限定がついての話でしかありえず、
>そういった限定をはずして何が「本質的に異なる」かは問題です。
「本質的に異なる」は、「問題図に変換を適用した時にも、問題の
可解性が損なわれず、問題を解いた後に逆変換を適用すれば元の問題図
の解答図が得られることが保証される」という変換を指しています。
このように定義した時、
回転・鏡像変換、
数字の置換、
行・列のブロック内での置換、
ブロック単位での行・列の置換
以外に、上記の条件を満たす変換は存在しそうにありません。
（存在しないことを証明するのは困難ですが）
検索の方法を、もう一度最初から考えてみることにします。
最後に、いくつかの言葉の定義と、私が興味を持っている問題をいくつか
挙げておきます。
解答図
9x9の行列で、各マスが1～9の自然数値を取り、
各行・各列・各ブロック(3x3の小行列)の値がすべて異なるもの
部分図
解答図から、1個以上のマスを0に置き換えたもの
生成する
解答図から部分図を作ること
途中図
部分図のうち、その部分図を生成できるような解答図が
1個しか存在しないもの
表出する
マスの値が0以外であること
問題図
途中図のうち、図に表出している数字のどれを0に置き換えても
その結果が途中図でなくなってしまうもの
初等的に解ける
(a)あるマスに着目して、同ブロック・同行・同列にn以外の8種類の
自然数がすべて存在することから、そのマスの取る値をnに確定する。
(b)あるブロック・行・列の中に存在する値0のマスすべてのうち、
各マスの上下・同ブロック内に値nのマスが存在しないようなマスが
1個しかない場合、そのマスの取り得る値をnに確定する。
上記の操作(a)(b)を繰り返すことにより、途中図から問題図を
求めることができるような途中図を、「初等的に解ける途中図」と
言う。
(1) 問題図は何個あるか。
(2) 問題図に表出している数字の個数の最大値、最小値はいくつか。
(3) 初等的に解ける問題図は何個あるか。
(4) 初等的に解ける問題図に表出している数字の個数の最大値、最小値はいくつか。