
View previous topic :: View next topic 
Author 
Message 
 Moschopulus
 Joined: 12 Aug 2005  Posts: 39  :   Items 

Posted: Mon Mar 06, 2006 10:01 am Post subject: 


I think this is an interesting idea, thanks. I've thought about your questions for 2 minutes, and can't answer either of them. Hopefully I will have more time later. A priori, I agree with what you say. It is certainly possible, and even likely, that each grid is generated with equal probability. 

Back to top 


 Moschopulus
 Joined: 12 Aug 2005  Posts: 39  :   Items 

Posted: Mon Mar 06, 2006 8:36 pm Post subject: 


Soultaker wrote: 
What I do is initialize the grid with a random permutation of all symbols (so I start, for example, with nine 1's on the first row, nine 2's on the second, and so on, and then shuffle the entire grid). This, ofcourse, is not a valid grid yet because there are many cases of two symbols (eg. two 1's) on the same row, column or block. I count each extra symbol in a row, column or block as a conflict.

Just a thought, if you were to remove the block conflicts then you should get a Latin square generator. Maybe there is a way to test whether each Latin square is generated with the same probability. 

Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

Posted: Tue Jan 16, 2007 8:03 pm Post subject: 


Red Ed was kind enough to test my three fullgrid generation methods for bias, using a sample of 10,000 for each. The results were interesting so I post them with my reply below.
Regards,
Mike Metcalf
> The results (Zscores scaled up to 1 million grids) are:
>
> * nine.txt = +91 (not bad; beats gsf & dukuso)
This works by laying down the numbers 19 in random order a row at a time.
For rows 28, the numbers are shuffled as necessary to avoid any column/box
clashes (there are no row clashes by definition). At row 5 a check that row
6 is not subject to a deadlock condition is required; this causes a restart
from row 4 in about 10% of cases. Row 9 is trivial. (This method scales to
higher sizes, in practice up to 49x49, and for 64x64 and 100x100 as a
hybrid, using a construction for even rows.) Speed: 0.14s per 1000, at
1.6GHz using Fortran 95 with the highlyoptimizing CVF compiler.
> * brute.txt = 94 (ditto, not bad)
A grid is zeroed. Three vectors containing the numbers 19 in random order
are generated. The first two define the rows and columns, respectively, into
which the third set of values are positioned. There can be no clash by
definition. This is repeated once, now checking for clashes. The rest of the
grid is filled by a bruteforce solver algorithm, progressing rowbyrow and
columnbycolumn. What I've been intending to do is to program this such
that at each empty cell the pencil marks are processed in random order.
Instead, for the moment, it processes at each cell either from 19 or from
91, selected randomly, and when a valid grid is found, the horizontal and
vertical chutes, respectively, are permuted randomly, and the rows and the
columns within each chute, respectively, are permuted randomly. Speed: 0.4s
per 1000.
> * grid.txt = +90000 (disaster!  all grids in this file are isomorphic!)
>
Correct. This is the only way I can generate grids of 121x121 and above,
using a construction. Here it's used for 9x9 and it shows! Speed: 0.04s per
1000.
> Judging by their bias profile, the first two methods appear to be
> genuinely different to others I have seen, namely those of gsf, dukuso,
> anttiahola, soultaker and holdout. Interesting.
>
Should I put this note onto a thread at one of the Forums? And which?
> btw, I think the quest for fast unbiased grid generation is mainly
> academic: about the only use I can think of for such a perfectionist
> algorithm is in the estimation of the total number of proper puzzles. For
> other purposes, especially puzzle generation, anything with a scaled
> Zscore of about 100 (absolute value) or less seems absolutely fine.
>
Definitely. 

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
