The New Sudoku Players' Forum

[coloin]

Saturn - my ****

Uranus' Satellite - Oberon

mass - 3.03e21 kg or about 6.68e21 pounds
quick facts - Heavily cratered surface. Discovered by Herschel in 1787.


The Gravitational Constant, G, has a value of 6.67 ´ 10 ^–11 Nm2 kg-2

not really close

Earth, Mass (kg): 5.98 x 10^24 kg

- an overestimate - but a better approximation than I ever got.

[coloin]

[quote="geoff"][quote="coloin"]Guest

"The last box - where do you get the 9 out of 70 ? I thought 1/30"

i.e. box 7
in boxes :
123
456
x89

"for the last box we know the three numbers required for each column the requirements for each row must match. wlog are columns must be 1,2,3 4,5,6 7,8,9 so 1 can be required in any row. 2 must be required in a diffrent row i.e. 6 of the possible 8 places. 3 must be in the remaining row 3 of 7 available places. 4 can go in any row 5 in 4 of 5 places 6 in 2 of 4.
789 must now be in different rows so multiplying 144/1120 = 9/70."

Thanks for the clarfication - your approximation was also pretty good.

[su bloko]

Sudoku will be Wikipedia's featured article of the day tomorrow, the 10th of June. As such it will take centre spot on the main page of Wikipedia. No reference is made in the article to the disturbing Oberon coincidence. As yet. ;-)

[Dominic]

I think if some-one were to program in C this pseudo code for counting solutions, it may be easy/faster as it relies on very few and CPU-friendly instructions:

Code: Select all

' This array is a bit map identiying the block, row and column for each square:
long map(81)
' This array tells us the blocks, rows and columns taken by each number
long num(9)

' These are inialised as follows (recording any preset-numbers in each cell)
' Note also that the <block/cell/column of i> as below should origin with 0
for i=0 to 80 {
....map(i)=2^<block of i>+2^(9+<row of i>)+2^(18+<column of i>);
....num(<number on i'th cell>) OR= map(i);
}
' don't forget to set our counter to zero!
Counter=0

' To count the solutions call this with the starting cell:
Sub Solve(cell as integer) {
    int i;

    if cell=81 Counter+=1;
    elseif <cell is not preset with a number>  {
         for i=1 to 9
            if num(i) AND map(i) = 0 {
                num(i) OR= map(i);
                call Solve(cell+1);
                num(i) XOR= map(i);
            }
        }
    }
}


Even in dead-slow VB it does several million solutions per second. written in C it should fly.

[Dominic]

Apologies, the Solve code was slightly wrong:

Code: Select all

    if cell=81 Counter+=1;
    elseif <cell is not preset with a number>  {
         for i=1 to 9
            if num(i) AND map(cell)= 0 {
                num(i) OR= map(cell);
                call Solve(cell+1);
                num(i) XOR= map(cell);
            }
        }
        else call Solve(cell+1)   
    }


[Dominic]

Impressive work there, by the way, on the total number of solutions front. But...

I am very suspicious about that huge prime number. Indeed, the fact that previous posts have correctly pointed out that every solution can be transformed into another using a number of simple and obvious rules which include:
digit replacement = 9!
block swapping on row basis = 6
block swapping on column basis = 6
column swapping within each block column= 6^3
row swapping within each block row = 6^3
Point to the fact that the solution should at least be divisible by the product of these - which the bertram/afj solution is not.
Ofcourse, the above assumes that these transformations are mutually exclusive, but I can't quite see that they would not be...

I would also corroborate the "theoretical average" solution which has been alluded to which is equal to:
9!^3 * (36/5)^6 = 6.65708E+21

I had a logical approach to this solution which made me think that it would be the exact answer - except that it not only fails the above test but has a fractional part to it!!! Averages, you can't trust 'em.

I do not think we can consider the job done until we have a general solution for all Sudokus of extent N. (where we've only really considered N=3 and even there have resorted to a computer to trawl through the combinations. That's not going to be possible for N=4)

[Red Ed]

... the fact that the solution should at least be divisible by the product of these

Not true. For immediate evidence that this doesn't work, consider the N=2 case where your transformations argument would say that the number of solutions is divisible by 4! x 2!^2 x 2!^(2x2) = 1536, when in fact it is less than this number. You're double-counting (and then some).

[Dominic]

Understood. Clearly my "mutually exclusive" assumption is rubbish.
Hmmm, so that big prime in the answer is very odd.

[Red Ed]

Hmmm, so that big prime in the answer is very odd.

I should hope so -- large primes aren't supposed to be even ...

There's nothing weird about having a large prime factor: see http://www.mail-archive.com/mersenne@base.com/msg03890.html

[su bloko]

