黒マスはどこだを解くプログラム

はじめに

2001年度後期に、東京大学電気電子情報系3年進学予定者対象とした伊庭助教授担当「コンピュータプログラミング」の講義があったらしく、それに某知人が参加している。そして、最終レポートがニコリのペンパである黒マスはどこだを解けというものであった。それに関して質問が来たりしたので、ちょうど春休みに入ったこともあり暇だったため開発をし、めでたく解けるプログラムが出来上がった。
　そこでソースプログラムなどは提出締切までは非公開だったが、無事提出期限は過ぎたので公開したい。

なお、課題を出しているページは年度が変わったときに消滅しているのでミラーを作っておいた。

注意

プログラムにはバグがつきもの。エラーが出たら遠慮なく指摘しよう。
単純に作ったためあまりコードを最適化していないので、遅いとかダサいとか言うな。
strtokは危険だから使うなとか言うな。
C++の機能をクラス以外使ってないじゃんとか言うな。
最大の注意点。このままだと、繰り返して何度も解かせた場合、数字の位置を保管した部分を開放していないため、メモリリークが発生する。ソースファイルにも書いてあるが一応こちらにも。

ダウンロード

main関数: とりあえず課題で用意された２０問を順に全て解く。ただのインタフェースなので別に要らんかも。
ヘッダファイル: 使うヘッダファイル。クラス定義。クラスのインタフェースはここを見れば分かる。
クラスの中身その１: クラスの中身のほとんど。
クラスの中身その２: 解くルーチン。
クラスの中身その３: 問題用意ルーチン。消してないのでゴミが多い。

解説

解く順番はこのようになっている。

２の斜めを白マスにする ch2solve();
簡単な仮定をする oneStepSolve();
1. 大きい数値の白マスを伸ばす chLargeNumSolve();
2. 全てのマスについて、白マスまたは黒マスだったら大きい数値ができるか（isThereOverNumber();）を調べ、ハタンしないのが一方だったらその色にする
全マスについて１段階仮定をして、簡単な仮定を呼び出し、同様にハタンしないのが一方だったら確定 BOARD::twoStepSuppose();
これでもできなかったら再帰的に３を呼び出す

そんなことより大事なのは、「黒マスだったらハタンする」を検索するための、黒マス分断禁ルールの実装である。その判定をいかに行うかを示す。黒マス配置用メソッドにおいて、黒マスを配置した場合はそのタテヨコ４方は白マスに確定させている。

黒マスを配置するときに、そこに黒マスを配置すると盤面が分断されるかどうか、を調べればよい。そこでsetBlack(x,y)中にて、チェック用関数に飛ばすようになっている
斜めに連なった黒マスの塊を「群」と呼ぶ。群には番号がつけてある。
群が外壁に接している場合は群番号は正。
群が外壁に接していない場合は群番号は負。

あとはソースを見てくれれば、どこで何をしているかはコメントが多いので分かると思うが、分かりやすいよう図を示しつつ解説する。今から*印のところに黒マスを配置しようとするときのチェック内容である。

ちなみに、後で気づいたのだが、外壁に接している群番号は正であれば別に同じでも構わなかったので、1に統一すれば簡略化できるようだ。「周りに２つ以上外壁と接する～」を「周りに同じ番号が複数あったら～」に含ませることができる。


		*


					*

まわりにひとつも黒マスがない場合。
外壁に接していれば正の壁番号をつける。
接していなければ負の壁番号をつける。

	1
*		1
			1
				1
					*

黒マスを配置しようとする点が最外壁で、周りに正の壁番号があるときは分断

1
	1
		*
			2
				2

周りに２つ以上外壁と接する壁番号がある場合は分断。


	-1
-1		-1
	*

周りに同じ番号が複数あったら分断


		-1
			-1
1				-1
	*		*

周りにひとつしか壁番号がないときはその番号をコピーする。要するに群が広がる

1
	1
		*
	-1		-2
				-2

周りに複数の壁番号があった場合。
どれかが正ならば全ての壁番号が正の新しい壁番号に変更
全て負ならば全ての壁番号が負の新しい壁番号に変更
要するに群が一体化

このチェックによって黒マス分断は全て判定できると思われる。私には証明なぞできません。

黒マス分断判定はほかの人のプログラムではどうやって実装されているのか気になってしょうがないのであった。

以上。疑問点などはメールなり掲示板なりでどうぞ。

ホームに戻る