第20講　魔方陣汎用的生成プログラムVer.3　第１話　Ver.3の核心部分＝魔方陣の種

第20講　魔方陣汎用的生成プログラムVer.3＝末項確定法
第１話　末項確定法とは？

－－－以下VC++講義より引用－－－

今回はいつもと手法を変えて、
最初に、今回の成果を最初に紹介した後に、
末項確定法とは何か説明しましょう。
以下のデータは各次魔方陣を１００個作るのにかかった時間です。

１個あたり０．０１５９１２秒です。
前話のデータが０．０７２８４秒ですから、約４．６倍のスピード差です。
さらに、10次魔方陣の場合
VBA
1個あたり０．３９８８９２秒ですから、約５．６倍です。
今までソフトがバージョンアップする度に、
１万倍とか１１００万倍とかとう桁外れの性能アップを見せていたのに比べるとかなり地味に見えるかもしれませんが、
結構大きな戦果だと思います。
プログラミングの世界では、１．１倍でも大きな成果です。
（例えば、数独問題作成ソフトのスピードを１．１倍にするのに私は数日も場合によっては数週間費やしていました。
皆さんからすれば結果だけ見ているので、その苦労は見えないと思いますが、
プログラミングとは地味な研究の積み重ねなのです。
ただ、前々話で紹介したようにときには驚愕の成果を見せることもあります。）
ですから５，６倍はかなり大きな成果です。
さらに、今回の改良によって１１次魔方陣も１個あたり約０．０５６秒でできています。
前話のときは途中で実験を打ち切ってしまったので、単純比較はできませんが、
２０秒まで探索範囲を広げて、６０分も実験を続けましたが最適乱数系列を発見できませんでしたので、
仮に前話のソフトが２０秒であると前提しても、
２０÷０．０５６＝約３６０倍です。
－－－以上VC++講義より引用－－－

上の例は、VC++版の場合ですが、Java版でもかなりの高速化が期待できます。
ただし、VC++版では一般種法を先にやってから、末項確定法を適用しています。
一般種法をまだ適応していないJava版では、６次を１個あたり０．０１５９１２秒で作ることが出来ません。
しかし、末項確定法の後、一般種法を組み合わせます。
すると同程度の性能を実現できます。

－－－以下VC++講義より若干内容を変更して引用－－－

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99	9

末講確定法とは、水色以外のセルについては、初めから入る数字は確定していることに、
着眼した方法です。
例えば、

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99

と来たときに、青のセルに入る数字は決まっています。

`１`	`２`	`２`	`５`	`０`	`４`	`５`	`５`	`９`	`７`
`７`	`12`	`７`	`６`	`１`	`３`	`５`	`４`	`６`	`２`
`３`	`１`	`29`	`８`	`４`	`７`	`６`	`２`	`０`	`５`
`３`	`３`	`１`	`39`	`７`	`３`	`４`	`５`	`６`	`９`
`５`	`４`	`１`	`７`	`47`	`２`	`４`	`３`	`９`	`９`
`９`	`７`	`５`	`１`	`６`	`60`	`３`	`７`	`３`	`４`
`２`	`８`	`５`	`２`	`２`	`８`	`72`	`８`	`０`	`２`
`０`	`２`	`１`	`６`	`７`	`８`	`９`	`86`	`８`	`１`
`３`	`８`	`５`	`０`	`８`	`９`	`０`	`８`	`93`	`０`
`７`	`６`	`９`	`６`	`９`	`１`	`１`	`０`	`０`	`６`

（表を見るときには、セルに入っている数字がセル番号のｇかそのセルに実際に入っている数字かを常に区別してください。
上表の数字は、セル番号ｇではなく、そのセルに入っている実際の数字です。
本講義においては、セル番号ｇのときは基本的にはピンクとしています。）
１＋１２＋２９＋３９＋４７＋６０＋７２＋８６＋９３＝４３９
対角線の合計は、
（１＋２＋３＋・・・＋１００）÷１０＝｛１００×（１＋１００）÷２｝÷１０＝５０５
ですから、

６

に入る数字は
５０５－４３９＝６６
と確定してしまうのです。

ですから、このセルについてはfor文で探索するのは無駄です。

６

に来たら、for文は通らないで次の世界（ｇ＋１）に進むか、
前の世界（ｇ－１）に戻るしかないのです。
戻る場合の言うのは、例えば

`１`	`２`	`２`	`５`	`０`	`４`	`５`	`５`	`９`	`７`
`７`	`10`	`７`	`６`	`１`	`３`	`５`	`４`	`６`	`２`
`３`	`１`	`19`	`８`	`４`	`７`	`６`	`２`	`０`	`５`
`３`	`３`	`１`	`28`	`７`	`３`	`４`	`５`	`６`	`９`
`５`	`４`	`１`	`７`	`31`	`２`	`４`	`３`	`９`	`９`
`９`	`７`	`５`	`１`	`６`	`38`	`３`	`７`	`３`	`４`
`２`	`８`	`５`	`２`	`２`	`８`	`52`	`８`	`０`	`２`
`０`	`２`	`１`	`６`	`７`	`８`	`９`	`66`	`８`	`１`
`３`	`８`	`５`	`０`	`８`	`９`	`０`	`８`	`72`	`０`
`７`	`６`	`９`	`６`	`９`	`１`	`１`	`０`	`０`	`６`

なら、１＋１０＋１９＋２８＋３１＋３８＋５２＋６６＋７２＝３１７ですが、
合計の４５との差をとると、５０５－３１７＝１８８

６

にはいる最大数は１００ですから、
このセルのある対角線の合計を５０５にするのは不可能になっているわけです。
この場合には1つ前のセル

72

に戻ってやり直すしかありません。

あるいは

`16`	`２`	`２`	`５`	`０`	`４`	`５`	`５`	`９`	`７`
`７`	`23`	`７`	`６`	`１`	`３`	`５`	`４`	`６`	`２`
`３`	`１`	`36`	`８`	`４`	`７`	`６`	`２`	`０`	`５`
`３`	`３`	`１`	`46`	`７`	`３`	`４`	`５`	`６`	`９`
`５`	`４`	`１`	`７`	`57`	`２`	`４`	`３`	`９`	`９`
`９`	`７`	`５`	`１`	`６`	`69`	`３`	`７`	`３`	`４`
`２`	`８`	`５`	`２`	`２`	`８`	`80`	`８`	`０`	`２`
`０`	`２`	`１`	`６`	`７`	`８`	`９`	`87`	`８`	`１`
`３`	`８`	`５`	`０`	`８`	`９`	`０`	`８`	`95`	`０`
`７`	`６`	`９`	`６`	`９`	`１`	`１`	`０`	`０`	`６`

の場合も１６＋２３＋３６＋４６＋５７＋６９＋８０＋８７＋９５＝５０９となり、

６

に入る数字が－４となってしまいこれも禁則に反します。
セルに入る数字は０から９までですから。
この場合にも

95

に戻ってやり直すしかありません。

－－－以上VC++講義より若干内容を変えて引用－－－

つまり、末項確定法とは最後の空欄は値が決まっていることに注目した方法です。
末＝最後は確定しているので、末項確定法です。
魔方陣の研究においては、残確定法と名付けていましたが、
VC++講義から名称を変更しています。
さて、皆さんVer.2のコードを改良しましょう。

第２０講第８話へ　第２話へ



VB講義へ
 ＶＢ講義基礎へ
 vc++講義へ第1部へ
 初心者のための世界で一番わかりやすいVisual C++入門基礎講座
 初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語入門 C++ 入門基礎から応用まで第１部
 初心者のための VC++による C言語入門 C++ 入門基礎から応用まで第２部
 初心者のための VC++による C言語入門 C++ 入門基礎から応用まで第３部

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99	9

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99	9

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99	9

ｙ
↓	0	1	2	3	4	5	6	7	8	9	←	ｘ
0	0	20	21	22	23	24	25	26	27	10
1	28	1	36	37	38	39	40	41	11	42
2	29	43	2	50	51	52	53	12	54	55
3	30	44	56	3	62	63	13	64	65	66
4	31	45	57	67	4	14	72	73	74	75
5	32	46	58	68	15	5	80	81	82	83
6	33	47	59	16	76	84	6	88	89	90
7	34	48	17	69	77	85	91	7	94	95
8	35	18	60	70	78	86	92	96	8	98
9	19	49	61	71	79	87	93	97	99