
View previous topic :: View next topic 
Author 
Message 
 holdout
 Joined: 30 Dec 2006  Posts: 8  :  Location: Bowie, MD (USA)  Items 

Posted: Sat Dec 30, 2006 4:14 pm Post subject: Generating Grids with Templates 


GENERATING FULL GRIDS WITH TEMPLATES
==============================
I was under the impression that one could use templates to randomly generate full standard Soduko grids, and that it could be done without backtracking or restarting. This impression proved to be false. Nevertheless, I learned that with some extra work, the desired result could be obtained.
A thumbnail review of the basic algorithm:
1) Generate all 46656 = 6*6*6*6*6*6 possible templates, where each template marks 9 of 81 positions which might legally hold the same Soduko digit.
2) Set: clue = 0.
3) Randomly select a template from among those which remain (initially, there are 46646 choices).
4) Set: clue = clue + 1
Using the selected template, set indicated grid positions to 'clue'.
If clue equals 9, then quit, as we have a solution.
5) In the template list, filterout all templates which conflict with the one
just chosen.
6) If the template list is not empty, repeat step (3).
7) Here's the problem: the list is empty, but we have no solution.
One million Monte Carlo trials were made, and the point where the list became empty was recorded. Also, maximum and average template list lengths were calculated for each template assumption.
Code: 
Legend:
A = Number of times of template list became empty after filtering with
the 'clue' template.
B = Maximum list length after placement of 'clue' template.
C = Average list length after placement of 'clue' template.
Clue AAAAAA BBBBB CCCCCCCCCCC
==== ====== ===== ===========
1 0 17972 17972.00000
2 0 6576 6197.23000
3 0 2187 1853.65000
4 0 760 458.29700
5 0 234 87.69000
6 155 84 11.87640 Failure 155 times
7 582798 16 1.02508 Failure 582798 times
8 0 1 1.00000
9 417047 0 0.00000 Solution!

Solution was obtained 417047 times, and was not obtained the rest (155 times after the 6th template was placed, and 582798 times after the 7th template was placed).
I encountered 582798 emptylist failures at clue equal 7. Did we make an unfortunate random selection for template #7? The answer is both "yes" and "no." The answer is "yes" when other templates exist which would have lead to solution, but "no" when all other templates would have failed.
In the trials, the list first became empty with the placement of the 6th template. It is my belief (without proof) that the list will never become empty at an earlier stage. Why? Because each template placement represents 9 digits, and the decrease (column 'A') from clue 6 to clue 5 should be just as dramatic as the one from clue 7 to clue 6.
Algorithm Modification
================
1) Generate the first five templates as described above.
2) Using the templates which remain, implement a 4deep nested loop to construct all possible 4tuples of noncrashing templates. Record each 4tuple as you find them.
3) If the final 4tuple list is empty (not the norm), repeat step (1).
4) Randomly chose one of the 4tuple template sets and add them to the ones from step (1). We're done!
In one million Monte Carlo trials, the 4tuple list had a maximum of 1024 entries, so saving 4tuples should not be a problem. However, there was a problem in 762 of the trials  yes, you guessed it, the list again became empty. This failure rate is acceptable  just restart.
Time Trials
=======
One million grids were generated (no output, except for the grid array) at a rate of 619.64 grids per second. My computer is a "Gateway 700S PC" and runs with a "Intel 2.26 GHz Pentium 4 Processor". Routines are written in 'C'.
Go Figure
=======
For your amusement, here follows one of the 5template selections (step (1)) for which the 4tuple list (step(2)) became empty.
Code: 
. . 2 1 3 5 . 4 .
4 5 . . . 2 . 3 1
1 3 . . 4 . . 5 2
. . 5 2 . 4 1 . 3
. 1 4 3 . . 2 . 5
2 . 3 . 5 1 4 . .
3 4 1 . . . 5 2 .
. . . 5 2 3 . 1 4
5 2 . 4 1 . 3 . .



Back to top 


 holdout
 Joined: 30 Dec 2006  Posts: 8  :  Location: Bowie, MD (USA)  Items 

Posted: Sat Dec 30, 2006 11:25 pm Post subject: Two Problems 


To: daj95376
1) I don't believe it matters what cells get filled first, so why choose
from 81 (at first) and then eliminate?
2) You really don't address the question of what to do when the template list becomes prematurely empty. There is about a 42% chance of success if you restart every time the list becomes empty. 

Back to top 


 Red Ed
 Joined: 04 Nov 2006  Posts: 21  :   Items 

Posted: Thu Jan 11, 2007 8:45 pm Post subject: 


Coincidentally (I assume), I posted a description of a templatebased solution grid generator on the Players' Forum 3 weeks before this thread appeared. Uniquely among methods I have seen published, it is unbiased.
I've (just now) tested your generator using the statistics described in that thread. It's the least significantly biased (in terms of Zvalue) of all the solution grid generators other than my own. The bias is a little worse with the modified algorithm than with the original one, but both beat the opposition comfortably.
Both variants of your algorithm produce too many bands or stacks isomorphic to this pattern: Code:  ++++
123......
...123...
......123
++++  The bias in the original version is ~15%. In the modified version it's ~18.5%. 

