Contest 6 - Sudoku solver - Discussion

Quote:

---

Originally Posted by Merri

You shouldn't steal my icon! It is a copyrighted work afterall! ;) I'll sue you!

Code will come in... what, 11 days?

---

Oh, I didn't know you made the icon. In that case, I will use one that doesn't relate to sudoku in ANY way. ;)

BTW, I scrapped my entire project and created a new one that I'm sure will beat everyone's entry. I'll only ask manavo11 to save everyone's puzzle solutions to disk and run my code last.

VB Code:

Private Sub cmdWinTheContest_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles cmdWinTheContest.Click
 
        Dim SW As New StopWatch
 
        Dim files() As String = System.IO.Directory.GetFiles(mskDir, "*.sol.*")
        For i As Integer = 0 To files.GetUpperBound(0)
            If files(i).IndexOf("merri") > -1 Then
                System.IO.File.Move(files(i), files(i).Replace("merri", "ntg"))
            Else
                System.IO.File.Delete(files(i))
            End If
        Next
 
        MessageBox.Show("Time=" + (SW.Peek() / 10).ToString("N8") + " - beat THAT!", "I win", MessageBoxButtons.OK)
 
        SW = Nothing
 
    End Sub

:lol: :lol: :lol:

Nice one ntg. I had been wondering if someone would try to sneak something like that into their code to try to cheat, but I doubt it.

At this point I can only say: VB.NET looks horrible! Good thing I don't need to do those complicated and long lines...

Wonder if my solver is faster than just moving files... atleast on my computer it took much longer creating the files than solving them :D

Quote:

---

Originally Posted by ntg

BTW, I scrapped my entire project and created a new one that I'm sure will beat everyone's entry. I'll only ask manavo11 to save everyone's puzzle solutions to disk and run my code last.

---

What makes you think you're so special? :p :D j/k

I'm not sure if this was ever clarified, but are VB.net and VB6 going to be judged together or separately?

Separately!

Hey, 10 days still to go... I could take this VB2005 and make a VB.NET2 version of my code, too. I'm sure everyone would appreciate that! :D

/slap merri

I could go make a javascript version of my code seeing as how that is the only other language that I know (unless you count the 1 line of C++ code I can write). I'm sure I would win in that catagory. :)

Someone say something. I check this thread 20 times a day it seems. I'm getting sick of seeing my reply as the last one. ;)

How is the code going? Someone want to post times (not that it matters all that much). How about you just post your entire project, then I can combine all you good ideas with my project. Sounds good, right? :D

is this the first and only sudoku programming contest or are others known ?
I found with google, that University of Hongkong is doing something...

I'd hardly come to the idea to split a file with 7611 lines into
7611 files... no wonder it's getting slow.

Yup, 7611 files. It is insane, but I'd have to recode my program to be able to test a single batch file. And I guess the same applies to others. Things that are on the "features to be added" list.

My program has a slowdown in showing results, because it uses a listbox to sort the results. Not so fast thing to do. I guess that's what I fix next.

BTW, merri, which tab control is that you are using on your program?

Custom user control.

Did you make it?

Wanna hook me up?

You'll find it at PSC ;) Not made by me.

Well could you at least give me some search terms? :)

Here it could be tabstrip merri. Sheesh! You ought to know I share EVERYTHING here! :D

Why would it be tabstrip merri if you didn't make it? Whatever... I'll go search. ;)

Yeah, but I said to search here :D

(making your life hard today, but probably only because I'm not having easy time myself; or then I'm just evil)

I'd say your just evil. ;)

I found a crap load of other cool stuff on PSC though. I have never had the time to browse for random stuff. Now I am gonna have 20 add-ins that I never use and 1000 more user controls that I never use. But who cares! They're cool! :D

Atleast my avatar doesn't look like evil? But you have to say: my future homepage design is evil. I say, Evil.

Off the topic. Back to topic! You're really trying to make an exact copy of my solver, aren't you? ;)

No, I was -- Ok well maybe.

Not really. I kinda just wanted a better tabstrip control for future use. But like I said, I can't get all your good ideas out of my head. :D I'll try not to copy it too bad. ;)

:)

PS - That site looks nice, but I can't read it. Is it about small fluffy creatures? Or is it a blog?

Just a homepage in general, no blog atm. Adding some other stuff there. I'll make some English content as well, I guess. Though you're right: small fluffy creature describes me well. I just miss the fluffy part. Except from my legs, but that's not really the point here.

PSC controls are nice, but most of them are pretty badly done. Atleast almost each time I look into source I cry in pain.

Good thing I don't have the time to code all my ideas, otherwise you'd have plenty to copy! :D

:lol:

I think I will spend some timing looking around PSC for a grid control to do a project that I gave up on because I didn't feel like messing around with a flexgrid. I know, I know... I'm lazy. :D

You must be running out of out optimizations Merri, you havn't posted any times lately. Or maybe you are just "lurking". But we all know by now that you can't hold it in when you cut your times in half AGAIN.

Nah, there isn't much to optimize. I did try a few things, but they just lenghtened the processing time for most sudokus. There is a limit for everything blah blah blah. And I'm not that interested to start benchmarking single parts of code trying to see which things work the fastest and in which order the code should be :D

Though really, I've had some bad days now. Was depressed a few years ago and it is easy to get into that mood every once in a while...

Yeah, I have been curious what order I should put my logic rules in too.

