The New Sudoku Players' Forum

[Mathimagics]

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.

[dobrichev]

For N=9 Red Ed shared code focused on the randomness of the generated grids. It is mentioned here and published here.

[Mathimagics]

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!

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