LoginSignup
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@TETSURO1999

今さら森博嗣「笑わない数学者」のビリヤードの問題を解く(11)～40年越しの回答

Last updated at Posted at 2024-03-31

0. はじめに

前回の記事では約40年前の BASIC プログラムを紹介した。下林山氏の作成した魔円陣プログラムは探索範囲が狭く，計算量を抑えた非常に優れたアルゴリズムである。しかし，現代の感覚で細かく見てみると，新たな数を配置するたびに加算チェック用の配列を全クリアして計算し直す点が非効率的である。ココを改善すれば，おそらく一桁近く速くなると考えられる。

もう一つの課題として，左右対称解を排除し切れていないことが挙げられる。

1. インクリメンタルチェック

魔円陣の個数 $n$ とし，$k$ 番目（$1 \le k \le n$）の数値 $a_k$ とする。表されていない最小数を $a_k$ に置くとき，新たに作られる数のみを列挙したい。

1.1 空きスペースが一つ以上残っている場合

表されていない最小数を $a_k$ に置いた後も空きスペースがまだ一つ以上残っている場合を考える。このとき $a_k$ を含み，空きスペースを含まない連続する最大集合を

a_{k - L},\ \cdots,\ a_{k - 3},\ a_{k - 2},\ a_{k - 1},\ a_k,\ a_{k + 1},\ a_{k + 2},\ a_{k + 3},\ \cdots,\ a_{k + R}

とおく。$L + R + 1 < n$ とする。なお $a_k$ の添え字 $k$ は $1 \le k \le n$ の範囲に正規化される，すなわち $n$ を超える場合は $n$ を差し引き，$1$ を下回る場合は $n$ を加算するものとする。このとき $a_k$ を含み，連続する部分集合は $(R + 1)(L + 1)$ 通りある。以下のように表形式で整理すると分かりやすい。

1.2 空きスペースがない場合

すなわち魔円陣の最後の数値を埋める場合である。$a_k$ を含み，連続する部分集合の組み合わせの数は $n(n - 1) / 2$ 通りになる。なお，厳密には下記の表に加えて，全ての数の総和からなる組み合わせが一つ追加されて $n(n - 1) / 2 + 1$ 通りになるが，総和のチェックは不要であるため省略した。

全ての数の総和チェックが不要な証明
たとえば五個のボールのビリヤード問題で考えよう。隣り合う一個から四個のボールの数の和で１～２０までの数を作ることができた場合，五個のボールの数の総和は必ず２１になることを証明する。

まず１のボールは必ず存在する。１のボールを除く四個のボールの数の和は２０になることを示せばよい。

１のボールを除く四個のボールの数の和が２０未満だと仮定しよう。この場合，１のボールを除く四個のボールのうち三個以内のボールの組み合わせで作る数は最大でも１８未満になり，これと１のボールを組み合わせても１９未満にしかならない。つまり２０の数を作れない。これは２０までの数を作れたという前提条件に反する。

よって五個のボールの数の総和は必ず２１になり，チェック不要である。

2. 左右対称解

前回の記事より，重複しない真の解の個数とmaenjin の結果を比較すると，maenjin の結果が過剰，すなわち重複する左右対称解を出力しているのは魔円陣の個数 $n$ が偶数のときのみであることに気づく。

表１　解の個数
n 真の解の個数 maenjin の結果
3 1 1
4 2 3
5 1 1
6 5 7
7 0 0
8 6 7
9 4 4
10 6 6
11 0 0
12 18 18
13 0 0
14 20 21
15 0 0
16 0 0
17 6 6

$n$ が奇数の場合，２の数は二番目から $(n + 1) / 2$ 番目まで移動させればすべての解を網羅でき，かつ左右対称解の重複を避けることができる。

一方，$n$ が偶数の場合，すべての解を網羅するためには２の数を二番目から $n / 2 + 1$ 番目まで移動させる必要がある。２の数がちょうど $n / 2 + 1$ 番目の位置，すなわち先頭にある１の数から見て左回りにも右回りも等距離にある場合が問題で，１と２の数が離れているので３の数が必要となり，左右対称解を避けるためには３の数の位置を二番目から２の数の位置の手前までに制限する必要がある。

前回の記事における魔円陣プログラムはこの制限を行っていなかったため，魔円陣の個数 $n$ が偶数のとき，かつ２の数値の位置がちょうど $n / 2 + 1$ 番目の位置にあるとき，左右対称の重複解を生み出していたのだ。なお，この欠陥には下林山氏本人も気づいており，文献[2]の中で上記の改良点を挙げている。

3. その他細かな改善点

些細な改善ではあるが，加算チェックのエラー判別に等号を追加した。

変更前
IF T > H ORELSE B(T) THEN GOTO SKIP
変更後
IF T >= H ORELSE B(T) THEN GOTO SKIP

非表示の最小数 S を検索する処理を少しだけ効率化した。

変更前
FOR S = 2 TO H
	IF NOT B(S) THEN EXIT FOR
NEXT
変更後
FOR S = M + 1 TO H
	IF NOT B(S) THEN EXIT FOR
NEXT

4. 実際のプログラム

実際のプログラムを以下に示す。

MAENJIN2.VB（魔円陣プログラムⅡ）
OPTION STRICT ON
'*******************************************************************
' 魔円陣プログラム
'
' ORIGINAL PROGRAM by M.S     1985/12/20
' PORTED TO VB.NET by TETSURO 2024/03/11
' IMPROVED VERSION by TETSURO 2024/03/19
'*******************************************************************
MODULE MAENJIN
	DIM	A()	AS INTEGER		' 魔円陣を作る配列
	DIM	B() AS BOOLEAN		' 表される数をチェックする配列
	DIM	N	AS INTEGER		' 魔円陣の個数
	DIM	H	AS INTEGER		' 表される最大数
	'***************************************************************
	' メイン関数
	'***************************************************************
	SUB MAIN(ARGS() AS STRING)
		DIM	K	AS INTEGER
		'***********************************************************
		' 準備
		'***********************************************************
		IF ARGS.LENGTH <> 0 THEN
			N = CINT(ARGS(0))
		ELSE
			CONSOLE.WRITE("何個の魔円陣ですか? ")
			N = CINT(CONSOLE.READLINE)
		END IF
		H = N * (N - 1) + 1
		REDIM A(N)
		REDIM B(H)
		'***********************************************************
		' １の数は先頭に固定する
		' ２の数は二番目から中央まで移動する
		'***********************************************************
		A(1) = 1: B(1) = TRUE
		RCHECK(2, (N + 1) >> 1)
		'***********************************************************
		' 魔円陣の個数 N が偶数かつ２の数の位置が中央のとき
		' ３の数は二番目から２の数の手前まで移動する
		'***********************************************************
		IF (N And 1) = 0 Then
			K = 1 + (N >> 1)
			A(K) = 2: B(2) = TRUE
			RCHECK(3, K - 1)
		END IF
		CONSOLE.WRITELINE("END")
	END SUB
	'***************************************************************
	' 再帰チェック関数，非表示の最小数 M，移動範囲の上限 E とする
	'***************************************************************
	SUB RCHECK(M AS INTEGER, E AS INTEGER)
		DIM	K, S	AS INTEGER
		FOR K = 2 TO E
			IF A(K) <> 0 THEN CONTINUE FOR
			A(K) = M
			IF ICHECK(K) THEN
				FOR S = M + 1 TO H
					IF NOT B(S) THEN EXIT FOR
				NEXT
				IF S >= H THEN
					OUTPUT
				ELSE
					RCHECK(S, N)
				END IF
				ICLEAR(K)
			END IF
			A(K) = 0
		NEXT
	END SUB
	'***************************************************************
	' インクリメンタル加算チェック，非表示の最小数の位置 K とする
	'***************************************************************
	FUNCTION ICHECK(K AS INTEGER) AS BOOLEAN
		DIM	I, J, L, R, T, U	AS INTEGER
		R = K: T = 0
		FOR J = 2 TO N
			IF A(R) = 0 THEN EXIT FOR
			T += A(R)
			IF T >= H ORELSE B(T) THEN GOTO SKIP
			B(T) = TRUE
			L = K - 1: U = T
			FOR I = J + 1 TO N
				IF A(L) = 0 THEN EXIT FOR
				U += A(L)
				IF U >= H ORELSE B(U) THEN
					DO WHILE TRUE
						U -= A(L): B(U) = FALSE
						IF U = T THEN EXIT DO
						L += 1: IF L > N THEN L = 1
					LOOP
					GOTO SKIP
				END IF
				B(U) = TRUE
				L -= 1: IF L = 0 THEN L = N
			NEXT
			R += 1: IF R > N THEN R = 1
		NEXT
		RETURN TRUE
SKIP:
		DO WHILE J > 2
			J -= 1
			T -= A(R): B(T) = FALSE
			L = K - 1: U = T
			FOR I = J + 1 TO N
				IF A(L) = 0 THEN EXIT FOR
				U += A(L): B(U) = FALSE
				L -= 1: IF L = 0 THEN L = N
			NEXT
			R -= 1: IF R = 0 THEN R = N
		LOOP
		RETURN FALSE
	END FUNCTION
	'***************************************************************
	' インクリメンタル加算クリア，非表示の最小数の位置 K とする
	'***************************************************************
	SUB ICLEAR(K AS INTEGER)
		DIM	I, J, L, R, T, U	AS INTEGER
		R = K: T = 0
		FOR J = 2 TO N
			IF A(R) = 0 THEN EXIT FOR
			T += A(R): B(T) = FALSE
			L = K - 1: U = T
			FOR I = J + 1 TO N
				IF A(L) = 0 THEN EXIT FOR
				U += A(L): B(U) = FALSE
				L -= 1: IF L = 0 THEN L = N
			NEXT
			R += 1: IF R > N THEN R = 1
		NEXT
	END SUB
	'***************************************************************
	' 魔円陣の表示
	'***************************************************************
	SUB OUTPUT
		DIM	I	AS INTEGER
		CONSOLE.WRITE("[ " & A(1))
		IF A(2) < A(N) THEN
			FOR I = 2 TO N
				CONSOLE.WRITE(" " & A(I))
			NEXT
		ELSE
			FOR I = N TO 2 STEP -1
				CONSOLE.WRITE(" " & A(I))
			NEXT
		END IF
		CONSOLE.WRITELINE(" ]")
	END SUB
END MODULE

5. 実行結果

実行結果を以下に示す。以前のバージョンでは左右対称解が重複していたが，今バージョンでは解の重複を避けることができている。また解を二番目の数字が最後の数字よりも常に小さくなるよう並べ直して出力するようにした。

残念ながら今回のバージョンアップで $n = 2$ の場合の解を得られなくなったことを断っておく。

実行結果
n = 3 のとき
[ 1 2 4 ]
END

n = 4 のとき
[ 1 2 6 4 ]
[ 1 3 2 7 ]
END

n = 5 のとき
[ 1 3 10 2 5 ]
END

n = 6 のとき
[ 1 2 5 4 6 13 ]
[ 1 2 7 4 12 5 ]
[ 1 3 2 7 8 10 ]
[ 1 3 6 2 5 14 ]
[ 1 7 3 2 4 14 ]
END

n = 7 のとき
END

n = 8 のとき
[ 1 2 10 19 4 7 9 5 ]
[ 1 6 12 4 21 3 2 8 ]
[ 1 4 22 7 3 6 2 12 ]
[ 1 4 2 10 18 3 11 8 ]
[ 1 3 8 2 16 7 15 5 ]
[ 1 3 5 11 2 12 17 6 ]
END

n = 9 のとき
[ 1 2 4 8 16 5 18 9 10 ]
[ 1 11 8 6 4 3 2 22 16 ]
[ 1 6 4 24 13 3 2 12 8 ]
[ 1 4 7 6 3 28 2 8 14 ]
END

n = 10 のとき
[ 1 2 6 18 22 7 5 16 4 10 ]
[ 1 5 4 13 3 8 7 12 2 36 ]
[ 1 4 2 20 8 9 23 10 3 11 ]
[ 1 6 9 11 29 4 8 2 3 18 ]
[ 1 4 3 10 2 9 14 16 6 26 ]
[ 1 3 9 11 6 8 2 5 28 18 ]
END

n = 11 のとき
END

n = 12 のとき
[ 1 2 14 4 37 7 8 27 5 6 13 9 ]
[ 1 2 9 8 14 4 43 7 6 10 5 24 ]
[ 1 2 12 31 25 4 9 10 7 11 16 5 ]
[ 1 2 14 12 32 19 6 5 4 18 13 7 ]
[ 1 5 12 21 29 11 3 16 4 22 2 7 ]
[ 1 4 19 20 27 3 6 25 7 8 2 11 ]
[ 1 4 16 3 15 10 12 14 17 33 2 6 ]
[ 1 14 3 2 4 7 21 8 25 10 12 26 ]
[ 1 22 14 20 5 13 8 3 4 2 10 31 ]
[ 1 7 13 12 3 11 5 18 4 2 48 9 ]
[ 1 3 23 24 6 22 10 11 18 2 5 8 ]
[ 1 3 8 9 5 19 23 16 13 2 28 6 ]
[ 1 3 12 34 21 2 8 9 5 6 7 25 ]
[ 1 4 7 3 16 2 6 17 20 9 13 35 ]
[ 1 8 10 5 7 21 4 2 11 3 26 35 ]
[ 1 15 5 3 25 2 7 4 6 12 14 39 ]
[ 1 14 10 20 7 6 3 2 17 4 8 41 ]
[ 1 4 20 3 40 10 9 2 15 16 6 7 ]
END

n = 13 のとき
END

n = 14 のとき
[ 1 2 21 17 11 5 9 4 26 6 47 15 12 7 ]
[ 1 2 13 7 5 14 34 6 4 33 18 17 21 8 ]
[ 1 2 28 14 5 6 9 12 48 18 4 13 16 7 ]
[ 1 6 8 22 4 5 33 21 3 20 32 16 2 10 ]
[ 1 5 2 24 15 29 14 21 13 4 33 3 9 10 ]
[ 1 10 48 9 19 4 8 6 7 17 3 2 34 15 ]
[ 1 4 20 2 12 3 6 7 33 11 8 10 35 31 ]
[ 1 12 48 6 2 38 3 22 7 10 11 5 4 14 ]
[ 1 9 21 25 3 4 8 5 6 16 2 36 14 33 ]
[ 1 9 5 40 3 4 21 35 16 18 2 6 11 12 ]
[ 1 3 12 7 20 14 44 6 5 24 2 28 8 9 ]
[ 1 8 21 45 6 7 11 17 3 2 10 4 23 25 ]
[ 1 9 14 26 4 2 11 5 3 12 27 34 7 28 ]
[ 1 3 24 6 12 14 11 55 7 2 8 5 16 19 ]
[ 1 3 5 6 25 32 23 10 18 2 17 7 22 12 ]
[ 1 4 6 31 3 13 2 7 14 12 17 46 8 19 ]
[ 1 10 22 34 27 12 3 4 2 14 24 5 8 17 ]
[ 1 5 23 27 42 3 4 11 2 19 12 10 16 8 ]
[ 1 8 3 10 23 5 56 4 2 14 15 17 7 18 ]
[ 1 4 8 52 3 25 18 2 9 24 6 10 7 14 ]
END

n = 15 のとき
END

n = 16 のとき
END

n = 17 のとき
[ 1 2 4 8 16 32 27 26 11 9 45 13 10 29 5 17 18 ]
[ 1 7 31 2 11 3 9 36 17 4 22 6 18 72 5 10 19 ]
[ 1 7 12 44 25 41 9 17 4 6 22 33 13 2 3 11 23 ]
[ 1 21 11 50 39 13 6 4 14 16 25 26 3 2 7 8 27 ]
[ 1 3 12 10 31 7 27 2 6 5 19 20 62 14 9 28 17 ]
[ 1 7 3 15 33 5 24 68 2 14 6 17 4 9 19 12 34 ]
END

6. 計算時間の比較

面倒なコーディングの効果は実感できるほど顕著に表れた。以下，計算時間の比較を示す。単位は「秒」である。

表２　計算時間の比較
n billiard maenjin maenjin2
4 0.01 0.03 0.03
5 0.01 0.03 0.03
6 0.01 0.03 0.03
7 0.01 0.03 0.03
8 0.01 0.03 0.03
9 0.03 0.03 0.03
10 0.15 0.04 0.04
11 1.17 0.11 0.06
12 11.39 0.65 0.18
13 112.67 4.22 0.92
14 1124.96 36.15 6.85
15 11178.60 280.58 51.00
16 112038.24 2562.51 415.09
17 1122292.52 21700.87 3442.07

グラフにすると分かりやすい。maenjin2 は前バージョン maenjin と比べてもざっくり５倍は速くなっている。

7. まとめ

文献[2]を読むと，下林山氏自身が「改良すればもっとスピーディなアルゴリズムがつくられる」と述べている。また，左右対称解を排除できる基本アイディアを提案していたが，煩雑になるため敢えて実装せず「気になる方は，プログラムを修正して使ってください」とも述べている。

本記事は，この二つの課題に対する40年越しの回答である。

8. 参考文献

[1] 島内剛一，λ倍取りゲーム，数学セミナー1982年1月号，10～14頁，日本評論社
[2] 下林山稔，パソコンで魔円陣を，数学セミナー1987年7月号，55～59頁，日本評論社
[3] 秋山茂樹，魔円陣と有限幾何，数学セミナー2013年7月号，25～31頁，日本評論社

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?