Deutsch in Python

Sugoku kann leicht mit Kombinationsoptimierung gelöst werden. Zunächst der Ausführungszustand. (Benötigt "pip install -U oder toolpy" im Voraus)

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

Die Methode sudoku nimmt 81 "Zahlen oder Punkte (.)" Und gibt "Lösung und Eindeutigkeit" zurück. Mal sehen, ob das obige Problem einzigartig ist.

`python`


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

Da es wahr ist, kann man sehen, dass es einzigartig ist (es gibt nur eine Lösung). Werfen wir einen Blick auf den Inhalt von Sudoku.

`ipython`


sudoku??

`Ausgabe`


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

Sie können es lösen, indem Sie ungefähr 10 Zeilen formulieren und lösen aufrufen. Die Berechnungszeit ist ein Augenblick. Ob es eindeutig ist oder nicht, ist auch eindeutig, wenn die erste Lösung verboten und erneut gelöst wird und es keine andere Lösung gibt.

Referenz

das ist alles