Calculating Tree Depth

mugnyte · Posted: Wed Jan 11, 2006 12:05 am Post subject: Calculating Tree Depth

I was thinking on assigning a limit to the "required moves to solve" adjustment in my generator. By choosing the logic modules to employ, and a number of moves greater than just (81-givens), one creates puzzles that the chosen logic cannot solve. So far, i've used this to quickly generate puzzles of specific difficulty. But it's getting slower, as you can imagine, as I write more logic and ask for a large number of moves. Then I realized that there's a limit I'm hitting.

For example, checking only "basic rules" and 200 moves generates a puzzle that requires >=200 moves (counting "forwards" only in a TE search). This is easy and there are puzzles with 15k moves using just the basics. But by clicking Range Scanning, Subset Elim, etc, and ">(81-givens) moves", the generator discovers that yet another logic module is required. I know this, and they'll eventually get done, however...

The limit on how many moves are possible quickly shrinks with each logic module, and the generator takes longer each time to find such a puzzle. It seems that each logic technique creates it's own set of M-constrained puzzles, and by adding yet another strategy, the M-constrained puzzle sets dimish.

I would guess that if all puzzles were M-0, then either you have T&E mixed up in your logic, or you have all the logic necessary to solve those puzzles (*see next reply for more on this)

Anyway, as I code each logic technique and ask for ">(81-givens) moves", there needs to be limit on the number of moves any possible puzzle could take, based on the logic employed. Any ideas on how to calculate this? At the moment, I'm building stats like this:

Basic Rules: avg number of cell possibilities at start of X games
Logic Module 1: "
Logic Module 2: "
..etc..

where X is 1000 or so

and then just using those stats restrict the maximum moves possible on a game. (avg_poss ^ open_cells) I realize this ignore cell realtionships, but I need a hard limit, so that I'm guaranteed one *cannot* generate a game with: "m Moves with g Givens and L logic employed"

Thanks!
_________________
thanks