2
$\begingroup$

I tried asking this on StackOverflow and it was quickly closed for being too broad, so I come here to get the mathematical part nailed down, and then I can do the rest with no help, most likely.

From this web page, I learned that there are 5,472,730,538 essentially different solved sudoku grids.

Please, I beg you, do not respond unless you have read the entire webpage and have a decent understanding of it. You can think of a 9x9 sudoku as being represented by a string of 81 numbers, separated by commas.

I want to find a way to generate one sudoku board from each of the 5,472,730,538 groups, do some quick analysis on it, and move on to the next board, continuing until all 5.4 billion are analyzed. In this way, I will have analyzed all possible essentially different Sudoku boards. I am not familiar with GAP.

So, I need someone, if they are willing, to help me bridge the knowledge gap I have, which is this: How do I go from this web page to actually finding (iterating through) each solution?

I do not expect a full detailed thorough answer on this. Instead, any post that I think is helpful to me in reaching my goal will be upvoted, no matter how short or how detailed.

EDIT 3-25-2015

Thanks to Nick Gill's suggestion, I contacted Frazer Jarvis himself and here is his very helpful reply:

Dear Jeremy,

The method we used simply evaluated the number of puzzles there had to be, and didn't count them by listing them all, so it wasn't a constructive proof in that sense. Nor can the proof be made to give a list, as far as I can see. As you are probably aware, this work of mine dates to 2005, and my active interest in Sudoku and related mathematical problems probably ended soon after, although I followed forums for a little while (my wife still likes doing them, but it has been a long time since I did one!) - but I did read towards the end of that time that someone had made a file of all of these. I don't remember who it was, however. You may be able to find the forum postings if you look around the internet. I'll have a quick look around too.

OK - the forum that contained the discussions no longer exists, but has been retitled, and is now at http://forum.enjoysudoku.com/sudoku-the-puzzle-f5.html

Ah - here's the thread: http://forum.enjoysudoku.com/catalog-of-all-essentially-different-grids-t6679.html - perhaps you could contact someone there?

Best wishes, Frazer

He also added later:

For what it's worth, the discussions about the number of different grids is in the thread http://forum.enjoysudoku.com/su-doku-s-maths-t44.html

$\endgroup$
10
  • $\begingroup$ what does "do some quick analysis on it" mean? $\endgroup$ – Nick Gill Mar 24 '15 at 16:41
  • $\begingroup$ He doesn't need help with the analysis, presumably, just the enumeration. @NickGill $\endgroup$ – Thomas Andrews Mar 24 '15 at 16:43
  • 1
    $\begingroup$ Are these puzzle grids, or solved grids? As far as I could tell from the linked page, these are solved grids. $\endgroup$ – Joffan Mar 24 '15 at 16:45
  • $\begingroup$ @ThomasAndrews, I guess you're right. But the nature of the analysis might affect the answer to "what does it mean to enumerate all of these grids?". By the way, I presume the linked page uses Burnside's Lemma to obtain the 5.4 billion number from the listed data. The final calculation isn't described. $\endgroup$ – Nick Gill Mar 24 '15 at 16:48
  • 5
    $\begingroup$ By the way, to answer the question, my office mate (who is an expert on these things) says that she thinks Russell & Jarvis have an explicit list of 5.4 billion representatives in a file somewhere. So perhaps the easiest thing would be to email them. $\endgroup$ – Nick Gill Mar 24 '15 at 16:51
1
$\begingroup$

In response to the OP's request that I post an answer:

I believe that Russell & Jarvis have an explicit list of representatives for the 5.4 billion essentially different types of sudoko grid.

The credit for the answer should go to my office mate, Sian Jones.

$\endgroup$
2
$\begingroup$

What about brute forcing ?

You can explore the tree of all possible grids of 81 digits, enforcing the placement constraints. Without constraints, there are 9^81 grids and generating all and checking the constraints is out of question. But checking the constraints as you go filling the grid might not be so unrealistic.

Represent the grid as a list of 81 mask of 9 bits; the bits tell you if the corresponding digit is still allowed at the given location, taking into account the digits already placed.

So start traversing the tree from the top left location and try all 9 possible digits in turn; for every try, only consider the digits that are allowed by the mask, and perform a recursive call to the next location in the grid; the full recursion depth will be 81.

When you try a digit, you will clear the relevant allowance bit in the whole row, column and square. Actually, you need to keep a copy of the masks in the corresponding locations, so that you can restore them after the trial.

If, when trying a new location, it turns out that the mask is empty, you have reached a dead-end and you will implicitly backtrack. This is where there is some hope of achieving a reasonable running time: if many attempts fail early enough, there will be severe pruning of the tree.

The required stack space will remain reasonable, as the maximum stack depth is 81, and on every level you will need to save 27 masks (9/row, 9/column, 9/Square), i.e. 54 bytes or so.

Try(Location):
  for Digit= 1..9:
    if Mask[Location][Digit]:
        Save & clear masks [Digit] for all locations on the same row
        Save & clear masks [Digit] for all locations on the same column
        Save & clear masks [Digit] for all locations on the same square

        if Location == Last one:
          Success, evaluate the grid
        else:
          Try(Next(Location))

        Restore masks on the square
        Restore masks on the column
        Restore masks on the row

As the Save & clear operations are very intensively used, any optimization trick is welcome there, the first being usage of a compiled language.

$\endgroup$
4
  • $\begingroup$ This is a lovely solution, but does not address the "essentially different" issue, which is the point of that webpage. $\endgroup$ – vadim123 Mar 24 '15 at 17:20
  • $\begingroup$ I missed that. If there are 5 billion essentially different grids, then the number of truly different grids must be astronomical and this procedure can't do. Anyway, it is the scheme of a brute force solver (it suffices to initialize the masks with already known data), which has proven to be effective. $\endgroup$ – Yves Daoust Mar 24 '15 at 17:24
  • $\begingroup$ If you fix the first row to be the numbers 1 to 9 in sequence, then you've eliminated the simple recoding equivalence. There are still row and column swaps of course. $\endgroup$ – Joffan Mar 24 '15 at 17:28
  • 1
    $\begingroup$ @Joffan: yep, though I see no simple way to rescue the situation and adapt the brute force approach to deal with the "essentially different" property. $\endgroup$ – Yves Daoust Mar 24 '15 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.