View previous topic :: View next topic |
Author |
Message |
| feather
| Joined: 12 Oct 2005 | Posts: 2 | : | Location: UK | Items |
|
Posted: Wed Oct 12, 2005 11:07 am Post subject: My Method Seems to work |
|
|
I am not really into the Maths but I written a sudoku game widget in javascript, after reading this forum came up with my own way just trial and error.
I was not keen on using known templates or starting from a known grid. Tried this first and always ended up with similar games no matter how much I randomised it.
So starting from scratch this is how I create a completely random game.
This is a highly simplified psudo code
Start
Loop 7 times
Select a random number that has not been used before from 1 - 9
Keep looping until you have placed the number in all miniBlocks (3x3)
with no conflicts on rows & cols (selected at random looping).
end Loop
This leaves 2 random numbers missing
Find the numbers
Solve puzzle (trivial)
If puzzle is not workable then goto Start and repeat
End
The number 7 loop is critical, less numbers and my solver takes too long, more and due to the random aspect it takes too long to create a valid grid.
With this method I am seeing
Average min time 20ms
Average max time 2700 ms
Average time 890ms
In theory due to the randomness it would be possible to have an infinite time but I have never seen it, only once I have seen 6 seconds. _________________ www.purefineart.co.uk
Affordable Fine Art for Everyone |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Thu Oct 13, 2005 6:38 pm Post subject: |
|
|
It doesn't sound like your algorithm is actually capable of determining if a grid is valid, only if there are no apparent conflicts. You can have a lack of apparent conflicts, though, and still have an invalid grid. Consider this example:
Code: | . . 1|. . .|. . .
. . 2|. . .|. . .
. . 3|. . .|. . .
-----------------
. . 4|. . .|. . .
. . .|. . .|. . .
. . .|5 6 7|8 9 .
-----------------
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . . |
There are no solutions to that board. It's also entirely possible to have a grid with multiple solutions, which is equally invalid.
So far the consensus is that the best method for finding valid grids--and verifying them--is the dancing links algorithm. |
|
Back to top |
|
|
| feather
| Joined: 12 Oct 2005 | Posts: 2 | : | Location: UK | Items |
|
Posted: Thu Oct 13, 2005 8:52 pm Post subject: ??? |
|
|
I am not sure I understand
part of the process is that the grid is solved and therefore I assume must be valid, if it cant be solved then the process loops. Every complete iteration ends in a valid grid
or am I missing something ?
is it possible to have a solvable grid that isnt valid and if so what determines and valid grid ??? _________________ www.purefineart.co.uk
Affordable Fine Art for Everyone |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Fri Oct 14, 2005 3:55 am Post subject: |
|
|
It depends on how you're determining a grid is "solvable". If you're guessing and backtracking, then you still need to backtrack even if you find a complete solution just because it's possible more than one solution exists. Dancing links is quite good at this and also is less prone to bias.
If you can reach a solution by guessing, it does not guarantee the sudoku is valid. If multiple solutions exist, guessing can pick just one and give you the illusion of a valid board. |
|
Back to top |
|
|
|