Entering Passive Mode

カテゴリ 'VBA, VB Classic' の記事
< 1 2 3 4 5 >

PuzzleSolver #6: 飾り付け

行が選ばれ 確定される

だいぶ満足できるところまできたが、
もう少し飾り付けをしよう。解答中の行を可視化したい。

現在は、縦横のヒントを順に検索するだけだが、
行や列の解答を求めようとしても答えが出ない場合、
その行について調べてあきらめたのか、
まったく調べていないかがわかりにくいからだ。

解答中の行が見えるようにしておけば、
明らかに現状では解けない行に対する処理などの
無駄な処理を見つけやすくなる。

SolveAction: Solve マクロクラス

Solve マクロにクラスの皮を被せて、
イベントを受け取れるように、
SolveAction クラスを作成しよう。

名前は重要でないので適当につけたが、
SolveMacro クラスとかでもいいかも。

実際の Solve マクロは、
F8 ダイアログから呼び出すためだけのために残しておき、
実装はごっそり SolveAction に移行しよう。

解答進捗の可視化

現在は、マクロを実行するといきなり結果が表示される。
それはそれで急ぎのときは便利だが、
デバッグ中や、進捗を視覚的に確認したい場合は、
随時画面上に反映されたほうがよい。

結果がいきなり表示される理由は、
Solve マクロの実装にある。

Solve マクロは、PuzzleSolver を作成し、
Solve メソッドを実行して解答を求め、
解答が出てから Answer プロパティ経由で解答を取得し、
一気に画面に反映させる手順を取っているからである。

PuzzleSolver #5: 解けるまで解く

さて、PuzzleSolver はテスト仕様であり、
今までは縦横のヒントを一度実行するだけだった。

このままでは、一度行列のスキャンを行うだけで、
PuzzleSolver や PuzzleLine などのオブジェクトが
解体されてしまい、昨日作った進捗管理が意味を成さない。

そこでこれを改造し、PuzzleSolver の Solve 呼び出しで、
一気に答えが出るところまでもっていこう。

中には、これらのアルゴリズムで解けない問題もあるため、
終了条件としては、1 セルも解けなくなるか、
エラー(矛盾)が発生するまでということにしよう。

PuzzleLine #4: イベントの受け取り

これで 2 つのアルゴリズムが準備できた。

PuzzleLine を改造し、状況によって
アルゴリズムを切り替えて自動的に解答するようにする。

行の解答状況を記憶するために、
以前準備しておいた、m_lProgress フィールドを使用しよう。
この値によって、進捗度を調べることにする。

では、Solve メソッドを書き換えてみる。

IPuzzleLineSolver: 解法アルゴリズムの分離

さて、帰謬法を応用したの実装を導入したいところだが、
PuzzleLine に追加して肥大化させるのはあまりよくない。

複数のアルゴリズムをうまく使い分けるためにも、
PuzzleLine から解法の実装部分を切り離すことを考えよう。

そこで、IPuzzleLineSolver というインタフェースを定義し、
解法は個別のクラスとして、インタフェースを実装させる。

IPuzzleLineSolver は、なるべくシンプルにしよう。
関数的な役割を持つインタフェースなので、
必要なのは、メソッド 1 つだけとする。

帰謬法の実装

では、帰謬法の実装をしてみよう。

1 セル確定するまで処理を行うメソッドを作ってみる。

Function SolveLineByRaa( _
        ByVal Hints As PuzzleHintCollection, _
        ByRef States() As CellStateConstants) As Long

    Dim fFilled    As Boolean
    Dim fChecked    As Boolean
    Dim c          As Long

帰謬法

では、帰謬法を応用して考えてみよう。

矛盾していることもあるので、
厳密には、数学における帰謬法とは少し違うが、
これを応用して、以下のように考えることができる。

1. 未確定セルを 1 つ選ぶ。
2. セルを塗り潰しと仮定し、矛盾するか調査する。
3. セルを空白と仮定し、矛盾するか調査する。
4. 両方とも矛盾する場合、解答前から矛盾している。
5. 両方とも矛盾しない場合は、確定できない。
6. 片方が矛盾しない場合、そちらで確定する。

アルゴリズムと性能

ののぐらむに限ったことではないが、
特定の命題を成し遂げるためのアルゴリズムは、
たった一つだけであるとは限らない。

例えば、アルゴリズムの代表ともいえる、
ソートやサーチには、色々な手法が存在し、
それらにはそれぞれ良し悪しがある。

今回の題材に当てはめてみると、最初に考えた手法は、
特定の領域が占有する部分を確定する思考ルーチンだ。
昨日の考察により、この方法では確定できないが、
人間的に見ると確定できる部分があることが分かった。

解けない行

基本的に、昨日のアルゴリズムを順番に適用して行けば
大抵の問題は解けるのだが、
難解な問題には、それだけでは不十分なことがある。

例えば、以下のような場合を考えてみよう。

_____□_□_____

ここで、ヒントは、2 2 だとする。
従来の考察でいけば、前と後ろに詰める。

< 1 2 3 4 5 >
このページのトップへ戻る
© 2008 Project Loafer/Project Fireball and all blog writers. Powered by Nucleus CMS