このアーカイブは同期化されません。 mixi の日記が更新されても、このアーカイブには反映されません。
では、帰謬法を応用して考えてみよう。
矛盾していることもあるので、
厳密には、数学における帰謬法とは少し違うが、
これを応用して、以下のように考えることができる。
1. 未確定セルを 1 つ選ぶ。
2. セルを塗り潰しと仮定し、矛盾するか調査する。
3. セルを空白と仮定し、矛盾するか調査する。
4. 両方とも矛盾する場合、解答前から矛盾している。
5. 両方とも矛盾しない場合は、確定できない。
6. 片方が矛盾しない場合、そちらで確定する。
この方法を使えば、従来の方法では判断できなかったセルを、
確定させることができる可能性が出てくる。
ただ、これは 1 つのセルを決める手法だ。
行に対してこの方法を適用する場合、
更に考える必要がある。
行の解法アルゴリズムでは、完全な答えを求める必要はない。
1 箇所でも確定させることができたのであれば、
1 度の処理でなるべく多く確定させる必要はないのだ。
そのため、「どれくらいまで解くか」によって、
進捗度と時間のバランスの違う幾つかの考え方がある。
1. 未確定セルを順に調べ、1 つ確定できればそこで終わる。
2. 未確定セルを全て 1 度だけ調べる。
3. 確定できなくなるまで未確定セルを調べ続ける。
1 は、最も速く処理を終わらせることができる。
2 は、バッファ確保や繰り返しなどのバランスに優れる。
3 は、1 度呼ぶだけで確定できる限り確定される。
さて、どうするか。