MUCH FASTER than half a second????? How fast????Quote:
Originally Posted by si_the_geek
Printable View
MUCH FASTER than half a second????? How fast????Quote:
Originally Posted by si_the_geek
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.Quote:
Originally Posted by taxes
Kaffenils,
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.
How fast does your new code solve it?
-Lou
The code I posted creates the base of a sudoku.Quote:
Originally Posted by si_the_geek
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.
:wave:
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. :wave:
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.Quote:
Originally Posted by kaffenils
Weeks? Nah... Only 1 thing left to do and then it's starting :)
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!).Quote:
Originally Posted by taxes
I can't remember, but the version I saw wouldn't win anyway - speed isn't the main issue, solving the puzzles is ;)Quote:
MUCH FASTER than half a second????? How fast????
Quote:
Originally Posted by si_the_geek
????? 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 :blush:
Sorry I got you to sweat over it!Quote:
Originally Posted by taxes
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?
:wave:
Hi Something Else,
Yep. I had fun. One stage more pleasant than banging my head against a wall :bigyello:
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.
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).Quote:
Originally Posted by taxes
He's already very kindly agreed to that :)Quote:
BTW notlkh can provide the puzzles
Hi,
I managed NotLKH's puzzle in 8 minutes by hand. Can I enter myself? :D
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... :cool:
zaza
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?Quote:
Originally Posted by si_the_geek
I just might do that!Quote:
Originally Posted by zaza
:bigyello:
How about this one?Quote:
Originally Posted by zaza
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?
:wave:
-Lou
The one that solves the most. This is about solving the problem (the sudoku's) more than the speed.Quote:
Originally Posted by taxes
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!).
Quote:
Originally Posted by NotLKH
That one took me 35 minutes :blush: But it gave me problems I have not encountered before and has given me an idea to improve my solver :thumb:
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.
I don't want to worry anyone or anything but what if someones' program started solving any puzzle in under 1 second?
Good, Good!
Whats your longest time, BTW?
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!
:wave:
Shortest time so far = 873ms
Longest = 2040 ms
There is a big bug in my code though so it might mess all of this up when I fix it :(
Can you start generating a few puzzles for us so we can test our apps? maybe start a contest support thread with nothing but puzzles in it?
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.
Yes, but in a day or two.Quote:
Originally Posted by wossname
I'm under some cruch time, at the moment.
Gotta:
#1: finish developing the job generation process for a new customer product, and
#2: break my mom out of the hospital as soon as #1 is done.
So, I'm kinda tied up today.
So, tomorrow or friday.
:wave:
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 :)
Hi,
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.
zaza
I'll believe that when I see it :D
What would be a better approach: To start with a grid and work by elimination or the other way round? I'm using the elimination approach right now...
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.
BTW, should I also attach the solutions?
:wave:
-Lou
Might be a good idea. If you have them that is. So people don't have to do them all by hand. But only if you have them that is..:)
PS: And you are able to make more for the contest right? So these don't have to be used for the contest?
- ØØ -
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.
:wave:
-Lou
PS: If you can, maybe you could open a new thread for these test patterns in the contest area?
I can't do that...but I will contact someone that might do it for me.
Thanks for everything you have done.
- ØØ -
"Tab deliminated" :lol: You invent that format yourself Lou? :D
My program is getting complicated now, I have 9 classes and 1 interface so far. Its getting out of hand. :eek:
Don't think you should be using classes there. IINM, instantiating them should cause your time taken to solve to increase? UIA. :(
IINM, UIA????
What?
you can't get me to tell you how my program works before the contest finishes.
"Verily, I wath not borne yefterdaye" - William Shakespear
This is my result, how does it look ?
Code:File name Time taken
0000_0001_022.msk 2.71909399947331
0001_0001_022.msk 3.71132311550857
0002_0003_022.msk 3.49031870885219
0003_0003_022.msk 31.7336726734635
0004_0001_022.msk 2.42342045822204
0005_0003_022.msk 4.09064906010559
0006_0003_023.msk 2.15500244535571E-02
0007_0001_023.msk 1.2505083581004
0008_0003_023.msk 1.03720573174657
0009_0001_023.msk 16.5584227430621
0010_0003_023.msk 15.5263699133466
0011_0001_023.msk 3.7023805575411
0012_0001_023.msk 6.52451268700701
0013_0003_023.msk 6.38957079618274
0014_0001_023.msk 1.16988286871575
0015_0003_023.msk 3.19137721931706
0016_0003_023.msk 0.256800431385827
0017_0003_023.msk 4.27013421616944
0018_0001_023.msk 8.66439679470298
0019_0001_023.msk 2.58067997441782
0020_0001_023.msk 0.127753658628344
0021_0000_023.msk 0.119299710319401
0022_0003_023.msk 0.147342517838556
0023_0003_023.msk 8.53933460241024
0024_0001_023.msk 12.7805091155337
0025_0003_023.msk 5.99652135485246
0026_0001_023.msk 0.470022306660146
0027_0001_023.msk 0.964925322598849
0028_0000_023.msk 0.122390870672034
0029_0003_023.msk 3.11695027275121
0030_0003_023.msk 28.9548248749106
0031_0003_023.msk 28.298185731663
0032_0003_023.msk 8.44545747212922
0033_0003_023.msk 11.4160296853642
0034_0001_023.msk 2.03757704626111
0035_0003_023.msk 0.440596415986356
0036_0001_023.msk 0.723511972210727
0037_0003_023.msk 0.518182541414293
0038_0001_023.msk 0.274212226778526
0039_0003_023.msk 10.9860151938101
0040_0003_023.msk 2.97657928094002
0041_0000_023.msk 7.80455629710445
0042_0003_023.msk 20.6754762273805
0043_0000_023.msk 0.286548808045847
0044_0001_023.msk 1.32737509248461
0045_0000_023.msk 4.46436900208587
0046_0003_023.msk 14.6780527745382
0047_0003_023.msk 2.25563453594673
0048_0001_023.msk 0.993217180191365
0049_0001_023.msk 1.44367607940509
0050_0003_023.msk 13.9840324442271
0051_0001_023.msk 46.2796064055779
0052_0003_023.msk 0.847475214125378
0053_0001_023.msk 6.52727453611393E-02
0054_0003_023.msk 19.4206162095733
0055_0000_023.msk 3.78575920143461
0056_0003_023.msk 218.038033121402
0057_0003_023.msk 1.09445579925511
0058_0000_023.msk 1.48135816309896
0059_0001_023.msk 0.147877857617597
0060_0001_023.msk 0.294045537957355
0061_0000_023.msk 134.354554757157
0062_0003_023.msk 0.514168767164516
0063_0003_023.msk 3.05458975960272
0064_0001_023.msk 6.08798224295549
0065_0001_023.msk 6.3147506364195
0066_0000_023.msk 2.18249128324743
0067_0000_023.msk 58.7978776519569
0068_0003_023.msk 20.4921087593895
254869317Quote:
Originally Posted by NotLKH
713542896
869371425
972458631
638127954
541693278
187934562
495216783
326785149
Time taken: 1.06426517520869 Seconds
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???
:confused:
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!
:wave:
-Lou