The New Sudoku Players' Forum

[su bloko]

... and that was me ^^^

[Animator]

parralising this problem should be an issue... it's finding the resources to run it... Currently the fastest solution I have find an average of about 100000 valid solutions a second...

Ofcourse this isn't enough (except when someone has a really large cluster of pc's).

Doing this really brute force is only possible with a high number of pc's...

[su bloko]

My estimation technique has come up with a figure of 6.4 * 10^21. A figure of that order seems to have been arrived at independently several times.

Establishing a definitive figure seems a bigger challenge.

[su bloko]

Currently the fastest solution I have find an average of about 100000 valid solutions a second

ooh. I won't bother with a race then! Are you running your solution on a PC? Written in C?

[Animator]

My first solution I wrote was in Perl, but obviously this was too slow... Then I switched to C...

It is currently running (for the past 12 days to be correct), at my server (which has a 1400 mhz CPU) which is for about 80% idle... But I will probably stop running it one of these days, since it really is pointless...

If you calculate how many seconds it will take to reach 10 * 10^22 then you will get a way to high number...

If it would be done simultaniously with 1000 pc's it would take ??? days... but where can you find 1000 pc's? which are mostly idle? :) (Updated, the ??? used to be a number, but I don't know how I got it... as in, recalculating it seems to fail :) )

I tried doing some calcuations myself using the rows but I can say that I didn't reach a good point... as in, I got a different number when I multiplied the number of possibilites from the last 4 rows with doing a brute force on the last four... (the end result was something * 10^22...)

I am considering re-writing it in assembler but it has been a really long time since I used it and I can't say I know much assembler... but atm I'm to busy to really do that...

For those intrested in the code: http://b.wizbit.be/Sudoku/solve.c
(A note about the code: I reliase that grid[i] = j is useless, but I wonder if it really has a big effect on the performance, as in would it be worth it stopping it removing the line and re-running?) (Updated, the loops were useful after all)
I compiled this code using gcc, if anyone can see an optimalisation in it, then feel free to tell me!

[Guest]

Very interesting contributions again. I no longer think that brute force is hopeless, although one has to put in quite a bit of thinking to reduce the size of the search first. We've already noted that of the 948109639680 possibilities for blocks 1-3, we can relabel block 1 to reduce us to 2612736 possibilities. As I noted above, since we can reorder the columns in block 2 and in block 3, and can interchange the blocks, this reduces the possibilities by a further factor of 72, to 36288. I'm hopeful of finding sufficiently many more reductions that the possibilities for blocks 1-3 can be reduced to around 1000 or even fewer (i.e., working out how many ways these blocks can be completed to a full grid is enough to solve the problem). I think this should be possible; I have some more ways to reduce this number, but haven't finished programming this. Once blocks 1-3 are fixed, one can try to do the same for blocks 4 and 7, although there will be less leeway for this, once blocks 1-3 are fixed in place. At the moment, my program is taking about 36 hours to find the number of Sudoku for given blocks 1-3 (after 6 full runs, I'm predicting an answer of about 6.67 x 10^21). I hope that with more efficient programming (C rather than Perl, as Animator suggests, although I'm rather rusty!), the running time could be cut to less than a year (!) from the 7-8 years I'd currently need.

Frazer

[Animator]

I'm not 100% sure on what exactly you mean so allow me to ask this question:

Is the basic idea to fix blocks 1, 2 and 3, and run a brute force on all the others? and do this for the 32668 number of possible blocks?
Also, if you did then, then how would you go on defining the total result? as in, multiple it with what number?

[Guest]

My plan was to form a catalogue of possibilities for blocks 1-3, and then to brute force for each, as you say. To get from the total for the 36288 to the total for the full number, I'll have to multiply by 72*9!.

Frazer

[su bloko]

Hi, back again. I am with afj on his approach. A pure brute force attack does not seem feasible without access to some serious computing power. However, a combination of logic and brute force might get us there. C seems the way to go on the language front. I have been writing in VB6. Given three filled in start mini grids, I can compute the number of possible sudoku's for the rest of the grid (averaging around 100000) in about 10 minutes. That seems to compare poorly with the results you are getting with C Animator. I have not written in C before, so I am a bit wary of making the switch.

Where our approaches differ afj is I am looking at pre filling mini grids 1,5 and 9. You are pre filling 1,2 and 3. I guess that makes the brute force element of my approach less arduous, but the logic element more complex.

The logic element would mean figuring out something like this:

there are x1 ways to fill mini grids 5 and 9 that produce exactly y1 legal sukoku's
there are x2 ways to fill mini grids 5 and 9 that produce exactly y2 legal sudoku's

.... to xn, yn

If logic (and/or brute force) allows us to determine all values of x and y, and n is sufficiently small, the problem is determined.

[su bloko]

I am stumped. I had originally hoped that n would equal 1, x1 would be 9!^2 and all that would be needed would be to calculate y1. It does not take much computing to demonstrate that n> 1, however. I then hoped that n would be a fairly small number and logic would allow calculation of x1 to xn, and brute force would provide y1 to yn. Looking at some results, it appears likely that n will not be trivially small. Worse, I can't see a way to calculate how big it will be or how to calculate x1, x2 etc. (which is the same problem).

Maybe we will have to be happy with our approximation, which we seem to have established as being close to 6E21.

[su bloko]

I have cross posted this problem to another forum in which I am active. An interesting idea has already emerged:

http://boards.straightdope.com/sdmb/showthread.php?t=317099

[Guest]

... I no longer think that brute force is hopeless, although one has to put in quite a bit of thinking to reduce the size of the search first...since we can reorder the columns in block 2 and in block 3, and can interchange the blocks, this reduces the possibilities by a further factor of 72, to 36288. I'm hopeful of finding sufficiently many more reductions that the possibilities for blocks 1-3 can be reduced to around 1000 or even fewer (i.e., working out how many ways these blocks can be completed to a full grid is enough to solve the problem)....

Some earlier posts on this thread combined with the above got me to thinking. (I suspect afj has already been down this road)

There's probably a relatively small number of PATTERNS to filling in blocks 2 and 3 given block 1.

For the rest of this discussion, assume block1 is filled in as
123
456
789


For example, for blocks 123, consider
123 bbb ccc
456 ccc aaa
789 aaa bbb where a is any one of (123), b is any one of (456) and c is any one of (789) that satisfies the block rule.

If 123 winds up in the same row in either block 2 or 3, then the rest are 'forced'. afj's swapping of middle and right chutes then account for all of the other possibilities.

You guys seem to have a way to 'brute force' the possibilities from here for each permutation of a row grouping. But I'll assert that
123 456 789
456 789 123
789 123 456
and
123 465 789
456 789 123
789 123 456
should have exactly the same number of valid solutions for blocks 3-9, as would any other permutation of abc.

Then there's
123 bbC ccB
456 ccA aaC
789 aaB bbA
where a capitalized letter shows where the same value must appear. So the value for A (say '1') must be the same in blocks 2 and 3, but the rest of the values for 'a' can be either 2 or 3. Note that A can be any one of (123) in turn. Swapping middle and right vertical chutes cover off the 'other' possibility.

As far as I can tell, this enumerates all of the row possibilities. (123) either appear together somewhere in a row in block 2 or 3, or they do not. Where they do not, then two of them must be together in one of these blocks. The rest fall into place 'automatically' once 123 (or aaA) are placed in block 2 or 3, and chute-swapping makes the decision to place two of (123) into rows 2 or 3 of block 2 equivalent.

So it may just be a matter of counting permutations of these patterns, and brute forcing a sample for each of them.

[su bloko]

OK, I can switch my code to prefill blocks 1,2 and 3. Valid solutions from there are more numerous than prefilling 1, 5 and 9. I guess that means my speed will drop drastically from 10 minutes. How many permutations for 2 and 3 do we need to brute force tinfoil? Can we determine how many permutations each permutation is representative of?

[Guest]

Following afj's approach, if we assume blocks 1-6 are filled with a valid combination, consider blocks 7-9, in that order.
There are 9 cut-down columns of 3 cells each, and for each exactly 3 numbers are valid. These 3 numbers could in principle be ordered in any way within the column, so for block 7, where no new constraints apply, there will be 3!x3!x3! (ie 216) valid possiblilities.

But in block 8 there will be the additional constraint that for each number one row is ruled out, because that number occurs in block 7.
Consider the first column of block 8, and suppose the numbers available are a,b,c.
If 'a', 'b', and 'c' occur in the different rows in block 7, say in this order, then the only possibilities for this column in block 8 are b,c,a and c,a,b.
If 'a' and 'b' occur in one row, say the first, and 'c' in the second, then the possibilities are c,a,b and c,b,a.
a,b,c cannot all occur in the same row in block 7.
So there will be only 2 possibilities for the first column of block 8, irrespective of whether these numbers occur in the first, second or third rows in block 7.
The same argument applies to the two other columns, since no further constraints will apply.
So there will be 2x2x2 ways in which block 8 can be filled.

When only block 9 remains unfilled the puzzle is complete, as for any number two rows and two columns will unavailable, leaving only one valid cell.

Therefore the total number of possibilities for the last three blocks is 216 x 8 = 1728.

Looks as if this could be used to reduce this problem a little.

Mike

[Guest]

Permutations if my prior post is valid:

(123) in same row in Blocks 2,3:

For example, for blocks 123, consider
123 bbb ccc
456 ccc aaa
789 aaa bbb where a is any one of (123), b is any one of (456) and c is any one of (789) that satisfies the block rule.

If 123 winds up in the same row in either block 2 or 3, then the rest are 'forced'. afj's swapping of middle and right chutes then account for all of the other possibilities.

You guys seem to have a way to 'brute force' the possibilities from here for each permutation of a row grouping. But I'll assert that
123 456 789
456 789 123
789 123 456
and
123 465 789
456 789 123
789 123 456
should have exactly the same number of valid solutions for blocks 3-9, as would any other permutation of abc.

If this is true, then each of the six 'rows' of blocks 2 and 3 can be permuted 3! (or 6) ways, for 6^6 ways altogether (times 2 for the chute-swap), leaving 2*(6^6) permutations, when (123) appear together in blocks 2 and 3

(123) in different rows in Blocks 2,3:

Then there's
123 bbC ccB
456 ccA aaC
789 aaB bbA
where a capitalized letter shows where the same value must appear. So the value for A (say '1') must be the same in blocks 2 and 3, but the rest of the values for 'a' can be either 2 or 3. Note that A can be any one of (123) in turn. Swapping middle and right vertical chutes cover off the 'other' possibility

Assuming that each of these permutations does actually lead to an identical number of valid solutions (and I have not tested this 'postulate' in any way):

A,B, and C can each be one of 3 values. The 'aa', 'bb' and 'cc' parts of each row are then fixed by our choices for ABC: 3^3 permutations so far.

Each 'row' in blocks 2 and 3 can then be arranged 3! ways, for 6^6 such arrangements.

Finally, the 'chute-swap' doubles the permutations, for 3^3*6^6*2 (or 3^9*2^7) permutations, when (123) DOES NOT appear together in blocks 2 and 3.


As a check, this should ADD to our 56*3!^6 ways to fill a chute for a given block1. Factoring this gives 2^9 * 3^6 * 7

Same (123) + different (123) = [2^7 * 3^6] + [3^9*2^7] ?= 2^9 * 3^6 * 7

Skipping the algebra and simply doing the math, both sides of the equation in fact equal 2 612 736, so the permutations add up.