70ms(1GHz) for the 123 from msk_003.
Not sure what you mean by "pure" logic, but it seems that
"mixed" logic (logic+backtracking) is faster (and easier)
Do you guys know some web-sites that show some logic rules for Sudoku ?
I've been using this one: Sudoko Solver by Logic, but I don't know how to implement the complicated ones, and the solver on that website does not solve all sudokus by logic.
I'm wandering if there are more logic rules than that ?
Edit
I modified the "guessing" part of my solver so that it does not return right away when it finds the first valid result. This way it finds ALL valid solution. But it found only one for this puzzle...
Last edited by CVMichael; Aug 7th, 2005 at 01:57 PM.
Yeah, and it had a index-related bug. Fixed it now and I'm quite surprised that all other puzzles that've been posted here are solved correctly as were reported by that method.
Seems that I had my glitch for today (2 bad it's Sunday). This result came out of a rule I added but forgot to add inconsistency checking. It now gives the same result as that you've posted - big thanks CVMichael.
In the previous post I was saying I made it find more than one solution...
I put "1" in the grid in the first cell, and I clicked on "Solve", i'ts giving me about 1000 solutions per second
I'm curious to see when it stops, it will probably be a few million solutions
All sudokus are 6,670,903,752,021,072,936,960. I think that if you set a cell to 1, you'll get 72^2 × 2^7 × 27,704,267,971 different solutions. If that's so, don't hold your breath waiting for the program to end.
All sudokus are 6,670,903,752,021,072,936,960. I think that if you set a cell to 1, you'll get 72^2 × 2^7 × 27,704,267,971 different solutions. If that's so, don't hold your breath waiting for the program to end.
That's good to know.... I was turning red...
Hmmm... that means that a Long type cannot even hold the count... I better stop it now
Save each solution to your hardisk in the contest format! 97 bytes * 27704267971 = a bit less than 2,45 terabytes
On the other news... I managed to speed up the solving of "next to very easy", which dropped the total time a little:
NotLKH1, 69 files: ~35 ms -> 0,5 ms per file
NotLKH2, 532 files: ~665 ms -> 0,8 ms per file
NotLKH3, 123 files: ~240 ms -> 1,95 ms per file
Hardest, 337 files: ~2600 ms -> 7,7 ms per file
Still running the very same logic I've used all the time since I combined my basic rules solver and my backtracker... only optimized the use of variables. However, I'm planning on adding more logic to this code as I probably don't have the time to figure out a new logic solver.
Also, as you can see, NotLKH is managing to improve his generator, even though it is still a long way to get close to the hardest
Late edit: oh yea, and of that sudokusolver url CVMichael posted... I have only the "Method A" and "Method B" coded. After that it is all backtracker if those aren't enough to solve the puzzle.
Atleast you can identify which are the hard ones and which the easy ones... for my code. Didn't really have a killer sudoku, although I believe the last one there might be even more evil to others.
Sheesh. 10000 characters limit really kills. Anyways, I guess you're 1337 enough to be able to sort out the data into an array and then make it show what you want.
last week i discovered sudoku so yesterday i wrote a solver that combines both logic rules and recursive backtracking. Once you set your goals at speed its not hard to optimize data structures and looping. So progression is easy at the beginning. But after a while you meet your bounderies.
I dont see how one can solve a sudoku in less than 1 ms when it takes me 2.8 ms to set up the game depending variables. So let's do the test:
last week i discovered sudoku so yesterday i wrote a solver that combines both logic rules and recursive backtracking. Once you set your goals at speed its not hard to optimize data structures and looping. So progression is easy at the beginning. But after a while you meet your bounderies.
I dont see how one can solve a sudoku in less than 1 ms when it takes me 2.8 ms to set up the game depending variables. So let's do the test:
Q.StartTime
For i = 1 To 1000000
Next
Q.StopTime
My average is about 12.50 ms, what's yours?
Yeah, that's also how I felt at first. My understanding (and anyone please jump in to correct me if I'm mistaken) is that if your variable setup has nothing to do with each particular sudoku (so we're actually talking about all the things you need to do in order to load the puzzle into your internal representation), then this will not be included in the timing. Same stands for displaying your solution (spit it out in a 9x9 text matrix or use GDI and display dancing elephants forming the solution, it's the same). On the other hand, if your initial variable setup is geared towards solving the actual puzzle in any way (performing puzzle-specific initialization or reductions), this will be included in the final timing. I take it that it's also inferred that if you have to create certain structures or precalculate stuff that don't have to do with any one puzzle (so this would have to be done only once at the beginning of the application's run), then such code will also be excluded from the timing.
Now...I haven't got the faintest idea what's the purpose of that specific loop...but my time would be ~1ms for that. Just keep in mind that all contest entries will be executed on the same computer.
Hmmm,
looks like I might have to submit only type 15's and 79's.
In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard. If you pick the hardest only based on what is hard for my solver, you probably favor someone else. I guess there will be some background lurkers taking part in this contest not telling their times, laughing at the slow speed of my backtracker code...
Originally Posted by Brick1
Q.StartTime
For i = 1 To 1000000
Next
Q.StopTime
My average is about 12.50 ms, what's yours?
You compiled your code and with all optimizations turned on? No? Do it Also... the trick is not to do that much math.
What should I use to time my program? I tried the one mentioned in the 'Rules' post, but it says it returns seconds, but there is no way my program is taking 5 seconds? Do I divide the number it returns by 1000? Does it actually return miliseconds? Or should I use a different timer method?
In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard. If you pick the hardest only based on what is hard for my solver, you probably favor someone else.
Sorry!
I agree that a variety should be used. I'm not out to get you, I'm just concerned that, on average, my submissions are "too easy".
{honestly, how many times have I heard how easy mine are, that there are harder ones, like these... }
So, do you really think my variety is best for the contest?
You really don't think I should try to submit only challanging ones?
Yes, I do. Because that would be the most "fair" thing for everyone. If there are different kind of sudokus instead of a lot of the same kind, it wouldn't be too harsh to every code. Like, some code might be bad at one certain thing and if all the sudokus happen to be like that as they are diffucult in a same way, it would be very unfair against that code: the contest would be more like a test against the code. The contest wouldn't also see a broader view to the situatation: the code might be very good speedwise in something else, but if there are only sudokus of the same kind, the code couldn't show the potential.
So this is why I think variety is a good thing. It gives every code the chance it deserves. I think that in the end there should be equal amount of sudokus that are beforehand thought to be of certain difficulty. Like, ten very easy, ten easy, ten medium, ten difficult and ten very hard. All of them should try to be that in a different way. How to figure that out, well, it is your task and not mine
In the contest test sudokus there should be a variety of different kinds of sudokus: very easy, easy, medium, hard and very hard.
That sounds exactly right, that should give every algo a fair chance. My code for example won't solve very easy problems fast but it works better for more difficult puzzles and I'd hate to see only easy-medium puzzles being used for timing.
Try displaying the data with Format$(Q.RetTime, "0.000000") - if you have E stuff there, it is pretty confusing... using Format$ will fix that.
I just used Round(objTimer.RetTime, 15). I figured it out a few minutes after I posted because I widened my textbox and saw that the E stuff was there.
1) I'll start with the stupid one: Is a millisecond 0.001 or 0.0001?
2) What is backtracking? I have a few logic things in my program, but I don't have anything that I would define as backtracking. Could someone explain this to me please. Thanks.
3) Should I optimize for Pentium Pro in my program? It makes the program run faster on my comp, but I don't know how it will effect the comp these programs are going to be tested on. Will that comp have a Pentium chip?
2) I think this is where you place numbers without actually knowing that they are correct, and trying to continue from there. If this fails, backtracking is the process of returning to where you were before placing the number.
3) I presume you mean ticking the box in the "Compile" options. I think all computers these days are compatible with P-Pro, but I could be wrong. The "Advanced" options will certainly make a difference, if your code is safe .
I don't know what the exact process will be for marking, so these options may or may not make a difference.
The way I "backtrack" is extremely inefficient at this time.
However, you might be able to improve upon it.
For each cell thats unassigned,
- For each possible could be for that cell
- - Make a copy of your structure
- - Delete all the other could be's for that cell in the copy
- - Try to solve the copy
- - - If the copy disastrously fails to solve, ie.. it turns out that two or more cells in a group ends up with the same number, then delete this could_be from its original cell
- - - else, if it "worked", ie... it might not be solved, but it is Not conclusively impossible, don't do anything except test the next possible.
Once you've done this, hopefully some of the couldbe's have been deleted in such a way that the changed structure now solves.
Again, doing it this way is extremely inefficient. but its a start.
3) I presume you mean ticking the box in the "Compile" options. I think all computers these days are compatible with P-Pro, but I could be wrong. The "Advanced" options will certainly make a difference, if your code is safe .
I don't know what the exact process will be for marking, so these options may or may not make a difference.
I hope we can clear this up before submission time.
I honestly don't care about the optimizations in the project advanced settings.
Why ? Because even if the tester decides to test in de IDE with no optimizations, he will do the same with the other contestants... So, why worry about that ?
In whatever conditions the tester will test my code, in the same conditions he will test the other people. So if the algorithm is exactly the same on 2 people (i doubt it, but lets say...), then it will be the same time for both contestants...
And of course... the tester will test all submissions on the same computer
3) Should I optimize for Pentium Pro in my program? It makes the program run faster on my comp, but I don't know how it will effect the comp these programs are going to be tested on. Will that comp have a Pentium chip?
Personally I don't have a pentium at all, but as CVMichael says, all entries will be marked on the same PC under the same conditions...
Has someone helped you? Then you can Rate their helpful post.
That makes sense. Especially because we can't submit .EXEs, so if the tester wanted to test it in .EXE format, then they would have to compile it and would therefore compile everyones (and in the same way).
Reply With Quote
Originally Posted by ntg
. Fixed it now and I'm quite surprised that all other puzzles that've been posted here are solved correctly as were reported by that method.
}
