Pythonで数独
数独は、組合せ最適化で簡単に解ける。
まずは、実行の様子。(事前に、「pip install -U ortoolpy」が必要)
python
from ortoolpy import sudoku
data = """\
4 . . |. . . |1 . .
. 5 . |. 3 . |. . 8
2 . . |7 . 8 |. 9 .
------+------+------
. 4 5 |6 . . |8 . 1
. . 3 |. 5 . |. . .
. 2 . |1 . 3 |. . .
------+------+------
8 . . |. . 5 |. . .
. . 4 |. . . |. . .
. 1 . |. 6 4 |3 . 9
"""
sudoku(data)[0]
>>>
[[4, 7, 8, 5, 9, 6, 1, 2, 3],
[6, 5, 9, 2, 3, 1, 7, 4, 8],
[2, 3, 1, 7, 4, 8, 6, 9, 5],
[9, 4, 5, 6, 7, 2, 8, 3, 1],
[1, 8, 3, 4, 5, 9, 2, 6, 7],
[7, 2, 6, 1, 8, 3, 9, 5, 4],
[8, 9, 7, 3, 2, 5, 4, 1, 6],
[3, 6, 4, 9, 1, 7, 5, 8, 2],
[5, 1, 2, 8, 6, 4, 3, 7, 9]]
メソッド sudoku は、81個の「数字またはドット(.)」を入力とし、「解とユニークかどうか」を返す。上記の問題が、ユニークかどうか見てみよう。
python
sudoku(data, checkOnlyOne=True)[1]
>>>
True
Trueなので、ユニーク(解が1つしかない)ということがわかる。
sudokuの中身を見てみよう。
ipython
sudoku??
出力
def sudoku(s, checkOnlyOne=False):
"""
sudoku(
'4 . . |. . . |1 . . '
'. 5 . |. 3 . |. . 8 '
'2 . . |7 . 8 |. 9 . '
'------+------+------'
'. 4 5 |6 . . |8 . 1 '
'. . 3 |. 5 . |. . . '
'. 2 . |1 . 3 |. . . '
'------+------+------'
'8 . . |. . 5 |. . . '
'. . 4 |. . . |. . . '
'. 1 . |. 6 4 |3 . 9 ')[0]
"""
import re, pandas as pd
from itertools import product
from pulp import LpProblem, lpSum, value
data = re.sub(r'[^\d.]','',s)
assert(len(data) == 81)
r = range(9)
a = pd.DataFrame([(i,j,(i//3)*3+j//3,k+1,c==str(k+1))
for (i,j),c in zip(product(r,r),data) for k in r],
columns=['行','列','_3x3','数','固'])
a['Var'] = addbinvars(len(a))
m = LpProblem()
for cl in [('行','列'),('行','数'),('列','数'),('_3x3','数')]:
for _,v in a.groupby(cl):
m += lpSum(v.Var) == 1
for _,r in a[a.固==True].iterrows():
m += r.Var == 1
m.solve()
if m.status != 1:
return None, None
a['Val'] = a.Var.apply(value)
res = a[a.Val>0.5].数.values.reshape(9,9).tolist()
if checkOnlyOne:
fr = a[(a.Val>0.5)&(a.固!=True)].Var
m += lpSum(fr) <= len(fr)-1
return res, m.solve()!=1
return res, None
10行ほど定式化して solve を呼ぶだけで解ける。計算時間は、一瞬である。
ユニークかどうかも、最初の解を禁止して解きなおし、もう1つの解がなければユニークである。
参考
以上