このアーカイブは同期化されません。 mixi の日記が更新されても、このアーカイブには反映されません。
昨日のアルゴリズムは非常に人間的であり、
プログラムのロジックにするには難しい。
まっさらな行に対して、左詰にするのは簡単だが、
既にある程度解答が求まっている場合は難しい。
まず、左に詰めることを考えてみよう。
後でこれをコード化することを考慮して、
小さな手順に分けて考えてみよう。
ヒントがまったくない場合、
すべてのセルが空白となるので終わりだ。
それ以外の場合は、状態とヒントを照らし合わせていく。
まず状態を格納する配列が必要だ。
この配列には、現在の行の状態が格納されているとする。
例として下のような状態とする。
___■__□___■__□_■_
次に、ヒントの数値が必要だ。
これも例として下のような状態とする。
3 2 3
最初は、個々のヒントについて、左から順に当てはめてみる。
まず、当てはまる条件を考えてみよう。
単純に考えた場合、以下の条件が必要と思われる。
1. ヒントが占める範囲が、未確定又は塗り潰し確定である
2. ヒントの左右が塗り潰し確定ではない
最初のヒントで試してみよう。塗り潰しの長さは 3 だ。
最も左に当てはめてみると、以下のようになる。
(◆記号で書く)
◆◆◆■__□___■__□_■_
これはヒントの右に既存の塗り潰しがあるため、
条件 2 を満たさないからだめだ。
1 つ右にずらして次の位置を試す。
_◆◆◆__□___■__□_■_
これは両方の条件を満たすので、OK だ。
これにより、1 つ目のヒントの位置が確定した。
では、次のヒントを試してみる。塗り潰しの長さは 2 だ。
1 つ目のヒントの位置が決まっているため、
そこから空白を 1 つあける必要があるので、
最も左に当てはめてみると、以下の場所になる。
(●記号で書く)
_◆◆◆_●○___■__□_■_
これは既存の空白確定セルと被っており、
条件 1 を満たさないからだめだ。
1 つ右にずらして次の位置を試す。
_◆◆◆__○●__■__□_■_
上記と同じ理由でだめだ。更にずらして試す。
_◆◆◆__□●●_■__□_■_
これは両方の条件を満たすので、OK だ。
これにより、2 つ目のヒントの位置が確定した。
では、最後のヒントを試してみる。塗り潰しの長さは 3 だ。
同じく、2 つ目のヒントから空白を 1 つあける。
最も左に当てはめてみると、以下の場所になる。
(▲記号で書く)
_◆◆◆__□●●_▲▲▲□_■_
これは両方の条件を満たすので、OK だが、
最後のヒントには特別な条件がつくのだ。
3. 最後のヒントよりも後に塗り潰し確定セルがない
この場合、右から 2 番目に■があるのでだめなのだ。
この■は、少なくとも最後のヒントに含まれる必要がある。
そのため、まずは■が含まれるようにずらして試す。
_◆◆◆__□●●_■__△▲▲_
だめだ。
_◆◆◆__□●●_■__□▲▲▲
最後の位置で、条件を満たした。
これにより、すべてヒントの位置が確定した。
でも、これは明らかにおかしい。
この場合、右から 7 番目に■のセルが残っており、
このままでは、3 2 1 3 となり、ヒントと合わない。
実は、まだ条件があるのである。
4. 前のヒントとの間に塗り潰し確定セルがない
5. 最初のヒントの前に塗り潰し確定セルがない
今回の例のように、最初からいくつか確定している場合には、
このようなことも考えなければならない。
この場合、最後のヒントを決めた時点で、
その直前のヒントとの間に■のセルが残っている。
つまり、2 番目のヒントの位置はだめということであり、
再度 2 番目のヒントから調べなおす必要があるのだ。
_◆◆◆__□_●●■__□_■_
_◆◆◆__□__●●__□_■_
このようにして、2 番目のヒントの次の候補が見つかった。
最初のヒントの間に塗り潰し確定セルはないので、
4 の条件は満たしているので大丈夫である。
もし、4 を満たしていなければ、
最初のヒントからやり直しである。
さて、改めて最後のヒントを当てはめてみる。
_◆◆◆__□__●●__△▲▲_
_◆◆◆__□__●●__□▲▲▲
これで最後のヒントの候補が見つかった。
これですべての条件を満たした。
最終的に、左詰めにした場合、
以下のような位置になることが決定した。
_◆◆◆__□__●●__□▲▲▲