More sudokus! These include the hardest I've found so far. Beware the minimal sudokus!
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.
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.
That's how we learn it in Greece The "." isn't needed. Or use the dot if you want in the Format function... Doesn't make much difference...
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 ","
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.
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...
Hey Merri, can you define what a "minimum sudoku" is? How is it different than a normal one?
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.
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.
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 !
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:
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.
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
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 :
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 ?
Last edited by dukuso; Aug 14th, 2005 at 09:29 AM.
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.
I'm taking the first puzzle from http://magictour.free.fr/top100I can't understand why it's so easy to solve for Merri....The point is, that this 24-clue sudoku was no easier for my solver
than the original 17-clue-puzzle.
Clear now ?
The point is, that this 24-clue sudoku was no easier for my solver than the original 17-clue-puzzle.
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.
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.
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.
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.
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)
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.
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.
EDIT: Can I steal your icon? I think I'll resource hack it, unless you don't want me to.
Last edited by eyeRmonkey; Aug 15th, 2005 at 12:48 PM.
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 ).
Originally Posted by Merri
Reply With Quote
The "." isn't needed. Or use the dot if you want in the Format function... Doesn't make much difference...
