Assignment 3 - Question 3

===================================================================================================================
Input/Output
===================================================================================================================
IN:
059000483
000000012
010028000
098074020
040080030
070630540
000160050
620000000
735000860

OUT:
2 5 9 7 1 6 4 8 3
0 6 0 0 0 0 0 1 2
0 1 0 0 2 8 0 0 0
0 9 8 0 7 4 0 2 0
0 4 0 0 8 0 0 3 0
0 7 0 6 3 0 5 4 0
0 8 0 1 6 0 0 5 0
6 2 0 0 0 0 0 0 0
7 3 5 0 0 0 8 6 0

===================================================================================================================
Main Function
===================================================================================================================
# Jethro Muller
# Assignment 9 - Q3: Sudoku Solver
# MLLJET001
# 12.05.2013

from TestListQ3 import testSudoku
state = []
def toIntList2D(lst):
    """Function that works with a 2D list as the parameter\nIt returns the list as a list of integers"""
    newLst = []
    for i in range(9):
        newLst.append([int(lst[i][j]) for j in range(9)])
    return newLst

def toIntList(lst):
    """Takes a list as the parameter\nIt returns the list as a list of integers"""
    return [int(lst[i]) for i in range(9) if type(lst[i])==str]

def inCol(gridN, i, colN):
    """Searches for int i in a column"""
    if i in makeCol(gridN, colN):
        return True
    else:
        return False

def makeCol(gridN, colN):
    """Creates the column grid from the grid\nReturns the column grid"""
    vertGrid = []
    for x in range(9):
        placeholder=[]
        for y in range(9):
            placeholder.append(gridN[y][x])
        vertGrid.append(placeholder)
    return vertGrid[colN-1]

def inSquare(nGrid,i, rowN, colN):
    """Searches for int i in a grid area"""
    if i in makeSquare(nGrid, rowN, colN):
        return True
    else:
        return False

def makeSquare(nGrid, rowN, colN):
    """Creates the specified block from the grid\nReturns the block"""
    newTest =[]
    newLst = []

    for i in range(9):
        newLst.append([str(nGrid[i][j]) for j in range(9)])
    nGrid = newLst
    threeby3 = [[] for i in range(3)]
    for i in range(9):
        newTest.append("".join(nGrid[i]))
        for j, s, e in zip(range(3), [0,3,6], [3,6,9]):
            threeby3[j].append(newTest[i][s:e])

    final = [[] for i in range(9)]
    for i,j in zip(range(9),[0,1,2]*3):
        if i<=2:
            final[i] = threeby3[j][0:3]
        elif 3<=i<=5:
            final[i] = threeby3[j][3:6]
        elif 6<=i<=8:
            final[i] = threeby3[j][6:9]
    return final[determineBlock(rowN, colN)-1]

def determineBlock(rowN, colN):
    """Determines which block the number is in"""
    a,b,c = [1,2,3],[4,5,6],[7,8,9]
    if rowN in a and colN in a:
        return 1
    elif rowN in b and colN in a:
        return 2
    elif rowN in c and colN in a:
        return 3
    elif rowN in a and colN in b:
        return 4
    elif rowN in b and colN in b:
        return 5
    elif rowN in c and colN in b:
        return 6
    elif rowN in a and colN in c:
        return 7
    elif rowN in b and colN in c:
        return 8
    elif rowN in c and colN in c:
        return 9

def populate(grid):
    """Populates the grid by generating values and testing them for each position"""
    nGrid = []
    for i in range(9):
        nGrid.append([int(grid[i][j]) for j in range(9)])
    for i in range(9): # Rows
        rowSet = set(nGrid[i]) #Creates a unique list of numbers from each row
        if 0 in rowSet:
            rowSet.remove(0)
        for j in range(9): #Columns
            toAdd = []
            if nGrid[i][j] ==0:
                # Creates a unique set of numbers from 1-9 that aren't in the row, column or 3X3 Square
                for k in [op for op in range(1,10) if op not in rowSet and (inCol(nGrid, op, j+1)==False and inSquare(nGrid, op, i+1, j+1)==False)]:
                    toAdd.append(k)
            if len(toAdd)==1:# If there is only one value in that list, it adds it to the grid
                nGrid[i][j]=toAdd[0]
            elif len(toAdd)!=0:
                finalCheck = additionalCheck(nGrid, toAdd, i+1, j+1)
                if finalCheck!=False:
                    nGrid[i][j] = finalCheck
    print()
    print("Old: ")
    printGrid(toIntList2D(grid))
    print("New: ")
    printGrid(toIntList2D(nGrid))
    return nGrid


def additionalCheck(grid, toCheck, rowN, colN):
    """The final check before moving on the the next square"""
    print("To Add:",toCheck)
    rowCol = [[1,2,3],[4,5,6],[7,8,9]]
    nRow, nCol = 0,0
    toAdd=[]
    for i in range(len(rowCol)):
        if rowN in rowCol[i]:
            setRC = set(rowCol[i])
            setRC.remove(rowN)
            nRow = list(setRC)
        if colN in rowCol[i]:
            setRC = set(rowCol[i])
            setRC.remove(colN)
            nCol = list(setRC)
    print("Row:",nRow)
    print("Col:",nCol)
    for k in toCheck:
        if (k in grid[nRow[0]-1]) and (k in grid[nRow[1]-1]) and (inCol(grid, k, nCol[0])==True and inCol(grid, k, nCol[1])==True) and inSquare(grid, k, rowN, colN)==False:
            toAdd.append(k)
    if len(toAdd)==1:
        return toAdd[0]
    else:
        return False


def printGrid(grid):
    """Prints the grid in a user friendly format"""
    for i in range(len(grid)):
        print(" ".join([str(k) for k in grid[i]]))


def main():
    fi = open("sudoku.txt", "r")
    inFile = fi.read()
    print(inFile)
    grid = [list(i) for i in inFile.split("\n")]
    if testSudoku(grid)==True:
        printGrid(grid)
    else:
        while True:
            newGrid = populate(grid)
            grid=newGrid[:]
            if testSudoku(grid)==True:
                printGrid(grid)
                break

main()


===================================================================================================================
Test Function
===================================================================================================================

def testSudoku(testGrid):#HORIZONTAL CHECK
    for i in testGrid:
        if len(set(i))!=9:
            return False

    #CREATE VERTICAL
    vertGrid = []
    for x in range(9):
        placeholder=[]
        for y in range(9):
            placeholder.append(testGrid[y][x])
        vertGrid.append(placeholder)


    #VERTICAL CHECK
    for i in vertGrid:
        if len(set(i))!=9:
            return False

    #CHECK 3X3
    ##Join
    newTest =[]
    threeby3 = list([] for i in range(9))
    for i in range(9):
        newTest.append("".join(testGrid[i]))
        for j, s, e in zip(range(3), [0,3,6], [3,6,9]):
            threeby3[i].append(newTest[i][s:e])
        "".join(threeby3[i])

    for i in threeby3:
        if len(set("".join(i)))!=9:
            return False

    return True