The New Sudoku Players' Forum

[evert]

Another AN-puzzle:

Code: Select all

750080000
000000000
003000600
000012009
000073000
000000000
000500100
900000000
000004000


[Pyrrhon]

List updated.

Pyrrhon

[JFA]

Hello, how many Anti-knight sudoku are there ? How I can calculate this number ?

[Mathimagics]

A good question!

I think the current situation is, nobody knows.

I doubt that the number can be calculated, some sort of enumeration is required.

A brute-force approach is out of the question - one would need to test all the ED grids (5,472,730,538), but also the 3,359,232 variants for every case, since these transformations don't preserve the AK property. We can only reduce this by a factor of 4, for rotation/reflection symmetries, but still the number of grids to test is enormous.

But these AK grids are likely to be very rare, since up to 8 extra eliminations can be associated with each cell (the central square has the full 8). Rarity seems to be confirmed by a random grid generator that tested over 1.5 billion grids before finding one anti-knight case … not very scientific, but it does suggest that an exact count is probably easily obtained ...

[JFA]

Yes I think adapt a fast Sudoku solver to solve in this mode is a good solution, but I don't have one. I hope you will succeed

[Mathimagics]

Ok, that was fairly simple, really …

I decided not to bother with template generation, the grid count should be small enough to warrant an "all in one go" approach. So I just set the appropriate table for my solver, and gave it row 1 = "123456789" as the puzzle to be solved, asked for all solutions, and it came back 75s later with the answer 8,490,104.

My learned friend blue, or indeed anybody with a reasonably fast solver that can easily enforce the AK rules, should be able to confirm this figure.

ED grid count would probably be around 2.1 million?

[JFA]

Ok good job and very speed ..............., thank's
Beautiful method of resolution

[Michal56]

the answer 8,490,104.

I have got very similar but not the same result: 8,490,164 and I would like to know if:
- my solver is wrong
- there is a typo in Mathimagics' post

Can someone check it out?

[mith]

I'm aware of an independent count (again generating all solutions with r1 fixed) which agrees with the 8,490,104 reported by Mathimagics.

[Michal56]

Mathimagics' solution is correct - I have found an error in my computations.
Moreover:
Anti knight 6x6 - 16 x 6! = 11,520 solutions
Anti knight 8x8 - 209,213 x 8! = 8,435,468,180 solutions

Anti knight & Anti king 6x6 - no solutions
Anti knight & Anti king 8x8 - 1 x 8! = 40,320 solutions
Anti knight & Anti king 9x9 - 4 x 9! = 1,451,520 solutions