2012年03月03日

ナイト(騎士)巡回問題

   このエントリーをはてなブックマークに追加 Clip to Evernote
ナイト巡回問題とは、チェスのナイトを、チェス盤の上を動かし、すべてのマスを通り、
最初の場所に戻ってくる経路を求めるというものです。

Gushwell's C# Programming Pageに掲載しました。
ナイト(騎士)巡回問題
C#+ Silverlightで解いています。

KnightTour

  

Posted by gushwell at 22:30Comments(0)TrackBack(0)

2010年09月12日

Triangle15パズル

   このエントリーをはてなブックマークに追加 Clip to Evernote
久しぶりに、Gushwell's C# Programming Pageの「C#プログラム小品集」にプログラムをアップしました。

「横に並んだ2つの数の差(正数)をその下の○に入れる」という条件を満たして、○を組み合わせた逆三角形に1~nまでの数字を配置するというパズルを解くプログラムです。

Triangle15パズルというのは、僕が勝手に付けた名前です。正式な名前はわかりません。

Solveボタンを押すと、解の探索を開始し、解答を表示します。


解は2つありますが、その一つだけを表示しています。興味がある方は自力で解いてみてください。

順列を求める応用でこの問題を解いています。 ソースコードは、こちらに掲載しています。  
Posted by gushwell at 22:23Comments(4)TrackBack(1)

2009年07月05日

[パズル]多角形の完全グラフ

   このエントリーをはてなブックマークに追加 Clip to Evernote
今回の問題は、前回の「[パズル](n*2+1)多角形の一筆書き」の続きです。

今度は、多角形の頂点の数が偶数のときでも、完全グラフが描けるようにするプログラムです。
でも、偶数のときは一筆書きはできないので、できるだけ、ペンの移動が少なくなうようにというもが問題なのですが、ペンの移動量については無視し、とりあえず、完全グラフが描かれるようにしました。
ただし、奇数のときには、一筆書きになるようになっています。

頂点の数が奇数か偶数かで処理を分岐させないで、これをやれるようにしています(SearchPathメソッド)。
でもちょっとややこしい再帰処理になってしまいました。
PerfectGraphクラスのほうは、LINQ使ってそれぞれのメソッドを簡潔に書けたと思います。

前回同様、WPFで、DoubleAnimationを使ってアニメーションさせています。この部分は、前回のコードと変わっていません。(多分)

PerfectGraph1PerfectGraph2

XAMLとC#のコードを張り付ければ、動くと思うので、興味ある方は動かしてみてください。

なお、今年初めから『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を解き、ここに掲載してきましたが、興味ある問題は、ほぼやり終えたので、いったん終了したいと思います。
頭の体操になったし、LINQの勉強にもなったし、再帰処理の勉強になったし、最後は、WPFにも挑戦できたしで、なかなか楽しかったですね。
『続・ナノピコ教室』も手元にあるので、こちらもいつか挑戦したいと思います。




※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。  
Posted by gushwell at 22:35Comments(0)TrackBack(1)

2009年06月07日

[パズル](n*2+1)多角形の一筆書き

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
自然数 n を入力した時に、ノード数 n * 2 + 1 の完全グラフを一筆書きするようなプログラムを書いてください。スタートは画面上の一番上胃に位置する頂点とします。 完全グラフとはどの二つの頂点も一本の線で結ばれているグラフのことです。

------
この問題は、本当に一筆書きができているのかを目で確かめたかったのと、動きがあったほうが面白いので、WPFのアニメーションを使ってみました。

OneStroke01 OneStroke02


まずは、問題の本質部分である一筆書きを求めるクラス OneStrokeを作成します。
このコンストラクタで n を受け取り、そこから 正多角形になるように(n*2+1)個の座標を配列にセットします。コメントにも書きましたが、本当は、OneStrokeで扱う座標は、仮の座標であって、表示するときにこの座標から本来の表示座標に変換したいところですが、面倒なので、実際に表示する実座標を扱っています。

