ユニファ開発者ブログ

ユニファ株式会社システム開発部メンバーによるブログです。

JavaScriptに数独のヒントをもらおう その1

新年明けましておめでとうございます。今年もよろしくお願いいたします。

先週、新年早々ハトにフンを落とされました。ウン(運)のついている柿本です。
※フンはきちんと拭き取って洗濯したのでご安心を!

2018年最後のエントリーで赤沼が発表している通りこの開発ブログでは年末にアクセスランキングが発表されるようです!つまり、年始のこのエントリーはかなり有利なはず!

もうランキングにノミネートされた気分でおりますが、冒頭にくだらないことを書いていると離反されてしまうので、本題に入ります。

今回のエントリーではJavaScriptを使って、数独のヒントを教えてもらうことにしました。

タイトルに「その1」とあることから察していただきたいのですが、今回のエントリーでは完成まで行き着いていないので悪しからず。「その2」以後があるかもわからないので悪しからず。

夫の威厳と数独

昨年の終わりにひょんなことから私の妻が数独にはまりました。

私はもともと数独が好きで、週末の新聞に載っているものを必ず解いているのですが(それ以外で私が新聞を開くことはない)、文系人間の妻が好きになるとは意外でした。

とはいえ、妻はそれほどスラスラ解けないので、少し詰まると「ヒントちょうだい」と言ってきます。もちろん私は上から目線で「これはね、、」と教えるわけですが、もっと上から目線の “僕が教えるまでもないよね” スタンスでいたいので、代わりにJavaScriptにヒントを教えてもらうことにしました。

今ここ

とりあえず今時点のものをこちらに上げました。
https://unifa-inc.github.io/sudoku_solver/

「ヒントちょうだい」ボタンを押すと、数字が特定できるマスをピンクにして教えてくれます。難しくてヒントが思いつかないと、開き直って5歳児になります。

f:id:unifa_tech:20190110222021g:plain
実際に動かしたGIF。途中一度だけ叱られます。

数独の解き方

数独ってそもそも何?という方はWikipediaあたりをご覧ください。

ja.wikipedia.org

簡単に説明すると、3×3のブロックで区切られた9×9のマス目に、それぞれの行・列・ブロックに1〜9が1つずつ入るように数字を埋めていくゲームです。

数独にはいくつかの解き方がありますが、一般的に大きく以下のステップに分かれます。
①ルールをそのまま適用する
②2国同盟(n国同盟)
③仮定法(背理法)

それぞれの説明はgoogle先生にお願いするとして、私は①でさらに以下の2つの解き方で進めます。

①-1:1つのブロックの1つの数字に注目して、以下を全ブロック×全数字(1〜9)に対して繰り返し行います。

  • 水平方向の2つのブロック両方にその数字がある場合、ブロック内の行が特定できる
  • 垂直方向の2つのブロック両方にその数字がある場合、ブロック内の列が特定できる

 ===> 行と列が交差しているマスにはその数字が入る

f:id:unifa_tech:20190110180059p:plain:w300
例(①-1)左上のブロックに注目した時に、赤枠と青枠が交差している黄枠のマスに1が入ることがわかる

①ー2:1つの行(もしくは列)の空マスに注目して、以下を全行(列)に対して繰り返し行います。

  • とあるマスに入れられる数字が1つのみである
  • とある数字を入れられるマスが1つのみである

 ===> どちらかの場合、そのマスにはその数字が入る

f:id:unifa_tech:20190110180150p:plain:w300
例(①-2)赤枠の行に注目した時、青枠と紫枠には1を入れられないため、黄枠のマスに1が入ることがわかる

完成形は③の解法まで適用されたヒントを出すことなのですが、このエントリーでは①ー1で解ける範囲内でヒントを出すことをゴールとします。

処理の流れ

左上のブロックから順番に1から9までの各数字について、以下の検証を行うことにします。

ターゲットとする数字(n)について、

  1. ブロック内に既にnが存在するかを確認
    • 存在する場合 → 次のブロックへ
    • 存在しない場合 → 処理を続行
  2. ブロック内の空きマスを確認
    • 空いていないマス → そのマスにはnは入らない、という制約を保持
    • 空いているマス → 処理を続行
  3. 水平方向(左右)のブロックにnが存在するかを確認
    • 存在する場合 → 同じ行にはnは入らない、という制約を保持
    • 存在しない場合 → 処理を続行
  4. 垂直方向(上下)のブロックにnが存在するかを確認
    • 存在する場合 → 同じ列にはnは入らない、という制約を保持
    • 存在しない場合 → 処理を続行
  5. 制約のかかっていないマスの数を確認
    • 1つのみの場合 → そのマスを色付け表示して処理を終える(そのマスに nが入ると断定できる ため、ヒントとして色付け)
    • 2つ以上の場合 → 次のブロックへ(このブロックでは nが入るマスを断定できない

ロジック

ソースコードをGitHubで公開しておりますのでそちらをご覧ください。

github.com

工夫と課題

工夫したところ: 制約の持ち方

『処理の流れ』で書いている「制約」をどうデータとして保持するか、に少し悩みました。

結果、3×3のブロックのマスを表す2次元配列に0と1を保持し(0:制約あり/1:制約なし)、最終的に「1」が1つだけの場合はnがそのマスに入ると断定できる、と判断する方法をとりました。

課題なところ: 公然の多重ループ

パズル系に関わらず、ゲーム要素のあるものを作ろうと思うと必ず多重ループや多重分岐の罠にハマる気がします。世にある多くのゲームたちもやはり多重ループが量産されているのだろうか?と疑問に思いました。

知見のある方、ぜひ教えてください。

終わりに

サーバーサイドエンジニアの仕事は、DBのデータを出したり入れたり、の繰り返しです。実際には検証したりくっつけてみたり離してみたりもあるのですが、意外とロジカルなロジックを書くことは少ないです。

なので、たまにこういうロジックロジックしたものを書くとなんだか心が温まりますので、皆様もぜひ!

それではみなさま、良い2019年をお過ごしください!

保育をハックするエンジニア募集中

ユニファでは一緒に働く仲間を募集中です。DBのデータをただ出し入れすることに飽き飽きしている方、もっともっと出し入れしまくりたいぜ!という方、ぜひご応募ください!

www.green-japan.com