My Method Seems to work

feather · 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

Lummox JR · 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:

feather · 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

Lummox JR · 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.