Yes, kind off.

> All bets are off...

Well IMHO the multidimensionality makes it much easier to solve.

The trick is always to always concentrate on the smallest dimension.

E.g. there is no V allowed, about 6 dog-names have a V, so they can be excluded right away for the rest of the search.

Then there is only 1 Z allowed, only about 7 dog-names include a Z.

After trying each Z-names out in the first level, all other Z-Names must be excluded for the next levels.

And trying one Z-name also diminishes other characters which become minimal now, so other names can be excluded for the subtree. (e.g. Xoloitzcuintli includes an X, but only one X was allowed, all other X-names must be excluded now, and so on)

IMHO the search tree becomes comparatively small with this strategy. (brute force has a worst case of faculty(n) combinations to check with n=100 here)