we'll have to see about that, I'm sure that people will come up a variety of methods - some of which may be noticably better than those which have been posted already.
(I have already seen one privately which is much faster, but may not be capable of solving the grids above).
MUCH FASTER than half a second????? How fast????
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Your posted code is pretty good.
My Soduko Pattern Generator created the attached pattern, and your code solved it.
It took 2 minutes, uncompiled, 600 Mhz, but it still worked.
Just a quick note, there is a competition starting soon (in the VBForums Coding Contests forum) for a Sudoku solver, so you may not want to make your methods too public
NotLKH, thanks for that - I haven't had a chance to look yet (no .Net at home ), but I'm sure I'll have fun with it
The code I posted creates the base of a sudoku.
Since then, I've brought it up to speed for creating true sudoku, with N-cells exposed. The above image is one of the thousands that its made.
I've got a few more tweaks to make it build harder problems, but I have little time to incorporate them. By this time next week, I should have it making some really tough ones.
Does anyone know where this game came from? I had no idea what it was and all of a sudden its everywhere. I like the solver though. If I come across one in the paper that I can not solve, I use the solver and get the answer. Thanks for it.
I have done a LOT of changes since last, and it is now superfast. Cant tell how fast yet or give you code since there will probably be a contest.
I can't see there being a contest. They have been talking about it for weeks on the other thread and it's got nowhere.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
I can't see there being a contest. They have been talking about it for weeks on the other thread and it's got nowhere.
It has been going somewhere - we had to determine interest first, then once we since we knew it was worthwhile we have been organising the rules and scoring for the competition (and sources for the puzzles!).
MUCH FASTER than half a second????? How fast????
I can't remember, but the version I saw wouldn't win anyway - speed isn't the main issue, solving the puzzles is
I can't remember, but the version I saw wouldn't win anyway - speed isn't the main issue, solving the puzzles is
????? If it does not solve the puzzle it's a non starter. I would have thought that speed was the major determining factor followed by innovative coding.
BTW notlkh can provide the puzzles (but I hope they won't be as difficult as his last one (above). That took me 45 minutes to solve by hand as opposed to my normal 10. It also revealed a flaw in my coding which got into a perpetual loop over it
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
????? If it does not solve the puzzle it's a non starter. I would have thought that speed was the major determining factor followed by innovative coding.
BTW notlkh can provide the puzzles (but I hope they won't be as difficult as his last one (above). That took me 45 minutes to solve by hand as opposed to my normal 10. It also revealed a flaw in my coding which got into a perpetual loop over it
Sorry I got you to sweat over it!
At least you proved its solvable by hand. I havn't had a chance to go for it yet, although the 5 in the center square seems to be the first solvable value.
However, My Generator, which is also a solver, goes through that puzzle like a hot knife thru butter. I can't even count to one before its solved. 'Course, my solver is using the same techniques as the builder, so its not necessarily a fair fight.
kaffenils is a great brute force method. However, in terms of speed, you need extra technique. I'll be tweaking my solver to do brute force when techneque can't go furthur, then back to technique when its found a lead.
BTW, Did you have fun?
Last edited by Something Else; Jul 25th, 2005 at 09:07 PM.
Yep. I had fun. One stage more pleasant than banging my head against a wall
Yes, if you know the principles on how the puzzle was constructed you can follow the same course in solving it. My programme just uses the same technique as my brain. It selects a number and then checks to see if there is only one place it will go. Puts it there and then repeats the process. If there is no complete logical progression, or there is more than one possible solution, it will not solve it.
Kafenils' solution appears to include the use of iteration at various points. He is updating the screen, which must consume time. I use a control array to hold the values and only update the screen when completed ( or failed to complete!!) - but his is still faster than mine on the puzzles I've tried so far.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
????? If it does not solve the puzzle it's a non starter. I would have thought that speed was the major determining factor followed by innovative coding.
It could solve several, but not others. The winner will be the one that can solve the most, in the quickest time (ie: more quickly than any others that can solve the same sudoku).
I managed NotLKH's puzzle in 8 minutes by hand. Can I enter myself?
I reckon a good (tough) puzzle would be one from the Times on Thurs or Fri - the Fiendish puzzles. Pick one at random - they're usually sufficiently difficult and have enough different moves in them to make a solver work a bit. Unless NotLKH rises to the challenge...
It could solve several, but not others. The winner will be the one that can solve the most, in the quickest time (ie: more quickly than any others that can solve the same sudoku).
So what happens if a project solves ten out of ten puzzles in 20 minutes and another project solves nine out of ten in 5 minutes??? Which one is considered best?
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
I managed NotLKH's puzzle in 8 minutes by hand. Can I enter myself?
I reckon a good (tough) puzzle would be one from the Times on Thurs or Fri - the Fiendish puzzles. Pick one at random - they're usually sufficiently difficult and have enough different moves in them to make a solver work a bit. Unless NotLKH rises to the challenge...
So what happens if a project solves ten out of ten puzzles in 20 minutes and another project solves nine out of ten in 5 minutes??? Which one is considered best?
The one that solves the most. This is about solving the problem (the sudoku's) more than the speed.
As you are already aware, some are extremely hard to solve manually, so creating a program to do it will be even harder for several people (of course others may find it easier).
The speed is just a "tie-breaker".
Note that this is how things usually work in business too - you need to solve the problem first, afterwards you can worry about the speed (if you get the time!).
How about this one?
kaffenils's solver/iterator took 7m 30s's, so it is seemingly a little harder than my other one.
Can you beat kaffenils time by hand?
-Lou
That one took me 35 minutes But it gave me problems I have not encountered before and has given me an idea to improve my solver
BTW Unless you can immediately see a pattern, you will never beat a solver programme because the computer can do it's logical eliminations at the rate of something like 16,000,000 per second. (AMD 2.2 gig processor) Granted that the computor can't take a global view an ignore obvious impossibilities ( which could slow it down by a factor of 6561) but that leaves it something like 2500 times faster than a human in that part of it's computing.
Last edited by taxes; Jul 27th, 2005 at 06:31 AM.
Taxes
The more I learn about VB.NET the more I like dBaseIII Plus
The foregoing, whilst believed to be correct, is given without guarantee as to it's accuracy and entirely without recourse. You are required to decide for yourself whether or not it is suitable for your purposes and no liability for loss of any nature can be entertained.
Anyways, I've got a couple more strategy tweaks to perform, then I want to tweak it to bring the number of exposed cells down, but I don't have any time to do any development on my generator today.
Tomorrow or the next day, I'll post some more testing patterns, in the format as specified by the contest rules.
Woss:
My generator is also a solver, and it solves my own patterns pretty fast, < 1 second. However, I am certain that other, more cleverer generators will use strategies that I cannot conceive of. So, I'll be tweaking my solver to, when it runs into a dead end, Guess away 1 cell, 2 cells, 3 cells, ... until it correctly guesses and lets my strategy solver run to conclusion.
Needless to say, but I won't be entering the contest since I'll be generating the tests. However, the good news is,... I saved a bunch of money by switching over to Geico!
AND... since I won't be entering the contest, I won't be revealing my code, which means I could commercially develop and release my progie!
I don't know what other approaches are available but I'm trying to mimic the human brain's own throuh processes during the solving process. I think it can be done very quickly if the puzzle can be strongly represented inside the computer.
I predict the recursive and iterative approaches to be, by far, the slowest (by a few orders of magnitude).
Its interesting just how difficult this is, given the seemingly very simple puzzle rules.
Ok. I sincerely hope the judges will be using .Net Framework 2005 (v2.0) for this because that's what I've got at home. If not then I'll have to write my entry at work
Humm... my algorithm solves a basic sudoku in ~0,004 seconds under the IDE and ~0,0001 seconds compiled. Of course this code isn't very wise. I hope I'm able to code some good rules for the harder puzzles.
To ease your mind: I've never solved a sudoku myself
NotLKH, I managed that one in just over 10mins. So a bit harder than the other one .
I can recommend trying these puzzles by hand, for anybody who's interested. There are a couple of methods that you'll spot by doing them manually which if included in coding will speed things up no end.
I'd make my own solver, but with so many luminaries entering this contest I'm overawed.
I'm using logical deduction. However this is proving hard to code, My initial approach is quite a loose system and if it works, I'll tighten it up and optimise it for speed later.
I can't see that any iterative approach can be faster. But then again, who am I to say?
Here are some patterns in the format requested by the contest.
The lines terminate with vbcrlf.
If a number is not masked, it is the number.
If it IS masked, then it is a decimal point.
They are a smattering of 22 and 23 exposed cells.
They are at the Various levels of "difficulty", ie... 0000, 0001, and 0003.
Ok, I'll attach the solutions here for those.
BTW, My generator has been making them with the numbers 0 thru 8, tab deliminated, and those that I attached were converted to the 1 thru 9, decimal for masked position format, with a sub I just whipped together.
I inspected a couple, and they seem to be properly converted, but if they aren't, please get bak to me. In an hour or two, I'll build a reader, and test each one. If I screwed up, I'll fix them, and repost.
BTBTW, Yes, I'll be making more new ones for the contest, that should be even more difficult, and hopefully, My progie will be able to generate patterns with Numbers revealed < 22. I also hope I can make them with Visual Patterns, such as the revealed cells form smilie faces, or other symetrical patterns.
-Lou
PS: If you can, maybe you could open a new thread for these test patterns in the contest area?
Hmm.
I wasn't able to connect an hour ago, so I've been pinging & tracerting ever since!
Ping and Tracert still fails, but I now find myself able to browse again???
Anyways, an hour ago I finished building a routine to load all my msk files, all the sol files, submit the loaded msk array to my solver, build the solved array, and verify that they were valid solutions, while also simultaneously checking them against the sol data.
69 loaded, solved, and verified in under 2 seconds.
Looks like they're good!
Originally Posted by si_the_geek
we'll have to see about that, I'm sure that people will come up a variety of methods - some of which may be noticably better than those which have been posted already.
Reply With Quote
), but I'm sure I'll have fun with it 
