Printable View
Ok, I used the program I made to fix dukuso's puzzles and modified it a little to fix merri's "minimum sudokus." I attached them here.Quote:
Originally Posted by Merri
Note: the first (original) file (000.txt) was in a different format then the rest (and caused my program to not output the right type of file) so there might be others in the group, if so please let me know.
Now I have choices to make? Thats no good. I need to be told exactly what to do. I have no decision making capacity. I guess I will just use the format function then replace "." with ","Quote:
Originally Posted by manavo11
I just needed to clear up that the , represented the decimal point in seconds and that we weren't talking about miliseconds or 1000 seconds or something like that.
I specified in the rules that the "," is the decimal point character :)
lol merri :lol:Quote:
Originally Posted by Merri
Thanks. ;)Quote:
Originally Posted by manavo11
I'll stop being dumb now. :D
Hey Merri, can you define what a "minimum sudoku" is? How is it different than a normal one?
maybe we should stop measuring time in ms...
Let 1 Merri (mr) be the number of CPU-cycles needed by Merri's solver
to solve one of the easy sudokus. (about 72000)
My solver takes about 4mr for a msk_001-sudoku and 20mr for a top100-sudoku.
My exact-cover matrix has 729*324 (=placements*constraints) cells,
that's 3.3mr, but the matrix is sparse, so I only store the
addresses of the nonzero entries which is 2*0.04mr .
Would I process this list just only for each of the about 55 placements
of a sudoku-clue with one examination per CPU-cycle, then I would already
need 4.4mr, so there must be a better method.
I guess, if your solver takes 10mr for an average sudoku,
that's already pretty good...
It has only 17 starting values, yet the puzzle has only one solution. There is no known single solution puzzle with only 16 given values. If we put it straight, I think some of this kind of puzzles cause the most work for a backtracker.Quote:
Originally Posted by eyeRmonkey
the number of clues has not been a useful measure for hardness.
In fact most of the 17-clue-puzzles from Gordon Royle's webpage
were rather easy to solve.
Yes, most of course. But some of them are the hardest my solver has got its hands into, thus there is some point behind my words.
you're right. I never noticed this. Distribution of clues in my 100 hardest:
10,0,1,1,65,0,2,9,5,4,1,1 counts for 17,18,..,28 clues.
Even my 3 top-hardest are 17-clue-puzzles.
I'll ask Gordon for his other 17-clue sudokus, he has about 5000 of them !
The interesting part being: I thought some of them must be the hardest when I first read about them :)
that's what the creator thought too. But it soon turned out that they were not, see:
http://www.sudoku.com/forums/viewtop...r=asc&start=15
having this in mind, I didn't very much check which of these finally made their
way into my top100 list.
In the hardest 17-puzzle, you can fill in some numbers and it's still hard:
.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.
lol.
The only way that is a seventeen is if you think .18...73. is a 2 entry! But it really is a 4 entry.
.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.
That is a 24 entry.
BTW, I've been marking my sol & msk files since the getgo with the #Entries as the first number in the filename.
:wave:
-Lou
The discussion you pointed to... he clearly haven't thought in that point that there are always easy ones and hard ones. Majority of the puzzles are always easy, otherwise it wouldn't be hard to find the hard ones. So majority with 17 clues are easy, but the select few among them are very hard.
Btw, that one isn't hard. Atleast for my solver.
Something Else: re-read his post :)
"In the hardest 17-puzzle, you can fill in some numbers and it's still hard:"
and then its followed with a puzzle with 24 entries.
Its NOT sayingthat its a 17 entry WITH some cells solved, its implying that if you look at this 17 entry, you'll find some numbers to fill in.
If they were filled in, how would you know what numbers were easily filled in?
Or is this not what you're talking about?
:wave:
-Lou
I'm saying that, atleast to me, he is clearly stating he is giving a 17 puzzle with additional numbers included (which is different thing than solved) and claiming it still is hard with those numbers included.
In the other hand... it is quite hard to follow what dukuso is saying or meaning with what he says every now and then :D
I'm taking the first puzzle from http://magictour.free.fr/top100
which is by far the hardest for my solver which I ever found,
even when considering 1000 random equivalence transformations
of that sudoku :
.18...7.....3..2...7...........71...6......4.3........4..5....3.2..8...........6.
.18...7..
...3..2..
.7.......
....71...
6......4.
3........
4..5....3
.2..8....
.......6.
I can't understand why it's so easy to solve for Merri.
I swapped the 1s and 3s in that sudoku, since one of my programs solves for
the one-digit. You can fill in all 9 threes in above sudoku by relatively simple logic.
These then are painted as ones and vice versa. Plus one seven could also be filled in.
That was the 24-clue-sudoku which I posted.
The point is, that this 24-clue sudoku was no easier for my solver
than the original 17-clue-puzzle.
Clear now ?
Especially if you notice that if you count the number of run on number groups per line, you DO have 17 such groups:
.18...73.
...3.72..
.73......
....713..
6...3..4.
3........
4..5....3
.2..83...
.3.....6.
Line 1: 18, 73 : 2 run on groups of numbers
Line 2: 3, 72 : 2 RunOn's
Line 3: 73 : 1 RunOn
Line 4: 713 : 1
Line 5: 6,3,4 : 3
Line 6: 3 : 1
Line 7: 4,5,3 : 3
Line 8: 2, 83 : 2
Line 9: 3, 6 : 2
So, # RunOn's = 2 + 2 + 1 + 1 + 3 + 1 + 3 + 2 + 2 = 17
Which is coincidentally the number of the order that he claims it to be.
So, if he did start with a true 17, ie.. 17 single hints given,
And then added his fillins, resulting in 24 revealed cells, somehow it ended up with 17 runon groups of numbers, which led me to think that he was counting the groups instead of the individual numbers themselves.
I wonder what it looked like before he added his fillins, if this is the case.
:wave:
-Lou
Thanks!Quote:
Originally Posted by dukuso
-Lou
Maybe because the result is different. The numbers 1 and 3 switch their place on several occasions. The 24 clue one is a bit harder for my solver as well. But since the numbers switch their place in the solution, it is a completely different sudoku.Quote:
Originally Posted by dukuso
Ok, not to change the subject, buuuuut...
I was wondering about when the timer should start. Here me out:
Everyone has to store the possiblities that each cell could be in some manner. Lets assume they use a string to do this (although I hope no one is). The string would originally be "123456789" for each cell.
Now lets assume that the actual value of each cell is stored in a different (byte?) array.
When the original board is loaded into the solver the program sets the byte array to the given numbers.
Now the time starts
Now the solver takes any cell that was originally solved for and removes the rest of the possiblites from the string for that cell.
(Now the solver does everything else.)
Time stops.
My questions is if the step in bold should be included in timing or not. Because if someone did is similarly, but instead automatically eliminated all the possibilities in the string AND set the byte array before the time started that wouldn't necessarily be against the rules.
Did that make sense?
I know not everyone will do theirs in a manner similar to this, but I think some people will.
As told before, I have a function called PrepareSudoku. What it actually does is, besides initializing my optimization arrays (only in first call), convert the given array into the internal format I use to process in. However, it does not do any real calculation. It only fills the array and counts how many solved cells there are. It does not work out any possibles. Thus all the real work is done by the solver, which I time. PrepareSudoku is not included in timing.
Removing possibles should be counted in the timing, because that is what the whole thing is about. But I think setting the sudoku can be counted as initialization, which is not required to be timed (though in the other hand it wouldn't make a big difference).
That is how I have it now Merri (the way you just mentioned).
I was just thinking that if someone took a class approach then maybe sudoku.setval(cellnumber, value) might automatically remove all other possibles. What I mean is that when they are loading the original puzzle, their class will do work (untimed) that out methods time. They would have a leg up on us, just by design.
True, but doing it that way is slow, so there isn't much to complain :) Though, that would be solving the puzzle, because it is using a solving method.
Yeah, plus its a waste... nevermind. I think I won't finish that because I would be giving away more hints (not that I have that many to give).
I wrote that my top1-example is still hard for my solver when
I rotate and permute the sudoku without destroying its structure and the
number of solutions.
And I wrote that I don't understand why it's so easy for Merri's solver.
Now I permuted the order of the constraints and placements,
and that did indeed make my solver solve it much faster.
(but without being faster on the list as a whole)
So, what was happening ? Presumably I went into a
large region of the search tree with no solution
and lots of useless branches, while Merri avoided this region
either by mere luck or by lookahead-prediction.
But such things happen rarely and it might be better to
tolerate it rather than to waste time on predicting how to
avoid it ?!?
I know, there are also sudokus which my program solves much
faster than Merri's - it would help, if we were able to
detect which problems are best solved by which method.
It makes me also believe that further optimizations
in the algorithm are possible....
can't we forget about the contest and work together on the
best program in teamwork instead ?
I mean, it's better to exchange ideas right now,
since after the contest people will be no longer interested to
improve the programs.
Gordon Royle kindly uploaded all his 17-clue-puzzles !
4.6sec*GHz for these 7600:
http://www.csse.uwa.edu.au/~gordon/sudoku17
I don't think so. Entered code will be available after the contest ends. It will be a learning experience for everyone, and things can continue after it ends. The thread was started before the contest was even brought up.
wouldn't that be a cool contest, if people would collaborate to find
the best program and everyone is _somehow_ scored by the
"value" of her contribution ?
Well, only 11 days before the contest is over. I make my own code public right away after the deadline, atleast elsewhere if not here. I'm actually expanding my program in other ways, I have made a multifile converter for an example (still a bit buggy though). Should next make the required feature for the contest, I still don't save the data in the required way...
My problem is starting to be that there isn't much to improve. The list of includeable logics is pretty short... probably the only one I can do to speed things up is Nishio. Probably I'll continue to do some work even after the contest, if my interest just keeps going on.
The contribution contest would be pretty hard to rate. It sounds nice as an idea, but it doesn't work well in practise. Atleast I think it is unlikely to be so.
Her contribution sounds a bit weird btw :D
Here are the 7611 17 clues in the contest format :) Though... the ZIP file contains a 7-zip file. I had to do this because for some reason the ZIP file became over 1 MB in size, even though the files it stored took only about 300 kB compressed! So, I decided to use the best format I know: ending result is 129 kB. So... curse the ZIP.
How to uncompress:
- extract clues.7z.txt from the ZIP file
- rename the file to clues.7z
- extract in a program that can open 7z files (IZarc is a good one)
Oh... and solved them all in ~1710 ms.
But they're in msk format already in my post?
Ignore me. I have edited that reply 5 times then re-read yours and notice I am still worng. Let me edit it again.
EDIT: Ok, I deleted that reply. Now, what I was trying to say is can you upload them in separate .zip's?
In the other hand... you could always get my converter program to change sudoku files from a format to another. You can get that list for example, save it as a text file and then convert that "batch" file to separate sudokus. The converter can save five different file formats and read several others.
I hate silly TYPOS!
Nice one. Yours is much more flexible than mine. I had to modify mine every time I was dealing with a different format.
EDIT: MERRI!!! I think I am going to wet myself. That is beautiful! So clean... SO FAST!! Gimme gimme code! GIMME! ... Ok, I'm done. Deep breaths. I'm better now. :wave:
EDIT: Can I steal your icon? I think I'll resource hack it, unless you don't want me to.
You shouldn't steal my icon! It is a copyrighted work afterall! ;) I'll sue you!
Code will come in... what, 11 days?
Hey lurkers, ;) about 3secs for those 7611 puzzles. I won't do much more work on this, so I'll be posting in a few days because my girlfriend is pressuring me to take vacations on something called the real world - we'll probably go to the place on attached pics (try not to cry too much everyone :D ).
Well, as your wordings in each of your posts say... bit happens. Try to survive!