"puzzled why" vs "puzzled as to why"

Grammatical rules that apply to units larger than a word apply only to constituents.
"Puzzled why", however, is not a constituent, but rather a string taken from a sentence.

The psych predicate adjective (be) puzzled can take a number of complements, including tensed that- and wh-clauses

• He was puzzled why she hadn't arrived yet.
• He was puzzled that she hadn't arrived yet.

and a number of other constructions, often with prepositions

• He was puzzled at Bill's expression.
• He's puzzled about the circus.
• He was puzzled at Mary's leaving early.

There is also a Passive construction (like most psych predicates, which often come originally from passive participles), which allows a by-agent.

• He was puzzled by Bill's expression. ~ Bill's expression puzzled him .

As to the as to, that's just a longer (and optional) compound preposition governed by puzzled, like at and about.