｢数独｣を数学する Jason Rosenhouse他 2023.3.29.

2023.3.29.　｢数独｣を数学する　世界中を魅了するパズルの奥深い世界

Taking Sudoku Seriously:

 The Math Behind the World’s Most Popular Pencil Puzzle         2012

 

著者　

Jason Rosenhouse　アメリカの数学者。ジェームズ・マディソン大学准教授。著書に『モンティ・ホール問題――テレビ番組から生まれた史上最も議論を呼んだ確率問題の紹介と解説』

Laura Taalman　アメリカの数学者。シカゴ大学で数学の学士号、博士号を取得。デューク大学で数学の学士号を取得。ジェームズ・マディソン大学教授。ソフトウェア開発者の夫と共にパズル制作活動を行う。彼女の研究対象には、ゲームやパズルの数学が含まれており、数独の数学について全国で講演を行っています。

 

訳者　小野木明恵　翻訳家。大阪外国語大学英語学科卒業。訳書にマンディ『コード・ガールズ』（みすず書房、2021）、モフェット『人はなぜ憎しみあうのか』

 

発行日           2014.9.30.　第1刷印刷　　10.7.　第1刷発行

発行所           青土社

 

 

序章

数学者にとって数学とは、好奇心と想像力を刺激され、問題を解決するもの

数独パズルを解く際に用いられる推論は、まさしく数学の核心にあるもの

第1章では、数独パズルを解くテクニックを調べ、数学の問題を構成する者は何かという一般的な疑問について考える

第2章では、ラテン方陣について解説。数学者を長年虜にしてきたものであり、数独の盤はその特殊な例

第3章では、ラテン方陣の考え方を延長したギリシアテン方陣を取り上げる

第4,5章では、数独に関連する数え方の2つの問題について考える。｢根本的に異なる」数独の盤がいくつあるのかを特定。その中で組み合わせ論や抽象代数学の基本的な考え方に触れる

第6章では、興味深い数独パズルをどのようにして見つけるかという問題を提起

第7,8章では、数独とグラフ理論、多項式との関連を調べる

第9章では、数独の極端な例を捜す

最終章では、様々な変種を紹介

本書に掲載した数独パズルを作成したフィリップ・ライリーのサイトBrainfreeze

 Puzzlesにおける業績、数独の権威レベッカ・フィールドにも感謝

Brainfreeze Puzzles Page　(全6冊のバリエーション)

 

 

1     ゲームをしよう　数学を使って応用パズルを解く

1.1       数学とパズル

ケーニヒスベルクの橋の問題――ブレーゲル川によって4分割され7つの橋で結ばれている。各橋を1回だけ渡って町を1周することは可能か

出発点と到着店が異なる場合にはオイラー路、出発点に戻る場合にはオイラー閉路と呼ぶ

1.2       強制的にマスを埋める――数独パズル

単一の選択/場所――タテとヨコの列と3ｘ3のマスをチェックするだけで、強制的にマスを埋めるテクニックで入れる数字が決まる

1.3       双子

候補が2つあるマスを捜す(双子)

1.4       Ｘウィング

3つ子のマスまで含めた長方形の角にある4つのマスに注目、対角線上の角の関係から入れる数字を特定する

1.5       アリアドネの糸

ギリシア神話で、アリアドネの恋人が迷宮の怪物を退治に行くときに道に迷わないよう赤い糸を渡し、迷ったらまた糸を辿って戻れるようにした故事を引いたもので、最後の手段として2者選択のマスの一方を選択して行き詰まったら、もう一方が正解になるという解き方。数学では推論の1つとしてよく用いられる解法

あてずっぽうとの指摘もあるが、いろいろな解法を試した後のことであり、格別に難しいパズルでは論理の筋道があまりにも長くて複雑であるために特別な能力のある人にしか太刀打ちできないことがあるので、これが他の解法/テクニックと根本的に違うというわけではなく、まったくのあてずっぽうとは似ても似つかない

1.6       数学はまだやらないの?

数独パズルは純粋な論理で解く者なので、数学の問題である

1.7       3つ子、ソードフィッシュ、一般化の技法

すべての数学の定理は、一定の条件を定めて、一定の仮定を認めると、一定の結論が論理的に導かれる。仮定が少ないほど定理は一層有用になりやすい

ピタゴラスの一般的な定理は　c^２=a²+b²2ab cosθ　であり、θが直角なら余弦は0となる特殊ケースで、お馴染みの定理となる

この手法を数独の解法にも適用

双子のテクニック――3つ子でも4つ子でも同じことが言える。3ｘ3のブロックの空きマスに考え得るすべての候補の数を当てはめていき、145，148，1458，458のような候補が入ることになる場合は、1，4，5，8の数が何らかの配列で4つのマスに入るので、そのブロック内の他の空きマスからはその4つの数字を排除できる。この一般的な規則とは、1つのブロック内のn個のマスに、同じn個の数の集まりからの候補の数が入るなら、そのn個の数はこのn個のマスに入るはずだというもの

Xウィング――2つの行のそれぞれに特定の数が入ることのできる空きマスが2つしかなく、それら4つのマスが長方形の4隅をなしていると、その数は対角線上の反対側にある2つ1組のマスのいずれかに入る。別な言い方では、2つの行のそれぞれに特定の数の入るマスが2つだけあり、これらのマスがすべて、2つの特定の列にあるなら、その数がこれら2つの特定の列にある他の空きマスに入ることはない。行と列を入れ替えても同じ

3つの行と列でも同じだが、3つの場合は、3ｘ3の格子になり、このテクニックはその格子の形状からソードフィッシュと呼ばれている

４ｘ４の格子にも一般化することができる。このテクニックはスキムバグと呼ばれる

1.8       もう一度やり直す

テクニックを一般化して、追加された領域を対象に含めるようにしたパズルの例として、盤の2本の対角線に1～9の数が1回だけ入るという条件を付け加えたものや、異なる3ｘ3のブロックを4個加えてそれぞれに1～9の数が1回だけ入るというものがある

パズル7　4つの正方形の数独

5	4						6	3
6							5	4
		1				2
					3
			6	9	2
			7
		6				7
3	1							9
2	5						3	1

 

規則を変えた数独の例

①   パズル8　3つ星の数独――各列・行・ブロックに、1～6が1個づつと星が3つづつ入る

		6			1
★			5		4	6
	★			6		★	2
		★					3	6
1			★		★			5
4	2					★
	3	★		1			★
		5	6		2			★
			4			5

②   パズル9　二重トラブルの数独――各列・行・ブロックに、奇数の1，3，5が1回づつ、偶数の2，4，6が2個づつ入る

				4				2
4	4				5	6
	2	2				1	5
			6	6			1
3								2
	2			4	4
	1	3				2	2
		5	1				6	6
4				5

 

2     ラテン方陣　数学者は何をするのか?

数独の1つの盤から何通りでも問題が作れる。解いてみると同じ盤になる――数独の兄弟

1			3					7									2	7
	7			4		8	1				7		9				★	3
		8	1			5	6					8	1			5
		5	2					6			4	5			1
	2						8							5			★
7					8	2							4			2	9
	5	1			9	7						1			9	7
	8	6		3			4			2					7		4
9					4			2		9	3

左はレベル1、右はレベル4/5(★の1か8かでアリアドネの糸)

ラテン方陣とは、n個の別々の記号が、nｘnの配列を持ち、すべての行と列に1回づつ入るものをいう。ｎを次数といい、次数9のラテン方陣に3ｘ3のブロックの条件を付けたものを数独という

2.1       ラテン方陣は存在するのか?

数独の｢ブロックの条件｣を満たさないラテン方陣もある

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

数独に比べて一意の解になるようにするには、さらに多くの最初の手掛かりが必要になる

パズル14と15

隣り合った2つのマス(斜め隣も含む)には同じ数字が入らないものとする

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

 

2.2       いろいろな大きさのラテン方陣を作る

パズル16――次数10のラテン方陣を作る

1～10の数を横に並べ、1行下には2～10と1を入れ、行を下がるごとに数を1つづつずらしていけば、ラテン方陣は出来る

2.3       移動と可分性

2.4       川の中でジャンプする

 

3     ギリシアラテン方陣　36人の将校の問題

