のだなのだ

ほげ〜

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の２つのみですが、殆どの問題を探索無しで解けている感じです。ただ、16x16の56個問題とかになると相当時間がかかります。LocalizationとかNaked Pairとかを実装していく必要がありそうです。

 

ソースコード

github.com