<jupyter_start><jupyter_text>Solving Sudoko with MIP  <NAME>   06.2019Problem formulation : We note N=size*size * **Objective function** : 0  * **Variables** : $$x_{i,j,k}=1~if~the~number~k~is~in~the~row~i~and~the~column~j~and~0~otherwise$$ * **Constraints**  1. Each case in the Sudoku should have only one number : $$\sum_{k=1}^{N} x_{ijk} = 1~\forall~(i,j) \in \{1..N\}*\{1..N\}$$	2. Each number is used once in each row $$\sum_{i=1}^{N} x_{ijk} = 1~\forall~(j,k) \in \{1..N\}*\{1..N\}$$	2. Each number is used once in each column $$\sum_{j=1}^{N} x_{ijk} = 1~\forall~(i,k) \in \{1..N\}*\{1..N\}$$4.Each number should be present once in every "group" :$$\sum_{i=p}^{p+2}\sum_{j=q}^{q+2} x_{ijk} = 1~\forall~k \in \{1..N\}$$$$ p~and~q~are~multiples~of~size,~strictly~smaller~than~N~$$5. To express the numbers fixed from the beginning, we should introduce the following constraint :$$x_{ijk} = 1$$$$for~example~x_{115}=1 if~the~element~(1,1)~is~fixed~to~have~the~value~5 $$	 --- The code :<jupyter_code>import numpy as np
import cvxopt
import cvxopt.glpk
from cvxopt import matrix
import pandas as pd
size=3
n=size*size
#Initial Configuration of the sudoku table
Ai = np.array([
[0,8,0, 9,0,1, 0,5,0],
[0,0,2, 6,8,7, 3,0,0],
[0,0,3, 0,0,0, 6,0,0],
[3,9,0, 0,0,0, 0,6,5],
[6,0,0, 4,7,5, 0,0,3],
[5,7,0, 0,0,0, 0,8,4],
[0,0,9, 0,0,0, 8,0,0],
[0,0,5, 1,2,4, 9,0,0],
[0,4,0, 8,0,3, 0,2,0]])
ii=pd.DataFrame(Ai)
newcol=['|','|','|','|','|','|','|','|','|']
ii.insert(loc=3,column='O',value=newcol)
ii.insert(loc=7,column='o',value=newcol)
print ("intial configuration")
ii
## Bijection from i,j,k to the index in the x-vector

def indice(i,j,k,size):
    n = size*size
    return(k+ j*n+ i*n*n)
## Take into account initial configuration
def initialconstraints(Ini,size):
  n=size*size
  nb=np.count_nonzero(Ini)
  A=np.zeros((nb,n*n*n))
  m=0
  for i in range(n):
    for j in range(n):
      if Ini[i,j]>0:
        A[m,indice(i,j,Ini[i,j]-1,size)]=1
        m=m+1
  return A

#line constraints
def lineconstraints(size):
  n=size*size
  m=0
  A=np.zeros((n*n,n*n*n))
  for j in range(n):
    for k in range(n):
      for i in range(n):
        A[m,indice(i,j,k,size)]=1
      m=m+1
  return A

#column constraints
def columnconstraints(size):
  n=size*size
  m=0
  A=np.zeros((n*n,n*n*n))
  for i in range(n):
    for k in range(n):
      for j in range(n):
        A[m,indice(i,j,k,size)]=1
      m=m+1
  return A
    

#column constraints
def columnconstraints(size):
  n=size*size
  m=0
  A=np.zeros((n*n,n*n*n))
  for i in range(n):
    for k in range(n):
      for j in range(n):
        A[m,indice(i,j,k,size)]=1
      m=m+1
  return A

#one number in every case
def kconstraint(size):
  n=size*size
  m=0
  A=np.zeros((n*n,n*n*n))
  for i in range(n):
    for j in range(n):
      for k in range(n):
        A[m,indice(i,j,k,size)]=1
      m=m+1
  return A    
    
  
#group constraints
def groupconstraints(size):
  m=0
  n=size*size
  A=np.zeros((n*n,n*n*n))
  for k in range(n):
    for p in range(size):
      for q in range(size):
        for ii in range (size):
          for jj in range(size):
            A[m,indice(size*p+ii,size*q+jj,k,size)]=1
        m=m+1
  return A
#Constraints Matrix
A=np.vstack((initialconstraints(Ai,size),lineconstraints(size),columnconstraints(size),groupconstraints(size),kconstraint(size)))
A.shape
## solving
def solving(A):
  b=matrix(np.ones(A.shape[0])) 
  c=matrix(np.zeros(A.shape[1])) 
  G=matrix(np.zeros(A.shape))
  h=matrix(np.zeros(A.shape[0]))
  M=matrix(A)
  (status, solution) = cvxopt.glpk.ilp(c=c,G=G,h=h,A=M,b=b,B=set(range(A.shape[1])))
  return (status, solution)
(status,solution)=solving(A)
import pandas as pd 
def show(solution,size):
  n=size*size
  l=[]
  for ind in range(size*size):
    l.append(ind+1)
  df = pd.DataFrame(index=l,columns=l)
  for i in range(n):
    for j in range(n):
      for k in range(n):
        if solution[indice(i,j,k,size)]==1:
          df.loc[i+1,j+1]=k+1
  return df
df=show(solution,size)
newcol=['|','|','|','|','|','|','|','|','|']
df.insert(loc=3,column='O',value=newcol)
df.insert(loc=7,column='o',value=newcol)
print("Solution of the sudoku")
df<jupyter_output>Solution of the sudoku<jupyter_text>--- Let's find the result for the second table (with fewer intial elements)<jupyter_code>Aih = np.array([
[7,0,0, 0,0,0, 4,0,0],
[0,2,0, 0,7,0, 0,8,0],
[0,0,3, 0,0,8, 0,0,9],
[0,0,0, 5,0,0, 3,0,0],
[0,6,0, 0,2,0, 0,9,0],
[0,0,1, 0,0,7, 0,0,6],
[0,0,0, 3,0,0, 9,0,0],
[0,3,0, 0,4,0, 0,6,0],
[0,0,9, 0,0,1, 0,0,5]])
iih=pd.DataFrame(Aih)
newcol=['|','|','|','|','|','|','|','|','|']
iih.insert(loc=3,column='O',value=newcol)
iih.insert(loc=7,column='o',value=newcol)
print ("intial configuration")
iih
Ah=np.vstack((initialconstraints(Aih,size),lineconstraints(size),columnconstraints(size),groupconstraints(size),kconstraint(size)))
(statush,solutionh)=solving(Ah)
dfh=show(solutionh,size)
newcol=['|','|','|','|','|','|','|','|','|']
dfh.insert(loc=3,column='O',value=newcol)
dfh.insert(loc=7,column='o',value=newcol)
print("Solution of the harder sudoku")
dfh<jupyter_output>Solution of the harder sudoku<jupyter_text>--- Let's find the result for the special version (the computer scientist version)*we have replaced the value 0 in the intial configuration given in the statement by G<jupyter_code>size2=4
n2=size2*size2
#Initial Configuration of the sudoku table
Ais = np.array([
[8,15,0,12,0,0,0,0,0,10,0,0,0,0,0,6],
[0,0,0,10,0,0,0,15,0,0,0,11,7,4,13,0],
[11,0,4,0,0,0,13,6,0,7,0,0,16,0,5,0],
[1,0,0,0,0,0,0,16,3,0,9,2,0,0,0,0],
[0,0,0,0,0,1,15,13,0,3,16,0,0,14,7,4],
[0,1,0,6,0,0,0,12,0,11,0,0,10,0,3,0],
[0,12,0,13,0,0,6,3,0,5,0,0,9,2,0,0],
[9,0,3,4,14,0,2,0,0,0,7,13,0,0,0,0],
[0,0,0,0,5,7,0,0,0,8,0,12,3,16,0,10],
[0,0,14,2,0,0,4,0,7,1,0,0,15,0,6,0],
[0,5,0,3,0,0,8,0,9,0,0,0,14,0,12,0],
[7,16,6,0,0,12,9,0,13,14,3,0,0,0,0,0],
[0,0,0,0,13,14,0,4,16,0,0,0,0,0,0,2],
[0,7,0,8,0,0,12,0,4,2,0,0,0,11,0,5],
[0,2,9,14,11,0,0,0,5,0,0,0,4,0,0,0],
[6,0,0,0,0,0,7,0,0,0,0,0,1,0,8,3]
])
iis=pd.DataFrame(Ais)
newcol=['|','|','|','|','|','|','|','|','|','|','|','|','|','|','|','|']
iis.insert(loc=4,column='O',value=newcol)
iis.insert(loc=9,column='o',value=newcol)
iis.insert(loc=14,column='0',value=newcol)
print ("intial configuration")
iis.replace([10,11,12,13,14,15,16],['A','B','C','D','E','F','G'])
As=np.vstack((initialconstraints(Ais,size2),lineconstraints(size2),columnconstraints(size2),groupconstraints(size2),kconstraint(size2)))
(statuss,solutions)=solving(As)
dfs=show(solutions,size2)
newcol=['|','|','|','|','|','|','|','|','|','|','|','|','|','|','|','|']
dfs.insert(loc=4,column='O',value=newcol)
dfs.insert(loc=9,column='o',value=newcol)
dfs.insert(loc=14,column='0',value=newcol)
print('the solution of 16*16 sudoku')
dfs.replace([10,11,12,13,14,15,16],['A','B','C','D','E','F','G'])<jupyter_output>the solution of 16*16 sudoku
{'fraction_non_alphanumeric': 0.2621132516053707, 'fraction_numerical': 0.08639813193228255, 'mean_word_length': 5.950304259634889, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '234394', 'license': 'Apache-2.0', 'n_tokens_mistral': 3456, 'n_tokens_neox': 3325, 'n_words': 527, 'path': 'sudoku_LP.ipynb', 'repo_name': 'belgacemi/Sudoku-', 'size': '6859'}