読者です 読者をやめる 読者になる 読者になる

のだなのだ

ほげ〜

Sudoku Solver

はじめに

 なんで急に数独を解き始めたかというと、がっこの先生が図書室にプログラミングコンテストチャレンジブックを入れてくれて、それをやっと借りることができて(プログラミングの本としては超人気、現在5件も借りられてる)、それの二章に再帰関数が書いてあって、その部分和集合問題(n個の要素を持つ集合が与えられて、その和がkとなる部分集合は存在するかどうかを判定する問題)を理解したので、「チョット難しめなの解いてみるか〜」とおもったからです。(日本語力がないのでここまですべて一文)

 ちなみに私は数独超ニガテです。小学校6年ぐらいの時以来解いてないし、ちょっとでもむずかしい問題は解けません。

 

アルゴリズム

 深さ優先探索depth-first search)です。その名の通りまずノードをできるだけ深いところまで伸ばしてから最も近い未探索ノードへ遷移します。

 数独は深さが定まらない木には使えませんが、数独は問題にかかわらず深さは常に一定以下(9×9なら最大81)なので使えます。

 また数独の問題は基本的に解を一つしか持ちません(持つ場合もあるがすぐに対処できる)。そのため、不正解となる探索はすべての空きマスを埋める前に空いているマスに打てる数字の候補がなくなります。そのため終了条件は「探索をおこなって空きマスがなくなったら終了」となります。

 

実装

www.dropbox.com

こういう感じで実装しました。(一部の英語がカス!)

 アルゴリズムのところでも言ったように、すべての空きますが埋まったら表示してtrueを返すというふうに書いてあります。実は最初に判定するところを組んでいたのですが、途中で枝刈りがすでに十分であることに気づいて消しました。(nは空きマスの番号)(つまり深さ)

f:id:coilgunrailgun:20170207073358p:plain

 ちなみに斜めでも1〜9を揃えたい場合は斜めで判定するメソッドを書いて、return trueをreturn target.jadge();的な感じに変えればいけます。

 解が複数あるときは、trueをfalseに変えればいけます。(下のようにいっぱい表示される)

f:id:coilgunrailgun:20170207074038p:plain(画像長すぎ)

 この状態のプログラムでも9×9の数独ならば問題にほぼ関係なく瞬時に、世界最高難易度と言われている問題でも0.5秒程度で終わります。

 

16×16への挑戦

 9×9が瞬殺できるなら16×16に挑戦するまでです。16×16は計算量が飛躍的に向上するようで(詳しい近似とかはしらんけど)、今までのものをそのまま拡張しただけでは現実的な時間(数時間)内に終わりそうにありません。(目標は数秒以内)(これも問題によりけりだけど)

 

高速化手法① 分岐の少ない順にソート

 数独を解くときに左上から当てはめていくドアホなんて普通いません。普通候補が少なそうなところから順に埋めていきます。

 途中で枝が刈れない木なら、分岐の少ないところから埋めたところでノードの総数は変わりません。しかし数独の探索木の場合、探索を進めて行くと多量の枝刈りが自動的に行われるので分岐の少ないところから埋めたほうが有利に埋めていくことができます。

 実際、実験用に適当に選んだ問題は普通に解くと右側の4ブロックが早い段階で埋まるらしく、プログラムでもそこを先に探索されるように左上に配置して入力したら8分ぐらいとかなり速くなりました。

 ただ、どこのマスの候補が一番少ないかは常に変化します。なのでノードごとにソートし直すものを組んだところ、400分経っても終わりませんでした。

 これの効果が薄かった(あるいは確認できなかった)のにはいくつか理由があります。

 

・まず一つに、ノード一つあたりの処理コストが向上したことです。すべての空きマスに対して打てる数を列挙してソートするので非常に高コストです。

・そして二つ目に、脈絡のない場所を次々に探索しすぎという問題です。横や縦に並んだブロック中の空きマス(相互に影響しあう空きマス)ならば効果的に枝刈りができていたかもしれませんが、斜めのブロック(相互に影響しない)中の空きマスが次々に探索されていくことが考えられるアルゴリズムなため、浅いノードでの枝刈りがあまり発生しなかったという点です。

 

 これらを解決するために考えたのは、縦横のブロック同士の干渉を計算しながら探索順序を最初に決め、あとは変更しないというものなのですが、いかんせん具体的にどうすればいいかというのが思いつきません。しょんぼり。

 

