Entering Passive Mode

さて、テスト再開だ。
PuzzleSolver には変更は必要ないので、
そのままテストをすることができる。

まず、シートの解答欄をクリアした後、
解答欄を選択して実行してみよう。
1 回の実行で、縦と横の全ての行（列）に対して処理をする。

1 回目……（左図）

前回と比較して、空白部分も確定していることが分かる。

空白の確定に関する考え方は
塗り潰しの確定と同じということが分かった。

これを実装する場合、PuzzleLine の
SolveLine メソッドに追加するのが最も自然だ。
塗り潰しセルを確定するコードの後に追加しよう。

少しややこしいのは、前詰めと後ろ詰めの位置だ。

lStarts と lEnds という配列には、
後ろ詰めでの塗り潰し部分の開始位置、
前詰めでの塗り潰し部分の終端位置が格納されている。

昨日のテストで、忘れていることが明らかになった。
それは、空白セルの確定だ。

ヒントの数を見て考えると、塗り潰しセルに目が行くが、
ヒントの状態によっては、空白セルも確定する場合がある。

例えば、以下のパターンを調べてみよう。
ヒントが 2 3 で、
現在以下のような状態であるとする。

＿□＿■＿＿＿＿■＿□＿＿

さて、PuzzleSolver を仕上げてテストをやろう。

PuzzleSolver は、PuzzleLine を呼ぶだけで OK だ。
取りあえず、縦横全ての行に対して、
1 度ずつ Solve を呼び出すことにしよう。

Public Sub Solve()

    Dim c As Long
    Dim r As Long
   
    For c = 0 To m_oAnswer.Width - 1
        Call m_oColumns(c).Solve
    Next
   
    For r = 0 To m_oAnswer.Height - 1
        Call m_oRows(r).Solve
    Next

さて、実装ばかりだったんので、
ちょいとテストをしてみたい。
そのために、今までのコードを埋め込み、
テストできるような体制を作ろう。
って、やっぱり実装なんだが……

まず PuzzleLine だ。
PuzzleLine には、この何日かで作っていた実装を埋め込む。
SolveLine、PackFront、PackRear はここに入れる。

そして、保留にしていた Solve メソッドを作る。
Solve は PuzzleSolver から呼ばれるメソッドで、
基本的に引数は必要ない。
PuzzleLine 自体が行のことを知っているからだ。

両端詰めのルーチンはできたので、
これらを利用して、共通部分を調べる処理を作る。
これさえできればあと少しのはずだ。

まず、関数のシグネチャを考えてみよう。

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

ヒントの値を格納したオブジェクト Hints と、
現在の状態を保存しているセル配列 States を受け取り、
確定できるセルを確定して States に反映し、
戻り値として、確定できたセル数を返す。
矛盾が生じた場合は、-1 を返す。

右詰めは、左詰めと同じような考えでいける。
左からではなく右から考えていけばよいのだ。

左詰めの実装を逆方向にして実装する方法もあるが、
引数を完全に左右逆転して呼び出す方法もある。

後者の方がスマートで、アルゴリズムの保守性に優れるが、
今回は昨日の整理も兼ねて、左右逆転の実装をしてみよう。

では、もう少し掘り下げて実装してみよう。

処理を 1 つの関数として考えてみる。
PackFront という名前にしよう。
入出力となる引数は以下の通りだ。

・現在の状態配列: States（入力）
・ヒントの数値配列: Hints（入力）
・左詰めしたヒントの終端位置配列: Ends（出力）

Function PackFront(ByVal Hints() As PuzzleHintCollection, _
        ByRef States() As CellStateConstants, _
        ByRef Ends() As Long) As Boolean

昨日のアルゴリズムは非常に人間的であり、
プログラムのロジックにするには難しい。

まっさらな行に対して、左詰にするのは簡単だが、
既にある程度解答が求まっている場合は難しい。

まず、左に詰めることを考えてみよう。
後でこれをコード化することを考慮して、
小さな手順に分けて考えてみよう。

ののぐらむの解法を考えてみよう。

解答欄は 2 次元だが、解法の基本は
1 つの行や列に着目することである。

行や列のセル数とヒントの数値によって
自動的に幾つかのセルを決定させることができる場合がある。
それを見つけ出すのが最も重要である。

例えば、7 個のセルがあり、
そのヒントが、「2 3」の場合を考えてみよう。