SAT ソルバーで数独を解いてみた

October 22, 2020

SAT ソルバーの簡単な説明数独の問題を CNF 形式で表す空いているマスに1〜9のいずれかの数字を入れる縦・横の各列及び、太線で囲まれた3×3のブロック内に同じ数字が複数入ってはいけない盤面に既に存在する数字 SAT ソルバーに投げる形式に変換する SAT ソルバーを使う

会社の勉強会で SAT ソルバーについての発表がありました。その発表が面白くて「SAT ソルバー使ってみたい！」となったので、思いつきで数独を解いてみました。

SAT ソルバーの簡単な説明

SAT ソルバーの入力には、以下の CNF 形式と呼ばれる論理式を用います。 $(p_{11} \lor p_{12} \lor \cdots \lor p_{1m_1}) \land (p_{21} \lor p_{22} \lor \cdots \lor p_{2m_2}) \land \cdots \land (p_{n1} \lor p_{n2} \lor \cdots \lor p_{nm_n})$ $p_{i1} \lor p_{i2} \lor \cdots \lor p_{im_i}$ を節 (clause) と呼び、節の論理積で表されています。

SAT ソルバーはこの全体の論理積が true となる $p_{ij}$ の組 (true or false) を求めます。愚直に計算すると指数関数的に組み合わせが増えることが容易に想像できますね (NP完全みたいです: wiki)。 SAT ソルバーでは制約伝搬などの様々なテクニックを使って高速化しています。変数の数が $10^4$ ぐらいなら十分計算可能らしいです。

簡単な例として、 $(\lnot p_1 \lor p_2) \land (p_1 \lor p_2 \lor \lnot p_3)$ が true となる $p_1, p_2, p_3$ を求めるとき、ソルバーに入力する形式としては、

p cnf 3 2
-1 2 0
1 2 -3 0

という形式になります。 1行目の右2つの整数はそれぞれ変数の数、節の数であり、2行目からはそれぞれの節の論理式を符号付き整数を使って表します。0 は節の終了を意味します。

数独の問題を CNF 形式で表す

数独の問題を SAT ソルバーで解くには、上で説明した CNF 形式に変換する必要があります。ここではマス $(i, j)$ ( $0\le i < 9, 0\le j < 9$ )に数字 $n$ ( $1\le n \le 9$ )を書くことを $v_{ijn}$ と表すことにします。 $v_{ijn}$ にそれぞれ別の整数のラベルを与えるため、以下の関数を用意します。

def v_to_num(row, col, n):
    return row * 9 ** 2 + col * 9 + n

これで $1 \le v_{ijn} \le 9^3 = 729$ となります。

とりあえず wiki から問題を適当に持ってきました。

board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]

ルールを wiki から引用すると、

空いているマスに1〜9のいずれかの数字を入れる。
縦・横の各列及び、太線で囲まれた3×3のブロック内に同じ数字が複数入ってはいけない。

空いているマスに1〜9のいずれかの数字を入れる

ここからは clauses 変数に、節をリストの形式で追加していきます。

for row in range(9):
    for col in range(9):
        tmp = []
        for n in range(1, 10):
            tmp.append(v_to_num(row, col, n))
        clauses.append(tmp)

縦・横の各列及び、太線で囲まれた3×3のブロック内に同じ数字が複数入ってはいけない

# 同じ行に同じ数字は現れない
for row in range(9):
    for col0, col1 in combinations(range(9), 2):
        for n in range(1, 10):
            clauses.append([-v_to_num(row, col0, n), -v_to_num(row, col1, n)])

# 同じ列に同じ数字は現れない
for row0, row1 in combinations(range(9), 2):
    for col in range(9):
        for n in range(1, 10):
            clauses.append([-v_to_num(row0, col, n), -v_to_num(row1, col, n)])

# 同じブロックに同じ数字は現れない
for block_row in range(3):
    for block_col in range(3):
        for pos0, pos1 in combinations(range(9), 2):
            row0 = 3 * block_row + pos0 // 3
            row1 = 3 * block_row + pos1 // 3
            col0 = 3 * block_col + pos0 % 3
            col1 = 3 * block_col + pos1 % 3
            for n in range(1, 10):
                clauses.append([-v_to_num(row0, col0, n), -v_to_num(row1, col1, n)])

盤面に既に存在する数字

clauses = []
for row in range(9):
    for col in range(9):
        if (n := board[row][col]) != 0:
            clauses.append([v_to_num(row, col, n)])

SAT ソルバーに投げる形式に変換する

数独のルール的には以上で解が決定されるはず。

s = []
s.append(f"p cnf {9**3} {len(clauses)}")
for c in clauses:
    s.append(" ".join(map(str, c + [0])))

with open("output.ps", "w") as f:
    f.write("\n".join(s))

SAT ソルバーを使う

SAT ソルバーは Java で動く sat4j を使いました。 (Java ならいつか android アプリで使えるかも？と思い)

