puzzle =   {0 : [0,0,0,0,0,0,0,0,0],
            1 : [0,3,0,0,0,0,1,6,0],
            2 : [0,6,7,0,3,5,0,0,4],
            3 : [6,0,8,1,2,0,9,0,0],
            4 : [0,9,0,0,8,0,0,3,0],
            5 : [0,0,2,0,7,9,8,0,6],
            6 : [8,0,0,6,9,0,3,5,0],
            7 : [0,2,6,0,0,0,0,9,0],
            8 : [0,0,0,0,0,0,0,0,0]
        }

def makeGrid(puzzle):
    for a in list(range(1,10)):
        #print('Checking for: {}'.format(a))
        grid = []
        # Set block list
        blockList = []
        for x in puzzle:
            row = []
            y = 0
            for n in puzzle[x]:
                if n == a:
                    row.append(0)
                    blockList.append([x,y])
                elif n != 0:
                    row.append(1)
                else:
                    row.append(0)
                y += 1
            grid.append(row)
        # Block using standard logic
        for b in blockList:
            grid = blockGrid(b, grid)
        # Block using simplified dancing links (algorithm X) for fun
        blockDLX(grid, a)
        solveRow(grid, a)
        solveColumn(grid, a)

def blockGrid(b, grid):
    # Block row
    x = b[0]
    y = 0
    for n in grid[x]:
        grid[x][y] = 1
        y += 1
    # Block column
    x = 0
    y = b[1]
    for row in grid:
        grid[x][y] = 1
        x += 1
    # Block square
    x = b[0]
    y = b[1]
    rowRange = [0,3,6]
    columnRange = [0,3,6]
    for a in rowRange:
        if x >= a and x < a + 3:
            for b in columnRange:
                if y >= b and y < b + 3:
                    i = 0
                    while i < 3:
                        j = 0
                        while j < 3:
                            grid[a + i][b + j] = 1
                            j += 1
                        i += 1
    return(grid)

def blockDLX(grid, a):
    # Reduce rows
    x = 0
    subGrid = {}
    for row in grid:
        if row.count(0) != 0:
            subGrid[x] = row
        x += 1
    # Reduce columns
    for x in subGrid:
        y = 0
        solvedCount = 0
        checkColumns = []
        blockColumn = []
        for n in subGrid[x]:
            if n == 1:
                check = 0
                for row in subGrid:
                    if subGrid[row][y] == 1:
                        check += 1
                if check != len(subGrid):
                    checkColumns.append(y)
                else:
                    solvedCount += 1
            else:
                blockColumn.append(y)
            y += 1
        # Check columns
        if len(checkColumns) > 0:
            blockRow = []
            for z in subGrid:
                match = 'y'
                for column in checkColumns:
                    if subGrid[z][column] == 0:
                        match = 'n'
                if match == 'y':
                    blockRow.append(z)
            if len(blockRow) == subGrid[x].count(0) and len(blockRow) != (len(subGrid[x]) - solvedCount):
                for column in blockColumn:
                    x = 0
                    for row in grid:
                        if x not in blockRow:
                            grid[x][column] = 1
                        x += 1

def solveRow(grid, a):
    x = 0
    for row in grid:
        if row.count(0) == 1:
            y = 0
            for n in grid[x]:
                if n == 0:
                    #print('Match found x:{} y:{}'.format(x, y))
                    puzzle[x][y] = a
                y += 1
        x += 1

def solveColumn(grid, a):
    y = 0
    while y < 9:
        column = []
        for row in grid:
            column.append(row[y])
        if column.count(0) == 1:
            x = 0
            for n in column:
                if n == 0:
                    #print('Match found x:{} y:{}'.format(x, y))
                    puzzle[x][y] = a
                x += 1
        y += 1

while any(0 in puzzle[row] for row in puzzle):
    makeGrid(puzzle)
print('\n\nSolved:')
for x in puzzle:
    print(puzzle[x])