Maybe i'll optimize this enough for 7x7 someday

skyscrapers.py

clues = (3, 2, 2, 3, 2, 1,
         1, 2, 3, 3, 2, 2,
         5, 1, 2, 2, 4, 3,
         3, 2, 1, 2, 2, 4)

expected = ((2, 1, 4, 3, 5, 6),
            (1, 6, 3, 2, 4, 5),
            (4, 3, 6, 5, 1, 2),
            (6, 5, 2, 1, 3, 4),
            (5, 4, 1, 6, 2, 3),
            (3, 2, 5, 4, 6, 1))

from time import time

# clues = (
#     (2, 2, 1, 3,
#      2, 2, 3, 1,
#      1, 2, 2, 3,
#      3, 2, 1, 3),
#     (0, 0, 1, 2,
#      0, 2, 0, 0,
#      0, 3, 0, 0,
#      0, 1, 0, 0),
#     (4, 3, 2, 1,
#      1, 2, 2, 2,
#      2, 2, 2, 1,
#      1, 2, 3, 4)
# )
#
# expected = (
#     ((1, 3, 4, 2),
#      (4, 2, 1, 3),
#      (3, 4, 2, 1),
#      (2, 1, 3, 4)),
#     ((2, 1, 4, 3),
#      (3, 4, 1, 2),
#      (4, 2, 3, 1),
#      (1, 3, 2, 4)),
#     ((1, 2, 3, 4),
#      (2, 3, 4, 1),
#      (3, 4, 1, 2),
#      (4, 1, 2, 3))
# )


