Sugoku peut être facilement résolu avec Optimisation de combinaison. Tout d'abord, l'état d'exécution. (Nécessite au préalable "pip install -U ou toolpy")
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]]
La méthode sudoku prend 81 "nombres ou points (.)" Et renvoie "solution et unicité". Voyons si le problème ci-dessus est unique.
python
sudoku(data, checkOnlyOne=True)[1]
>>>
True
Puisqu'il est vrai, on peut voir qu'il est unique (il n'y a qu'une seule solution). Jetons un coup d'œil au contenu du sudoku.
ipython
sudoku??
production
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=['ligne','Colonne','_3x3','nombre','Solide'])
a['Var'] = addbinvars(len(a))
m = LpProblem()
for cl in [('ligne','Colonne'),('ligne','nombre'),('Colonne','nombre'),('_3x3','nombre')]:
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].nombre.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
Vous pouvez le résoudre en formulant environ 10 lignes et en appelant résoudre. Le temps de calcul est un instant. Qu'elle soit unique ou non est également unique si la première solution est interdite et résolue à nouveau, et qu'il n'y a pas d'autre solution.
c'est tout
Recommended Posts