研究帖16

 

 

 


作者へのメッセージ
研究課題 8bitの領地に住む8人の女王

研究課題 8bitの領地に住む8人の女王

 

 

そよ風さん「博士、今日は。」

ナイス博士「おお、そよ風さん、久しぶりだな。」

そよ風さん「ええ、ご無沙汰しました。BB君はあれから、来ましたか?」

ナイス博士「いや、それが、財布や携帯をおいたまま、全然来ないんだ。」

そよ風さん「ああ、そうですか。ずいぶん怒っていたみたいですからね。」

ナイス博士「うん、まずかったな。個人的な事に立ち入りすぎたな。」

そよ風さん「そうですね、今度やってきたら、謝らないといけないですね。」

ナイス博士「うん。ところで、」

そよ風さん「なんですか?」

ナイス博士「彼は、『これで全部分ったぞ!』とか、言っていたな。」

そよ風さん「ええ、どういう意味でしょうね。」

ナイス博士「わからん。気になるな。」

そよ風さん「そうですねっ、何とかうまく聞き出す手を考えないと!」

ナイス博士「いや!まてまて!それがだめなんだよ。」

そよ風さん「ああっ、そうでしたね!個人的な事ですからね。」

 

 

ナイス博士「ところで、君も久しぶりじゃないか。どうしたんだい?」

そよ風さん「ええ、急に仕事が忙しくなったんです。」

ナイス博士「へえ、商売繁盛で良かったじゃないか。」

そよ風さん「いや、そうじゃなくて、面倒な仕事が出来ちゃったんです。」

ナイス博士「そうか。どんな事だい?」

そよ風さん「ええ、実はですね、うちのお店のオーナーが、8階建てで各階に8部屋あるビルを 建てたんです。」

ナイス博士「ほう、それはすごいな。何のビルなんだい?」

そよ風さん「それがですね、何と、そのビルで風俗業を始めるんです。」

ナイス博士「へええっ、8階建てのビルで、風俗業をねえ、大規模だな!」

そよ風さん「ええ、で、さっそく、美人でまじめで、安い給料でも一生懸命働く女王様を8人 やとったんです。」

ナイス博士「ほうっ、うまく行ったじゃないか。じゃ、オーナーは大儲けだな!」

そよ風さん「それが、そうはうまく行かないんです。」

ナイス博士「ふうん、どうして?」

そよ風さん「8人とも女王様だけに、すごくプライドが高くて気が強いんです。」

ナイス博士「そうか、まあ、職業柄、やむをえないな。」

そよ風さん「いや、それだけなら別にいいんですが、8人で、喧嘩ばっかりするんです。」

ナイス博士「うーん、いったいどんな理由で喧嘩するんだい?」

そよ風さん「まず、同じ階で顔を合わせると、それだけで喧嘩します。」

ナイス博士「なんだ、そんな事か。せっかく8階もあるんだから、全員を別々な階に入れて置けばいい んだよ。」

そよ風さん「いや、それだけじゃだめなんです。」

ナイス博士「どうして?」

そよ風さん「自分の真上に他の人の部屋があると、どんなに離れた階にいても、『私の事を 見下してるのね!!』と怒り出すんです。」

ナイス博士「うーーん、じゃ、部屋をひとつずつずらして対角線上に並べたら どうなんだい?」

そよ風さん「いや、それでも、斜め上から見下してる!と、怒り出すんです。」

ナイス博士「うーーーーーん、我がままだな。それじゃ、どうしようもないじゃないか。」

そよ風さん「いや、良い方法があって、斜め上でも少しずれていればいいんです。」

ナイス博士「と言うと?」

そよ風さん「隣の部屋の1つ上の部屋だとだめですが、隣の部屋の2つ上や、2つ隣の1つ上 とか、少しずれた斜めなら別に怒らないんです。」

ナイス博士「うーーーーーん、何だか良く分らんな。」

そよ風さん「ええ、私も訳が分らないんですが、とにかくそうすれば丸く収まるんです。」

ナイス博士「ふうん、まあ、良かったじゃないか。一件落着だな。」

そよ風さん「それがだめなんです。」

ナイス博士「なんだ、まだか。今度は何なんだい?」

そよ風さん「いくら考えても、8人全員をうまく並べる部屋の配置が出来ないんです。 それで、」

ナイス博士「それで?」

