Solution Grids in U-Space (Unavoidable Sets)

dobrichev · Last edited by dobrichev on Tue Mar 09, 2010 7:21 pm; edited 4 times in total

Unavoidable Set is a subset of cells in the Sudoku grid, where at least one clue must be given in order the puzzle to have unique solution. It has been discussed in details in the forums years ago.
The smallest Unavoidable Set I can imagine is of size 4. It is a symmetry in 4 cells located in 2 boxes and forming a rectangle where the diagonal digits are the same. Such symmetries are easy and fast to be found in a known complete grid.
Performing the counting of the size 4 sets on the whole set of the essentially different sudoku grids resulted in the following:
EDIT: There was a bug and the data have been recalculated and updated after the fix.

JPF · Posted: Thu Feb 25, 2010 8:04 pm Post subject:

Interesting, thanks.

Here Red Ed claimed 9 grids, up to isomorphism, with 36 U4s.

JPF

dobrichev · Posted: Fri Feb 26, 2010 6:49 pm Post subject:

Thank you for the link!

The data have been recalculated and the table and picture are updated.

The pass took 14088 seconds (~4 hours) for the 5472730538 grids on 2x2.8GHz Pentium D. It is ~2.57 us/grid or ~70 000 grids per core per GHz.

JPF · Posted: Fri Feb 26, 2010 10:40 pm Post subject:

I don't want to pit nick, but here

dobrichev · Posted: Sat Feb 27, 2010 12:30 am Post subject:

The data posted here represents the essentially different grids.

Since Red Ed uses this average to check the bias of the grid generators he should use all valid grids as a basis. The difference between the number of the essentially different grids scaled by the number of permutations, from one side, and the number of all valid grids, from other side, is in the automorphism. The grids with automorphism must be scaled by a factor less than the whole number of permutations.
While recompressing the grids I lost the authomorphism data - the algorithm I am using fits in 79 bits and I decided to omit the authomorphism level generated by gsf's tool. So I can't take into account the count of unavailable sets of size 4 for each of the grids with authomorphism.

In the counting algorithm only integers are used so there can't be lost of precision. Hope it is true for RedEd's calculations too. Excluding the bugs, the data which are out of my control is the list of the grids but I don't intend to verify the generator.

If I am right, the conclusion is that the subset of all the grids with authomorphism is biased using the number of U4 sets as criterion. This is expected 1) as effect of their statistically unrepresentative number, and 2) due to the degree of internal symmetry the both indicators are measuring for. Laughing

JPF · Posted: Sat Feb 27, 2010 9:32 pm Post subject:

Good points dobrichev Smile

Here are the numbers for all the sudokus :

dobrichev · Posted: Sun Feb 28, 2010 11:37 pm Post subject:

Wow! It is a very good result.

It seems there are no grids with authomorphism having 1, 29, and 31 U4.

Did you apply scaling and corrections for U4s for the 560151 grids with authomorphism over the table on the top (the U4s int the essentially different grids) or use some different method?

BTW it gives me pleasure this time you didn't respond with a link to article dated 2006 Very Happy

JPF · Posted: Mon Mar 01, 2010 9:55 am Post subject:

dobrichev · Posted: Tue Mar 02, 2010 1:19 pm Post subject:

Fine!
Altrough I'm not sure the result is truly independent, it is a confirmation of the Red Ed's calculations.

In the next days I'll try to see could the U6 be found in a reasonable processing time, and then eventyally make a matrix of 36x? with the grid count of U4 and U6.

Later a MCN calculation could be tried, taking into account only U4 and U6. Have no idea about the processing time.

dobrichev · Posted: Tue Mar 09, 2010 6:53 am Post subject: Grids in U6/U4 Space

Hello again,

There are some results for Unavoidable Sets of size 6 (U6) available.

Surprisingly for me, processing of U6 can be done fast too. A pass trough entire set of 5 472 730 538 grids took about 1 kWh (6 hours on 2 core Pentium 2.8).

All the results below are based on the raw data for All 5472730538 Grids, Solutions of 48826 17-clue Puzzles, and 53 Grids of the known 39-clue Puzzles.

The known noice in the data is:

not

- The set of the 17-clue puzzles includes a duplicate of the grid for each representative puzzle.

- Count axis in the pictures is in logarithmic scale. Linear is not representative. The formula used is log10(1 + count) avoiding the uncertainity for the values of zero.

Counting U6

There are 4 types of U6 I found in the source code of Sudoku Checker.

JPF · Posted: Tue Mar 09, 2010 11:02 am Post subject:

Impressive work !!
Congratulations.

dobrichev · Posted: Tue Mar 09, 2010 7:12 pm Post subject:

dobrichev · Posted: Tue Mar 09, 2010 7:23 pm Post subject: Subject Change

Changed the topic's subject from "Unavoidable Sets of size 4" to "Solution Grids in U-Space (Unavoidable Sets)"

dobrichev

Hello again,

The next pass trough all ED grids counted the grids with each possible combination of U-coordinates.
The result was a 5-dimentional array for U4, U6_1, U6_2, U6_3, and U6_4 coordinates. The range of the coordinates is respectively:

dobrichev · Posted: Tue Mar 16, 2010 5:48 am Post subject: The Flattenning Source

Hi,

The data files (see links above) are updated and several new values and tables are added.

Here is the property causing the flattening. It has been represented in 2 ways - once by assuming orthogonality between different types of unavoidables discussed, and second time assuming additivity.

In the following graphics the x axis represents the Radius of the cell in the 5-dimentional U-space, calculated as a square root of the sum of the squares of the coordinates.

It is smoother than next graphics, which may be due to a) nature of the grids, or more likely b) the distance is not integer and the representation combines range of points into one value. The ratio is flat in the part where majority of the subset grids are located.

In the second graphics the additivity of the unavoidables of any kind is assumed and the x axis represents the sum of the unavoidables. The y axis is the same. The grid counts (not shown) have similar shape but are sharper near to the secondary maximums.

Both graphics are in logarithmic scale with uncertain points removed.

MD