Re^3: Another word puzzle with too many permutations

Replies are listed 'Best First'.
Re^4: Another word puzzle with too many permutations (multiple dimensions) by LanX (Saint) on Oct 16, 2013 at 16:07 UTC
> This looks like a multiple-constrained Knapsack problem. 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) Cheers Rolf ( addicted to the Perl Programming Language)	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^4: Another word puzzle with too many permutations (multiple dimensions)
by LanX (Saint) on Oct 16, 2013 at 16:07 UTC

> This looks like a multiple-constrained Knapsack problem.

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)

Cheers Rolf

( addicted to the Perl Programming Language)

[reply]
[d/l]
[select]