GetPointsメソッドが、一筆書きになるような座標のシーケンスを返す部分で、このプログラムの中心になる部分です。実際に動かしてから、このコードを読んでいただいたほうが、理解が早いと思います。
簡単に書くと、まずは左隣の点まで線を順に引いてゆきます。左隣の点までの線が引き終わっていたら、ひとつ置きの点まで線を引き、これを繰り返し、次に2つ置き... と続けてゆきます。
実際には、ここでは点のシーケンスを求めているだけです。

で、実際にWPFで描画しているのが、Window1クラスのほうです。XAML側ではアニメーションの指定は特にしていません。
すべてC#のコードでアニメーションを行っています。WPFについては素人なので、よくわからないんですが、点の数も入力値で決まるので、事前にXAMLで指定しておくことはできないのかな思います。
単に僕がXAMLの書き方を知らないってだけのような気もしますが... どなたかわかる方教えてください。

DrawAnimatedLineメソッドが一つの直線を引くアニメーションを担当しています。で、線が引き終わると、myStoryboard_Completed イベントハンドラが呼び出されるので、ここで、次の線を引くために、再度、DrawAnimatedLineを呼び出し、これを繰り返しています。
そういうことで、Storyboard と DoubleAnimation を使ったC#のサンプルコードとしても面白いものになったかなと思います。

以下、今回のプログラムコードです。



※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。   
Posted by gushwell at 22:51Comments(0)TrackBack(0)

2009年05月17日

[パズル]円環の塗り分け

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
放射状にn等分された円環を2色で塗り分けて、図のように内環と外環とを切り離します。外環を固定し、内環を回転してずらしたとき、どの位置でも(最初の位置を除き)内外同色の組み合わせと、内外異色の組み合わせの数の差を1以下にしたいとします。
n=31の時に、このような塗り分け方をひとつ求めるプログラムを作ってください。
Ring_335_297
図の例では、
同色:2つ
異色:6つ
となり、差は4となり、当てはまりません。

----
これをどうやって実現するかですが、問題がn=31であり、色が2色なので、ビット配列で円環を表すこととします。

そのために、BitArrayというクラスを作成します。
このクラスは、Rotateという要素を右にひとつずらすメソッドがあります。
はみ出た要素は、ぐるっと回って先頭に格納されます。
つまり、円環を表しているということです。
またインデクサも用意し、bits[n] のようにアクセスできるようにしています。 各要素のとりうる値は、1 と 0 です。
クラス Ringは、外環と内環をデータに持っています。IsOKメソッドは、どの位置でも、内外同色の数と内外異色の数の差が1以下ならば、trueを返します。
つまり、その円環は、求める円環ということになります。
このIsOKの下請けメソッドとして、Turn と、CountSameColorがあります。
同じ色の数がわかれば、異なる色の数もわかるので、カウントするのは、同色の数だけです。
Printメソッドは確認用です。

クラスSolverは、円環の配色のパターンすべてに対して、求める円環かどうかを調べていきます。問題は一つだけ求めれば良いので、求まった時点で、ループをやめています。
なお、すべての塗り分けパターンを求めるのは、数字を 1から2,3,4.. と加算することで、そのビットパターンを求めています。これを 0 と 1の組み合わせとして求めようとすると、もっと複雑なコードを書かなければならなくなります。

以下が、C#で書いたコードです。今回は、ちょっと LINQ度が低かったかな。
僕のPCだと、 46秒かかっています。もっと効率のよいやり方があるとは思うのですが、深入りはしていません。

※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。   
Posted by gushwell at 21:48Comments(0)TrackBack(0)

2009年05月06日

[パズル]凸多角形の外周

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
任意の数の点が与えられた時、点と点を結び凸多角形の外周を作ってください。 凸多角形の外側には点が存在しないようにします。