Back to top 


 holdout
 Joined: 30 Dec 2006  Posts: 8  :  Location: Bowie, MD (USA)  Items 

Posted: Tue Jan 16, 2007 12:10 am Post subject: Templates adn Bias 


Red Ed wrote: 
I've (just now) tested your generator using the statistics described in that thread. It's the least significantly biased (in terms of Zvalue) of all the solution grid generators other than my own. The bias is a little worse with the modified algorithm than with the original one, but both beat the opposition comfortably.

When attempting to produce a grid using templates, it is clear that bias is introduced when one must "backtrack" or "restart." What this really means is that, when stacks become empty (no choices exist), you have randomly chosen something that is impossible; that is, you have inadvertenly assigned some nonzero probability to something which never happens.
For this reason, I am surprised that the modified algorithm (which restarts less than 1/1000 times) is a little more biased than the unmodified algorithm (which restarts about 58% of the time).
A third algorithm:
1) Randomly choose 4 noncrashing templates.
2) Given these four, make a list of all 5tuples of templates which complete the grid.
3) Randomly choose one of the 5tuples from the list. We're done!
I would not expect the 5tuple list to ever become empty (no proof) . The compute time would get big really quick, but the resulting grid should be without bias, since no backtracking/restarting is involved.
Sorry, but I could not find reference to your Zvalue. 

Back to top 


 Red Ed
 Joined: 04 Nov 2006  Posts: 21  :   Items 

Posted: Tue Jan 16, 2007 7:27 pm Post subject: 


The third algorithm you presented is not unbiased, since not all sets of 4 noncrashing templates have the same number of completions. But I bet that the bias is very small. Too lazy to generate the grids myself to check, though. 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Sat Feb 17, 2007 8:38 am Post subject: 


[Withdrawn: Nothing useful.]
Last edited by daj95376 on Thu Feb 22, 2007 6:51 am; edited 1 time in total 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Sun Feb 18, 2007 6:43 pm Post subject: 


[Withdrawn: Nothing useful.]
Last edited by daj95376 on Thu Feb 22, 2007 6:52 am; edited 1 time in total 

Back to top 


 rkral
 Joined: 21 Oct 2005  Posts: 233  :   Items 

Posted: Sun Feb 18, 2007 9:11 pm Post subject: 


daj95376 wrote:  Code:  *i*
[1] t_count = 10000 t_left = 46656
[2] t_count = 10000 t_left = 46655
[3] t_count = 10000 t_left = 46634
[4] t_count = 10000 t_left = 46574
[5] t_count = 10005 t_left = 46432
[6] t_count = 14075 t_left = 45394
[7] t_count = 49227 t_left = 21
[8] t_count = 10000 t_left = 0
[9] t_count = 10000 t_left = 589


How can t_left increase between i=8 to i=9?
Last edited by rkral on Sun Feb 18, 2007 10:35 pm; edited 1 time in total 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Sun Feb 18, 2007 10:34 pm Post subject: 


rkral wrote:  How can t_left increase from i=8 to i=9? 
I only record the number of remaining table entries when a level is reached. So, when i=9 was actually reached, there were always at least 589 entries left to be examined.
Since t_count[8]=10000, this means that I was always able to find a suitable entry for i=9 among the remaining entries. I find this interesting! 

Back to top 


 Red Ed
 Joined: 04 Nov 2006  Posts: 21  :   Items 

Posted: Mon Feb 19, 2007 9:09 pm Post subject: 


daj95376 wrote:  Since t_count[8]=10000, this means that I was always able to find a suitable entry for i=9 among the remaining entries. I find this interesting!  It's always the case that once you've placed all 1s, 2s, ..., 8s in a grid, the nine "holes" left over make a valid template for the 9s. (I think that this fact is what you've rediscovered; apologies if I've not been paying attention.)
Quote:  Finally, execution time was horrible!!! I believe Red Ed reported similar results in his link.  I did indeed. But now I'm using a different, nontemplates, method with which I can produce 10000 unbiased grids/sec.
( Continuing on the theme of unbiased grid generation ... You've got to remember that this is all largely academic. I mean, mildly biased grid generation is virtually irrelevant when making puzzles. The only time you would want truly unbiased grid generation is when you're trying to answer questions like: what's the average number of size6 unavoidable sets in a grid, and other such trivia. Even then, you're probably better off with gsf's catalogue of all* grids up to isomorphism. Hmm... here's me raining on my own parade )
(( * : yes, really, all of them. Want to know if there are any grids that <insert_nerdy_question_here> ? gsf's catalogue has the answer. )) 

Back to top 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
