| LarryLACa
| | Joined: 21 Oct 2005 | | Posts: 2 | | : | |
Items |
|
 Posted: Fri Jan 06, 2006 9:25 pm Post subject: Math of Sudoku |
 |
|
Each of the Gang of 44 corresponds only indirectly to a Sudoku grid, which limits their usefulness in many (non-math) situations.
Each of the 'Gang of 44' is a very 'compact' representation of all the possibilities of creating a valid top band Sudoku grid. Each of the 44 can be unfolded into N (canonical) top band solutions (usually identifed as siZe of the set or equivalence class). Each of the canonical band solutions (fixed Box1 numbering, ordered Box2,3..) can be expanded into 9! * 72 distinct solutions.
Each of the top band (partial) solutions can be completed in M (compact) ways, to form a full grid. M is the last(?) column in the G44 table, and is like ~100,000,000. Each of these can be expanded into another 72 distinct solutions.
Computing the weighted sums of the Ms with 9! * 72 * 72 and their class size, gives the 6.7e21 total number of distinct solutions.
The G44 IDs are the column values of Boxes2 & 3 that have been 'flattened'. To flatten a Sudoku box, order the cell values in the box mini-columns, lowest at the top. The flattened representation is no longer a valid Sudoku box, but it simplifies the counting. Box1 is numberedThere's more to the flattening consolidation, but this gives the general idea.
Constructing a (few) valid band solution(s) that belongs to the set (equivalence class) for each of the G44 is not hard. Think of it as another type of puzzle for constructing a top band, the above gives clues for Box1..3 values. But this only gives you a few bands. Expanding them further (to full grids or all implied equivalent bands) is not so easy. 
Wikipedia - Math of Sudoku has a longer explanation of the technique. Anyone interested in helping with the Wikipedia related pages, is always welcome. |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
