How many Sudoku exist

Everything about Sudoku that doesn't fit in one of the other sections

How many Sudoku exist

Postby Pi » Mon Sep 05, 2005 10:30 am

There must be a maximum number of sudoku possible, i am interested to know how many and therefore find out the feasibility of calculating them all and storing them on a database as a super-solver

I drew a sudoku grid and wrote in how many candidates there would be for each cell and worked out that there are no more than 1.0189 x 10^31 which is quite a lot

I am sure that there are actually a fraction of that amount

Has anyone else attempted something similar?

p.s i am talking about finished sudoku's
Pi
 
Posts: 389
Joined: 27 May 2005

Postby frazer » Mon Sep 05, 2005 11:14 am

Yes, the number of completed sudoku grids is known. There are 6670903752021072936960 such grids (computed by Bertram, using some analysis of mine -- the number was confirmed by Red Ed and by dukuso). As for the feasibility of storing all of these -- clearly storing the 6.67e21 grids is not feasible. But I'm sure that there must be possibilities to store all the solutions. One thing you could do, looking at the results above, is to store what has become known as "the gang of 44" (a particular set of 44 possibilities for the top three rows of the grid). Every possible top three rows is "equivalent" to one of these in some sense. Each of these 44 has only about 100000000 (10^8) possible completions to a full sudoku grid. So you could store these 44*100000000 grids as a catalogue. Further details of the calculation are at: http://www.shef.ac.uk/~pm1afj/sudoku/, although the article there is about to be replaced with a new version...
frazer
 
Posts: 46
Joined: 06 June 2005

Postby Pi » Mon Sep 05, 2005 11:21 am

Thank you

are those grids all completeley different or are some of them equivelant
i know that there are 72576 equivelant grids for each different grid
Pi
 
Posts: 389
Joined: 27 May 2005


Return to General

cron