Sudoku in Python

Sudoku in Python

Sudoku can be easily solved with Combinatorial optimization. First of all, the state of execution. (Requires "pip install -U or toolpy" in advance)

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]]

The method sudoku takes 81 "numbers or dots (.)" And returns "solution and uniqueness". Let's see if the above problem is unique.

python

sudoku(data, checkOnlyOne=True)[1]
>>>
True

Since it is True, it can be seen that it is unique (there is only one solution). Let's take a look at the contents of sudoku.

ipython

sudoku??

output

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=['line','Column','_3x3','number','Solid'])
    a['Var'] = addbinvars(len(a))
    m = LpProblem()
    for cl in [('line','Column'),('line','number'),('Column','number'),('_3x3','number')]:
        for _,v in a.groupby(cl):
            m += lpSum(v.Var) == 1
    for _,r in a[a.Solid==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].number.values.reshape(9,9).tolist()
    if checkOnlyOne:
        fr = a[(a.Val>0.5)&(a.Solid!=True)].Var
        m += lpSum(fr) <= len(fr)-1
        return res, m.solve()!=1
    return res, None

You can solve it by formulating about 10 lines and calling solve. The calculation time is an instant. Whether it is unique or not is also unique if the first solution is prohibited and solved again, and there is no other solution.

reference

-Learn Combinatorial Optimization Through Sudoku -Use combinatorial optimization -Solving puzzles by mathematical optimization -Python in optimization -Puzzle Combinatorial Optimization Technique

that's all