数独を解く

組合せ最適化を使うと数独も簡単に解けます。

「数独」はニコリの登録商標です
出典ニコリhttp://www.nikoli.co.jp/ja/

定式化

$\mbox{variables}$	$x_{ijk} \in \{0, 1\} ~ \forall i, j, k$	マスi,jが数字k+1か (1)
$\mbox{subject to}$	$\sum_k{x_{ijk}} = 1 ~ \forall i, j$	数字は1つ (2)
	$\sum_k{x_{ikj}} = 1 ~ \forall i, j$	縦に同じ数字はない (3)
	$\sum_k{x_{kij}} = 1 ~ \forall i, j$	横に同じ数字はない (4)
	$3 \times 3$のマスについても同様 (5)
	数字指定 (6)

Pythonで解く

pulpとpandasを使います。

問題は、文字列に入っているとします。

python

prob = """\
..6.....1
.7..6..5.
8..1.32..
..5.4.8..
.4.7.2.9.
..8.1.7..
..12.5..3
.6..7..8.
2.....4..
"""

定式化して解いてみましょう。

python

import pandas as pd, numpy as np
from more_itertools import grouper
from pulp import *
r = range(9)

m = LpProblem() # 数理モデル
a = pd.DataFrame([(i, j, k, LpVariable('x%d%d%d'%(i,j,k), cat=LpBinary))
                  for i in r for j in r for k in r],
                 columns=['縦', '横', '数', 'x']) # (定式化1)
for i in r:
    for j in r:
        m += lpSum(a[(a.縦 == i) & (a.横 == j)].x) == 1 # (定式化2)
        m += lpSum(a[(a.縦 == i) & (a.数 == j)].x) == 1 # (定式化3)
        m += lpSum(a[(a.横 == i) & (a.数 == j)].x) == 1 # (定式化4)
for i in range(0, 9, 3):
    for j in range(0, 9, 3):
        for k in r:
            m += lpSum(a[(a.縦 >= i) & (a.縦 < i+3) & # (定式化5)
                         (a.横 >= j) & (a.横 < j+3) & (a.数 == k)].x) == 1
for i, s in enumerate(prob.split('\n')):
    for j, c in enumerate(s):
        if c.isdigit():
            k = int(c)-1 # (定式化6)
            m += lpSum(a[(a.縦 == i) & (a.横 == j) & (a.数 == k)].x) == 1
m.solve() # ソルバーで求解
f = a.x.apply(lambda v: value(v) == 1) # 選ばれた数字
print(np.array(list(grouper(9, a.数[f] + 1))))
>>>
[[5 3 6 8 2 7 9 4 1]
 [1 7 2 9 6 4 3 5 8]
 [8 9 4 1 5 3 2 6 7]
 [7 1 5 3 4 9 8 2 6]
 [6 4 3 7 8 2 1 9 5]
 [9 2 8 5 1 6 7 3 4]
 [4 8 1 2 9 5 6 7 3]
 [3 6 9 4 7 1 5 8 2]
 [2 5 7 6 3 8 4 1 9]]

Docker

他のパズルもtsutomu7/puzzleにあります。下記を実行してブラウザでホストのアドレスを見てください。

docker run -d -p 80:8888 tsutomu7/puzzle

参考

以上