FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Generating Grids with Templates          Sudoku Programmers Forum Index -> Setting sudoku 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, filter-out 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 empty-list 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 4-deep nested loop to construct all possible 4-tuples of non-crashing templates. Record each 4-tuple as you find them. 3) If the final 4-tuple list is empty (not the norm), repeat step (1). 4) Randomly chose one of the 4-tuple template sets and add them to the ones from step (1). We're done! In one million Monte Carlo trials, the 4-tuple list had a maximum of 1024 entries, so saving 4-tuples 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 5-template selections (step (1)) for which the 4-tuple 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 template-based 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 Z-value) 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 Z-value) 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 non-zero 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 non-crashing templates. 2) Given these four, make a list of all 5-tuples of templates which complete the grid. 3) Randomly choose one of the 5-tuples from the list. We're done! I would not expect the 5-tuple 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 Z-value. 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 non-crashing 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, non-templates, 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 size-6 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 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Setting sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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