Sorry to hear about the depression. Were always here for you though buddy. :)

Winning the sudoku contest should boost your mood a little though. ;)

Like if I had a proper job :/ Nope, I have never got a real salary to my hands.

http://www.icparc.ic.ac.uk/~hs/sudoku.pdf

Don't make me read it mommy! I DON' WANNA!

J/K. I remember wiki mentioned constraint programming, I guess I should read and maybe I will shave some time of my results.

I added a new logic, Nishio to my program. No much gain: results went down by ~0.2 ms by avarage for a harder puzzle.

I don't know, whether this could be useful for your
sudoku-specific,optimized versions - but here is,
what the author of that paper just wrote:

>Dear Guenter,
>I'd be happy for you to redistribute the discussion.
>
>From a constraint programming point of view, I think
>the fastest solver would be based on a bounds
>consistent alldifferent and a depth-first search
>routine which selects the most constrained variable
>first. If the inverse constraint is coded effectively,
>then a channeling model (with another set of variables
>for the values in each alldifferent) could be even
>better. My hyper arc-consistent inverse constraint is
>too simple to make this competitive.
>My initial interest in the problem was not to solve
>the puzzles quickly, but to see how much can be done
>without resorting to search. There clearly is room for
>further improvements in the constraint reasoning
>concerning the interaction of the row/column and block
>constraints.
>
>Best regards
>
>Helmut

Could that be written in Finnish... er, I mean, English? ;) I have to admit, my problem is that I don't understand theoretical text very well. I understand the code much better than the text. In the other hand, reading code and understanding it from there is slow.

All the words that make no sense to me:
- constraint (dictionary translates this as "forced", which doesn't really help)
- alldifferent (understand the words as separate words, but can't figure out the meaning)
- depth-first (again, familiar words used in a completely bizarre way)
- inverse contraint (because I don't understand constraint)
- channeling model (familiar words...)
- hyper arc-consistent inverse contraint (familiar words...)

What I'm trying to say here... all this stuff could be explained in a way it can be understood by someone who doesn't know all the nice terms. It requires more words and probably even sentences, but it really would help if the language was understandable. Using these words limits the amount of people who can get into it. I place a bet most programmers here aren't able to follow the text smoothly.

I couldn't understand it either Merri. I had the same problem with all the words you listed.

On a side note I FINALLY got my backtracker working and I am VERY VERY happy about it.

Now I can finally get around to doing all those optimizations I have been waiting on. I can also design a nice GUI for my program (my proggie still doesn't allow benchmarking and I need to add that so I can test out the speeds of things).

My solver now meets the contest requirements (finally). I have too much unrequired extra stuff, but I guess that isn't against the rules :D

>Could that be written in Finnish... er, I mean, English?
>I have to admit, my problem is that I don't understand
>theoretical text very well. I understand the code much
>better than the text. In the other hand, reading code
>and understanding it from there is slow.
>
>All the words that make no sense to me:
>- constraint (dictionary translates this as "forced",
> which doesn't really help)

324 constraints in sudoku: exactly one symbol per cell, exacly one cell
per row and symbol,exactly one cell per symbol and column,
exactly one cell per block and symbol.
You'd probably call them "naked or hidden singles" - like if
these were easier to understand ;-)

>- alldifferent (understand the words as separate words, but can't
> figure out the meaning)

presumably because _all_ symbols in a row,column,block are _different_
Apparantly there are similar problems with other sorts
of constraints. So, if we are only interested in sudoku,
we can ignore that "alldifferent".
http://citeseer.ifi.unizh.ch/cache/p...ldifferent.pdf

>- depth-first (again, familiar words used in a completely bizarre way)

never heard about "depth-first-search" ?
http://en.wikipedia.org/wiki/Depth_first_search

>- inverse contraint (because I don't understand constraint)
>- channeling model (familiar words...)
>- hyper arc-consistent inverse contraint (familiar words...)

I don't know about these either. But presumably you could put
these as keywords into a search-engine and find something.
He is preparing another paper for a conference in Oct. in Spain
with timings etc.
Seems that the only really efficient method he tested was "shaving".

>What I'm trying to say here... all this stuff could be explained
>in a way it can be understood by someone who doesn't know all the
>nice terms. It requires more words and probably even sentences,
>but it really would help if the language was understandable.

this was probably done elsewhere. Usually a survey or an introductory
text is given in the references. This could be his first reference:
Apt,K.: Principles of constraint programming...
I don't know whether it's suitable for those who never heard about it.
I will ask him for a reference to an introduction into the
matter for beginners.

>Using these words limits the amount of people who can get into it.

yes. It's addressed to these experts from the workshop etc.

>I place a bet most programmers here aren't able to follow
>the text smoothly.

you still get an idea, that/how your work here relates to
real problems where much research is spent.
It's just a special case of constraint programming !
These constraint-programming programs can be used to
solve sudoku.
Whether they are faster than your sudoku-specific optimized
programs - that's another question.



BTW. the forum-page is awfully slow loading !

Guenter.

ummm.. i have made a generator.. i have also made a SUDOKU checker.. the thing is.. i can't even start writing for a solver.. :(

how can you generate them wothout solving ?

i mean i generate sample puzzles.. like those posted.

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

1 week left :) Start wrapping them up slowly :)

Quote:

---

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.

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

Quote:

---

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

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

Quote:

---

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!

:wave:
-Lou