Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Very New & Clueless

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
BrianGriffin

Joined: 28 Sep 2005
Posts: 1
:

Items
PostPosted: Thu Sep 29, 2005 12:02 am    Post subject: Very New & Clueless Reply with quote

Not sure if I am posting this in right place but will keep fingers crossed lol.

I am a huge fan of Sudoku and for some time have been interested in compiling a book. Now instead of doing hand generated puzzles I would like to develop my own program which can create them for me.

There are quite a few programs out already and have no idea on where to start making one, so could someone point me in the right direction as to which threads in here I should look at to help get me started on making my own Sudoku program.
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Thu Sep 29, 2005 5:53 am    Post subject: Reply with quote

Well, generally the place to start is with dancing links, sometimes referred to as DLX (and often mistakenly on this forum as DXL). Source code for one DLX implementation can be found here.

Basically the typical way puzzles are generated is to add a few clues at random, then plug the grid into dancing links to see if it is unsolvable or has multiple solutions. If it's unsolvable, remove clues at random until it has at least one solution. From that point, as long as you have multiple solutions you should keep adding clues. (My own DLX implementation spits out a potential new clue from one of the solutions it finds, if it finds more than one. You can stop the algorithm once it hits 2 solutions unless you're really interested in counting them all.) Once you have a single-solution grid, shuffle your clues and try to remove one at a time to see if the grid still has just one solution; repeat until no more clues may be removed. You now have what is called a minimal sudoku.

Since I started where you did not too long ago, I can tell you at this point that the puzzles you get from the above method may not fit your desired level of difficulty. In general you'll tend to get puzzles that are too easy (about half), and puzzles that are ridiculously hard. You'll find few of a medium difficulty level that only require basic techniques; they're there, though. The preferred method of finding such puzzles seems to be to generate a large number of them and then sift for difficulty. Assessing difficulty is a whole other problem unto itself, which is discussed in this thread among others.

So far I've found creating a sudoku program to be a fascinating exercise, since I'm learning many new advanced techniques and finding puzzles to use them on. My program in a normal run will spit out 100 puzzles to a file, and show me what steps it used to try to solve them and rate difficulty. With the array of solving techniques it has now, only about 5% of those puzzles are impossible to finish. I've been sticking to strictly logical techniques and now I have a pretty good set to work with:
  • Naked and hidden singles
  • Pointing pairs, box-line intersections
  • Naked and hidden subsets
  • X-wing and swordfish (and up)
  • Remote pairs
  • Uniqueness
  • XY-wing and XYZ-wing
  • Coloring
  • Fishy cycles*
  • 4D coloring**

All of the above techniques are strictly logical. Since I implemented coloring though, fishy cycles is never used anymore. My original simple coloring algorithm was only partially transitive (i.e., it couldn't say a->b,c and b->a,c and c->a,b means a=b=c, which would make it fully equivalent to fishy cycles), but now it's complete. The 4D coloring method, for lack of a better term, is one I started using recently. It doesn't seem to be the same as multicoloring as I've seen it described, and it's definitely not ultracoloring. It basically extends the conjugates from coloring into the digit dimension (hence the term 4D, since it finds conjugates in boxes, rows, columns, and digits). I'm sure this method has a name but I don't know it yet; I do know however that it supercedes forcing chains.

As a purist I haven't yet implemented Nishio or other T&E methods. Typically I find at this point that the ultra-difficult 5% don't crack with Nishio anyway; at best it yields a few clues.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Sep 29, 2005 6:45 am    Post subject: Reply with quote

you can get a generator based on the solver from Lummox'
link here:
http://www.setbb.com/phpbb/viewtopic.php?t=206&mforum=sudoku

let me say (again) that the hardest required technics necessary
to solve a puzzle doesn't really "rate" the difficulty of solving it
suitably.

Some technics could be easy to understand/implement
but timeconsuming to check exhaustedly.

Usually it's faster to just backtrack than using one of the advanced
technics. However for some reason most people here don't
like backtracking, so they try to avoid it ....
They call it "trial and error" , even if you search exhaustedly
and not randomized Monte-Carlo tries.


-Guenter
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Thu Sep 29, 2005 11:39 pm    Post subject: Reply with quote

Well yes, anything that forces you to backtrack is trial and error by definition. This departs from pure logic which tries to find a pattern rather than simply trying something to see if it fails.

Regarding difficulty I've found the method of adding scores together for the techniques used tends to be quite a good measure of difficulty. The hardest technique is also a decent guideline there; overall I think my rating algorithm would do well to include some of that information too. I also need to give it some means of testing alternate solve paths, since sometimes a slightly more difficult technique will crack the puzzle wide open while others will simply chip away at it.

It's also fair to say that a wide mix of techniques also makes puzzles vastly more interesting.

On the whole I've found that randomly generated puzzles tend to be evenly split between singles-only or some that get no more complex than pointing pairs, and an entire spectrum of difficulty ranging from moderate to brutal. This very much departs from what I first expected; after playing the evil level at websudoku.com, I found only one puzzle demanding a technique beyond finding subsets, which needed an X-wing.
Back to top
View user's profile Send private message
Moschopulus

Joined: 12 Aug 2005
Posts: 39
:

Items
PostPosted: Thu Sep 29, 2005 11:46 pm    Post subject: Reply with quote

dukuso wrote:

Usually it's faster to just backtrack than using one of the advanced
technics. However for some reason most people here don't
like backtracking, so they try to avoid it ....
They call it "trial and error" , even if you search exhaustedly
and not randomized Monte-Carlo tries.

-Guenter


Now Guenter, let's not start that again!

I can't resist. You know that some people say "trial and error" when they mean backtracking....
Back to top
View user's profile Send private message Visit poster's website
Sudomuso

Joined: 04 Nov 2005
Posts: 2
:

Items
PostPosted: Fri Nov 04, 2005 4:12 pm    Post subject: Reply with quote

Lummox JR wrote:

  • Naked and hidden singles
  • Pointing pairs, box-line intersections
  • Naked and hidden subsets
  • X-wing and swordfish (and up)
  • Remote pairs
  • Uniqueness
  • XY-wing and XYZ-wing
  • Coloring
  • Fishy cycles*
  • 4D coloring**



Hi

can someone point me to a web site where I can find explanations for all these solving tactics?
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Nov 04, 2005 5:09 pm    Post subject: Reply with quote

Quote:
can someone point me to a web site where I can find explanations for all these solving tactics?


You're already on one.

Try the search function, or check my SOLVING TECHNIQUES INDEX topic in the Solving Sudoku section.

If this is too high-tech, check these sites:

http://www.simes.clara.co.uk/programs/sudokutechniques.htm
http://www.angusj.com/sudoku/hints.php
Back to top
View user's profile Send private message Visit poster's website
Sudomuso

Joined: 04 Nov 2005
Posts: 2
:

Items
PostPosted: Fri Nov 04, 2005 6:58 pm    Post subject: Reply with quote

It is too high tech as long as Im not familiar with the terminology.

Thanks a lot, those links are most helpful!
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron