[PYTHON] Solution optimale en combinant les mathématiques

Résoudre le nombre

Avec Optimisation de combinaison, vous pouvez facilement résoudre les mathématiques.

"Sugoku" est une marque déposée de Nikori Source Nikori http://www.nikoli.co.jp/ja/

Formulation

$ \ mbox {variables} $ $ x_ {ijk} \ in \ {0, 1 \} ~ \ forall i, j, k $ La masse i, j est-elle le nombre k + 1? (1)
$ \ mbox {sujet à} $ $ \ sum_k {x_ {ijk}} = 1 ~ \ forall i, j $ Un nombre (2)
$ \ sum_k {x_ {ikj}} = 1 ~ \ forall i, j $ Pas de même nombre vertical (3)
$ \ sum_k {x_ {kij}} = 1 ~ \ forall i, j $ Il n'y a pas le même numéro à côté (4)
3 $ \ fois 3 $ carrés (5)
Spécifiez le numéro (6)

Résoudre avec Python

[pulpe](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721#%E3%82%BD%E3%83%95%E3%83%88%E3%81%AE%E3%82 Utilisez% A4% E3% 83% B3% E3% 82% B9% E3% 83% 88% E3% 83% BC% E3% 83% AB) et les pandas.

Le problème est que c'est dans une chaîne.

python


prob = """\
..6.....1
.7..6..5.
8..1.32..
..5.4.8..
.4.7.2.9.
..8.1.7..
..12.5..3
.6..7..8.
2.....4..
"""

Formulons et résolvons-le.

python


import pandas as pd, numpy as np
from more_itertools import grouper
from pulp import *
r = range(9)

m = LpProblem() #Modèle mathématique
a = pd.DataFrame([(i, j, k, LpVariable('x%d%d%d'%(i,j,k), cat=LpBinary))
                  for i in r for j in r for k in r],
                 columns=['Verticale', 'côté', 'nombre', 'x']) # (Formulation 1)
for i in r:
    for j in r:
        m += lpSum(a[(a.Verticale== i) & (a.côté== j)].x) == 1 # (Formulation 2)
        m += lpSum(a[(a.Verticale== i) & (a.nombre== j)].x) == 1 # (Formulation 3)
        m += lpSum(a[(a.côté== i) & (a.nombre== j)].x) == 1 # (Formulation 4)
for i in range(0, 9, 3):
    for j in range(0, 9, 3):
        for k in r:
            m += lpSum(a[(a.Verticale>= i) & (a.Verticale< i+3) & # (Formulation 5)
                         (a.côté>= j) & (a.côté< j+3) & (a.nombre== k)].x) == 1
for i, s in enumerate(prob.split('\n')):
    for j, c in enumerate(s):
        if c.isdigit():
            k = int(c)-1 # (Formulation 6)
            m += lpSum(a[(a.Verticale== i) & (a.côté== j) & (a.nombre== k)].x) == 1
m.solve() #Résoudre avec le solveur
f = a.x.apply(lambda v: value(v) == 1) #Numéro sélectionné
print(np.array(list(grouper(9, a.nombre[f] + 1))))
>>>
[[5 3 6 8 2 7 9 4 1]
 [1 7 2 9 6 4 3 5 8]
 [8 9 4 1 5 3 2 6 7]
 [7 1 5 3 4 9 8 2 6]
 [6 4 3 7 8 2 1 9 5]
 [9 2 8 5 1 6 7 3 4]
 [4 8 1 2 9 5 6 7 3]
 [3 6 9 4 7 1 5 8 2]
 [2 5 7 6 3 8 4 1 9]]

Docker D'autres puzzles peuvent également être trouvés sur tsutomu7 / puzzle. Procédez comme suit pour voir l'adresse de l'hôte dans votre navigateur.

docker run -d -p 80:8888 tsutomu7/puzzle

référence

c'est tout