Entering Passive Mode

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

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

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

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

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

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

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

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

＿＿＿＿＿□＿□＿＿＿＿＿

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

さて、テスト再開だ。
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 を返す。

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

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

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