I mean, how do you verify that they have a unique solution ?
I somewhat doubt that he is. It's not too hard to make a program that throws 1-9 in a few cells, but making one that generates puzzles with unique soultions is a little more tough.
I think that I've read that you can use the four corners of a grid, to substiitute 4 different ways to solve any puzzle. This ignores the center cell also.
I have some good news for you all. At some point of optimizing, my code has broken. So, there are some puzzles that fail to solve. You lot must be happy now, I don't know if I have the time to figure out the bug.
ahh, why should we be happy ? Because that increases the chances of others
to win ? Some wise philosoph said: with sudoku not the solution counts,
but the path which you take. (or was it a newpaper journalist ? , well,
could have been Konfuzius too)
If it took you weeks to find a puzzle which wasn't solved, then
the judges won't probably have one for the contest.
No no, there are even basic ones that don't get solved. I didn't check for valid solutions for about a week (which was a bit silly of me, but I were a bit tired many of the times I coded), and now I've changed the code so much that it is very hard to find the error. I've tracked it as far as to the backtracker code itself, there seems to be no error in the logics. In worst case I have to rewrite the whole backtracker. Sounds nice, huh?
Whew. Luckily I had made a solution counter, which had almost the exact same code I happened to have a few days ago. So, now I can try to apply the new optimizations again and see when the error comes in. The latest optimization I did was pretty effective...
Edit Darn. Still not wholly clear. Debug, debug... Finally! Another error found in the naked subset code.
sounds as if your solver might suffer from complicatedness...
while you're there, could you measure how many % speedincrease these
"naked subsets" gave you ? Is it worth the trouble ?
When doing the 7611 minimal sudokus, it gave about 20% speed increase while retaining most sudokus valid. Note that it didn't take too long to fix the code, I just had to push time from something else (sorry Something Else for doing that). Though I need more time to analyze why the subset code doesn't work as it should.
Heh, I understand, I also push time from myself every now and then.
I Just had a bout of optimizationitus myself. I created a total rewrite of my generators solver, and It looks really good, although I havn't written any backtracking into it yet. I've been trying to get it to solve all my submissions without any backtracking. It solves all but the final 15 of my last submissions. I wrote a procedure that I thought was a generic version of several other strategies. But it, for some reason, couldn't solve 1 extra submission. In actuality, it made it impossible, blanking out all possibles for 1 cell and 1 cell only!!! I debugged it, and it worked in tandom with all the other procedures. But, commenting out the ones I thought it replaced, I saw it was lacking something. So, I'll comment it out, since it doesn't do anything extra even if I keep it.
I'm just going to go back to my old code, put a counter in a couple of spots, and tweak my generator a hair.
I'm done, finished, finito.
I have submitted my proggy and that's it. Am i the first?
Maybe I get some sleep again at night now, lovely.
Good luck to all of ya.
I'm done, finished, finito.
I have submitted my proggy and that's it. Am i the first?
Maybe I get some sleep again at night now, lovely.
Good luck to all of ya.
You're the 2nd Good luck to you too
Has someone helped you? Then you can Rate their helpful post.
not that it were so important for me, but just assume that
I wanted to submit something. I have a C-program which reads
sudokus from a file and solves them, So how much work is it
to meet the contest requirements ?
what's "C#" ? How to make it "callable", how to prompt, etc.
hehe i have made a checker not a solver. hehe guess that doesn't count for the contest.. oh well i am trying to create a new theory for solving sudoku puzzles i just have to make something out of my theory.. will the codes be posted? I can't wait to see those codes..
dukuso: C# is Microsoft's somewhat new language, which came with .NET when it appeared a few years ago. You can compile C# programs for free if you get the .NET framework.
For the requirements, there is another thread about it which should be rather straightforward.
C# is close to C++ in syntax, though it is more managed and it is easier to add GUI to it. I don't know much else about it. C# can be compiled to any environment that has a .NET compiler and framework available (Linux included).
oh, I thought it were something like C++ or such, an extension of C.
I guess, I'm out then. Maybe I shouldn't have come here in the first place.?!
Hmm, shall I post my link to another paper as goodbye ?
I know, you're eager to read these papers...
Why are you out of here?
We have a C and C++ area,
and if you know those, go ahead and code an entry with it!
Heck! We have assembly here! Code it in assembly!
Why are you out of here?
We have a C and C++ area,
and if you know those, go ahead and code an entry with it!
Heck! We have assembly here! Code it in assembly!
-Lou
who is "we" ?
where is that area ?
Are you saying, there is(or will be) a sudoku-programming contest in C ?
Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?
OK, I won't post the link to the announced paper.
Just a quote:
"A new strategy to select the next variable and the value to branch on
for Latin square problems was proposed in [4](2003) . This strategy clearly outperforms all the previous ones that have been tested.It consists of
selecting the variable with the minimum domain size and then select the value
which occurs the fewest times in the domains of the variables of the rows
and the columns of the selected variable.We have improved this strategy...."
Are you saying, there is(or will be) a sudoku-programming contest in C ?
I'm sure if you asked TPTB {ie.. the Mod of the contest area}, he might accept your C entry, and compete it against every single one of the other C entries. Of course, I have no say in this matter. But if he DOES take it, You'll probably be the Best C entry for this contest to date!
Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?
I have no idea if they've become any harder. I added a counter to weight the pattern development with iteration counts on the several strategies in my generator. Let me know if I broke it.
NotLKH: this is your fifth set this far, not fourth Unless I'm very badly mistaken...
Anyways, still relatively easy. 25 ms for 314 files = 0,08 ms per file. Compared to minimum set of 453 files: 103 ms; 0,22 ms per file. If you'd get rid of the all-too-easy ones, then your puzzles would start to compare.
I make a "human difficulty rating" to my code after the contest is over, so then we can more clearly see which puzzles are hard and which are not. Computer speed isn't the only measure one should take into account. I already have an idea on how to make it.
It would be, dukuso already mentioned mine is faster Aren't we keeping it separate anyways or will all be in the same category and compared against eachother?
The 3 categories I mentioned are going to be marked seperately. I meant that C doesn't fit in any of the 3 categories so I don't know if it would be fair to compare it with the entries of any of the 3 categories. Better now?
Has someone helped you? Then you can Rate their helpful post.
Here's the last that I'll post before the contest. Any feedback would be nice!
If you've wondered, the followin is what the numbers mean in the sol file name.
Given a filename like : 026_0674_0015-000019__Solved.sol
The first Set, 3 digits, indicates the number of exposed cells in the initial puzzle.
The second set, 4 digits, is the sequence index it was generated at.
The third set, 4 digits, is a binary composite:
A Zero means it only used naked and hidden singles
1 s: If it detected a number in a shared set of 3 cells at the intersection of a row/col and a 3x3 square that wasn't anywhere else in the row/col, but was in multiple other cells in the SQUARE, it was removed from the other multiple cells.
2: Same as 1, except the other way
4: Naked pairs were detected and processed
8: Hidden pairs were detected and processed
16: Naked and/or hidden trips were detected and processed
32: If I had it activated, it would mean naked/hidden Quads were detected and processed
64: This means, if after iterating thru all the first strategies until exhausted, and the puzzle still wasn't solved, then it went into the full iterate all posibles mode, until it found a solution. In my generator, it also counts all the solutions possible, and any that had more than 1 solution was considered a failure. None of these really should have more than 1 solution.
The 4th set, 6 digits, meant 2 possible things:
If the 3rd set < 64, then it is the count of how many times it looped adding sets of cells with only 1 possible into the solution matrix
if the third set was >= 64, then it indicates how many total possibles were available to all the unassigned cells, before it went into the 64 mode. Then I added 100.
This 4th number was what I used to filter on my generator as I tested removing revealed cells from an initiating set of succesful revealed cells.
Lets say, if I had a msk set of 26 cells that led to a solution, I would build and test 26 subsets, each of the the 26 combinations of 25 cells of this msk set, removing 1 of each 26 revealed cells. I would note which subset worked, and I would select the one with the largest 4th number as the new msk to test.
As I worked down, once I reached a set that had no good subsets, then that is the one that I'd output as a new msk entry.
Attached is my newest set, using the strategies as I've explained them, above.
-Lou
Last edited by NotLKH; Aug 24th, 2005 at 06:57 AM.
Finally submitted the code. Did some final changes to actually meet the contest requirements... noticed the required output timings file format just when doing last time reading of the rules.
I think I joined the contest a little too late. I am just now to the point of optimizing things (after finishing my backtracker). Each optimization I do breaks the whole solver for a while (until I can work out all the bugs), so I will be lucky to get 0 based arrays and 1-D arrays done by friday.
Can I turn it in at midnight on friday (my time zone)?
Last edited by eyeRmonkey; Aug 25th, 2005 at 12:09 PM.
Reason: spelling
You're slow. You get eaten. That's the rule of the jungle.
You ought to be a monkey so code like one! Code like mad!
Easier said than done, but I'm done already so there shouldn't be much to complain about Oh, btw, I tried converting my solver to do 5 x 5 puzzle... it would be great, if all my optimization arrays worked in that mode, they take almost 100 MB unless I counted wrong... my computer just swaps when I start the project Don't know if it solves, this far I've had some typos... too many of them. Subscript out of range etc.
Well, I got the base 0 arrays working and got a slight speed increase and 1-D arrays are coming along nicely (although I am not far enough to get to the debugging part yet and I think they might turn out to be hell).
I have at least 10 other optimizations to do and I know I won't have time for all of them. The only reason I am getting so much done today is because my girlfriend is busy for the first day in the last 2 weeks and we aren't hanging out today (well, we are, but not until later tonight).
GMT sounds fair enough manavo.
/me walks over to google to find a time convert
EDIT: Crap! Thats 7AM friday for me. I won't even be up by then. I guess I can stay up all night thursday and be useless. Fun fun!
Last edited by eyeRmonkey; Aug 24th, 2005 at 08:52 PM.