のだなのだ

ほげ〜

Solving Sudoku by Bit operation(16x16)

ボードの表現

16x16の数独なので16x16=256マスあります。

  a b c d e f g h i j k l m n o p
0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
2 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
3 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
4 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
5 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
6 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
7 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
8 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
9 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
10 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175
11 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191
12 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
13 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
14 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
15 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255

 256ビット型の各位(ビット)を上のように配置します。

 今回、ペンシルマーク記法を自然に表現するために、上のようなビットボードを16個合わせて配列にし、候補となる場所のビットを立てておきます。このようなビットボードを採用すると数独を解く上で必要な操作をより簡潔に書け、実行も高速になります。(速いかどうかは実験してないけど多分速い。)

 256bitの整数型としてつかったのはstd::bitsetです。

 

ビット演算で有利な操作

数字を入れる操作

 数字を入れる操作は数独を解く上で最も基本となる操作です。これは探索のどの場面においてもたくさん出てくるので、できるだけ高速に実行されることが求められます。

 ある場所のある数字Nを決定した時に、同じ行、列、ブロックのマスの候補数字Nを消去する処理が必ず発生します。これを普通の配列、及び数値代入でやった場合対象となるマスの数だけ(列、行で12x2、ブロックで15の39回)配列へのアクセスが必要があります。

 今回組んだものは列、行、ブロックごとにマスクを事前に用意して、ビットマスクを取ることでボードへのアクセスは1回で済みます。(確定させるNのボードだけの話)

用意するマスクは下の3通り(18個)です。

 

  a b c d e f g h I j k l m n o p
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

横用のマスク xMask

 

  a b c d e f g h I j k l m n o p
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

縦用のマスク yMask

 

  a b c d e f g h I j k l m n o p
0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
3 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

ブロック用のマスク(これが16通り)blockMask[16]

 

これを書いたものが以下になります。(baseは256bit整数型)

 

gist06a918a9ea81d7e0d23ae524ac759dab

 

 これをもとに数字をセットするメソッドを組みます。横マスク用の座標をx、縦マスク用の座標をyとして、xMaskを(x*16)ビット左シフトすることで任意の横、yMaskをyビット左シフトすることで任意の縦の操作を行え、どの blockに属するかをx,yから計算してblockMaskを添え字から指定し、ブロックも操作できます。

gist3e2a215961b14eadfcce5b5f1e1c7725

 

終わったかどうかの判定

 例によって深さ優先探索で最終的には答えを出していくわけですが、それには終了(すべてのマスが確定したかどうか)の判定が必要になってきます。

 候補があるかないかだけを示したビットボードしか無いと、いろいろと不便なので私は確定した数字とマスを記録しておくための256bit整数の16個のボードをもうひとつ用意しました。

 これを用いると終わったかどうかの判定は簡単で、16個の確定マス配列のビットORをとってすべてビットが立っていれば終了、一つでも0があれば続ける、と判定が可能です。(OR関数は入力された16個の配列のORを返す関数です。)

gistad2bd76ffad82600f3bf0c2f71de7044

※すべてのマスが1であるかどうかを判定するためにビットを反転させて0かどうか調べています。

 

矛盾があるかどうかの判定

 これも深さ優先探索に必要な処理です。矛盾があればfalseを返して戻れるところまで戻り、別の候補を入れてみて、、、、、といった処理が無数に発生します。

 具体的に矛盾とは、マズいところに入れてしまって、どこかのマスに一つも候補がなくなってしまったときが矛盾です。

 これも簡単な話で、ペンシルマーク用の配列のビットORをとってすべてのビットに1が立っていればtrue、一つでも0があればfalseを返せばクリアできます。

gistc91faf8889781b1b72984c86d6edbad4

お気づきの人も居ると思いますが、終了判定の返り値を反転させれば得られます。ですが今回は別のメソッドとして実装しています。

 

まとめ

 今組んでいるもので実装している埋める手段はNaked SingleとHidden Singleの2つのみですが、殆どの問題を探索無しで解けている感じです。ただ、16x16の56個問題とかになると相当時間がかかります。LocalizationとかNaked Pairとかを実装していく必要がありそうです。

 

ソースコード

github.com

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

問題はこちらです