Contest 6 - Sudoku solver - Discussion - Page 8-VBForums

# Thread: Contest 6 - Sudoku solver - Discussion

1. ## Re: Contest 6 - Sudoku solver - Discussion

I mean, how do you verify that they have a unique solution ?

2. ## Re: Contest 6 - Sudoku solver - Discussion

1 week left Start wrapping them up slowly

3. ## Re: Contest 6 - Sudoku solver - Discussion

Originally Posted by dukuso
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.

4. ## Re: Contest 6 - Sudoku solver - Discussion

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.

5. ## Re: Contest 6 - Sudoku solver - Discussion

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.

6. ## Re: Contest 6 - Sudoku solver - Discussion

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.

7. ## Re: Contest 6 - Sudoku solver - Discussion

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.

8. ## Re: Contest 6 - Sudoku solver - Discussion

just take your program from one week ago. Maybe the one you posted ?

9. ## Re: Contest 6 - Sudoku solver - Discussion

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.

10. ## Re: Contest 6 - Sudoku solver - Discussion

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 ?

11. ## Re: Contest 6 - Sudoku solver - Discussion

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.

12. ## Re: Contest 6 - Sudoku solver - Discussion

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.

-Lou

13. ## Re: Contest 6 - Sudoku solver - Discussion

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.

14. ## Re: Contest 6 - Sudoku solver - Discussion

Originally Posted by Brick1
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

15. ## Re: Contest 6 - Sudoku solver - Discussion

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.

16. ## Re: Contest 6 - Sudoku solver - Discussion

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..

17. ## Re: Contest 6 - Sudoku solver - Discussion

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.

18. ## Re: Contest 6 - Sudoku solver - Discussion

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...

19. ## Re: Contest 6 - Sudoku solver - Discussion

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).

20. ## Re: Contest 6 - Sudoku solver - Discussion

Originally Posted by dukuso
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!

-Lou

21. ## Re: Contest 6 - Sudoku solver - Discussion

Can I code one in FreeBASIC?

22. ## Re: Contest 6 - Sudoku solver - Discussion

Originally Posted by Something Else
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 ?

23. ## Re: Contest 6 - Sudoku solver - Discussion

Originally Posted by Merri
Can I code one in FreeBASIC?
could you translate that teethy smiley into English ?
you're going to bite someone ?

24. ## Re: Contest 6 - Sudoku solver - Discussion

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...."

25. ## Re: Contest 6 - Sudoku solver - Discussion

Originally Posted by dukuso
who is "we" ?
"We" are you and me, everyone who particibates in VBForums.
where is that area ?
http://www.vbforums.com/forumdisplay.php?f=23

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 ?
heh! Show Off!

-Lou

26. ## Re: Contest 6 - Sudoku solver - Discussion

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

27. ## Re: Contest 6 - Sudoku solver - Discussion

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.

28. ## Re: Contest 6 - Sudoku solver - Discussion

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.

-Lou

29. ## Re: Contest 6 - Sudoku solver - Discussion

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...

30. ## Re: Contest 6 - Sudoku solver - Discussion

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?

31. ## Re: Contest 6 - Sudoku solver - Discussion

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?

32. ## Re: Contest 6 - Sudoku solver - Discussion

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:
1. A Zero means it only used naked and hidden singles
2. 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.
3. 2: Same as 1, except the other way
4. 4: Naked pairs were detected and processed
5. 8: Hidden pairs were detected and processed
6. 16: Naked and/or hidden trips were detected and processed
7. 32: If I had it activated, it would mean naked/hidden Quads were detected and processed
8. 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:
1. 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
2. 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

33. ## Re: Contest 6 - Sudoku solver - Discussion

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!

34. ## Re: Contest 6 - Sudoku solver - Discussion

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)?

35. ## Re: Contest 6 - Sudoku solver - Discussion

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.

36. ## Re: Contest 6 - Sudoku solver - Discussion

I'll accept entries submitted till midnight Friday GMT. It's the easiest to keep track

37. ## Re: Contest 6 - Sudoku solver - Discussion

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!

38. ## Re: Contest 6 - Sudoku solver - Discussion

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.

39. ## Re: Contest 6 - Sudoku solver - Discussion

I mean the night from Friday to Saturday midnight...

40. ## Re: Contest 6 - Sudoku solver - Discussion

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured