ユニファ開発者ブログ

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

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

今更聞けない!?加速度ってなに??( ? _ ? )

みなさま、あけましておめでとうございます。 エンジニアの田渕です。

旧年中は大変お世話になりました。 本年も、よろしくお願いいたします。

昨年の最後のブログ更新となった赤沼の記事にも記載あります通り、ユニファ開発者ブログも開始から二年を超えまして、、、 これもひとえに、読んでくださる方がいらっしゃるおかげです。 ありがとうございます。

さて、そんな開発者ブログですが、2019年最初のブログは全然新年に関係のないネタです。

昨年はルクミー 午睡チェックの正式リリースとともに、いろんな場でサービス説明をさせて頂きました。 その中で、質問されるたびにその場ではうまいこと説明が出来なくてモヤモヤしていたネタをお届けしたいと思います。

続きを読む

開発者ブログ二周年&2018年人気記事ランキング

 みなさまこんにちは、赤沼です。あと数日で2018年も終わってしまいますね。ちょっと前に年が明けたと思ったらもう年末で、一年なんてあっという間です。まだまだ終わってもらっちゃ困るとも思いつつ、そうは言っても時は平等に過ぎて行くので、同じ時間の中でもレバレッジを効かせられるように動いて行きたいと思う今日この頃です。

 そんな中、この開発者ブログも今月で開設から二周年を迎えました。ご覧いただいている皆様、ありがとうございます。開始当初は続くかどうかわかりませんでしたが、だいたい週一本ペースでなんとか途切れることなく続いてきました。来年も変わらずアクティブに更新していけるようにしたいなと思いつつ、年末ということもありますので2018年に人気のあった記事をランキングしてみました。上位5本を紹介してみたいと思います。

No. 1: Perceptual Hashを使って画像の類似度を計算してみる

 画像の解析というと最近は機械学習や深層学習というイメージですが、こちらは各画像データからHashを計算し、その値の近さで類似度を判断するというものです。

tech.unifa-e.com

No. 2: iOSのCoreBluetoothの実装をしてみる

 最近はIoTデバイスも増えてきて、BLEでスマートフォンと連携しているものも多くなってきています。こちらは iOS で BLE の Central と Peripheral の実装をした記事になります。

tech.unifa-e.com

No. 3: イメージで覚えるReact + Redux

 フロントエンドの実装についてはデファクトと言えるものがなかなか決まらない状況ですが、その中でも React はポジションを得てきている気がしています。こちらは Rails と React, Redux を組み合わせての実装を紹介した記事になります。

tech.unifa-e.com

No. 4: Swift 4 で UserDefaults を簡単に扱う

 こちらは iOS の UserDefaults を、Kotlin の SharedPreferences と同じように簡単に扱う方法を紹介した記事です。

tech.unifa-e.com

No. 5: td-agent(Fluentd) を利用したログ収集

 ログ収集といえば Fluentd がかなり使われているかと思いますが、ユニファでの Fluentd(td-agent)を使用してのログ収集方法を紹介した記事になります。

tech.unifa-e.com

 開発者ブログは開発メンバーが持ち回りで書いているので、記事のジャンルも様々ですが、その中でも画像解析系やiOS、 IoT関連、インフラ関連の記事の注目度が比較的高かったようです。この辺りの領域はユニファのサービスにも密接に関係するところでもあり、関心を持っていただけていることは嬉しいですね。今年の年初からはR&Dチームも立ち上げて活動していますので、画像解析等は今後さらに力を入れていきたいと思っています。

まとめ

 ブログ二周年ということで、はてなブログのプロアカウントの契約も更新しましたし、最近では Podcast(UniFa Developer's Podcast) の配信もゆるく始めましたので、さらに情報発信を多くしていけると良いかなと思っています。そんなわけで皆様2019年もユニファをよろしくお願いいたします。良いお年を。

刑務所長問題の続き

こんにちは、ヘルスケア事業部のちょうです。前回のクイズ問題はいかがでしょうか。

実はその問題、続きがあります。(前回の問題分からなくてもオーケーです。条件はまったく新しくなりますので)

「The Art of Multiprocessor Programming」第一章 問題5

The same warden has a different idea. He orders the prisoners to stand in line, and places red and blue hats on each of their heads. No prisoner knows the color of his own hat, or the color of any hat behind him, but he can see the hats of the prisoners in front. The warden starts at the back of the line and asks each prisoner to guess the color of his own hat. The prisoner can answer only “red” or “blue.” If he gives the wrong answer, he is fed to the crocodiles. If he answers correctly, he is freed. Each prisoner can hear the answer of the prisoners behind him, but cannot tell whether that prisoner was correct.

The prisoners are allowed to consult and agree on a strategy beforehand (while the warden listens in) but after being lined up, they cannot communicate any other way besides their answer of “red” or “blue.” Devise a strategy that allows at least P − 1 of P prisoners to be freed.

続きを読む

RailsをAmazon ECS(AWS Fargate)で運用する際のログ設定で工夫した点

こんにちは、Webエンジニアの本間です。

今回、Railsアプリケーションを Amazon ECS、しかも AWS Fargate の上で運用する機会に恵まれました。 その中でログに関する話を書こうと思います。

というのも、これまでのEC2インスタンス上でのログと、ECSでのログでは扱いが大きく異なっており、色々と注意&工夫しないと障害調査等で苦労することがわかったためです。 従来から変更しないといけない点、それを見据えて工夫した点をばーっと書いていきたいと思います。

続きを読む

JAWS-UG横浜 #14 AWS re:Invent 2018 RecapのLT枠で参加して初LTしてきました

こんばんは!
ユニファでインフラ担当していて、
LT後の懇親会に参加し終電間違えてしまい深夜バスで帰りながらこのブログ書いてる… . すずきです…

先週AWS re:inventがありましたね! 私は日本にいましたがいろんな新サービス、アップデートがありとてもワクワクしました。 数が多くて全然追えていませんが…

そんな中本日「宇宙一早いAWS re:Inventふりかえりイベント」に参加してきました。 今回LT枠で参加したのは @ijin さんにどこかでLTしてみなよとアドバイスもらっていて、 ちょうどre:inventがあり、本イベントがあったのとLT枠がなんとか余っていたので申し込ませていただきました。

では本題

続きを読む