そよ風さん「オーナーから、上手な部屋の並べ方を、パソコンで計算してくれと頼まれたん ですが、どうしたらいいか分らないんです。」

ナイス博士「そうか、それは困ったな。」

そよ風さん「ええ、なにしろせっかく立派なビルが建ったのに、女王様が喧嘩を始めると、 ムチやロウソクを振り回して8人で暴れだすんで、壁に傷はつくわ、火は付くわ、客が怪我をするわ、 近所迷惑になるわ、商売どころじゃなくなって、オーナーもほとほと困り果てているんです。」

ナイス博士「そうか。困った人達だなあ。」

そよ風さん「ええ、で、オーナーから、もし良い方法を見つけたら、私の大好きな北海道の ニシンの干物をたくさんあげるって言われたんで、何とかしたいんですが、いい方法は 無いでしょうか?」

ナイス博士「うーーーーーーん、困ったな。8人の女王様ねえ。8人のクイーンか。うーーん、 8人の...........そうだ!

そよ風さん「なっ、なんですか!なにか、良い方法が有りますか!!」

ナイス博士「うんっ、すごいアイデアを思いついたぞ!!8クイーン問題って 知ってるかい?」

そよ風さん「ええっ、何ですか、それ。」

ナイス博士「チェスの、8×8のますに、女王様を8人、だれからも取られない位置に置く 問題なんだ。クイーンは、縦横斜めにいくつでも動けるので、その道筋に並ばないよう、女王様を並べる 方法のプログラムがあるんだ。それを使えば良いいんじゃないか?」

そよ風さん「へえっ、そんなのが有るんですか。さすが博士、素晴らしいアイデアですね。 8階建てのビルを横に置くと、チェス盤と同じになると言う、着眼点が素晴らしいですね!!」

ナイス博士「はっはっはっ、いや、それほどでもないがね。はっはっはっ。」

そよ風さん「で?」

ナイス博士「えっ、」

そよ風さん「で、どうするんですか?」

ナイス博士「えっ、」

そよ風さん「いや、だから、えっ、じゃなくて、そのプログラムを作って下さいよ!」

ナイス博士「ああ、何だ、プログラムか。ああ、それなら、たぶん『何でも入門書』に書いてある から、読んで作ってくれ。」

そよ風さん「なんだ、そうですか。まあ、やって見ます。」

 

そよ風さん「うーーーん、困ったわ。」

ナイス博士「どうしたんだい?」

そよ風さん「博士、『なんでも入門書』に8クイーン問題の解き方が書いてあるんですが、 難しくて良く分らないんです。」

ナイス博士「はっはっはっ、そんな事か、簡単じゃないか。書いてあるコードを丸写しして コンパイルすれば良いんだよ。」

そよ風さん「いや、もちろんそれはやったんですが、エラーが出てうまく動かないんです。」

ナイス博士「ふうん、じゃ、デバッグしたのかい?」

そよ風さん「それが、理屈がわからないんで、うまくデバッグ出来ないんです。」

ナイス博士「なあんだ、そうか。」

そよ風さん「ええ。で、どうしますか?」

ナイス博士「えっ、何を?」

そよ風さん「だから、プログラムですよ!何とかして下さいよ!!」

ナイス博士「ええっ、うーーーーーーん、」

そよ風さん「うーーーーん、じゃなくて、何とかならないですか!!!」

ナイス博士「うわっはっはっはっ!」

そよ風さん「また笑って誤魔化すんだから!!いつもこれなんだから。頼りにならないわね! あーーあっ、北海道のニシンの干物が、」

ナイス博士「ニシンの干物か。あーーあっ、ニシン.......。ニシン....? ニシン!! そうだ!!!ニシンだっ!ニシンを使うんだ!!!

そよ風さん「博士、何を言ってるんですか。ニシンはまだ手に入らないし、 使いようが無いでしょ!」

ナイス博士「違うよ!何を言ってるんだ。ニシンといえば!」

そよ風さん「ニシンの干物でしょ。」

ナイス博士「違う!!二進法だ!!!!」

そよ風さん「二進法?二進法は食べられませんよ?」

ナイス博士「そうじゃないよ!!8クイーン問題を、二進法で解くんだ!!」

そよ風さん二進法でえっ!!

 

 

 

そよ風さん「二進法で、どうやって解くんですか?」

