Sudoku solver: reduction + brute force

Anton Vredegoor anton.vredegoor at gmail.com
Fri Jan 20 12:55:53 CET 2006


ago wrote:

[Something I mostly agree with]

> According to Anton the number of possible solutions can be reduced
> using 1) number swapping, 2) mirroring, 3) blocks/rows/columns
> swapping. All those operations create equivalent matrices. For a 9X9
> grid, this should give a reduction factor = (9!)*(48)*(6^12) minus the
> number of duplicated combinations given by the methods above. I am not
> sure how to calculate the number of duplicated combinations and
> therefore do not know if the result is "good enough". As mentioned, I
> doubt that it is a viable approach, but I find it an intriguing
> approach nevertheless.

We could start hunting down net sites giving sudoku problems and claim
they are trying to sell us the same problem twice :-) Or produce
counterfeit problems ourselves and get rich quick.

But I wonder about that 6^12 term. Within each 3-row block there are 6
permutations. There are 3 3-row blocks and 3 3-column blocks. Then
between blocks (swapping complete 3-row blocks) permutations also give
a factor 6.

So in my count (but I suck at math) this term schould be: 6**8 (also
switching to Python exponentiation notation)

Anton




More information about the Python-list mailing list