def solve_puzzle(clues):
    def cross(a, b):
        return [i + j for i in a for j in b]

    size = len(clues) / 4
    digits = "123456789"[:size]
    rows = "ABCDEFGHI"[:size]
    cols = digits
    squares = cross(rows, cols)
    newBoard = {i: digits for i in squares}
    peers = {i: set(cross(set(rows) - set(i[0]), [i[1]])) | set(cross([i[0]], set(cols) - set(i[1]))) for i in squares}
    topClues = clues[:size]
    rightClues = clues[size:2 * size]
    bottomClues = clues[3 * size - 1:2 * size - 1:-1]
    leftClues = clues[:3 * size - 1:-1]
    colClues = (topClues, bottomClues)
    rowClues = (leftClues, rightClues)
    colCluePairs = {cols[i]: (colClues[0][i], colClues[1][i]) for i in range(len(cols))}
    rowCluePairs = {rows[i]: (rowClues[0][i], rowClues[1][i]) for i in range(len(rows))}
    cluePairs = {i: (rowCluePairs[i[0]], colCluePairs[i[1]]) for i in squares}

    def fillObvious(board):
        for i in cols:
            freq = {j: [0, None] for j in digits}
            for j in rows:
                for k in board[j + i]:
                    if freq[k][0] == -1:
                        continue
                    if freq[k][0] == 0:
                        freq[k][0] = 1
                        freq[k][1] = j
                    elif freq[k][0] == 1:
                        freq[k][0] = -1
            for j in freq:
                if freq[j][0] == 1 and len(board[freq[j][1] + i]) != 1:
                    board[freq[j][1] + i] = j + ' '
                    if not eliminate(board, freq[j][1] + i, ' '):
                        return False
        for i in rows:
            freq = {j: [0, None] for j in digits}
            for j in cols:
                for k in board[i + j]:
                    if freq[k][0] == -1:
                        continue
                    if freq[k][0] == 0:
                        freq[k][0] = 1
                        freq[k][1] = j
                    elif freq[k][0] == 1:
                        freq[k][0] = -1
            for j in freq:
                if freq[j][0] == 1 and len(board[i + freq[j][1]]) != 1:
                    board[i + freq[j][1]] = j + ' '
                    if not eliminate(board, i + freq[j][1], ' '):
                        return False
        return board

    def assign(board, s, d):
        board[s] = d + ' '
        if eliminate(board, s, ' '):
            return fillObvious(board)
        else:
            return False

    def validRow(board, s):
        if len(board[s[0] + cols[0]]) > 1 or len(board[s[0] + cols[-1]]) > 1:
            return True
        tempCols = cols
        for j in range(2):
            if rowCluePairs[s[0]][j] != 0:
                n = 0
                height = 0
                skip = False
                for i in tempCols:
                    temp = board[s[0] + i]
                    if len(temp) > 1:
                        if int(height) < size and n >= rowCluePairs[s[0]][j] or int(height) == size and n < rowCluePairs[s[0]][j]:
                            return False
                        skip = True
                        break
                    if temp > height:
                        n += 1
                        height = temp
                if rowCluePairs[s[0]][j] != n and not skip:
                    return False
            tempCols = cols[::-1]
        return True

    def validCol(board, s):
        if len(board[rows[0] + s[1]]) > 1 or len(board[rows[-1] + s[1]]) > 1:
            return True
        tempRows = rows
        for j in range(2):
            if colCluePairs[s[1]][j] != 0:
                n = 0
                height = 0
                skip = False
                for i in tempRows:
                    temp = board[i + s[1]]
                    if len(temp) > 1:
                        if int(height) < size and n >= colCluePairs[s[1]][j] or int(height) == size and n < colCluePairs[s[1]][j]:
                            return False
                        skip = True
                        break
                    if temp > height:
                        n += 1
                        height = temp
                if colCluePairs[s[1]][j] != n and not skip:
                    return False
            tempRows = rows[::-1]
        return True

    def eliminate(board, s, d):
        if d not in board[s]:  # already gone
            return board
        board[s] = board[s].replace(d, '')
        if len(board[s]) == 0:  # 0 possibilities
            return False
        elif len(board[s]) == 1:  # 1 possibility
            # if not fillObvious(board):
            #     return False
            temp = board[s]
            if not all(eliminate(board, i, temp) for i in peers[s]):  # propogate
                return False
            if validRow(board, s) and validCol(board, s):
                return board
            else:
                return False
        return board

    def some(seq):
        for i in seq:
            if i:
                return i
        return False

    def search(board):
        if board == False:  # failed down the line
            return False
        if all(len(board[i]) == 1 for i in squares):  # solved
            return board
        n = min((board[i], i) for i in squares if len(board[i]) > 1)[1]
        temp = some(search(assign(board.copy(), n, i)) for i in board[n])
        return temp

    def display(board, rowClues, colClues):
        largest = max(len(i) for i in board.values())
        print '    ' + ' '.join(i.center(largest) for i in rows)
        print '    ' + ' '.join(str(i).center(largest) for i in rowClues[0])
        print '\n'.join(i + ' ' + str(colClues[0][int(i) - 1]) + ' ' + ' '.join(board[j + i].center(largest) for j in rows) + ' ' + str(colClues[1][int(i) - 1]) for i in cols)
        print '    ' + ' '.join(str(i).center(largest) for i in rowClues[1])

    def prefill(board):
        for i in rows:
            temp = cols
            for j in range(2):
                if rowCluePairs[i][j] == 1:
                    assign(board, i + temp[0], str(size))
                elif rowCluePairs[i][j] == size:
                    for k in range(size):
                        assign(board, i + temp[k], str(k + 1))
                elif rowCluePairs[i][j] > 1:
                    for l in range(size - 1):
                        while int(board[i + temp[l]][-1]) > size + l + 1 - rowCluePairs[i][j]:
                            eliminate(board, i + temp[l], board[i + temp[l]][-1])
                temp = cols[::-1]
        for i in cols:
            temp = rows
            for j in range(2):
                if colCluePairs[i][j] == 1:
                    assign(board, temp[0] + i, str(size))
                elif colCluePairs[i][j] == size:
                    for k in range(size):
                        assign(board, temp[k] + i, str(k + 1))
                elif colCluePairs[i][j] > 1:
                    for l in range(size - 1):
                        while int(board[temp[l] + i][-1]) > size + l + 1 - colCluePairs[i][j]:
                            eliminate(board, temp[l] + i, board[temp[l] + i][-1])
                temp = rows[::-1]
        return fillObvious(board)

    current = time()
    newBoard = prefill(newBoard)
    display(newBoard, rowClues, colClues)
    newBoard = search(newBoard)
    print time() - current
    current = time()
    display(newBoard, rowClues, colClues)
    return [[int(newBoard[j + i]) for i in cols] for j in rows]

clues = [7,0,0,0,2,2,3, 0,0,3,0,0,0,0, 3,0,3,0,0,5,0, 0,0,0,0,5,0,4]
expected = [ [1,5,6,7,4,3,2],
    [2,7,4,5,3,1,6],
    [3,4,5,6,7,2,1],
    [4,6,3,1,2,7,5],
    [5,3,1,2,6,4,7],
    [6,2,7,3,1,5,4],
    [7,1,2,4,5,6,3] ]

print solve_puzzle(clues) == expected

clues = [0,2,3,0,2,0,0, 5,0,4,5,0,4,0, 0,4,2,0,0,0,6, 5,2,2,2,2,4,1]# for a _very_ hard puzzle, replace the last 7 values with zeroes
expected = [ [7,6,2,1,5,4,3],
    [1,3,5,4,2,7,6],
    [6,5,4,7,3,2,1],
    [5,1,7,6,4,3,2],
    [4,2,1,3,7,6,5],
    [3,7,6,2,1,5,4],
    [2,4,3,5,6,1,7] ]

print solve_puzzle(clues) == expected