C# Program for Solving / Generating Sudokus, Sudoku Blog

Sudoku puzzles, off-site games and other resources on the Internet

C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Fri Oct 24, 2014 3:44 pm

Hi!

I am a C# programmer and wanted to use this forum, to present two of my projects, I hope this is the right place to put it, and I hope it is interesting for you. As well I am curious about your opinions regarding the Sudokus.
So I personally am new to Sudokus, but started from an algorithmic perspective when I wanted to write a program to solve and generate Sudokus in C#. Of course the solving is not so hard, the computer can simply try out all solutions, but the generating is difficult - and contrary to my opinion, I did not find a "standard" method to do so (as for the rest of the post, as I am in any part wrong, please correct me). Therefor, I implemented a method which resembles how humans would solve a Sudoku, by applying certain rules (like Naked Pair etc.) I found online. (Prior I thought all Sudokus can be solved by using only a very few simple rules, but that is not the case, each of the very many turns out to be different from the others and thus might be required right?).
The rules I orderd according to how difficult I thought them to be, then the program simply creates a random Sudoku and checks, which rules it has to apply to be able to solve the Sudoku, the last one of course always being brute-force.
More details about the program you can found on my programming blog, starting with the article http://csharp-tricks-en.blogspot.de/201 ... dokus.html. There is another article posted which describes the implemented solving rules (http://csharp-tricks-en.blogspot.de/201 ... dokus.html), and I will publish two more posts in the next 2 weeks containing the source code etc.
Using that program, I also started another blog for fun, on which I publish every day 5 Sudokus with the different implemented difficulties (http://sudokusoftheday.blogspot.de/), where you thus can find sample Sudokus.

What I am especially curious now about is - next the questions already asked in the text: Is this the way for example news papers etc. also create their Sudokus? Are my implemented solving strategies "good", so is their difficulty about right evaluated, are there some missing which the program definitely has to know? And, last but not least, what do you think of the created Sudokus? Is their difficulty appropiate?
Already many thanks in advance, I would be very happy about answers! And of course I hope, also for you, the program etc., is interesting to read and maybe helpful.
Kind regards
Oliver
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby JasonLion » Sat Oct 25, 2014 1:59 pm

I believe a few places still use puzzles created by hand, but most use a process similar to what you describe. Most use many more solving techniques than you have used in their difficulty analysis. This obviously includes more complex techniques, but also many minor variations of the simpler techniques that allow for finer gradations of difficulty. For example, full house is a common technique to use in grading puzzle difficulty. Every full house is also solved with other simple techniques, but by distinguishing it from the others a more natural difficulty evaluation can be produced as a human will find a full house simpler to detect and solve compared to one of the more general techniques.
User avatar
JasonLion
2017 Supporter
 
Posts: 620
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Mon Nov 03, 2014 2:16 pm

Hi,
first thanks for your reply!
I looked and the Full House and honestly did not see the difference between it and Singles? And further, the technique seems to be so easy, that it only helps to disgintuish very easy and easy puzzles, I think I can create puzzles with lower difficulty pretty well, but for the higher difficulties I am missing a lot of techniques.
But again thanks for confirming how most puzzles are created.
Btw, the code is now fully online.
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

re: methods

Postby Pat » Thu Nov 06, 2014 9:16 am


  • Full House is indeed the simplest form of "singles"
    (a special case of "hidden single" and also a special case of "naked single")
  • Locked Triple, Locked Pair,
    = special cases of other methods,
    but deserve separate treatment
  • you list box\line,
    should add the reverse:
    line\box
  • naked / hidden X up to X=3:
    should go up to 4
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Thu Nov 06, 2014 4:01 pm

Thanks Pat! I will look into it.
But for hidden / naked X: Do you think X = 4 will be likely happen? With the size of 9 x 9 I thought it was very unlikely, and I think I read this too.

Another question I would be glad if confirmed (it should be correct, but checking never hurts, since I am already using this when publishing the Sudokus): When creating Sudokus with difficulties "lower than brute force", I do not run brute force on them to get all possible solutions, that is to count the number of solutions (as it should be uniquely solvable). This is, because all the implemented rules give a unique decision for the next step, so it is already guaranted that there exists only one solution if the Sudoku can be solved using these rules, correct? :)
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby ixsetf » Thu Nov 06, 2014 6:08 pm

I would recommend looking at Sudopedia as a reference instead of the sources you listed in your blog post. The information at Sudoku of the day is incomplete, and incorrect in its assumption that there are Sudoku which "require various forms of guessing to solve". No known Sudoku puzzle requires trial and error to solve. The PDF source you cite is also missing some techniques, and as a result it also uses trial and error unnecessarily. That said, I can't fault it too harshly as it seems to focus on lower level puzzles.
ixsetf
 
Posts: 50
Joined: 11 May 2014

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby enxio27 » Fri Nov 07, 2014 2:17 am

bloggeroliver, I collected a few posts in this thread that may be of assistance to you in your puzzle generation efforts:

http://www.rcbroughton.co.uk/sudoku/for ... =11&t=1221

I would be very interested to see what you come up with.

Sadly, the forum where most of the (remaining) sudoku programmers used to hang out and discuss various algorithms, methodologies, etc., is now defunct. A few of those people are here, but not sure whether there is sufficient critical mass to get some good discussion going again.
User avatar
enxio27
 
Posts: 206
Joined: 13 November 2007

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Mon Nov 10, 2014 3:52 pm

Hi,
thanks for your interesting answers.
First ixsetf, on the wiki there seem to be a lot of nice techniques. But now you confuse me a lot, I also thought that some Sudokus might need brute force, depending on how hard you create it. But if not, there has to exist some minimal set of techniques needed to require solve every Sudoku, which would it be then? I never found anything about that.

Then enxio27, thanks for your research. I now published my program created so far, on http://csharp-tricks-en.blogspot.de/201 ... udoku.html you can find the link to the source code and / or the executable alone, would be happy if you like it!
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Postby Pat » Tue Nov 11, 2014 8:27 am

bloggeroliver wrote:I also thought that some Sudokus might need brute force, depending on how hard you create it.
But if not, there has to exist some minimal set of techniques needed to require solve every Sudoku, which would it be then? I never found anything about that.

"forcing nets" will solve anything
(may be quite complex)
User avatar
Pat
 
Posts: 3295
Joined: 18 July 2005

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Thu Nov 20, 2014 6:09 pm

Very interesting, thanks!
(But yes, seems pretty complex - what is obvious though of course, since I read somewhere solving Sudokus is NP - complete).
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Big Sudokus

Postby bloggeroliver » Sat Feb 21, 2015 5:57 pm

Hey people,

in a previous post I asked you about your ideas and feedback about my Sudoku website and Sudoku creating techniques, today I just want to advertise some big, challenging Sudokus I created with my program. You can find them on this link: http://sudokusoftheday.blogspot.de/p/big-sudokus.html
So far I published the sizes 16 x 16 - 36 x 36, but I am able to go up to at least 64 x 64.
Would be interested if something actually does solve such big puzzles.

Have fun, and have a good day!
Oliver
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Tue Mar 31, 2015 1:27 pm

Now I would like to state that I now enabled a function to solve Sudokus online on my blog.
I don't know if anybody solves them online, but I think the funtionality should be there, so I'd be happy about checking it out and feedback!

Best
Oliver
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Re: Big Sudokus

Postby m_b_metcalf » Tue Mar 31, 2015 1:44 pm

bloggeroliver wrote: today I just want to advertise some big, challenging Sudokus I created with my program. You can find them on this link: http://sudokusoftheday.blogspot.de/p/big-sudokus.html
So far I published the sizes 16 x 16 - 36 x 36, but I am able to go up to at least 64 x 64.

I wanted to try your puzzles, but could find no way of copying them, for instance as .txt files.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8095
Joined: 15 May 2006
Location: Berlin

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby bloggeroliver » Tue Mar 31, 2015 10:46 pm

True, now I also upload the txt files for the online solver, but back then I didn't.
I will create new ones and send you by PM.
Out of curiousity or for also the other published Sudokus, why isn't the picture enough?
Do you (and others) use different programs to display etc.?
bloggeroliver
 
Posts: 14
Joined: 24 October 2014

Re: C# Program for Solving / Generating Sudokus, Sudoku Blog

Postby m_b_metcalf » Wed Apr 01, 2015 2:37 pm

bloggeroliver wrote:Out of curiousity or for also the other published Sudokus, why isn't the picture enough?
Do you (and others) use different programs to display etc.?


I like to load it into a local file so as to be able to study it with my own programs.

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8095
Joined: 15 May 2006
Location: Berlin

Next

Return to On the web

cron