2つのラテン方陣を重ね合わせたものがギリシアラテン方陣

 

3.1       ギリシアラテン方陣は存在するか?

3.2       オイラーのギリシアラテン方陣予想

3.3       相互直交の正しいデザイン

3.4       相互直交数独

3.5       誰も気にしない

 

4     数を数える　見た目よりも難しい

いくつの数独の盤が存在するのか

4.1 数え方

4.2 四独の盤の数を数える

4.3 数独の盤はいくつあるのか

4.4 数独の盤の数を推定する

4.5 200万から44まで

4.6 コンピュータに入力する

4.7 問題解決のための覚書

パズル30及び31　数独の報酬――右は難解

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

 

5     同類値　本質的に同一であることの重要性

1つの盤の各マスの数字に1を加えた数字を入れると、別の盤が出来上がるが、別の盤というのは正しくない。そういうものを除いた根本的に異なる盤はいくつあるのか

5.1       同一であるのと一緒

P.159　2つの奇数の和は奇数になる　⇒　偶数になる

5.2       数独らしさを保つ変換

3ｘ3のブロックを横に並べたものを｢帯｣、縦に並べたものを｢柱｣

同じ帯にある2つの行(もしくは同じ柱にある2つの列)を入れ替えることは有効な変換

帯や柱そのものを置換するという形も含まれる

対称軸をもとにして回転あるいは鏡映させると別の有効な盤ができる。回転は90度、180度、270度があり、鏡映では対角線に加えて5列目の垂直線と5行目の水平線も入る

P.165　ある帯または柱において、ブロックを入れ替える　⇒　帯や柱そのものを入れ替える

5.3       同値の四独の盤

5.4       自然な取り組み方が失敗に終わるわけ

5.5       群

5.6       バーンサイドの補題

5.7       痛感

パズル37と38――一連の数独の対称性と書き換えによって、一方からもう一方へと変わることができるという意味で、根本的に同値

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

 

6     探索　乾草の中に針を捜す技

6.1       数独のコウノトリ

パズルを作成する方法で最も簡単なのは、完成された盤から許容できるパズルになるまでマスの中の数を体系的に取り除くこと

盤の四隅を除く。左右上下対称になるように除くが、除いた数を入れ替えても正解になる場合は、解が2つになるのでそういう除き方はしてはいけない

対照的なペアをなす2つの数を取り除くことを念頭において、取り除く

6.2       GPSをもったコウノトリ

空の盤から始めて数字のペアを入れていく。許容できるパズルが現れるまで対照的な位置に2つづつ手掛かりを置いていく

6.3       探索の仕方

今のところ数独パズルでは、適切で対称的なパズルの手掛かりの最小の数は18と考えられている(非対称的なパズルでは17が最小値)

6.4       18個の手掛かりを持つ数独を探して

最初の手掛かりとして、18個のマスの対称的なパターン(マスクと呼ぶ)を選ぶ

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

9個の数字のうち少なくとも8個入っていなくてはならない

1つの数字をあまりにたくさんマスクに置かないように気を付ける

一般的には、数字が比較的むらなく配分されたマスクをもとに適切なパズルを見つける方が容易

適宜数字を入れてみて、正解の数を数えた後、同じ盤で適宜数字を入れ替えて、正解の数が減るかどうか調べ、減っていれば正しい入れ替えが行なわれたとされる。そうして繰り返し入れ替えながら正解が1つになるまで続ける。唯一の正解を持つパターンは右の通り(18個の手掛かりを持つ針)

パズル44と45　さらに2本の針

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

同じマスクだが、どちらも記号の置換以上の違いがあり、同値のパズルではない

パズル46　18個の手掛かりのπ

9つの数字の配分は自由だし、マスクにもいろいろ考えられるので、πの数字の最初の18桁における数字の配分と同じにして、異なるマスクを使ったものがこのパズル

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

6.5       難しさを測定する

最初の手がかりの数――手がかりの数が少なければ一般的には難しい。左は手がかりが少ないが易しく、右は手がかりは多いが超難解

パズル47と48　簡単な20と難しい28

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

マスクのパターンにもよる――手がかりをどう配置するかによるが、どのマスクが難易度が高いかは一概には言えない

