sudoku.py

from scipy.optimize import linprog
# vim: set fileencoding=utf-8
K=3
N=K*K
c = [-1 for i in range(N**3)]
A = [[0 for i in range(N*N*N)] for i in range(4*N*N)]
b = [1 for i in range(4*N*N)]
for i in range(N):
    for j in range(N):
        for k in range(N):
            A[0*N*N+i*N+j][i*N*N+j*N+k]+=1
            A[1*N*N+j*N+k][i*N*N+j*N+k]+=1
            A[2*N*N+k*N+i][i*N*N+j*N+k]+=1
for i in range(N):
    for j in range(N):
        for k in range(N):
            ix,iy=i%K,i//K
            jx,jy=j%K,j//K
            l=iy*K+jy
            A[3*N*N+l*N+k][i*N*N+j*N+k]+=1

known_list=[]
board=[[int(i) for i in input().split()]for j in range(N)]
for i in range(N):
    for j in range(N):
        if board[i][j]>0:
            known_list.append((i,j,board[i][j]-1))
# 決定変数の下限、上限
x_bound = (0, 1)
bound=[x_bound for i in range(N*N*N)]
for x,y,z in known_list:
    t=x*N*N+y*N+z
    bound[t]=(1,1)
res = linprog(c, A_ub=A, b_ub=b, bounds=bound)
ans=[int(i+0.1) for i in res.x]
board=[[0 for j in range(N)]for i in range(N)]
for i in range(N):
    for j in range(N):
        for k in range(N):
            if ans[i*N*N+j*N+k]:
                board[i][j]=k+1
print("#"*30)
if sum(ans)==N*N:
    print("answer found")
for line in board:
    print(*line)