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つの解がなければユニークである。

参考

以上