パズル49と50　易しい双子と難しい双子　右は超難解

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

パズルを解くのに必要とされる手法による難易度の判定――より複雑な推論が必要ならパズルはより難しいと言えるが、パズルを眺めるだけではわからない

6.6       容易さと興味深さは逆相関する

6.7       付加価値のついた数独

パズル7は変種。9個のマスを持つ領域を追加することで独自の新たな探索問題が出現する。この場合は4つの正方形の追加領域があった

パズル53　ジグゾープラス――9個の追加領域を持つ数独

パズル54　虹の帯――同上で、斜めの帯になった9個のマスにもそれぞれ1～9が入る

左上のブロックの9と右下のブロックの7は、解きやすくするために入れてあり、究極の形は16の手がかりで解ける

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

パズル55(下左)　位置数独――不連続の9個のマスの部分集合も可能

パズル56(下右)　ベン数独――別の数独の盤と重ね合わせる。3つの盤それぞれには何通りもの解があるが、重ね合わせると解は1つになる。このパズルの特徴は、3つの盤それぞれに回転対称性のある同一の手がかりのパターンがある

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

 

7     グラフ　点、線、数独

グラフ彩色の用語を用いて数独の盤にあるマスの関係を理解できる

7.1       物理学の教え

砲弾の経路を決定するのは、連続関数の問題

7.2       2つの数学的な例

パズル57　ジグゾーπ数独――πの最初の12桁の数字を入れる、各領域には、1と3が2つ、5が5つ入り、7がない、残りの数字は1つづつ

3			1	5	4			1		9	5
	1			3					1	3	6
		4			3		8			2
5			1			9	2	5			1
	9			5			5
5	8	1			9			3		6
	5		8			2			5	5	3
				5			6			1
2			5	1	5			5			9
	6			4		1			3
1	5	1					5			5
5	5		4			3	1	6			8

 

7.3       グラフの色分けとしての数独

数独は、色分け問題として書き直すことができる

7.4       4色定理

パズル61　アメリカを4色で彩色する

7.5       多くの道はローマに通じる

7.6       本型埋め込み

 

8     多項式　やっと代数の使い方がわかった

多項式を用いても、前章と同様、数独の盤にあるマスの関係を理解できる

8.1       和と積

8.2       一般化の危険

8.3       複素多項式

8.4       実験数学の出現

 

9     極値　数独を限界まで押し進める

9.1       極端に走る喜び

9.2       手がかりの最大の数

9.3       3つの驚くべき極値

パズル72　非対角の数独――主対角線上の3つのブロックに手がかりがないことに留意

パズル73　空っぽの空間のある数独――中央の5x5に手がかりが一切ないことに留意

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

パズル74　欠如の数独――適切なパズルにおいて空欄であってもよい領域の数は最大9と考えられている。ブロック3つと3行、3列がすべて空欄になっている例を挙げる。中央の5x5の正方形も空いている

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

9.4       ロックスター問題

未解決の問題: 一意の解をもつ数独パズルがもちうる最初の手がかりの最小の数はいくつか

パズル75(下左)　17個の手がかりを持つ数独

パズル76(下右)　12個の手がかりを持つX型の数独――2本の主対角線も数独の領域(1～9までが入る)とするという条件を加えると、手がかりは12まで縮小できる

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

9.5       数学に｢証拠｣はあるのか

9.6       数独は局所的な数学である

 

10  終章　パズルが多すぎて困ることはない

10.1    余分な領域

パズル77(下左)　ホチキスの針――色付けの領域にも1～9を入れる

パズル78(下右)　ピラミッド――色付けの4つのピラミッドにも1～9を入れる

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

パズル79　稲妻――5本の稲妻型の領域にも1～9を入れる

	2			7				9
		3
			4		1
		9				7
	1			4			9
		6				3
			7		9
						5
3				1			6

パズル80　XXX(靴下の柄)――各対角線上の数字が重複しないようにマスを埋める。9個よりマスの少ない部分的な領域の設定も可能で、数が重複しないようにとの条件をつける

						4	5
2						6
6	4				1
		9		6
			1	9	4
				7		3
			9				3	2
		3						7
	1	5

｢部分的な領域(9マスより少ない領域のこと)｣を持ったパズルで、領域内で数が重複しないようにとの条件が付く。以下のパズル81と82は靴下に因んだパズル

パズル81　アーガイル(靴下の柄)――各対角線上の数字が重複しないようにマスを埋める

			5
		3
	1	4				2	5
4	3				5			8
1			9		8			3
9			4				6	1
	5	9				1	4
						8
					9

パズル82　穴(靴下の柄)――穴の形をした4つの領域で数字が重複しないように埋める

(穴の数字が周囲の色付けした8マスの中でダブる可能性があることに注意。最後はアリアドネの糸を使う?)

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

パズル83及び84　ジグゾー数独――第6章のジグゾープラスの変形

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

10.2    値を付加する

3ｘ3のブロックの各行と各列の3つの数字の和がいずれも15になるような配置を｢半｣魔法陣という。対角線の和が同じになる場合を｢魔法陣｣というが、そこまでは要求しない

1	5	9
6	7	2
8	3	4

中央のマスに7が入るものはこの形しかない。次のパズルを解くには、半魔法陣の可能性について前もって探索しておく必要がある。取り掛かりのヒントは、これらの盤について、行の和と列の和の、1つだけのあり得る値を決定してみること

パズル85　3つの魔法の数独――色付きのブロックが半魔法陣になることが条件

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

パズル86　全魔法陣数独――すべてのブロックが半魔法陣という条件を付けることは可能で、その場合には最初の手がかりの最小は8

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

各ブロックの各行と各列の和が15となる組み合わせは、1+5+9，2+6+7、3+4+8が1つ、もう１つが1+8+6、2+9+4、3+5+7

10.3    比較の数独

10.4    その先へ

パズル94　ダース数独――9ｘ9の代わりに12ｘ12のマスを使う

		8	5	11	1			7			2
		6			2		10		5	4
	11				8	5				6
				7			12		4		9
		1	4			2					12
		11			5					1	3
7	9					10			6
6					4			5	2
11		10		8			9
	7				10	6				3
	8	9		5		12			11
5			11			8	1	4	12

P.365　各ブロックに1～9(ママ)が1回づつ入る

パズル96　テトロミノ数独――数学者の間でテトロミノと呼ばれるジグゾーの形をした各領域に1～4を入れ、各行、各列に1～4が2回づつ入る

パズル97　ペントミノ数独――各ペントミノに1～5を1回づつ入れ、各行、各列に1～5が2回づつ入る

1	1				2		2		2			4			3			4
4	2			1						4							5
		1	2			2	1				3					2
			2						2			1			1			3
				4									4	3
3	4			2	2								3	2
			1			2	4		4			1			2			5
4		2				4	3				4					3
										2							5
									1			5			4			1

 

 

訳者あとがき

数独の原型は、18世紀のスイスの数学者オイラーが考案したラテン方陣

著者らは、数独パズルは、数学の核である推論を用いて解く、非常に数学的なパズルだと主張

第1章では、様々な数独パズルの解法のパターンを紹介

第2章では、数独パズルの原型であるラテン方陣について触れる

第3章では、ギリシアテン方陣について触れる

第4,5章では、数独の盤はいくつ存在するのかについて触れる

第6～8章では、有効なパズルの作成方法、数学のグラフ理論や多項式との関連を論じる

第9章では、極端な数独パズルのが出される

最終章では、様々な変種を紹介

オリジナルのパズル90点以上を収める

 

 

 

青土社　ホームページ

世界を席巻した「数独」パズルを徹底研究! ! 数独パズルを目にすると湧いてくる、 答えを導くための推論という枠を超えたさまざまな興味深い問いをつぶさに検討。 「数独」ファンから数学者まで、 世界初、「数独」と数字パズルを数学する! オールカラー。オリジナルパズル90点以上を収録。「数独の父」鍛治真起氏 〔株式会社ニコリ 代表取締役社長〕推薦!! いまや、世界中のたくさんの人びとが「数独」を楽しんでいる。 本書の著者、J・ローゼンハウスとL・タールマンは、 数独ブームのおもしろさを理解しながら、斬新で興味深

 

 

