概要
こんにちは。Aidemyの刀根です。
Firebaseを駆使して数独を解くwebアプリを作成します。
今回は後編です。前編はこちら
ソースコードの全容はGithubの方で見てください。この記事に載せちゃうと記事の長さがえげつないことになるので。。。
Githubはこちら
また、今回作成したwebアプリはこちらで公開しています。
前回のあらすじ
フロント側の実装を終え、バックエンドの回答アルゴリズムの実装を開始。
とりあえずルールに則り、「縦横・ブロックに同じ数字が入らない」というルールに従い候補を絞るところまで実装しました。
これだけでも簡単な問題であれば解けてしまうのですが、以下の画像のように難しい問題は解けません。
(ちなみにこの問題はこちらのページで生成させていただきました。)
そこで、さらに回答アルゴリズムを洗練していきます。
人が解く方法の続きを実装する前に・・・
まずはとにかく解けるようにしていきたいので、先に総当たりのアルゴリズムを実装していきます。
バックトラック
バックトラック法とは総当たり方法の一種で、とりあえず適当に行けるところまで行ってみて、ダメだったら戻ってやり直す方法のことです。詳しくはこちら。
数独の場合は、片っ端から候補の数字を入れていき、矛盾が生じたらまた別の数字を入れて・・・という過程を繰り返すことで総当たりしていきます。
これを左上のますから走査する中で行なっていきます。
各ますでの処理の流れは以下の通りです。
- 候補として残っている数字を今見ているますに入れる
- ルールに反していないかチェックする
- ルールに反していなければ次のますへ行く
- ルールに反している場合は別の候補を今見ているますに入れる
- 全ての候補がルールに反してしまう場合は、１ます戻る
これをまず一旦実装します。
詳細な実装はGitHubをみてください。
byBackTrackHelper.ts
いざ、実行！！
先ほど解けなかった問題を解かせてみました。
解けました。
もっと難しい問題だとどうなる？
実はこれ、かなり予想外の展開です。本当はここでtimeoutして、もっと候補を少なくする必要があるという流れにしたかったのですが・・・
そこで、さらに難しそうな問題をこちらのページからお借りして解かせてみることにしました。
その結果・・・
ちゃんとtimeoutしてくれました。（画像はfirebase cloud function側のログ）
やっぱりもっと候補を少なくする必要がありそうですね！
人が解くアルゴリズムをさらに実装
ということで、人が解くアルゴリズムをさらに実装していきます。
行or列orブロックの中で１箇所しか入る場所がないパターン
例えばこのように候補が残っている行があった場合を考えます。
この行では、3が入る場所が１箇所(左から3列目)しか残っていないのでそこに3を入れることができます。
同様のパターンを行・ブロックでも処理できるように実装します。
byLastOneHelper.ts
行or列の中で2~3箇所しか入る場所がなく、それが全て同じブロックのパターン
例えば、上3行の候補が画像のように残っている場合を考えます。
この時画像の上から３行目に注目すると、1が入るマスは２箇所しかなく、かつ同じブロック内であることがわかります。
つまり、画像内の右のブロックにおいては１が入るのはその２マスだけで、他のマスには入らないことがわかります。
これも実装します。
byLast2Or3InSameAreaHelper.ts
ブロックの中で2~3箇所しか入る場所がなく、それが全て同じ行or列のパターン
これは直前で述べた奴の逆パターンです。
例えば、右3列の候補が画像のように残っている場合を考えます。
この時画像の下ブロックに注目すると、1が入るマスは２箇所しかなく、かつ同じ列であることがわかります。
つまり、画像内の右から２列目においては１が入るのはその２マスだけで、他のマスには入らないことがわかります。
これも実装します。
byLast2Or3InSameAreaHelper.ts
ここまでやったら・・・
あとはバックトラックでもそこまで時間がかからないので、バックトラックを利用します。
だいぶ候補を絞ったのでそれなりの速さで解けるようになっています。
まとめ
今回はアドベントカレンダーの一環で数独を解くwebアプリを一から作成しました。
もし今後も更新するなら、バックトラックなしでも解けるようにしていきたいですね。