|
Thanks for posting this article. It was a good explanation of how to generate a completed sudoku grid. I just finished a Sudoku game and had help from Spirch too. I couldn't follow his code, but he's a smart guy and he got me on the right track for my own code.
But, I think either your math is wrong or mine is. Your article says you can generate a Sudoku in 0.018 seconds.
For fits and giggles I ran the following Benchmark on my Grid Generator:
Private Sub BenchMarkGridCreation()
Dim ComputationTicks(10000) As Long
Dim ComputationMilliseconds(10000) As Long
Dim InstanceTimer As New Stopwatch
Dim ElapsedTimer As New Stopwatch
Dim thePuzzleGrid As clsGrid
Dim lngSumTicks As Long
Dim lngAvgTicks As Long
Dim lngSumMilliSeconds As Long
Dim lngAvgMilliSeconds As Long
ElapsedTimer.Start()
For i As Integer = 0 To 10000
InstanceTimer.Start()
thePuzzleGrid = New clsGrid
thePuzzleGrid.CreateCompletedGrid()
InstanceTimer.Stop()
ComputationTicks(i) = InstanceTimer.ElapsedTicks
ComputationMilliseconds(i) = InstanceTimer.ElapsedMilliseconds
InstanceTimer.Reset()
Next
ElapsedTimer.Stop()
For i As Integer = 0 To 10000
lngSumTicks = lngSumTicks + ComputationTicks(i)
lngSumMilliSeconds = lngSumMilliSeconds + ComputationMilliseconds(i)
Next
lngAvgTicks = lngSumTicks / 10000
lngAvgMilliSeconds = lngSumMilliSeconds / 10000
Debug.Print("Total Ticks:=" & lngSumTicks)
Debug.Print("Total Milliseconds:=" & lngSumMilliSeconds)
Debug.Print("Average Ticks per Grid:=" & lngAvgTicks)
Debug.Print("Average MilliSeconds per Grid:=" & lngAvgMilliSeconds)
Debug.Print("Elapsed Time (seconds):=" & ElapsedTimer.Elapsed.TotalSeconds)
Debug.Print("Elapsed Time (seconds) per Grid:=" & ElapsedTimer.Elapsed.TotalSeconds / 10000)
End Sub
My Results were:
Total Ticks:=17903103147
Total Milliseconds:=1200
Average Ticks per Grid:=1790310
Average MilliSeconds per Grid:=0
Elapsed Time (seconds):=5.9894137
Elapsed Time (seconds) per Grid:=0.00059894137
If my math is right, I'm taking .0006 seconds per grid. I'm running a low-spec Dell, not a Cray. Are you sure you're taking 0.018, not 0.0018?
|
|
|
|
|
The title for the article was made before all the adjustments in these threads. I'm sure it has improved a lot since these adjustments. And, of course, the method i used to calculate was very crude. Nowhere near as accurate as the code you have used. I will adjust the title soon.
|
|
|
|
|
Hey Anzac
I think you've got it the wrong way round. Your code was sweeter than mine and should have run faster. That's why I think you're underestimating your code
Thanks again for the article. Always good to see great code and ideas being shared.
Cheers
|
|
|
|
|
Greetings,
I have an article named "Sudoku Algorithm: Strategies to Avoid Backtracking".
I didn't make a benchmark, but I can suposse my solution is a little bit faster (Who will need to solve a Sudoku board some miliseconds faster, anyway??).
You can check the strategies I use to avoid backtracking and achieve a solution with less steps..
Got my 5...
|
|
|
|
|
Thanks for the 5.
I will check out you're article for certain.
The reason i used the benchmark to promote this is a couple of reasons.
- Producing the solution grid as fast as possible reduces the overall time needed to display a solvable puzzle. Post processing with the grid(removing numbers, painting etc) is a little slow.
- I also designed this for larger scale use. Say someone wants to develop a whole book of solvable puzzles. By producing them this quick they could produce a whole book in a very short time even with all the post-processing required.
- I surprised myself by making it so fast.
|
|
|
|
|
speed is always fun for the ego but your right, important thing is to make "good" code with "good" algorithm.
I made one, sudoku game, a few months ago. It was damn slow... about 150-190 9x9 sudoku per second and for a 16x16 sudoku, it was taking between 15 seconds to 2 minutes
last Christmas, I took a few day to look at my code and I did rewrite a lot of code, my application can now create over 32000 9x9 each seconds and over 70 16x16 each seconds. This is using backtracking.
My next goal, when i will have free time, will be to remove the backtracking.
Btw, you can try it here: http://pages.videotron.com/spirch/FredGames/[^]
|
|
|
|
|
I just posted my first article and it's about sudoku, let me know what you think if you have time
|
|
|
|
|
It doesn't produce solvable sudokus, just solved ones.
Jm
www.menendezpoo.com
|
|
|
|
|
It produces a solveable grid. You can do what you want with it. It is a solvable sudoku, its just not a solvable puzzle. Take the output and turn it into one. However you want to do that is your choice.
|
|
|
|
|
Actually, what you've produced is not "solvable" - it's "solved". This is the easy part of producing Sudokus - the hard part is getting rid of just enough that you have a unique, solvable sudoku puzzle. There is a super efficient way to come up with solved sudokus as you've done with no backtracking at all. Look at section 8.3 of http://www.math.washington.edu/~morrow/mcm/team2280.pdf[^] which explains a direct and essentially immediate way of producing solved puzzles.
|
|
|
|
|
I've toyed with the idea of coding a Sudoku game for the Atari 2600. The hardest part would seem to be puzzle generation in a constrained-RAM environment (128 bytes, including stack). If the cartridge were limited to applying transformations to puzzles stored in ROM, I wonder how many puzzles would be required to make the game interesting (and ensure that players didn't routinely find themselves "recognizing" transformed puzzles)?
Also, I wonder whether it would be practical to have a number puzzles that could be assembled by combining a "solved" grid with a list of pre-revealed revealed spaces. Obviously only some such combinations would work, but storing e.g. 256 9x9 solved grids of numbers along with 256 9x9 sets of pre-revealed spaces and a list of pairs of solved grids plus reveal-sets might allow a large number of puzzles to be stored in a reasonable amount of code space.
|
|
|
|
|
I think there are better ways than the preset "holes". In fact, I kinda doubt that that would work at all.
One possibility is to generate them. I've got a generator (which is why I had to code to produce solved puzzles). It essentially takes a random solution and intelligently drops out squares and solves the resulting puzzle looking for all possible solutions. If it finds exactly one solution, it tries dropping out more cells. If it finds more than one, it starts revealing more cells to disambiguate. It randomly orders the cells to see which ones it's dropping out and which ones it's putting back. Eventually, you have a uniquely solvable puzzle.
Another possibility is to put lots of "base" puzzles in and, after picking one at random, "shuffling" it and or/rotate/reflect it You can also move the 3 cell blocks around in random order. By the time you've done all that, it will look completely different thatn the original. The chances that somebody would recognize that such a modified puzzle is "equivalent" to one they've already done is essentially zero. That would really give you a large number I think.
I'd do the latter if you wanted something quick and dirty and then go back in later and implement the former.
|
|
|
|
|
Hi Darrell,
Impressive link you had posted earlier. I am not a Math student and struggle a bit to implement the 8.3.3 from that paper, which is in fact what you explain here above as the 'former' solution.
What I dont understand is the following:
The paper claims taking 40 values from the solved solution into an empty grid. Then removing values one by one while checking that the grid is still valid. This is what I dont understand. The values will always be valid and occur only once in the same row and column since its taken from a solved solution in first place.
Next it claims remove them as long until the appropriate difficulty is generated. But how do I know the difficulty only through code? So that the user who wanted an easy game gets an easy difficulty etc.?
I wished there was more explanation about 8.3.3.
It seems you are very fit in math, do you have any idea how this was meant on the paper? and how to implement it?
Many Thanks,
Houman
|
|
|
|
|
If you look back at the flow chart in 8.3.3, it doesn't check that the grid is "valid", it checks that it has a "unique solution".
Oh - I see where you're talking about. The flowchart doesn't say "valid" but they use it in the wording above. I'd rely more on the flowchart if I were you. If you do, you'll see that "valid" in this sense means "uniquely solvable". So they're not using valid in the sense of "solvable" - you're right, they're all valid in that sense. They're using it in the sense of "uniquely solvable" in which case, if you remove enough givens, you can end up with invalid sudoku puzzles. If the board they're currently looking at has more than one solution, then it's not valid as a sudoku puzzle. Sudoku puzzles must have exactly one solution. If you remove enough givens (meaning "cells that have their values given in the initial puzzle"), you can end up with more than one solution. In fact, if you remove them all, you end up with a blank sudoku board where any possible solution whatever will fit in. You want a board with a single unique solution so they're checking for that here. Then they start removing the givens - i.e., clearing cells. Each time they remove one there's a possibility that the resulting puzzle will have more than one solution so they check for uniqueness each time they remove a given. If it's non-unique, then it's unacceptable and they put that given back in and try another. If it does have a unique solution, they check it's difficulty to see if it lies within their acceptable limits and if it does, then they're done. If it doesn't, they start from scratch.
Actually, it seems to me that they wouldn't need to start from scratch if the difficulty isn't acceptable. They could just keep trying to remove other givens, but that's not what their flowchart says they do. I probably wouldn't do it that way. At least not initially - maybe there's actually a good reason for that but they don't explain what it would be in the paper. In my program I don't check difficulty at all. I'm just trying to generate a random puzzle of any difficulty so that last step on checking for difficulty isn't part of my program.
|
|
|
|
|
Darrell,
Sorry for the late response. I had to study much further before being able to respond and to continue the discussion.
You are right about what you said. It makes now a lot more sense to me. I think the challenge here is to create valid SuDoKus by utilizing Latin squares first, then selecting randomly 40 cells out of the previous grid as Givens. As the third step one given shall be removed at a time and every time a given is removed there will be a good chance that the puzzle doesn't lead to the same unique solution as before any more and that's bad.
In order to prevent of falling into this trap, the paper suggests using a Brute Force algorithm to check if the solution is still unique after each removal. So far so good, however there is a huge problem with this approach. A brute force algorithm is nothing more than a guess algorithm that is able to crack any puzzle. A human brain doesnt work like that, in fact only a selection of patterns can be solved by humans, while there are far more patterns - including the brute force - that can only be calculated by machines.
I came across some other papers. They suggested against using a brute force for validation. Since the end result could end up having very different level of difficulty than anticipated. So the idea is using instead of the brute force pattern the Naked Single and Hidden Single (Easy level patterns) as long as possible. If the puzzle is solvable (valid) this way, it means we have an easy puzzle generated. If more difficult patterns were required to get a solvable (valid) puzzle, then the end result would have been a more difficult puzzle respectively.
Something that is now confusing to me is the following: Using XWing for instance is considered a more advanced pattern. However an XWing never gives an absolute result but two possibilities of what could be. Literally like forking a flow. What if one way doesnt lead to a unique solution, would I have to "undo" everything back to this step and go the other branch down and see how this could lead to a valid solution? But since you havent been playing with difficulty, you might have no answer to this.
In the last part of your post, you mentioned your code generated puzzles. but from what I remember it only created a valid fully sudoku, but it doesnt create a valid puzzle from it. Or do you have your code extended in the meanwhile and not posted here. In that case, could I have a copy? I am curious how you implemented the brute force algorithm.
|
|
|
|
|
To the best of my knowledge, a Sudoku puzzle does not need to be uniquely solvable to be a valid Sudoku puzzle. The puzzle can have multiple solutions and still be a completely valid puzzle. In fact, most Sudoku puzzles that I've tried (especially programs) have more than one valid solution. I highly doubt that with the thousands of Sudoku puzzle books out there, every puzzle has a unique solution. Check out Sudoku on wikipedia; it's stated in the first paragraph that a puzzle "typically" has a unique solution, not that it's required to.
If you scroll further down to the mathematics section, it states that out of the 6,670,903,752,021,072,936,960 possible solution grids, only approximately 48,000 have been proven to have unique solutions with only 17 givens at the start of the puzzle. It should also be noted that 17 givens has been proven to be the lowest number of givens possible with a unique solution. However, you could have 77 givens and not have a uniquely solvable puzzle. But it's still a Sudoku puzzle, and a valid (although incredibly easy to solve) one at that.
|
|
|
|
|
Using the method I talked about in the previous post, I get a solved sudoku in 0.000015 seconds using 120 lines of code, most of which is initializing the 12 basic 3x3 Latin Squares. Here's the code:
static int[] arRowSwap = new int[] { 0, 3, 6, 1, 4, 7, 2, 5, 8 };
static int[, ,] LatinSquares3X3 = new int[12, 3, 3]
#region 3x3 Latin Square Enumeration
{
{
{0,1,2},
{1,2,0},
{2,0,1}
},
{
{0,1,2},
{2,0,1},
{1,2,0}
},
{
{1,2,0},
{0,1,2},
{2,0,1}
},
{
{2,0,1},
{0,1,2},
{1,2,0}
},
{
{1,2,0},
{2,0,1},
{0,1,2}
},
{
{2,0,1},
{1,2,0},
{0,1,2}
},
{
{0,2,1},
{2,1,0},
{1,0,2}
},
{
{0,2,1},
{1,0,2},
{2,1,0}
},
{
{2,1,0},
{0,2,1},
{1,0,2}
},
{
{1,0,2},
{0,2,1},
{2,1,0}
},
{
{2,1,0},
{1,0,2},
{0,2,1}
},
{
{1,0,2},
{2,1,0},
{0,2,1}
}
};
#endregion
static int[] RandomPermutation(int n, Random rnd)
{
int[] intRet = new int[n];
for (int i = 0; i < n; i++)
{
intRet[i] = i;
}
for (int i = 0; i < n; i++)
{
int iSwap = rnd.Next(i, n);
int iSwapVal = intRet[iSwap];
intRet[iSwap] = intRet[i];
intRet[i] = iSwapVal;
}
return intRet;
}
static int[] RandomPermutation(int n)
{
return RandomPermutation(n, new Random());
}
public static int[,] SolutionGenerator()
{
Random rnd = new Random();
int[,] ls = new int[9, 9];
int i3x3Outer = rnd.Next(12);
int[] arPermute = RandomPermutation(9);
for (int iRowMajor = 0; iRowMajor < 3; iRowMajor++)
{
for (int iColMajor = 0; iColMajor < 3; iColMajor++)
{
int iRowBase = iRowMajor * 3;
int iColBase = iColMajor * 3;
int i3x3 = rnd.Next(12);
int upperDigitVal = LatinSquares3X3[i3x3Outer, iRowMajor, iColMajor] * 3;
for (int iRowMinor = 0; iRowMinor < 3; iRowMinor++)
{
for (int iColMinor = 0; iColMinor < 3; iColMinor++)
{
ls[arRowSwap[iRowBase + iRowMinor], iColBase + iColMinor] =
arPermute[LatinSquares3X3[i3x3, iRowMinor, iColMinor] + upperDigitVal] + 1;
}
}
}
}
return ls;
}
|
|
|
|
|
Impressive. Its a very nice algorithm.
|
|
|
|
|
I can't claim credit - that would go to the paper's author - I just did the implementation. The author isn't actually listed in the paper but it's under Jim Morrow's website at the University of Washington so I assume he had something to do with it. Yours is a great demo of backtracking also. I really am not trying to demean it (it's probably about what I would have come up with before I saw the paper) - I just thought you might like to see an alternative.
Regards,
Darrell
|
|
|
|
|
Its ok, i'm not offended. I'm still quite happy with my own attempt considering I'm a psychology student who does this on the side for fun. haha. I appreciate the link though. It's an impressive algorithm that i may implement in future projects.
|
|
|
|
|
Sorry if my previous response was vague. In regards to it being solvable. Producing the solvable grid from the solution grid is the easiest part. Selectingly removing squares will produce a puzzle grid.
|
|
|
|
|
Actually, I also think you don't need to iterate through the squares 3 times, just check each condition on your way through, so here is how a modified sub would look. I did not test it but I think it should be faster.
Private Function Conflicts(ByVal CurrentValues As Square(), ByVal test As Square) As Boolean
For Each s As Square In CurrentValues
If (s.Across <> 0 And s.Across = test.Across) OrElse _
(s.Down <> 0 And s.Down = test.Down) OrElse _
(s.Region <> 0 And s.Region = test.Region) Then
If s.Value = test.Value Then
Return True
End If
End If
Next
Return False
End Function
|
|
|
|
|
Thanks or the improvements, will be sure to test them when I get back into coding I will make the adjustments. Psychology degrees don't lend much time to coding these days.
|
|
|
|
|
The ANZAC wrote: Psychology degrees don't lend much time to coding these days.
And how does that make you feel?
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
I've made all the changes you suggested. A slight increase in performance is noted. Thankyou.
|
|
|
|
|