<jupyter_start><jupyter_text>SUDOKU GENERATION PLUS MACHINE LEARNING TESTS In this notebook, my aim is to use Machine Learning algorithms to distinguish if a given matrix of numbers is, or not, a [sudoku](https://en.wikipedia.org/wiki/Sudoku). For doing that, I divide the notebook into two sections:1. The first section is devoted to the creation of a database of sudokus and non-sudokus with their respective labels for future Machine Learning algorithms.2. In the second section, I will use some Machine Learning algorithms for trying to predict the "sudokuness" of a table of numbers. 1. Firstly with a [Decision tree](https://en.wikipedia.org/wiki/Decision_tree_learning), and later, [Random forest](https://en.wikipedia.org/wiki/Random_forest) classifiers. They seem natural to me in the process of creating rules for classification of sudokus. 2. Secondly, I use an [MLP neural network](https://en.wikipedia.org/wiki/Multilayer_perceptron) with one hidden layer. I believe this should be enough for my purpose.Sudokus are not the typical example when someone wants to use Machine Learning models (as far as I know) but they have special characteristics that made me think this could be a cool example.1. There are deterministic rules to distinguish a sudoku from a non-sudoku. Could a Machine Learning algorithm learn the rules we are all thinking or would find some other ways?2. Sudokus has a nice structure that make them invariant whenever swapping elements. For example, if in a sudoku one permutes all 1's by 2' and vice-versa, one finds another sudoku. Furthermore, one could imagine (as it was my case before checking my results) that whenever one has a sudoku, for being "fair" with the model, one should feed it with all possible permutations so that it can "understand" that the actual numbers appearing are not important, but the structure behind (a sudoku could be made by nine different symbols without any mathematical intrinsic meaning). The total number of new sudokus one obtain permuting elements from just one sudoku is $9! = 362.880$ . Which is quite a big number for just one "real sudoku". How would a Machine Learning model distinguish between sudoku and non-sudoku if one does not use billions of training examples?    1. Creating Sudoku and non-Sudoku database<jupyter_code># I will mainly work with numpy arrays and some lists from python, so I have to import the library.

import numpy as np<jupyter_output><empty_output><jupyter_text>I will define all functions at the begining<jupyter_code># This function checks wether a numpy array is a sudoku or not


def sudo_or_not(sudo):    
    if len(np.unique(sudo.flatten())) != 9:  #check whether there are nine numbers
        print("It is not a sudoku\nThere are not 9 different numbers")
        return
    for numb in np.unique(sudo.flatten()):    #check whether these nine numbers are from 1 to 9
        if not (numb in [1,2,3,4,5,6,7,8,9]):
            print("It is not a sudoku\nThe numbers should be between 1 and 9 (inclusive)")
            return
    for i in [0,3,6]:     #here I check not repeated numbers for the 9 inner squares 3x3
        for j in [0,3,6]:
            if len(np.unique(sudo[0+i:3+i,0+j:3+j].flatten())) < 9:
                print("It is not a sudoku\nThe inner square ",(i,j)," has some repeated pattern")
                return
    for hor in range(9):   #here I check for the horizontal lines (rows)
        if len(np.unique(sudo[hor,:])) < 9:
            print("It is not a sudoku\nThe horizontal line with index number ",hor," has some repeated pattern.")
            return
    for vert in range(9):  #here I check for the vertical lines (columns)
        if len(np.unique(sudo[:,vert])) < 9:
            print("It is not a sudoku\nThe vertical line with index number ",ver," has some repeated pattern.")
            return    
    print("It is a sudoku!")
    return         
# Similar to the function given above but without print and returning numbers. The reason is that if I want to use it 
# with large amounts of data is not useful that the info is given as stdout in the screen.


def sudo_or_not_numeric(sudo):    
    if len(np.unique(sudo.flatten())) != 9:  #check whether there are nine numbers
        
        return 0
    for numb in np.unique(sudo.flatten()):    #check whether these nine numbers are from 1 to 9
        if not (numb in [1,2,3,4,5,6,7,8,9]):
            
            return 0
    for i in [0,3,6]:     #here I check not repeated numbers for the 9 inner squares 3x3
        for j in [0,3,6]:
            if len(np.unique(sudo[0+i:3+i,0+j:3+j].flatten())) < 9:
                
                return 0
    for hor in range(9):   #here I check for the horizontal lines
        if len(np.unique(sudo[hor,:])) < 9:
            
            return 0
    for vert in range(9):  #here I check for the vertical lines
        if len(np.unique(sudo[:,vert])) < 9:
            
            return 0
    
    return 1        
# Swapping functions both for rows and columns that will be very useful for generating sudokus

def swap_row(sudo, i, j): # Given a 2D np.array it permutes row i and row j 
    sudo[[i,j]] = sudo[[j,i]]
    return 
def swap_column(sudo, i, j):   # Given a 2D np.array it permutes column i and row j 
    sudo[:,[i,j]] = sudo[:,[j,i]]
    return 
# Count how many numbers "numb" there are in each inner square in "sudo". For a sudoku it should be a 3x3 array with
# all entries equal 1. This is very important for the optimization problem that allow me to create sudokus

def inner_numb(sudo, numb):
    in_sq_mean = np.zeros((3,3))
    for i in range(3):    
        for j in range(3):
            in_sq_mean[i,j] = sum( sudo[0+3*i:3+3*i,0+3*j:3+3*j].flatten() == numb )
    return in_sq_mean
#Sudoku generator!
#First step, create seed, second step, shuffle (so that I obtain different ones), third step Make the sudoku


def sudoku_gen():
    
    # Creating the seed, from it we will be able to be all our sudokus. The interesting property about the seed is that  
    # it almost fulfil the conditions for sudoku. The only property that lacks is that it has repeated numbers inside the 
    # inner squares. Good news, if we permute columns or rows all the other properties are still satisfied and we can 
    # eventually find sudokus!
    
    list_seed = []
    for i in range(1,10):
        row_list = []
        for j in range(9):
            if i+j <= 9:
                row_list.append(j+i)
            else:
                row_list.append((i+j) % 9)
        list_seed.append(row_list)    
    new_seed = np.array(list_seed)
    
    # Shuffling the seed. This is just random shuffling for obtaining a different sudoku each time we run the sudoku
    # generator.
    
    for i in range(50):
        if np.random.randint(2) == 0:
            swap_column(new_seed, np.random.randint(9),np.random.randint(9))
        else:
            swap_row(new_seed, np.random.randint(9),np.random.randint(9))
            
    # Generating the sudoku. Given the shuffled seed, we intelligently shuffle until finding sudoku. 
    # This is done following a optimization algorithm. I can compute a number that will tell me how "far" is my table 
    # from being a sudoku. Then I choose the permutation that minimize the most this number until it is zero that is 
    # the case of sudokus!
    
    cond = 100
    count = 0
    while cond != 0:
        count += 1
        if count > 10:
            return sudoku_gen() # If I have done more than 10 permutations I restart, just in case!
        for r_c in range(2):
            for l in range(9):
                for k in range(9):
                    if r_c == 0:
                        swap_column(new_seed, l, k)
                    else:
                        swap_row(new_seed,l ,k)
                    new_cond = sum([np.var(inner_numb(new_seed,i)) for i in range(9)])
                    if new_cond < cond:
                        my_rc = r_c
                        my_l = l
                        my_k = k
                        cond = new_cond
                    if r_c == 0:
                        swap_column(new_seed, l, k)
                    else:
                        swap_row(new_seed,l ,k)
        if my_rc == 0:
            swap_column(new_seed, my_l, my_k)
        else:
            swap_row(new_seed,my_l ,my_k) 
        
    return new_seed             
# Non-Sudoku generator! 
# First step, create seed, second step, shuffle (so that I obtain different ones). I need non-sudokus for having a good 
# model. If not, everything will "be" a sudoku!


def rand_nosud_gen():
    
    #Creating the seed
    
    list_seed = []
    for i in range(1,10):
        row_list = []
        for j in range(9):
            if i+j <= 9:
                row_list.append(j+i)
            else:
                row_list.append((i+j) % 9)
        list_seed.append(row_list)    
    new_seed = np.array(list_seed)
    
    #Shuffling the seed
    
    for i in range(50):
        np.random.shuffle(new_seed[np.random.randint(9)])
        np.random.shuffle(new_seed[:,np.random.randint(9)])
        if np.random.randint(2) == 0:
            swap_column(new_seed, np.random.randint(9),np.random.randint(9))
        else:
            swap_row(new_seed, np.random.randint(9),np.random.randint(9))
        
    return new_seed             
# This function checks, given a list of 2D arrays, how many of them are equal as I do not want
# to have repeated data in features, neither sudoku or non-sudoku.

def equal_check(a_list, destructor = False):
    new_list = []
    deleting = []
    for element in a_list:
        my_string =""
        for inner in list(element.flatten()):
            my_string += str(inner)[0]
        new_list.append(int(my_string))
    if len(set(new_list)) == len(new_list):
        print("no problem!")
    else:
        print(len(new_list)-len(set(new_list)), "conflicting cases.")
        if destructor:
            for i in range(len(new_list)):
                for j in range(len(new_list)):
                    if i < j:
                        if new_list[i] == new_list[j]:
                            print("Elements ", i, " and ",j, " are equal.")
                            if destructor:
                                deleting.append(j)
                            
    if destructor:
        return deleting
    else:
        return       
# I create a random non-sudoku

random_no_sud = rand_nosud_gen()
print(random_no_sud)
# If I check if it is sudoku or not, I should obtain that it is not

sudo_or_not(random_no_sud)
# I just copy a sudoku from the internet and check that my sudoku function confirm that

one_sud = np.array([[7,3,5,6,1,4,8,9,2],[8,4,2,9,7,3,5,6,1],[9,6,1,2,8,5,3,7,4],[2,8,6,3,4,9,1,5,7],[4,1,3,8,5,7,9,2,6],[5,7,9,1,2,6,4,3,8],[1,5,7,4,9,2,6,8,3],[6,9,4,7,3,8,2,1,5],[3,2,8,5,6,1,7,4,9]])

print(one_sud)
sudo_or_not(one_sud)
# Printing my sudoku seed. From it, the sudoku generator makes all sudokus I need (and the non-sudoku generator
# makes all the non-sudokus I need as well)

list_seed = []

for i in range(1,10):
    row_list = []
    for j in range(9):
        if i+j <= 9:
            row_list.append(j+i)
        else:
            row_list.append((i+j) % 9)
    list_seed.append(row_list)    

new_seed = np.array(list_seed)
print(new_seed)        
# Swapping two columns to check the result is what I want

swap_column(new_seed, 0, 8)

new_seed
# Checking how many 3's there are in each inner square

inner_numb(new_seed, 3)
new_seed
# Creating a random sudoku from my sudoku generator

rand_sudo = sudoku_gen()

print(rand_sudo)
# Is it a sudoku?

sudo_or_not(rand_sudo)<jupyter_output>It is a sudoku!<jupyter_text>Creating 20.000 sudokus and non-sudokus with a 0.5 prob each in every step. It takes some hours for my computer, So I save the results in features and labels for loading them whenever I need. ```pythonhow_many = 20000features = np.zeros((how_many,81))labels   = np.zeros((how_many,))for i in range(how_many):    if np.random.randint(2) == 0:        features[i] = sudoku_gen().flatten()        labels[i]   = 1 yes    else:        features[i] = rand_nosud_gen().flatten()        labels[i]   = 0 no  np.save("features",features)np.save("labels",labels) ```<jupyter_code># Loading previously created features and labels

features = np.load("features.npy")
labels = np.load("labels.npy")
# How many sudokus have I created?

np.sum(labels)
# Extracting all sudokus and non-sudokus created

apparent_sudo = []

apparent_no_sudo = []

for i in range(20000):    
    if labels[i]==1:
        apparent_sudo.append(features[i].reshape(9,9))
    else:
        apparent_no_sudo.append(features[i].reshape(9,9))
# Checking if they are all really sudokus with my pre-made function

check_sum = 0

for element in apparent_sudo:    
    check_sum += sudo_or_not_numeric(element)
    
if check_sum == np.sum(labels):
    print("Yeah!")
# Checking if the others are all really non-sudokus with my pre-made function

check_sum = 0

for element in apparent_no_sudo:
    check_sum += sudo_or_not_numeric(element)
    
if check_sum == 0:
    print("Yeah!")
# How many sudokus that I have created are actually equal?

equal_check(apparent_sudo) 
# How many sudokus that I have not created are actually equal?

equal_check(apparent_no_sudo)
# Printing a sudoku from my dataset

print(apparent_sudo[0])
# Here I eliminate all equal ocurrences inside my dataset

destructing = equal_check(features, destructor = True) 

features = np.delete(features, destructing, 0)
labels = np.delete(labels, destructing, 0)
equal_check(features)<jupyter_output>no problem!<jupyter_text>Machine Learning classifiers<jupyter_code># Starting with Decision tree classifier. This and random forest seems natural as there is a deterministic algorithm
# for distinguish a Sudoku, I think these algorithms should be able to do that quite straightforwardly

from sklearn import tree
from sklearn.model_selection import train_test_split
from sklearn.model_selection import cross_val_score


X_train, X_test, y_train, y_test = train_test_split(features, labels, test_size = 0.3, random_state = 0)

clf = tree.DecisionTreeClassifier(random_state = 0, max_depth = 15)

clf.fit(X=X_train, y=y_train)
# Printing some metrics of the model

from sklearn.metrics import confusion_matrix

y_pred = clf.predict(X_test)

con_mat_clf = confusion_matrix(y_test, y_pred)

print("The accuracy of the model is ", clf.score(X=X_test, y=y_test), "\n")  

print("The confusion matrix is \n\n", con_mat_clf, "\n")

print("The precision is ", con_mat_clf[1,1]/(con_mat_clf[0,1]+con_mat_clf[1,1]), "\n")

print("The sensitivity (recall) is ", con_mat_clf[1,1]/(con_mat_clf[1,0]+con_mat_clf[1,1]), "\n")

print("And so, the F1 score is ", 2*con_mat_clf[1,1]/(2*con_mat_clf[1,1]+con_mat_clf[1,0]+con_mat_clf[0,1]), " very similar to the accuracy, as we have more or less same number of sudokus and non-sudokus")<jupyter_output>The accuracy of the model is  0.8751250416805602 

The confusion matrix is 

 [[2545  464]
 [ 285 2704]] 

The precision is  0.8535353535353535 

The sensitivity (recall) is  0.9046503847440616 

And so, the F1 score is  0.8783498457040767  very similar to the accuracy, as we have more or less same number of sudokus and non-sudokus<jupyter_text>Not such a bad accuracy for just one tree! But making more depth does not improve so much the accuracy... Lets see a random forest.<jupyter_code># Importing a random forest classifier

from sklearn.ensemble import RandomForestClassifier

forest_clf = RandomForestClassifier(n_estimators = 250, random_state = 0)
forest_clf.fit(X_train, y_train)
# Lets see the metrics!

y_pred_forest = forest_clf.predict(X_test)

con_mat_forest = confusion_matrix(y_test, y_pred_forest)

print("The accuracy of the model is ", forest_clf.score(X=X_test, y=y_test), "\n")  

print("The confusion matrix is \n\n", con_mat_forest, "\n")

print("The precision is ", con_mat_forest[1,1]/(con_mat_forest[0,1]+con_mat_forest[1,1]), "\n")

print("The sensitivity (recall) is ", con_mat_forest[1,1]/(con_mat_forest[1,0]+con_mat_forest[1,1]), "\n")

print("And so, the F1 score is ", 2*con_mat_forest[1,1]/(2*con_mat_forest[1,1]+con_mat_forest[1,0]+con_mat_forest[0,1]))
# I want to know the maximum sudoku-probability in the set of non-sudokus from test, and the minimum of 
# sudoku-probabilities in the set of sudokus from test. The question is, is there clear gap?

sudo_prob_forest = []

no_sudo_prob_forest = []

for i in range(len(X_test)):
    if y_test[i] == 1:
        sudo_prob_forest.append(forest_clf.predict_proba(X_test[i].reshape(1,81))[0,1])
    else:
        no_sudo_prob_forest.append(forest_clf.predict_proba(X_test[i].reshape(1,81))[0,1])
        
print("The minimum of sudo-prob in the set of sudo is ", np.min(sudo_prob_forest), " \nThe maximum of sudo-prob in the set of non-sudos is ", np.max(no_sudo_prob_forest))<jupyter_output>The minimum of sudo-prob in the set of sudo is  0.524  
The maximum of sudo-prob in the set of non-sudos is  0.5<jupyter_text>Fantastic! So this monster can classify 100 % of the cases. But there are two main problems:1. It hasn't very clear the division of what is and what is not a sudoku.2. This model is really huge. Can we do something similar with a more compact (or reasonable) model? One thing that comes to my mind for solving both problems is:  Now lets see how good is a MLP neural modelFrom my point of view, just one hidden layer with around 27 neurons will be able to make the trick. Why? Well, there is 9 rows, 9 columns and 9 inner-squares<jupyter_code># As I just want one hidden layer, I think MLPClassifier from scikit-learn is good enough

from sklearn.neural_network import MLPClassifier

mlp = MLPClassifier(hidden_layer_sizes=(27,), tol=0.00000001, activation = 'logistic', max_iter = 400, random_state = 0) #27 makes so much sense for sudokus

mlp.fit(X_train,y_train)
# Lets see the metrics!

y_pred_mlp = mlp.predict(X_test)

con_mat_mlp = confusion_matrix(y_test, y_pred_mlp)

print("The accuracy of the model is ", mlp.score(X=X_test, y=y_test), "\n")  

print("The confusion matrix is \n\n", con_mat_mlp, "\n")

print("The precision is ", con_mat_mlp[1,1]/(con_mat_mlp[0,1]+con_mat_mlp[1,1]), "\n")

print("The sensitivity (recall) is ", con_mat_mlp[1,1]/(con_mat_mlp[1,0]+con_mat_mlp[1,1]), "\n")

print("And so, the F1 score is ", 2*con_mat_mlp[1,1]/(2*con_mat_mlp[1,1]+con_mat_mlp[1,0]+con_mat_mlp[0,1]))<jupyter_output>The accuracy of the model is  1.0 

The confusion matrix is 

 [[3009    0]
 [   0 2989]] 

The precision is  1.0 

The sensitivity (recall) is  1.0 

And so, the F1 score is  1.0<jupyter_text>Awesome!<jupyter_code># I want to know the maximum sudoku-probability in the set of non-sudokus from test, and the minimum of 
# sudoku-probabilities in the set of sudokus from test. The question is, is there clear gap?

sudo_prob_mlp = []

no_sudo_prob_mlp = []

for i in range(len(X_test)):
    if y_test[i] == 1:
        sudo_prob_mlp.append(mlp.predict_proba(X_test[i].reshape(1,81))[0,1])
    else:
        no_sudo_prob_mlp.append(mlp.predict_proba(X_test[i].reshape(1,81))[0,1])
        
print("The minimum of sudo-prob in the set of sudo is ", np.min(sudo_prob_mlp), " \nThe maximum of sudo-prob in the set of non-sudos is ", np.max(no_sudo_prob_mlp))<jupyter_output>The minimum of sudo-prob in the set of sudo is  0.9997766935737521  
The maximum of sudo-prob in the set of non-sudos is  0.3048344138661222
StarcoderdataJupyterStructuredCleanDedup