Sudoku Programmers Forum Index

 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Calculating Tree Depth

Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku
View previous topic :: View next topic  
Author Message

Joined: 07 Dec 2005
Posts: 13
Location: portland, or

PostPosted: Wed Jan 11, 2006 12:05 am    Post subject: Calculating Tree Depth Reply with quote

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: "

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"

Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> The mathematics of sudoku All times are GMT
Page 1 of 1

Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 

Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron