Random Sudoku Grid Generation

For fans of Killer Sudoku, Samurai Sudoku and other variants

Random Sudoku Grid Generation

Postby Mathimagics » Sat Jan 09, 2016 12:25 am

I've been hoping to expand my Futoshiki generator to produce Sudoku Inequality (Sudoshiki) puzzles of size 16 or even 25.

But first I needed to find a way to get starting grids, which involved revisiting the RSG problem.

I thought it worthwhile running some timing tests to indicate the problems associated with scaling up the grid size, N.

My results were:
Code: Select all

-------------------------------------------------------------------
 Size |     Method A      |     Method B      |     Method C
  N   |   Grids    Time   |   Grids    Time   |   Grids    Time     
------|-------------------|-------------------|--------------------
  9   |    100     163s   |  10,000    140s   |    10,000    0.065s
      |                   |                   | 1,000,000    6.482s
--------------------------|-------------------|--------------------
 16   |      0*  14400s   |  10,000   1800s   |    10,000    0.125s
      |                   |                   | 1,000,000   12.453s
------|-------------------|-------------------|--------------------
 25   |     **            |  10,000  18000s   |    10,000    0.299s
      |                   |                   | 1,000,000   30.151s
-------------------------------------------------------------------



I was going to provide descriptions of the methods, but since this is a puzzle forum, why not leave that for others to fill in? Bonus points for suggesting a method I haven't tested. 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 334
Joined: 27 May 2015

Re: Random Sudoku Grid Generation

Postby dobrichev » Sat Jan 09, 2016 4:09 am

For N=9 Red Ed shared code focused on the randomness of the generated grids. It is mentioned here and published here.
dobrichev
2016 Supporter
 
Posts: 1295
Joined: 24 May 2010

Re: Random Sudoku Grid Generation

Postby Mathimagics » Sat Jan 09, 2016 12:44 pm

dobrichev wrote:For N=9 Red Ed shared code focused on the randomness of the generated grids.


Thanks (and bonus point) for that useful reference.

I have added Red Ed's B2347 method to the table. It performs very well indeed, although it can't be used (understandably so) for arbitrary grid sizes.

I've also changed my figures for Method B, which were 30-40 times higher than they should have been because I was testing
an older version by mistake.

Together these changes should serve to clearly identify method B! 8-)

Timings are for an AMD Phenom II X6 (2.8GHz).

Code: Select all
---------------------------------------------------------------------------------------------
 Size |     Method A      |     Method B      |     Method C         |     RedEd B2347      |
  N   |   Grids    Time   |    Grids   Time   |   Grids    Time      |   Grids    Time      |
------|-------------------|-------------------|----------------------|----------------------|
  9   |    100     163s   |    10,000     2s  |    10,000    0.065s  |    10,000    0.512s  |
      |                   | 1,000,000   172s  | 1,000,000    6.482s  | 1,000,000   50.376s  |
--------------------------|-------------------|----------------------|----------------------|
 16   |      0*  14400s   |    10,000    42s  |    10,000    0.125s  |    n/a               |
      |                   | 1,000,000   387s  | 1,000,000   12.453s  |                      |
------|-------------------|-------------------|----------------------|----------------------|
 25   |     **            |    10,000   720s  |    10,000    0.299s  |    n/a               |
      |                   | 1,000,000    **   | 1,000,000   30.151s  |                      |
---------------------------------------------------------------------------------------------

   * indicates run abandoned

  ** indicates run not attempted

 n/a indicates method not available

User avatar
Mathimagics
2017 Supporter
 
Posts: 334
Joined: 27 May 2015


Return to Sudoku variants

cron