9
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Pythonで数独

Last updated at Posted at 2016-10-21

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

参考

以上

9
7
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
9
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?