generating random sudokugrids

Moschopulus · 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.

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

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

Red Ed was kind enough to test my three full-grid 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 (Z-scores scaled up to 1 million grids) are:
>
> * nine.txt = +91 (not bad; beats gsf & dukuso)

This works by laying down the numbers 1-9 in random order a row at a time.
For rows 2-8, 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 highly-optimizing CVF compiler.

> * brute.txt = -94 (ditto, not bad)

A grid is zeroed. Three vectors containing the numbers 1-9 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 brute-force solver algorithm, progressing row-by-row and
column-by-column. 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 1-9 or from
9-1, 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
> Z-score of about 100 (absolute value) or less seems absolutely fine.
>
Definitely.