Sudoku

    def solveSudoku(self, board):
        # Check if digit can be placed at position (i,j)
		def is_valid(digit, i, j):
            # check row
            for y in range(len(board)):
                if board[i][y] == str(digit):
                    return False
            # check column
            for x in range(len(board)):
                if board[x][j] == str(digit):
                    return False
            # check square
            square_x, square_y = i/3, j/3
            for x in range(square_x*3, square_x*3+3):
                for y in range(square_y*3, square_y*3+3):
                    if board[x][y] == str(digit):
                        return False
            return True

		# Find a valid digit for position (i, j), if possible, and recurse / backtrack
        def search(i, j):
            if i == len(board):
                return True
            elif j == len(board):
                return search(i+1, 0)
            if board[i][j] == ".":
                for digit in range(1, 10):
                    if is_valid(digit, i, j):
                        board[i][j] = str(digit)
                        if search(i, j+1):
                            return True
                        board[i][j] = "."
                return False
            else:
                return search(i, j+1)

        search(0,0)
        return board