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