manbet体育手机客户端

sudoku.py

#！/usr/bin/python # Copyright 2019, 狗万app足彩Gurobi Optimization, LLC # Sudoku示例。数独板是一个9x9的网格，它被进一步划分为3x3的网格。网格中的每个单元格都必须接受0到9之间的值。在同一行、列或3x3子网格中，没有两个网格单元格可以使用#相同的值。# #在MIP公式中，二进制变量x[i,j,v]表示# cell 是否取值'v'。约束条件如下:# 1。每个单元格必须恰好取一个值(sum_v x[i,j,v] = 1) # 2。每个值每一行使用一次(sum_i x[i,j,v] = 1) # 3。每个值每列使用一次(sum_j x[i,j,v] = 1) # 4。 Each value is used exactly once per 3x3 subgrid (sum_grid x[i,j,v] = 1) # # Input datasets for this example can be found in examples/data/sudoku*. import sys import math from gurobipy import * if len(sys.argv) < 2: print('Usage: sudoku.py filename') quit() f = open(sys.argv[1]) grid = f.read().split() n = len(grid[0]) s = int(math.sqrt(n)) # Create our 3-D array of model variables model = Model('sudoku') vars = model.addVars(n,n,n, vtype=GRB.BINARY, name='G') # Fix variables associated with cells whose values are pre-specified for i in range(n): for j in range(n): if grid[i][j] != '.': v = int(grid[i][j]) - 1 vars[i,j,v].LB = 1 # Each cell must take one value model.addConstrs((vars.sum(i,j,'*') == 1 for i in range(n) for j in range(n)), name='V') # Each value appears once per row model.addConstrs((vars.sum(i,'*',v) == 1 for i in range(n) for v in range(n)), name='R') # Each value appears once per column model.addConstrs((vars.sum('*',j,v) == 1 for j in range(n) for v in range(n)), name='C') # Each value appears once per subgrid model.addConstrs(( quicksum(vars[i,j,v] for i in range(i0*s, (i0+1)*s) for j in range(j0*s, (j0+1)*s)) == 1 for v in range(n) for i0 in range(s) for j0 in range(s)), name='Sub') model.optimize() model.write('sudoku.lp') print('') print('Solution:') print('') # Retrieve optimization result solution = model.getAttr('X', vars) for i in range(n): sol = '' for j in range(n): for v in range(n): if solution[i,j,v] > 0.5: sol += str(v+1) print(sol)