Nature Japan  

Nature ダイジェスト  

Vol. 9 No. 3  

NEWS

数独の重要問題が解けた

解を1つしか持たない数独問題の作成には、少なくとも17個のヒントが必要であることが証明された。

 

アイルランドの数学者が、複雑なアルゴリズムとスーパーコンピューターを用いて数百万時間に及ぶ演算を行い、数独に関する重要な問題を解決した。数独は日本から広まったパズルで、与えられている数字をヒントにして、9╳9のマスに1から9までの数字を入れて解盤面を完成させる。このとき、縦、横、および太い線で区切られた3╳3のブロック内のすべてで、1から9までの数字を1回ずつ使うようにしなければならない。新聞紙上の数独の大半は25個前後のヒントが与えられているが、ヒントの数が増えるほど、難度は低くなる。

2012年1月1日、ユニバーシティカレッジ・ダブリン（アイルランド）のGary McGuireは、数独の問題が成立するには最少で17個のヒントの数字が必要であるという論文をオンラインで発表した1。16個以下のヒントでは解が1つに定まらず、有効な問題にならない。

この発表に対し、1月7日に米国マサチューセッツ州ボストンで開かれたある学会に参加していた数学者たちの間では、McGuireの証明はおおかた理にかなっているし、数独の数学という新興分野に重要な進展をもたらしたという意見が多数を占めた。

ジェームズ・マジソン大学（米国バージニア州ハリソンバーグ）の数学者Jason Rosenhouseは、「彼のアプローチは合理的で、信頼できそうです。慎重な楽観論として受け止められたと思います」と言う。Rosenhouseは、同じ大学の数学者Laura Taalmanとともに、『Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle（数独をまじめに考える：世界で最も人気のあるペンシルパズルの背後にある数学）』という本を昨年12月末に出版している。

数独愛好家たちは、以前から、ヒントが17個の数独はあるが、16個の有効な数独は見当たらないことに気付いており、16個のヒントで解が1つに決まるようなものは存在しないのではないかという推測が広がっていた。これを証明する方法の1つは、考えられるすべての解盤面につき、その盤面を解とするヒントが16個の有効な数独問題があるかどうかを検証することだが、演算に時間がかかりすぎる。

そこでMcGuireは、「ヒッティング・セット・アルゴリズム」を設計して、この問題を単純化した。ポイントは、ある解盤面に並んだ数字のうち、互いに入れ替えることで別の解盤面が得られるような部分（これを「不可避集合」と呼ぶ）を探すことにある。不可避集合を含む盤面が数独問題の唯一の解になるには、ヒントと不可避集合との間に重なり（これを「ヒット」と言う）がなければならない。だとすれば、すべての解盤面につき不可避集合を見つけて、それらとヒットするヒント数16の有効な数独問題がないことを示せばよいことになる。

McGuireらは、2年かけてこのアルゴリズムのテストを行い、その後、アイルランド・ハイエンド・コンピューティング・センター（ダブリン）のコンピュータにより、考えられるすべての解盤面につき、ヒッティング・セット・アルゴリズムを用いて検証した。この作業には700万CPU時間を要した。

ウェスタン・オーストラリア大学（パース）の数学者Gordon Royleは、McGuireらとは別のアルゴリズムを用いて、ヒントが17個の数独問題を数え尽くそうとしており、「コンピューティングと数学の技術を極限まで高めなければならない難問です。エベレストに登るようなものです」と語る。

McGuireは、今回の方法は、ほかの分野でも成果を挙げる可能性があると言う。ヒッティング・セットの概念は、遺伝子の塩基配列の決定や細胞ネットワークに関する論文でも用いられており、彼は、自分のアルゴリズムがほかの研究にも利用されればと期待している。「今回の成果で、もっとさまざまな人が興味を持ってくれることを願っています」。

皮肉なことに、McGuireは、この問題に取り組むようになってから、楽しく数独をすることが少なくなったと言う。「確かに数独は気分転換になりますが、正直なところ、最近はクロスワードのほうが好きなのです」。

翻訳：三枝小夜子、要約：編集部

Nature ダイジェスト Vol. 9 No. 3

DOI: 10.1038/ndigest.2012.120304