sudoku

#!/usr/bin/env python
# coding: utf-8

# In[1]:


# sections of code borrowed from "You will Never Want to Play Sudoku Again" by Srini Devadas
# https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-s095-programming-for-the-puzzled-january-iap-2018/puzzle-8-you-wont-want-to-play-sudoku-again/sudoku.py
# Whatever license Srini chose applies to the code he or his grad students wrote. Standard MIT license applies to anything else that I wrote.


# In[2]:


import numpy as np


# In[3]:


# global to keep track of the number of backtracks necessary
limit = 10000
backtracks = 0


# In[5]:


def findNextCellToFill(grid):
    # Takes a 9 by 9 grid and looks row by column for the first zero.
    # Returns either x, y coordinates of first '0' or -1, -1
    for x in range(0, 9):
        for y in range(0, 9):
            if grid[x][y] == 0:
                return x, y
    return -1, -1


# In[6]:


def isValid(grid, i, j, e):
    # takes a 9 by 9 grid; i,j coordinates; and a number 'e' then looks row-wise, column-wise, and sector-wise for duplicates of the number 'e''
    # returns True if passes row/column/sector checks.
    # returns False otherwise
    rowOk = all([e != grid[i][x] for x in range(9)])
    if rowOk:
        columnOk = all([e != grid[x][j] for x in range(9)])
        if columnOk:
            # find the top left x, y coordinate of section containing the i,j cell
            secTopX, secTopY = 3*(i//3), 3*(j//3)
            for x in range(secTopX, secTopX+3):
                for y in range(secTopY, secTopY+3):
                    if grid[x][y] == e:
                        return False
            return True
    return False


# In[7]:


def makeRandomSudoku(number_of_randoms):
    # generates a random board with no constraints
    # board has number_of_randoms filled in values with all other values as zero
    grid_list = [0]*81
    locations = np.random.choice(81, number_of_randoms, replace=False)
    for location in locations:
            grid_list[location] = int(np.random.randint(1,high=10))

    i = 0
    grid = []
    while i < len(grid_list):
        grid.append(grid_list[i:i+9])
        i+=9
    return grid


# In[8]:


def solveSudoku(grid, i=0, j=0):
    # fills in missing squares of Sudoku puzzle using rules with a brute-force guess/check
    # takes a grid and starts looking in the top left corner i,j = 0,0
    global limit
    global backtracks
    if backtracks < limit:
        i, j = findNextCellToFill(grid)
        if i == -1:
            # we solved it or there's nothing left to solve
            return True

        for e in range (1, 10):
            # try different valies in i, j location
            if isValid(grid, i, j, e):
                grid[i][j] = e
                if solveSudoku(grid, i, j):
                    return True

                # undo current cell for backtracking
                if backtracks < limit:
                    backtracks += 1
                    grid[i][j] = 0
                else:
                    return False
    else:
        return False


# In[9]:


def printSudoku(grid):
    numrow = 0
    for row in grid:
        if numrow % 3 == 0 and numrow != 0:
            print(' ')
        print(row[0:3], ' ', row[3:6], ' ', row[6:9])
        numrow += 1
    return


# In[10]:


def process_input(grid):
    # converts a grid into a flat list with one-hot encoding
    onehot_encoded = list()
    flat_grid = [item for sublist in grid for item in sublist]
    for value in flat_grid:
        temp = [0 for _ in range(10)]
        temp[value - 1] = 1
        onehot_encoded.append(temp)
    #flat_onehot_grid = [item for sublist in onehot_encoded for item in sublist]
    return onehot_encoded


# In[11]:


def build_dataset(number_of_datapoints, number_of_randoms):
    # takes an int, number_of_datapoints, and builds a dataset of solvable Sudoku grids
    # each test_grid will have number_of_randoms constraints
    test_grid
    test_grid = makeRandomSudoku(number_of_randoms)



# In[12]:


import tensorflow as tf
print(tf.__version__)
tf.enable_eager_execution()


# In[51]:


def generate_pair():
    global backtracks
    # generates an unsolved and solved grid
    solved = makeRandomSudoku(5)
    unsolved = solved[:][:]
    if solveSudoku(solved):
        print(id(unsolved))
        print(id(solved))
        return unsolved, solved
    elif solveSudoku(solved) is None:
        pass
    else:
        backtracks = 0
        solved = makeRandomSudoku(5)
        unsolved = solved[:][:]
        generate_pair()


# In[14]:


backtracks = 0
solved = makeRandomSudoku(15)
printSudoku(solved)
if solveSudoku(solved):
    print('\n')
    printSudoku(solved)


# In[63]:


backtracks = 0
asdf1, asdf2 = generate_pair()