概要
こんにちは。Aidemyの刀根です。
Firebaseを駆使して数独を解くwebアプリを作成します。
ソースコードの全容はGithubの方で見てください。この記事に載せちゃうと記事の長さがえげつないことになるので。。。
Githubはこちら
また、今回作成したwebアプリはこちらで公開しています。
システムの概要
firebase hostingで最低限のフロントエンドを作り、firebase cloud functionで数独を解くバックエンドを作成します。
回答アルゴリズムを実装する前に・・・
まずはフロント側を実装していきます。今回はjQuery使ってゴリゴリ実装していきます。
そして今回は作ったものをfirebase hostingでホスティングします。
今回はデバッグのために各ますに入る数字の候補を確認できるようにもしました。
index.html
index.css
send.js
アルゴリズム
実装方針としては
1. 人が解くのと同じ方法である程度空きマスを埋める
2. バックトラックで残りを埋める
の２段階で実装していきます。
人が解く方法を実装していく
今回はこちらのサイトに掲載されている解法からいくつか抜粋して実装していきます。
ルールによる候補削除
まずは数独のルールに則り候補を削除していきます。
この処理の流れは以下の通りです。
1. 左上から順番に走査していく
2. 数字が入っているマスに当たったら、その行・列・ブロックに該当するマスの候補からその数字を消す
3. 右下までチェックし終わったら、確定できるマスがないかチェックしていく
4. もし新たに確定したマスがあったら、また1.に戻り繰り返す
今回はここまで
だいぶ長くなってしまうので今回はここで一旦区切ります。次の記事でこの続きを書くのでそれまでしばらくお待ちください。（12月13日公開予定）
ちなみにまだバックトラックを実装していませんが簡単な問題ならこれだけでも解くことが可能です。