高速化手法② 自明な場所を埋めておく

 あるマスにNが入っていたとすると、それと縦横とブロックないにNは存在しません。ボード上のすべてのNについて、Nが入らないマスを埋めて、Nが存在しないブロックの空きマスがひとつならそこがそのブロック中のNであるとわかります。これをすべてのNについて行って、わかるところを探索無しで埋めてしまおうというのがこれです。

 まだ実装が不完全なためなんとも言えませんが、この方法はゲーム全体においてかなり効果を持つように思います。

 ゲーム序盤では、簡単な問題ならば膨大な自明なマスがあります。これは完全に確定するので、探索を行わなければならない場所が大幅に減ることになります。

 探索を行っている途中でも、探索中に仮においた数字によってボードのどこかで矛盾(候補がなくなる)が起きればいいので早期に枝を刈ることができる気がします。

 

 ただ、一回自明なマスを確定させて、その確定によって新たな自明なマスが発生する可能性があります。(まあアップデートがあったかを受け取ればいいんだけど、実装が面倒っていうね、それだけだよ)

 

まとめ

 まあと言った感じで、16×16の数独には結構悪戦苦闘してるというわけです。プログラミングの勉強としての数独ソルバーですが、とても良い題材なのではないかなと思います。再帰関数を用いたプログラミングは始めたばかりなのですが、これを解くことによって結構自信がついたし、実際簡単なものなら瞬殺できる実力がつきました。

 暇すぎて爆発しそうな人は数独ソルバーを作ってみてはいかがでしょうか。

 私からは以上です。

 

P.S.このプログラム17個問題とかだとクソ

ビット演算使ってリュカレーマーテストを高速化したお話

ビット演算にした部分

 リュカレーマーテストでコストがかかる部分は主に2つ、二乗の演算と剰余算です。ちなみにどちらが痛いかというと剰余算です。(今回わかった)

 リュカレーマーテストに出てくる剰余算は割る数が限定されている(判定対象のメルセンヌ数)なのでbit演算に落とし込めそうだと思いたち、実装して今に至ります。

方法

※判定対象pを2^i-1とします。で割る数をnとします。ここではnをpで割ったあまりを求める操作を考えます。

1、nをpでマスクして下位iビットを得ます。

2、nをiビット右シフトして上位ビットを得ます。

3、1と2の結果を足してnに入れときます。

4、1~3をn<=pになるまで繰り返します。

5、n=pならn=0にします。

証明(というより詳しく言っただけ)

 1はnのp以下の部分を求めるところです。pを2^iと近似しているため5のような処理が最後に入ってきます。

 2について。1のpを2^iと近似するものによれば、nのp以上の部分には(n>>p)個のpがあるわけです。真値は2^i-1なのでこれ一つ一つにあまりが1ずつ発生していることになります。これを全部足したいのでnをi桁ビットシフトしてます。

 3について足します。

 4について。1と2を1回ずつ実行しただけでは64とかの数では答えが8とかになります。これを防ぐために複数回実行しています。(なので割る数とオペランドのbit数に大きな差がある場合は遅くなる)

 5について。このままだと割る数にpの倍数を代入された時にpが返ってしまいます。それを防ぐためです。

結果

f:id:coilgunrailgun:20161229021942p:plain30番目、2^132049-1を判定。上が今回、下が従来

5倍弱ぐらいの速度になってますね。今回のもので、割り算単品でかかっているコストがどの程度なのか分かりませんがだいぶ速くなっているはずだと信じています。

(実行環境i7 4770K single thread, linuxmint18 64bit, g++, gmp)

終わりに

 リュカレーマーテストの最大の問題である、実行速度がO(N^2)という点は変わっていませんが(変わったらマジで大事件だけど)、比例定数を落とすことには成功していると思います。二乗に関してはgmpを使っての実装なのでこれ以上にはならないでしょう。(GPU使うなら話は別ですが)

 

P.S.年明けにGTX1060 6GB買います

P.S.Wiki確認したら書いてあるやんけこのアルゴリズム

あーねんまつ

 今は12月28日あと数日で2016年が終わります。

 今年は今までになくいろんなことがあった年だったように感じます(昔の記憶はどんどん失われていくため)

 PCが新しくなったり、部活で大会に出たり、文化祭で激務だったり色々とありましたね

 

来年はもっと飛躍できる年にしたいですね

