grid.py

########################
## Sashank Thupukari   #
## 11/21/2014          #
## Pd. 6               #
########################

SIZE = 4

class Cell(object):
    def __init__(self, val, r, c, matrix):
        if (val != 0):
            self.value = {val, }
        else:
            self.value = {1, 2, 3, 4,}
        self.row = r
        self.col = c
        Cell.matrix = matrix
    def __str__(self):
        if (len(self.value) > 1):
            return '0'
        else:
            element = min(self.value)
            return str(element)

def createTheSudokuBoard():
    M = []
    string = "12342...3...4..."
    string = string.replace(".", "0")
    for x in range(SIZE):
        row = []
        for y in range(SIZE):
            row.append(int(string[0]))
            string = string[1:]
        M.append(row)
    matrix = []
    for r in range(SIZE):
        row = []
        for c in range(SIZE):
            row.append(Cell(M[r][c], r, c, matrix))
        matrix.append(row)
    return matrix

def printMatrix(matrix):
    print()
    for x in matrix:
        print()
        for y in x:
            print(y, end=" ")
    print()
    print("Empty:", numberOfEmptySells(matrix))
    print()

def checkRowsAndColumns(matrix):
    while True:
        (matrix, condition) = checkRowsAndColumnsHelper(matrix)
        if(condition == True):
            return matrix

def checkRowsAndColumnsHelper(matrix):
    for x in range(SIZE):
        for y in range(SIZE):
            if(len(matrix[x][y].value) > 1):
                for i in range(SIZE):
                    currentCell = matrix[x][i]
                    if(len(currentCell.value) == 1):
                        matrix[x][y].value -= currentCell.value
                        if(len(matrix[x][y].value) == 1):
                            printChange(matrix[x][y], "checkRow")
                            return (matrix, False)
                for j in range(SIZE):
                    currentCell = matrix[j][y]
                    if(len(currentCell.value) == 1):
                        matrix[x][y].value -= currentCell.value
                        if(len(matrix[x][y].value) == 1):
                            printChange(matrix[x][y], "checkColumn")
                            return (matrix, False)
    return (matrix, True)


def checkUniques(matrix):
    while True:
        (matrix, condition) = checkUniquesHelper(matrix)
        if(condition == True):
            return matrix
        else:
            matrix = reduceMatrix(matrix)


def checkUniquesHelper(matrix):
    for x in range(SIZE):
        currentRow = matrix[x]
        frequencyMap = {}
        for cell in currentRow:
            if(len(cell.value) > 1):
                for value in cell.value:
                    if(value in frequencyMap):
                        frequencyMap[value] = frequencyMap[value] + 1
                    else:
                        frequencyMap[value] = 1
        for x in frequencyMap:
            if(frequencyMap[x] == 1):
                for cell in currentRow:
                    if(x in cell.value and len(cell.value) > 1):
                        cell.value = {x}
                        printChange(cell, "uniqueRow")
                        return (matrix, False)
    for y in range(SIZE):
        currentCol = [row[y] for row in matrix]
        frequencyMap = {}
        for cell in currentCol:
            if(len(cell.value) > 1):
                for value in cell.value:
                    if(value in frequencyMap):
                        frequencyMap[value] = frequencyMap[value] + 1
                    else:
                        frequencyMap[value] = 1
        for x in frequencyMap:
            if(frequencyMap[x] == 1):
                for cell in currentCol:
                    if(x in cell.value and len(cell.value) > 1):
                        cell.value = {x}
                        printChange(cell, "uniqueColumn")
                        return (matrix, False)

    return (matrix, True)


def allCellsHaveValues(matrix):
    for x in range(SIZE):
        for y in range(SIZE):
            if(matrix[x][y].value == set()):
                return False
    else:
        return True


def numberOfEmptySells(matrix):
    count = 0
    for x in range(SIZE):
        for y in range(SIZE):
            if(len(matrix[x][y].value) > 1):
                count += 1
    return count


def reduceMatrix(matrix):
    matrix = checkRowsAndColumns(matrix)
    return matrix


def printChange(cell, method):
    print("\t %s \t| Cell (%s,%s) =>| %s" %
          (method, cell.row, cell.col, cell.value))


def duplicatesExist(thelist):
    seen = set()
    for x in thelist:
        if(len(x) == 1):
            (element,) = x
            x = element
            if x in seen:
                return (True, x)
            seen.add(x)
    return (False, 0)


def solutionIsPossible(matrix):
    rows = [[], [], [], [], [], [], [], [], [], ]
    cols = [[], [], [], [], [], [], [], [], [], ]

    for r in range(SIZE):
        for c in range(SIZE):
            rows[r].append(matrix[r][c].value)
            cols[c].append(matrix[r][c].value)

    for r in rows:
        (condition, value) = duplicatesExist(r)
        if condition:
            print("Duplicate in Row", r, {value})
            return False
    for c in cols:
        (condition, value) = duplicatesExist(c)
        if condition:
            print("Duplicate in Column", c, {value})
            return False
    return True


def solutionIsCorrect(matrix):
    if(numberOfEmptySells(matrix) > 0):
        return False

    rows = [[], [], [], [], ]
    cols = [[], [], [], [],  ]

    for r in range(SIZE):
        for c in range(SIZE):
            rows[r].append(matrix[r][c].value)
            cols[c].append(matrix[r][c].value)

    for r in rows:
        for n in range(1, SIZE + 1):
            if {n} not in r:
                print("Error: Missing in Rows", r, {n})
                return False

    for c in cols:
        for n in range(1, SIZE + 1):
            if {n} not in c:
                print("Error: Missing in Column", c, {n})
                return False

    return True


def recursiveSolve(matrix):
    matrix = reduceMatrix(matrix)
    if(solutionIsCorrect(matrix)):
        return matrix
    oldMatrix = deepcopy(matrix)
    if((not allCellsHaveValues(matrix)) or (not solutionIsPossible(matrix))):
        return matrix
    print("Entering Recursive solve")
    (r, c) = cellWithSmallestSet(matrix)
    for guess in matrix[r][c].value:
        matrix[r][c].value = {guess}
        matrix = recursiveSolve(matrix)
        print("Return from Recursion")
        if(solutionIsCorrect(matrix)):
            print("Good Guess. Returning Matrix")
            return matrix
        else:
            print("Bad Guess. Resetting Matrix")
        matrix = restoreValues(matrix, oldMatrix)
    return matrix


def restoreValues(matrix, oldMatrix):
    for x in range(SIZE):
        for y in range(SIZE):
            matrix[x][y].value = oldMatrix[x][y].value
    return matrix


def cellWithSmallestSet(matrix):
    minSet = float("inf")
    found = False
    for x in range(SIZE):
        for y in range(SIZE):
            if(len(matrix[x][y].value) > 1):
                if(len(matrix[x][y].value) < minSet):
                    minSet = len(matrix[x][y].value)
                    print("Making guess at", x, y)
                    minCords = (x, y)
                    found = True
    if found:
        return minCords


def main():
    matrix = createTheSudokuBoard()
    printMatrix(matrix)
    matrix = reduceMatrix(matrix)
    matrix = checkUniques(matrix)
    matrix = recursiveSolve(matrix)
    printMatrix(matrix)

    print("-------CHECKS--------") 
    if(numberOfEmptySells(matrix) == 0):
        print("SolutionCheck:", solutionIsCorrect(matrix))
    else:
        print("No Duplicates:", solutionIsPossible(matrix))

    print("All Cells Have Values:", allCellsHaveValues(matrix))

if __name__ == '__main__':
    from copy import deepcopy
    main()