artsym.py

# Il faut deux choses pour que ce code fonctionne :
# La librairie PuLP (pip install pulp)
# Le logiciel coin-cbc. Sur Debian: apt-get install coinor-cbc
from pulp import *

# puzzle.txt contient les chiffres lignes par lignes et espace pour les cases vides
with open('puzzle.txt', 'r') as f:
    puzzle = f.readlines()

ROWS = len(puzzle)
COLS = len(puzzle[0][:-1])

for i in range(ROWS-1):
    puzzle[i] = puzzle[i][:-1]  # On retire les sauts de lignes

def voisins(i, j):
  """
  Prend en entrée les coordonnées d'un point et renvoie la celule 3x3 centrée dessus
  """
    voisins = []
    for vi in range(max(0,i-1),min(ROWS,i+2)):
        for vj in range(max(0,j-1),min(COLS,j+2)):
            voisins.append((vi,vj))
    return voisins

print("Données : ")
print(ROWS, "lignes et", COLS, "colonnes")

problem = LpProblem("Zwolle 16", LpMinimize)  # On crée un problème de minimisation
problem += 0, "Dummy obj"  # On veut juste une solution, donc le score est constant

cells = LpVariable.dicts('x',(range(ROWS),range(COLS)),0,1,LpInteger)  # On déclare les ROWS*COLS variables binaires

# On parcourt les données en entrée et pour chaque chiffre, on ajoute la contrainte que le nombre de cases allumées
# dans la cellule centrée sur ce point est égal à ce chiffre
for i in range(ROWS):
    for j in range(COLS):
        c = puzzle[i][j]
        if c != ' ':
            c = int(c)
            problem += lpSum([cells[a][b] for a,b in voisins(i,j)]) == c

# On résout
problem.solve()

# Et on affiche : 0 -> case vide, 1->case coloriée, blanc->indéterminé
for i in range(ROWS):
        print("".join([str(int(value(cells[i][j]))) if value(cells[i][j]) is not None else ' ' for j in range(COLS)]))