soduku

from copy import copy
from operator import itemgetter

def weigh(arr):
    wx = [0,0,0,0,0,0,0,0,0]
    wy = copy(wx)
    wb = copy(wx)
    for i in range(0,9):
        for j in range(0,9):
            wx[i] += 1 if arr[i][j] != '.' else 0
            wy[i] += 1 if arr[j][i] != '.' else 0
            wb[i/3*3+j/3] += 1 if arr[i][j] != '.' else 0
    #print wx, wy, wb
    w = []
    for i in range(0,9):
        for j in range(0,9):
            if arr[i][j] == '.':
                w.append((wx[i]+wx[j]+wb[i/3*3+j/3], i, j))
    return sorted(w, key=itemgetter(0), reverse=True)

def validate(arr, x, y, v):
    for i in range(0,9):
        if arr[x][i] == v or arr[i][y] == v:
            return False
    xx = x / 3 * 3
    yy = y / 3 * 3
    for i in range(0, 3):
        for j in range(0, 3):
            if arr[i+xx][j+yy] == v: return False
    return True

it = 0
def try_one(arr, w, d):
    if (d == len(w)):
       print "Solution", it
       #print_one(arr)
       #raise "ok"
       return True
    unused, i, j = w[d]
   #print d, i, j
   #print_one(arr)
    for a in range(1,10):
        if validate(arr, i, j, str(a)):
            valid = True
            arr[i][j] = str(a)
            if (try_one(arr,w, d+1)): return True
        arr[i][j] = '.'

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        w = weigh(board)
        try_one(board, w, 0)

s = Solution()
f=[[".",".",".",".",".","7",".",".","9"],[".","4",".",".","8","1","2",".","."],[".",".",".","9",".",".",".","1","."],[".",".","5","3",".",".",".","7","2"],["2","9","3",".",".",".",".","5","."],[".",".",".",".",".","5","3",".","."],["8",".",".",".","2","3",".",".","."],["7",".",".",".","5",".",".","4","."],["5","3","1",".","7",".",".",".","."]]
s.solveSudoku(f)
print f