2006 年 5 月 20 日 22 時 2 分

左詰めの手順


このアーカイブは同期化されません。 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 を満たしていなければ、
最初のヒントからやり直しである。

さて、改めて最後のヒントを当てはめてみる。

_◆◆◆__□__●●__△▲▲_
_◆◆◆__□__●●__□▲▲▲

これで最後のヒントの候補が見つかった。
これですべての条件を満たした。

最終的に、左詰めにした場合、
以下のような位置になることが決定した。

_◆◆◆__□__●●__□▲▲▲



Copyright (c) 1994-2007 Project Loafer. All rights reserved.