|
| View previous topic :: View next topic |
| Author |
Message |
| wizard5
| | Joined: 31 Jul 2005 | | Posts: 1 | | : | |
Items |
|
 Posted: Sun Jul 31, 2005 8:20 pm Post subject: It is as simple as that! |
 |
|
I've found THE solution to easily generate all possible soltutions in just 2 steps:
1. Generate the trivial solution:
1.1 Set the smallest possible number to the most top-left corner (i.e.: Proceed top-down and left-right) if it is possible. This fills the top line with
1, 2, 3, 4, 5, 6, 7, 8, 9, the next line with
4, 5, 6, 7, 8, 9, 1, 2, 3, then
7, 8, 9, 1, 2, 3, 4, 5, 6,
2, 3, 4, 5, 6, 7, 8. 9. 1,
5, 6, 7, 8, 9, 1, 2, 3, 4,
8, 9, 1, 2, 3, 4, 5, 6, 7,
3, 4, 5, 6, 7, 8, 9, 1, 2,
6, 7, 8, 9, 1, 2, 3, 4, 5,
9, 1, 2, 3, 4, 5, 6, 7, 8.
2. Randomly mutate this grid with one of 4 operations, which lead to another valid grid. The operations are:
- Mutate a pair of numbers (all of them)
- Mutate a pair of lines/rows (within a 3x9 block)
- Mutate a pair of 3x9 blocks
- turn the grid by +/- 90°
Repeat 2. a few times, and you'll get one of all possible valid grids
To explain:
If you count all possible operations (leave alone a few effects of symmetry), you'll get 108 different operations. So, if you repeat 2. 5 times, you'll (theoretically) get 10 to the power of 32 different grids. And all valid!!!  |
|
| Back to top |
|
 |
| angusj
Site Admin
 | | Joined: 18 Jun 2005 | | Posts: 406 | | : | |
Items |
|
| Posted: Sun Jul 31, 2005 10:52 pm Post subject: Re: It is as simple as that! |
|
|
| wizard5 wrote: | | So, if you repeat 2. 5 times, you'll (theoretically) get 10 to the power of 32 different grids. |
If you repeat a random process you don't increase its randomness (otherwise there'd be an infinite number of solutions), so I really can't see how you could possibly achieve this number for possible grids using your method.
While you will still get a reasonably large number of unique grids using this method, I believe it'll only be a very small fraction of the total number of possible grids. |
|
| Back to top |
|
|
| jaap
| | Joined: 13 Jun 2005 | | Posts: 24 | | : | | Location: NL |
Items |
|
| Posted: Mon Aug 01, 2005 6:38 am Post subject: Re: It is as simple as that! |
|
|
| wizard5 wrote: | - Mutate a pair of numbers (all of them)
- Mutate a pair of lines/rows (within a 3x9 block)
- Mutate a pair of 3x9 blocks
- turn the grid by +/- 90°
|
The first operation alone leads to 9! possible grids.
The second leads to 3!^6 times as many.
The third leads to 3!^2 times as many.
The last leads to (up to) 4 times as many.
Combining these factors gives a number that is still a trillion times smaller than the total number of grids.
For example, you starting grid does not contain 4 cells in a rectangle that contain only 2 numbers i.e.
a...b
.....
b...a
The operations never create or destroy such a rectangle. Yet, there are grid that have such rectangles and they therefore cannot be generated by this method.
_________________
Jaap
--
Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Mon Aug 01, 2005 7:44 am Post subject: Re: It is as simple as that! |
|
|
| jaap wrote: | | wizard5 wrote: | - Mutate a pair of numbers (all of them)
- Mutate a pair of lines/rows (within a 3x9 block)
- Mutate a pair of 3x9 blocks
- turn the grid by +/- 90°
|
The first operation alone leads to 9! possible grids.
The second leads to 3!^6 times as many.
The third leads to 3!^2 times as many.
The last leads to (up to) 4 times as many.
Combining these factors gives a number that is still a trillion times smaller than the total number of grids.
For example, you starting grid does not contain 4 cells in a rectangle that contain only 2 numbers i.e.
a...b
.....
b...a
The operations never create or destroy such a rectangle. Yet, there are grid that have such rectangles and they therefore cannot be generated by this method. |
9!*6^8*2 operations in total. only 2 of the 4 rotations give new grids.
See the Sudoku-players forum or:
http://www.shef.ac.uk/~pm1afj/sudoku/sudgroup.html |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