--------------

FrameLine01FrameLine02


この問題は、Consoleアプリケーションとして解いても面白みがないし、検証も厄介なので、WPFアプリとして作成してみました。
どうやって解くかは、C#のコードに挿入したコメントを読んでください。

今回もLINQを使っています。IEnumerableは、もう手放せませんね。
WPFの勉強になりました。

実は、この問題は、外周の中の点も結んで、線分が交差しない三角形の編み目を作るという問題の一部なのですが、 三角形の網目を作るアルゴリズムが思い浮かばなかったのでパスしています。

※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。  
Posted by gushwell at 22:58Comments(0)TrackBack(0)

2009年04月26日

[パズル]オセロ最短詰め

   このエントリーをはてなブックマークに追加 Clip to Evernote
問題
黒と白のプレイヤーが二人で協力して、番面の石を黒か白一色にする最短の手順を求めよ。
石を裏返すルールはオセロのルールをそのまま採用する。

『ナノピコ教室』では、最短の9手解をひとつだけ求めるプログラムを作ってください、という問題ですが、ここでは、すべての解を求めるプログラムをC#で書いてみることにしました。
ただし、最初の一手は、どこに打っても、回転させれば同じことになるので、 3−4固定にしています。

プログラムを作っていざ実行したら、予想以上に時間がかかってしまいます。
そのため、スレッドを起動し、キーボードから Q が押されるまで、解を求め続けることにしました。

これまでこのブログに掲載してきたパズルの問題は、探索するのに深さ優先のアルゴリズムを採用していましたが、ここでは、幅優先のアルゴリズムを採用しています。こうすることで、最短手から解を表示するようにできます。

ちょっと苦労したのは、これまでのパズルは、プレイヤーはひとりだったわけですが、このパズルはプレイヤーが2人いるので、その制御に手こずりました。

実は、この文章を書きながら、プログラムを実行させているのですが、まだ全部求め終わっていません。

と、ここまで書いたら、OutOfMemoryExceptionが発生してしまいました。
プログラム内で用意しているキューがメモリを食いつぶしてしまったみたいです。 求めた結果のいくつかを検証してみましたが、合っているようなので、 考え方自体はよいと思うのですが。。。
たしかに、キューに入っている数がものすごく多いので、この数だけ、Boardオブジェクトのクローンを作っているので、メモリのバカ食いです。

10手解も含めて求めようとしていたので、これは諦めて、9手解のすべてを求めるように修正しました。

10手解まで求めようとすると、もっとメモリを使わないようにデータ構造・アルゴリズムまで含めて設計し直しが必要そうです。そこまでの気力がないので、とりあえず、このままコードを掲載します。

興味のある方、是非、直してください。


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。
  
Posted by gushwell at 22:16Comments(0)TrackBack(0)

2009年04月19日

[パズル]数独を解く

   このエントリーをはてなブックマークに追加 Clip to Evernote
数独は、あまりにも有名なパズルなので、説明するまでもないと思います。
この数独を解くプログラムを書くのが今回の問題です。

数独について知らない方は、こちら
http://www.sudoku.name/rules/jp
をご覧ください、また、このサイトでは、無料で数独に挑戦することもできるようです。
http://www.sudoku.name/index-jp.php

これも、今までの問題同様に、再帰処理による総あたり処理をしています。
今回もLINQを使ってます。LINQ便利ですね。

コメント途中まで書きましたが、面倒になったので、やめました。
あとは、以下のC#のソースコードを読んでください。

Mainメソッドのnums変数の値を書き変えれば、雑誌などに載っている 問題の答えを知ることができます。
なお、Mainメソッドで解いている数独の問題は、解答が2つ存在します。

コンソールアプリとして作成しているので、どなたかGUIをつけてください。


※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題を一部変更し、GushwellがC#で解いたものです。   
Posted by gushwell at 21:57Comments(0)TrackBack(0)