java -jar org.sat4j.core.jar output.ps
(中略)
c 8859 constraints processed.
s SATISFIABLE
v -1 -2 -3 -4 5 -6 -7 -8 -9 -10 -11 12 -13 -14 -15 -16 -17 -18 -19 -20 -21 22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 33 -34 -35 -36 -37 -38 -39 -40 -41 -42 43 -44 -45 -46 -47 -48 -49 -50 -51 -52 53 -54 -55 -56 -57 -58 -59 -60 -61 -62 63 64 -65 -66 -67 -68 -69 -70 -71 -72 -73 74 -75 -76 -77 -78 -79 -80 -81 -82 -83 -84 -85 -86 87 -88 -89 -90 -91 -92 -93 -94 -95 -96 97 -98 -99 -100 101 -102 -103 -104 -105 -106 -107 -108 109 -110 -111 -112 -113 -114 -115 -116 -117 -118 -119 -120 -121 -122 -123 -124 -125 126 -127 -128 -129 -130 131 -132 -133 -134 -135 -136 -137 138 -139 -140 -141 -142 -143 -144 -145 -146 -147 148 -149 -150 -151 -152 -153 -154 -155 -156 -157 -158 -159 -160 161 -162 163 -164 -165 -166 -167 -168 -169 -170 -171 -172 -173 -174 -175 -176 -177 -178 -179 180 -181 -182 -183 -184 -185 -186 -187 188 -189 -190 -191 192 -193 -194 -195 -196 -197 -198 -199 -200 -201 202 -203 -204 -205 -206 -207 -208 209 -210 -211 -212 -213 -214 -215 -216 -217 -218 -219 -220 221 -222 -223 -224 -225 -226 -227 -228 -229 -230 231 -232 -233 -234 -235 -236 -237 -238 -239 -240 241 -242 -243 -244 -245 -246 -247 -248 -249 -250 251 -252 -253 -254 -255 -256 257 -258 -259 -260 -261 -262 -263 -264 -265 -266 -267 -268 -269 270 -271 -272 -273 -274 -275 -276 277 -278 -279 -280 -281 -282 -283 -284 285 -286 -287 -288 289 -290 -291 -292 -293 -294 -295 -296 -297 -298 -299 -300 301 -302 -303 -304 -305 -306 -307 308 -309 -310 -311 -312 -313 -314 -315 -316 -317 318 -319 -320 -321 -322 -323 -324 -325 -326 -327 328 -329 -330 -331 -332 -333 -334 335 -336 -337 -338 -339 -340 -341 -342 -343 -344 -345 -346 -347 348 -349 -350 -351 -352 -353 -354 -355 -356 -357 -358 359 -360 -361 -362 -363 -364 365 -366 -367 -368 -369 -370 -371 372 -373 -374 -375 -376 -377 -378 -379 -380 -381 -382 -383 -384 385 -386 -387 -388 -389 -390 -391 -392 -393 -394 -395 396 397 -398 -399 -400 -401 -402 -403 -404 -405 -406 -407 -408 -409 -410 -411 412 -413 -414 415 -416 -417 -418 -419 -420 -421 -422 -423 -424 -425 426 -427 -428 -429 -430 -431 -432 -433 -434 -435 -436 -437 -438 -439 -440 441 -442 443 -444 -445 -446 -447 -448 -449 -450 -451 -452 -453 454 -455 -456 -457 -458 -459 -460 -461 -462 -463 -464 -465 -466 467 -468 -469 -470 -471 -472 473 -474 -475 -476 -477 -478 -479 -480 -481 -482 483 -484 -485 -486 -487 -488 -489 -490 -491 -492 -493 -494 495 -496 -497 -498 -499 -500 501 -502 -503 -504 505 -506 -507 -508 -509 -510 -511 -512 -513 -514 -515 -516 -517 518 -519 -520 -521 -522 -523 -524 525 -526 -527 -528 -529 -530 -531 -532 -533 -534 -535 -536 -537 538 -539 -540 -541 542 -543 -544 -545 -546 -547 -548 -549 -550 -551 -552 -553 -554 -555 -556 557 -558 -559 -560 -561 562 -563 -564 -565 -566 -567 -568 569 -570 -571 -572 -573 -574 -575 -576 -577 -578 -579 -580 -581 -582 -583 584 -585 -586 -587 -588 -589 -590 -591 592 -593 -594 -595 -596 -597 598 -599 -600 -601 -602 -603 604 -605 -606 -607 -608 -609 -610 -611 -612 -613 -614 -615 -616 -617 -618 -619 -620 621 -622 -623 -624 -625 -626 627 -628 -629 -630 -631 -632 633 -634 -635 -636 -637 -638 -639 -640 -641 -642 -643 644 -645 -646 -647 -648 -649 -650 651 -652 -653 -654 -655 -656 -657 -658 -659 -660 661 -662 -663 -664 -665 -666 -667 -668 -669 -670 671 -672 -673 -674 -675 -676 677 -678 -679 -680 -681 -682 -683 -684 -685 -686 -687 -688 -689 -690 -691 692 -693 -694 -695 -696 -697 -698 699 -700 -701 -702 703 -704 -705 -706 -707 -708 -709 -710 -711 -712 -713 -714 -715 -716 -717 718 -719 -720 -721 -722 -723 -724 -725 -726 -727 -728 729 0
c Total wall clock time (in seconds) : 0.062

SAT ソルバーで求まった解を python で表示してみます。

def num_to_v(num):
    num -= 1
    n = num % 9
    num -= n
    col = (num % 81) // 9
    num -= 9 * col
    row = num // 81
    return row, col, n + 1


ans_array = np.zeros((9, 9), dtype=int)
for a in ans:
    if a < 0:
        continue
    row, col, n = num_to_v(a)
    ans_array[row, col] = n

print(ans_array)

[[5 3 4 6 7 8 9 1 2]
 [6 7 2 1 9 5 3 4 8]
 [1 9 8 3 4 2 5 6 7]
 [8 5 9 7 6 1 4 2 3]
 [4 2 6 8 5 3 7 9 1]
 [7 1 3 9 2 4 8 5 6]
 [9 6 1 5 3 7 2 8 4]
 [2 8 7 4 1 9 6 3 5]
 [3 4 5 2 8 6 1 7 9]]

これで数独が解けました。お手軽ですね。今度、画像認識で数独の問題を読み取って解くスマホアプリを作ってみたり、他のパズルも解いてみたりしたいと思います。