数独

問題の説明


パズル「数独」は「ナンバープレース」とも呼ばれます.「数独」の名はパズ ル雑誌「ニコリ」で使われているもので,「数字は独身者に限る」を省略した ものだそうです.

数独の盤面は9x9の広さを持つ方眼です.25x25の問題など大きいものもありま すが,ここでは9x9に限定します.この方眼は3x3の小さい方眼(ここではグルー プと呼ぶことにします)を縦横3x3に組み合わせたものとなっています.このパ ズルは以下のルールに従ってすべてのマスに1から9までのいずれかの数字を配 置することを目的とします.

ルール1
各行のそれぞれマスには1から9までの別々の数字が1つずつ配置される.
ルール2
各列のそれぞれマスには1から9までの別々の数字が1つずつ配置される.
ルール3
各グループのそれぞれのマスには1から9までの別々の数字が1つずつ配置される.
百聞は一見にしかず,例を見てみましょう.
	+=======+=======+=======+
	| A 8 2 | . . 7 | . 9 . |
	| 5 . . | 3 . 4 | . 2 1 |
	| 3 . . | 1 . . | 6 . . |
	+=======+=======+=======+
	| . 5 8 | 7 . . | . 1 4 |
	| . E . | . 2 . | . . . |
	| 6 4 . | . B 3 | 2 8 . |
	+=======+=======+=======+
	| . . 9 | . . 6 | C . 5 |
	| 8 3 . | 2 . 1 | . . 7 |
	| . 6 D | 9 . . | 8 4 . |
	+=======+=======+=======+
	     図1 数独の問題例
盤面上で空白(分かり易さのために,例ではピリオド(.)を入れている)の部分 に数字を配置します.このとき,先ほど述べたルールにより,各行,各列,各 グループで重複しないように配置します.ただし,上記例において,AからDま での記号は説明上配置したものであって,ここも空白だと思ってください.

この例題において,まず,1に注目してみましょう.Aのあるグループでは,下 の行と中の行には1を置くことができませんから,上の行で唯一空いているAに 1が入ります.Bのあるグループでは,左の列,右の列ならびに上の列には1を 置くことができませんので,残るBが1となります.同じように考えて,C,D,E も1となることがわかります. 同様にして,ほかの数字も埋めていくと,最終的には,図2の解を得ます.

	+=======+=======+=======+
	| 1 8 2 | 6 5 7 | 4 9 3 |
	| 5 9 6 | 3 8 4 | 7 2 1 |
	| 3 7 4 | 1 9 2 | 6 5 8 |
	+=======+=======+=======+
	| 2 5 8 | 7 6 9 | 3 1 4 |
	| 9 1 3 | 4 2 8 | 5 7 6 |
	| 6 4 7 | 5 1 3 | 2 8 9 |
	+=======+=======+=======+
	| 4 2 9 | 8 7 6 | 1 3 5 |
	| 8 3 5 | 2 4 1 | 9 6 7 |
	| 7 6 1 | 9 3 5 | 8 4 2 |
	+=======+=======+=======+
	       図2 図1の解


電子情報工学特別実験のページへ戻る