I mean, how do you verify that they have a unique solution ?
Printable View
I mean, how do you verify that they have a unique solution ?
1 week left :) Start wrapping them up slowly :)
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.Quote:
Originally Posted by dukuso
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?
Every 1/50 puzzle seems to cause problems.
just take your program from one week ago. Maybe the one you posted ?
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.
:wave:
-Lou
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 :)Quote:
Originally Posted by Brick1
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.. :D
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.
titan7262: yes, the codes will be available.
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...
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).
Why are you out of here?Quote:
Originally Posted by dukuso
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!
:wave:
-Lou
Can I code one in FreeBASIC? :D
Quote:
Originally Posted by Something Else
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 ?
could you translate that teethy smiley into English ?Quote:
Originally Posted by Merri
you're going to bite someone ?
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...."
"We" are you and me, everyone who particibates in VBForums.Quote:
Originally Posted by dukuso
http://www.vbforums.com/forumdisplay.php?f=23Quote:
where is that area ?
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!Quote:
Are you saying, there is(or will be) a sudoku-programming contest in C ?
heh! Show Off!Quote:
Yes, I think I could do it in assembly, but why should I rewrite it,
when it already works in C ?
:wave:
-Lou
Heres some more patterns.
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.
-Thanks
-Lou
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.
I'd like to, hence My Ratings.
I just need feedback to determine what the ratings signifies in difficulty.
If you can list each ones speed, that'd help me determine whats what.
:wave:
-Lou
The contest is for VB6, VB.Net and C#. I don't really know if it would be fair to compare a C entry with any of those...
It would be, dukuso already mentioned mine is faster :D 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? :)
2 More days!
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.
:wave:
-Lou
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.
Happy benchmarking!
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)?
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 :D 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 :D Don't know if it solves, this far I've had some typos... too many of them. Subscript out of range etc.
I'll accept entries submitted till midnight Friday GMT. It's the easiest to keep track :)
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!
You sure you counted to 23:59 of Friday and not 0:00 of Friday? Afaik you have 30 hours to go at the moment.
I mean the night from Friday to Saturday midnight...
Thats it. I have submitted my contribution. I don't stand a chance agains Merri's solver ;) , but I'll be happy as long as I don't loose.
The most important thing is to participate, not to win... I guess :rolleyes: