# -*- coding: utf-8 -*-
"""sudoku_solver.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1DhhjghnCGoZO3GPXQESZIM8PgGdEk1nG
"""

!pip install pulp
from pulp import *

import time
import numpy as np # linear algebra
import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)

"""**Sudoku Solver function**"""

def solver(input_quiz): # input string
    quiz = np.reshape([int(c) for c in input_quiz], (9,9))

    # Create the LP Problem
    prob = LpProblem("Sudoku_Solver", LpMinimize)

    Rows = Cols = Boxes = range(0,9)
    Values = range(1,10)

    # Decision Variable/Target variable
    X = LpVariable.dicts("cell_value", (Rows, Cols, Values), cat = 'Binary') 

    # No objective function needed. Just randomly create one
    prob.setObjective(lpSum(0))


# Create the default sudoku constraints
#-------------------------------------------------------------------------------
    # Cell Constraint: only one value from 1 to 9 is filled for the cell
    for r in Rows:
        for c in Cols:
              prob += lpSum([X[r][c][v] for v in Values]) == 1, ''
    # Row constraint: each value from 1 to 9 is filled only once in the row
    for r in Rows:
        for v in Values:
              prob += lpSum([X[r][c][v]  for c in Cols]) == 1, ''
    # Column Constraint: each value from 1 to 9 is filled only once in the column        
    for c in Cols:
        for v in Values:
              prob += lpSum([X[r][c][v]  for r in Rows]) == 1, ''
    # Box Constraint: to ensure that values from 1 to 9 is filled only once in the 3x3 box       
    for b in Boxes:
        b_row = int(b/3)
        b_col = int(b%3)
        for v in Values:
              prob += lpSum([X[b_row*3+r][b_col*3+c][v]  for c in range(0,3) for r in range(0,3)]) == 1, ''
#===============================================================================


# Create the prefilled values from input sudoku as constraints
#-------------------------------------------------------------------------------
    for r in Rows:
        for c in Cols:
            if(quiz[r][c] != 0):
                  prob += lpSum([X[r][c][v]*v for v in Values]) == quiz[r][c], ''
#===============================================================================


    # Solve the problem
    prob.solve()

# Extract the solution if an optimal solution has been identified
#-------------------------------------------------------------------------------
    if LpStatus[prob.status] == 'Optimal':
        soln_matrix = np.zeros((9,9)).astype(int)
        soln_str = ''
        for r in Rows:
            for c in Cols:
                for v in Values:
                    if value(X[r][c][v]):
                        soln_matrix[r][c] = v
                        soln_str += str(v)
#===============================================================================
    return soln_matrix, soln_str

"""**Output Accuracy**"""

import random

# import Sudoku quiz data string
data = pd.read_csv("large2.csv")
N = len(data)

#--------------------------------------------------------------
# For large data set (comment out for testing small data set) |
#--------------------------------------------------------------
randomlist = random.sample(range(0, N), 1000)
#==============================================================

# Test the algoritm on the above 'data' data set.
corr_cnt = 0
start = time.time()


j = 0
#----------------------------------------------------------------------
# Use 'range(N)' for Small-dataset and 'randomlist' for Large-dataset |
#----------------------------------------------------------------------
for i in randomlist:
    j += 1
    quiz = data["quizzes"][i] # variable type == string
    solu = data["solutions"][i] # variable type == string

    # Solving the Sudoku Quiz
    soln_matrix, soln_str = solver(quiz)

    # map to board, ouput accuracy
    if soln_str != solu:
        # make sure the variable types match
        pass
    else:
        #print("CORRECT")
        corr_cnt += 1
    
    if j % 150 == 0: # number (after %) has to be adjusted
        end = time.time()
        print("Aver Time: {t:6.2f} secs. Success rate: {corr} / {all} ".format(t=(end-start)/(j), corr=corr_cnt, all=j) )

end = time.time()
print("Aver Time: {t:6.2f} secs. Success rate: {corr} / {all} ".format(t=(end-start)/(j), corr=corr_cnt, all=j) )

"""**Display the Sudoku in Grid**"""

#-------------------------------------------------------------------------------
def print_Sudoku_Grid(Name, input_quiz, Rows, Cols):

    # Conver string to matrix
    Solution = np.reshape([int(c) for c in input_quiz], (9,9))

    # Print to grid
    print(f"\n\n{Name}:")
    print("+---------+---------+---------+", end = "")
    for r in Rows:
        print(end = "\n| ")
        for c in Cols:
            num_end = " | " if ((c+1)%3 == 0) else "  "
            if Solution[r][c] != 0:
                print(Solution[r][c], end = num_end)
            else:
                print(' ', end = num_end)

        if ((r+1)%3 == 0):
            print("\n+---------+---------+---------+", end = "")
#-------------------------------------------------------------------------------



import numpy as np # linear algebra

data = pd.read_csv("small1.csv")
quiz = data["quizzes"][7] # string
solu = data['solutions'][7] # string
soln_matrix, soln_str = solver(quiz)



print_Sudoku_Grid('Given Quiz', quiz, range(0,9), range(0,9))
print_Sudoku_Grid('Computed Result', soln_str, range(0,9), range(0,9))
print_Sudoku_Grid('Correct Solution', solu, range(0,9), range(0,9))