Enumeration of Solved Sudoku puzzles

Question

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

Answer 1

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.

Answer 2

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.