All entries for Tuesday 31 May 2005

Sudoko Problem SOLVED!

Follow-up to Unsolved Problems In Mathematics #2242 : The Secret of Sudoku from The Militant Wing of Pacifism

Well, the number of solutions problem has been solved. I can't claim any credit, of course, but plenty of kudos for this Felgenhauer guy.

The number of valid Sudoku solution grids for the standard 9×9 grid with 3×3 regions was calculated by Bertram Felgenhauer to be 6,670,903,752,021,072,936,960 This number is equivalent to 9! × 72² × 2⁷ × 27,704,267,971, the last factor of which is prime.

Still awaiting confirmation, of course, but it seems pretty sound.

The mechanics of the solution isn't terribly technical, though. Basically, it's a brute force search by computer for unique solutions, which we then multiply by the appropiate number of symmetries. (From above, 27,704,267,971 are the unique solutions, and the rest we multiply by are symmetries.)

The code used is available here. It's in C++ and python, so you should be able to test it yourself. The solution was found based on discussions on an internet forum, so obviously these things are useful, after all!

The minimum givens problem is still open, though.

: 31 May 2005 15:23 |  Tags: Stuff |  Comments (5) |  Close comments |  Report a problem