このアーカイブは同期化されません。 mixi の日記が更新されても、このアーカイブには反映されません。
基本的に、昨日のアルゴリズムを順番に適用して行けば
大抵の問題は解けるのだが、
難解な問題には、それだけでは不十分なことがある。
例えば、以下のような場合を考えてみよう。
＿＿＿＿＿□＿□＿＿＿＿＿
ここで、ヒントは、2 2 だとする。
従来の考察でいけば、前と後ろに詰める。
◆◆○●●□△□△△△△△ （前詰め）
◇◇◇◇◇□◇□◆◆○●● （後ろ詰め）
この結果で、ヒントや空白の位置を考えると、
重なる部分がないため、どこも確定できないことになる。
しかし、これを人間が考えた場合、
明らかに確定できる部分がある。それはこの位置だ。
＿＿＿＿＿□☆□＿＿＿＿＿
ヒントが 2 以上の長さを持つので、
1 つの隙間が埋まることはないはずなのである。
また、以下のような状況も考えてみよう。
＿＿＿＿＿□■＿■□＿＿＿＿＿
ここで、ヒントは、3 1 3 する。
これも、従来の考察でいけば、前と後ろに詰めてこうなる。
◆◆◆○●□■▲■□▽▽▽▽▽ （前詰め）
◇◇◇◇◇□■◆■□●△▲▲▲ （後ろ詰め）
これも、どこも確定できないという結果となるが、
実際は、以下の位置を確定することができる。
＿＿＿☆＿□■★■□＿☆＿＿＿
以前の解法では、重なる部分しか考慮していなかったため、
特定のヒントが占める領域についての答えしか出ない。
上記のように、どのヒントが占有するかは分からないが、
塗り潰しか空白かどうか確定することも考えられるのだ。
明日は、このような考え方を、
どのように実装に反映させるか考えてみよう。
実際に問題を作るのは難しいので、
解けない問題の例を挙げることができないのが残念。
誰か問題を提供してくれないかなぁ。