Generating large grids

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Generating large grids

Postby Serg » Tue Oct 10, 2017 9:32 am

Hi, Mike!
m_b_metcalf wrote:Does this suggest another method of grid generation, by suitable generation of pairs?

I need some time to ponder this.

Mike, I feel my observation about solution grids structure should be well-known to community of this forum. Solution grids were carefully studied years ago. So, that observation about 2 possible types of a band is not probably new.

Serg
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Re: Generating large grids

Postby Serg » Sat Oct 14, 2017 11:11 pm

Hi, Mike!
First, I'd like to post some statistics, concerning my method of solution grids generation from MC grid by two-row/two-column UA sets application. I checked for non-equivalence first 100000 9x9 generated solution grids (check was done by excellent Mladen's Gridchecker), and I found that approx. 5% of grids should be dropped because they had equivalent grids in this sample set. So, observed efficiency of this algorithm - 95 %. I think, equivalent grids are produced when the same pair of rows (columns) are selected in 2 successive steps (probability to choose the same pair of rows (columns) in 2 successive steps is 1/18 for 9x9 grids). Fortunately, this probability of coming back to previous grid rapidly decreases when grid size grows.

Some words about possible usage of the fact that there are only 2 types of band (stack) fillings for 9x9 sudoku solution grids.
This knowledge can be used to descrease frequency of conflicts during band's filling when one uses simplest method of random solution grids generation - "random choosing of candidate digit in a cell and backtracking if it comes to conflict" method. To my mind, namely conflicts is the main obstacle for this method. I checked experimentally conflicts frequency for this method and found that for 9x9 solution grids conflicts took place during random choice of digits in 2 % of that choices. Not so bad for 9x9 case! But for 16x16 solution grids conflicts frequency increased rapidly - I observed conflicts after 98 % of digits choices! So, generation of 16x16 solution grids by this method is very slow. This method doesn't really work for larger grid sizes because of conflicts during bands filling. Certainly there are techniques to decrease conflicts frequence, for example - searching for naked and hidden singles after digit's choice. In theory, the knowledge of band (stack) structure can be used for decreasing conflicts frequency too, but there is an obstacle in application of this idea.

It's easy to prove that there are 2 types of band filling for 9x9 solution grid. It's very likely that there are 4 types of band filling for 16x16 solution grids and there are 6 types of band filling for 25x25 solution grids, but I cannot mathematically prove it :( . So, it isn't possible to discuss practical usage of this observation seriously for large grids. Otherwise, it's not so much sense to use such methods for improving 9x9 random choice plus backtracking method.

I see no ways to use the knowledge of band (stack) structure for my method of solution grids generation.

Serg

[Edited. I corrected typos - it was written "4x4" and "5x5" instead of "16x16" and "25x25", when larger then sudoku grids were discussed.]
Serg
2017 Supporter
 
Posts: 511
Joined: 01 June 2010
Location: Russia

Previous

Return to Sudoku variants