天使と悪魔と二分探索

 少し前に映画、天使と悪魔を見ました。爆弾の場所を探す時にカメルレンゴの提案でバチカンの各区画の電力を順番に落として映像の電気に変化があるかないかを探すシーンがありました。

 劇中ではたくさんある区画の電力を順番に落としていましたが、まず半分ずつ落として、映像に変化があった片方のさらに半分を落として、、、、を繰り返した方(二分探索)した方が圧倒的に速く探せるのに、、、、と感じました。

 仮に二分探索で最も効率的に探索が行える2の冪乗個、今回は128個の区画があったとすると劇中のやり方では平均64回の試行でわかることになりますが、二分探索なら8回の試行で分かってしまいます。64回で終わらないリスクを考えれば一回の試行にかかる時間が長くても二分探索を行ったほうがいいと思うんですけどね

パソコン甲子園裏本選について

 パソコン甲子園裏本選(予選落ちしたチームも同じ条件でオンライン本選に臨める)が昨日ありました。私のチームのパートナーが1時間ほどで帰ってしまったため残り3時間ほどは私一人で寂しかったのですが、予選落ち校では35位という成績を残せました。ここでは解けた問題についていろいろ言っていこうと思います。(解けたのは1~3番、家に帰ってちょっと書きかえて解けたのが10番)

 

1番「4つ入力された数値から長方形が作れるかどうか判定しろ」

 プログラム自体はソートして前2個と後ろ2個が等しければyes、そうでなければnoと出力するだけだったのですが、trueとfalseで出力したため提出回数が1回増えました。これはマジでもったいないミス

 

2番「12個入力された数値から直方体が作れるかどうか判定しろ」

 ソートして4つごとに等しいかどうか判定してyes noを返すという感じでときました。

これは特に問題なく通過

 

3番「入力された異なる4つの値を当てはめて(A+B)/(C-D)の最大値を求めよ」

 分母を優先する場合と分子を優先する場合に分けて組みました。差の最小は、ソートした後探索して求め、和の最大は昇順にソートして末尾の要素とその前の要素をとりました。(重複があってはならないので場合分けが必要だった)

問題文に

cout.setf(ios_base::fixed,ios_base::floatfield);

cout << result << endl;

って書けば小数点以下も表示できる

って書いてあったのにそのとおりに書いてもうまく行かず、結局

cout << fixed << result << endl;

って書きました。(これのせいで提出回数3回増えた)

ほんとにクソ

(あとから思い出したんだけどこれキャストして代入したらうまく行ったんだった int型のほうが強いんですねぇ)

 

10番「チェス盤を移動するアリが落下する順位を返すプログラムを作れ」

 予選落ち勢ではだれも解けていなかった問題です。プランとしてはそれぞれのアリが落下する時間を求めて配列に格納し、それに順位をつけて出力しました。

 アリの挙動もそこまで複雑ではなかったので10番という番号のわりにそこまで難しくは無かったと思います。(時間内に解けませんでしたが)

 

http://web-ext.u-aizu.ac.jp/pc-concours/2016/download/pck2016f_all.pdf

問題はこちらです

素数生成とグラボを使った多倍長演算

 かなり昔の話ですが、素数を600億まで計算しました。アルゴリズムはエラトステネスの篩です。7以上の素数は30で割って1,7,11,13,17,19,23,29余るという性質を利用して8個にスレッドを分けています。この8個という数字、私のコンピュータのロジックコア数に相当するのでそれなりに効率よく処理を配分できていると思います。

 タイムはintel Core i7 4770K 3.5~3.9GHzの8logic coreで、90秒でした。

 篩処理は配列の要素を1に書き換えていくという方法を取っているのでgccコンパイルの最適化オプションの-O3にかなり恩恵を受けています(タイムが半分ぐらいになった)

 部活のi5のデスクトップで300億まで計算させてみたところ、こちらは60秒でした。(私のだと45秒だった)シングルロジックコアに割り当てられるキャッシュ量が部活のPCの方が多いのが原因かも知れません。

 

 知っての通りC++のスタンダードライブラリに多倍長演算をサポートするものはありません。私はGMPという素晴らしいライブラリ(とにかく演算がめちゃくちゃ速い。FFTを使ってるんでしょううが8000万bit同士の演算が0.3秒で終わる)を使っていますが、それでももっと早くしたいなと思うことがあります。

 掛け算とかの簡単な処理はグラボで処理させたほうが速いと思って調べてみてるところなのですが、積表を用いて演算する方式が取られているものがありました。コンピュータで演算させることを考えたらビット演算でやるのが良さそうなきがしますがどうでしょうね。

 あと、一応CUDAの環境はあるのですがCUDAでなぜかC++コンパイルできない現象に悩まされています。悲しみ