We need an entry in http://www.research.att.com/~njas/sequences/Seis.html which is the Online Encyclopedia of Integer Sequences. It is true that we only have 3 numbers of the sequence (that is 1, 288 and 6,670,903,752,021,072,936,960) but it is an interesting and infinite sequence. I suspect it will be several years before the 4th number is discovered and I have my doubts as to the 5th number ever being enumerated. It might be the shortest sequence on their database!

[su bloko]

Well, I have made an entry to make sure your calculation is immortalised: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A107739

You are A107739!

[geoff]

Dominic missed the interchange of rows and columns another factor of 2. This can be either by reflection in a diagonal or rotation by 90 degees, row shuffling turns one into the other. So 9! * 6^8 *2.
For any solution the operations in this set that preserve a particular solution must form a subgroup and thus divide that number. Further as two subgroups of size 8! * 6^6 can be found that always give different solutions the size of the subgroup for any solution is at most 648 = 3^4 * 2^3. I have previously posted a solution with this degree of symetry.

I call solutions derived by these operations similar to the base solution. The solution set is thus divided into "similarity classes" with 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 27, 36, 54, 72, 81, 108, 162, 216, 324 or 648 times 8! * 6^6 members. Classes with the lowest numbers of members are likely to be rare.

I have a feeling representation theory could be useful but I gave that up 30 years ago.

For those interested my 2 subgroups are genrated by

1) permutations of rows and columns (6^6), permutation of digits 2 to 9 (8!).
Each of these gives either a different placing of the number 1's or a different box 1.

2)Permutation of the numbers 1 to 9. (9!) Permutation of rows 456 or 789 (36), permutation of the same columns (36) switching of boxes 456 with 789 or 258 with 369 (4).
all these solutions differ in box 1 row 1 or column 1.

Using the second of these I have shown that for my very symetric solution any other operation can be undone by a combination of the operations listed.

p.s. my estimate for N=4 posted earlier also fails to be an integer.

[frazer]

Dominic's earlier reply includes the suggestion that any valid grid can be transformed into any other by means of certain transformations; in fact, we don't know whether that is true yet. But geoff's remark that different grids can have different sizes of "similarity classes" make this less likely. (However, it did form the basis of several earlier attempts to enumerate the grids.) Also, the large prime would be very odd if this were the case. However, if there were, say, 2 basic grids, it's very likely that adding two numbers with only small prime factors will have a large prime factor. (For example, 50 + 144 = 194; the largest factor of the two numbers on the left is 5, but the sum has a factor of 97; the calculations of Bertram and Ed suggest that there are at least 44 essentially different grids.)

Geoff's calculations also go some way towards giving an enumeration of "essentially different" sudoku grids, whatever that should mean. This might be trickier to compute, however, although I've already been very impressed by what Bertram and Ed can do with computers...! I may try to think further about this next month, but I'm probably too busy at the moment...

Frazer

[Bertram]

Code: Select all

long map(81)
' These are inialised as follows (recording any preset-numbers in each cell)
' Note also that the <block/cell/column of i> as below should origin with 0
for i=0 to 80 {
....map(i)=2^<block of i>+2^(9+<row of i>)+2^(18+<column of i>);
....num(<number on i'th cell>) OR= map(i);
}


Even in dead-slow VB it does several million solutions per second. written in C it should fly.

How do you fit 81 bits into a 64 bit datatype? I'd expect you're generating a lot of invalid solutions with this code. Anyway, the basic idea works very well and both Ed's and my programs make use of bitmap manipulations to work as quickly and efficiently as possible. Ed's program uses 81 bit bitmaps that are compressed to fit into 64 bits by leaving out some unused bits. My program uses bitmaps for each block, row and column that contain the digits that were placed in them.

Bertram

[Dominic]

"map" is an 81-element array of LONGs. Each element represents one cell and has placed within it 3 bits which indicate the block, row and column to which the cell belongs. - I only need 3*9 bits (i.e. <32) to do this. This is a "static" array.

"num" is a 9-element array of LONGs. Each element represents one number. The bits set for each LONG are arranged like the "map" element whereby bits set indicate that the number already exists in that block/row/column. So if all 27 bits are set for num(1) then this means that the number 1 is present in every block,row and column. This is a "dynamic" array in that it tracks, for each number, its availability for placement in a block/row/column.

If you code what I've written it certainly works. But, ofcourse, with all brute force algorithms this is at the extreme of dumbly trying every possibility. In general, you can cut down the number of nodes needing to be searched by choosing the best "moves" first. but the more sophisticated that assessment is, the longer it takes and the less nodes you'll get to. And that's the nub of writing software for games like chess, draughts etc.

For example, in Sudoku, to brute force find a solution to a problem, it's probably quicker to always fill in the cell with the least number of possibilities at each recursion point instead of going from cell 1 to 81! But finding that cell is a considerable number of machine cycles compared to those taken up simply by "making the move" as per my simplest program example above.

All interesting stuff!