ナイス博士「うん、まず、1つの階にある8つの部屋を、8ビットの二進数で表す。 女王様がいる部屋を1にして、空き部屋を0にするんだ。」

そよ風さん「ふうん、そう言う事なら、たとえば3なら、00000011ですね。」

ナイス博士「そうだが、3はだめなんだ。同じ階に二人女王様がいると、 喧嘩になるだろう?」

そよ風さん「ああ、なるほど!!だとすると、128、64、32、16、8、4、2、1の、 どれかしか使えませんね!!」

ナイス博士「そうだ。8階建てだから、それらの数字の8つの配列を作るんだ。」

そよ風さん「そうですか。だとすると、たとえば、{ 128,64,32,16,8,4,2,1 } ですか?」

ナイス博士「いや、それもだめだ。前の数字を1つシフトした数を次に入れると、 1のビットが斜めに並ぶんだ。」

そよ風さん「ああ、そうか。と言う事は、2つ後に2つシフトした数字や、3つ後に3つシフトした 数字もだめですね。」

ナイス博士「そうだ。」

そよ風さん「あと、同じ数字を2回使うと、真上に別な女王様がいる事になるから、 それもだめですね!」

ナイス博士「そういう事だよ。まとめると、」

 

***********************************************

  * 128、64、32、16、8、4、2、1の数字を使って、8要素の配列を作る。これ以外は使えない。

  * 同じ数字は2回使えない。

  * 後の数字には、前に出た全部の数字の、インデックスの差の分だけシフトした数は 使えない。

  * これらの法則でマスクを作り、次の要素は、128から右に1をシフトさせていってそれにかからない 数字を見つけて使う。

  * 0になってしまったら、1つ前に戻り、そこの数字をさらに1つ右にシフトさせた位置から 続ける。

  * 8つともうまく行ったら、それを記録し、最後の数字を1つシフトさせて続ける。

  * 最初の要素が0になってしまったら完了。

***********************************************

 

ナイス博士「これで出来るんじゃないか?」

そよ風さん「ええ、これならうまく行きそうだわ!!早速やって見ます!!」

 

2時間後、そよ風さんが戻って来た。

そよ風さん「博士!出来ました!」

アプレット、8クイーン問題

ナイス博士「おお、うまく行ったな!」

そよ風さん「ええ、博士のおかげです。」

ナイス博士「どれどれ、コードを見せてくれ。」

そよ風さん「これです!」

 

コード

簡単なクラス図

 

ナイス博士「おや、アプレットなのにPlayApplicationクラスにmainのメソッドがあるな。」

そよ風さん「ええ、これは、PlayApplicationクラスを動かせば、アプレットじゃなくてアプリケーションとして 動くんです!」

ナイス博士「へえ、そんなことも出来るのか!......おや?」

そよ風さん「何ですか?」

ナイス博士「アプレットのPlayAppletクラスがずいぶん簡単だな。」

そよ風さん「ええ、コンポーネントで画面を作るBoad2クラスを、別に作ったんです。」

ナイス博士「ふうん、その方がメリットが有るのかい?」

そよ風さん「ええ、同じような画面は他のアプレットでも使えるので、これを改良して使える ようにしたんです。」

ナイス博士「ほう、なるほどねえ。」

そよ風さん「他にも、数字の配列をチェスの盤のように見せるのに、いろいろ考えました。」

ナイス博士「ああ、Display2メソッドだな。正規表現で1と0を●と□に書き換えるのか。 素晴らしいじゃないか!」

そよ風さん「いえいえ、博士のアイデアが良かったからです!大発明じゃないですか!!」

ナイス博士「うん、特許を取りたい位だ。でも、アルゴリズムでは特許が取れないんだ。」

そよ風さん「そうですか。残念ですね。」

ナイス博士「でも、特許は取れないがニシンは、採れるぞ!」

そよ風さん「そうですね、二進法でニシンの干物を採るわけですね!はっはっはっはっ!!」

続く

 

」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」」

 

 インターネットで調べたところ、ビット演算で8クイーン問題を解くアルゴリズムは、すでにJeff Somers さんが 先に作っていた事がわかりました。 

http://www.ic-net.or.jp/home/takaken/nt/queen/

http://www.jsomers.com/nqueen_demo/nqueens.html

(ナイスプログラム)

 

作者へのメッセージ

 

研究課題に戻る。

 見学者への注意事項に戻る。