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   

A few Questions

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

Joined: 19 Oct 2005
Posts: 13
:

Items
PostPosted: Wed Mar 22, 2006 9:50 pm    Post subject: A few Questions Reply with quote

Hello everybody,

I'm a newbie at creating sudoku solvers... this is a project I've wanted to attempt for a while now and am finally getting into it. I've read a lot of the posts here and while I've picked up some good information I think i'm more confused than I was when I started Smile

I started by building a program that generates a random filled grid that meets the Sudoku row/column/box constraints. I thought that the next step was to hide random squares until I got to the point where there was more than one solution (or pairs of numbers if I wanted to make a symetrrical Sudoku). However, reading posts here I've seen some posts that suggest you should instead go the opposite way and start with an empty grid and fill in givens until you have a single solution. Which is better and why? I read one post that suggested that starting with a full grid was better for a brute force solver, and starting with an empty grid was better for a logic based solver. Why is that? Why does it matter?

It seems to me that a brute force solver would use the exact same code I used to populate the random grid, except it would fill numbers in numerical order from one to 9 or from 9 to 1 in order rather than attempting random numbers at every position as my grid generator does.... so in a way I already have that coding done, but I really wanted to make a logic based solver so that my program can give hints on request to the user solving the puzzle.

Next problem, is testing for uniqueness. I saw one suggestion to run a brute force solution using numbers in order from 1-9... then running it again with reverse order... from 9-1 and see if the solutions are the same. That would do the trick, and I could do that... but dancing links seems lot more elegant and could tell me an actual number of solutions rather than just telling me I have more than one... but I have read the wikipedia article on algorithm X and DLX and I don't understand it at all... I very vaguely undrerstood how the base algorithm X worked but I don't understand at all how to apply it to Sudoku despite the explanation in the Dancing Links article. Are there any othere references at all on the web that anybody could point me at that gives me more insight on this? It's pretty confusing.

The last issue seems to be the one that is universally agreed upon as being hard, and that is determining difficulty. There seem to be as many opinions on what makes a puzzle difficult as there are people trying to define it. One method is looking at the level of the techniques used to solve the puzzle. That one makes some sense.... some of the others seem to me to not make as much sense, such as using the solving time of the DLX algorithm. I'm still not sure how i'll approach this but I definately want to code in some kind of way of generating "easy,moderate,difficult,diabolical" puzzles....

So this is kind of a synopsis of some of my questions and "understandings" that I've gained after reading a lot of the posts here, any pointers, suggestions, or help of any kind on any of these points would be very appreciated.

Thanks!
Jeff
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Wed Mar 22, 2006 11:31 pm    Post subject: Reply with quote

Jeff,

There are a lot of people in this forum with lots of experience and knowledge about Sudoku. I'm not one of them ... BUT ... I'm at the same place as you in taking the next step after generating a filled grid.

Decide now if you want to generate a puzzle from a filled grid and determine its difficulty. Not all approaches to writing a solver include this determination and thus may not be suitable for use in a puzzle generator. However, since many techniques for creating puzzles result in easy puzzles to solve, you may need a means of filtering out these puzzles.

Good luck on getting additional replies to your post. I'll be interested in reading them as well.

Maybe the following will help.

Quote:
There are matters of preference at play here.

Almost everyone agrees that puzzles with more than one solution are invalid, but not everyone agrees that the pattern of givens need to be symmetric.

Also, some people believe that the puzzle must be minimal in the sense that removing any one of the givens would make it invalid. Me, I'm happy with a non-minimal puzzle.

I've implemented a Goldilocks Depletion Heuristic (GDH); i.e., you keep searching until you find one that's 'just right'.

1. Start with a solved grid.

2. Randomly remove a cell -- or pair of cells if you want symmetry.
(DAJ restriction -- monitor that no band is depleted excessively or any row/column/block is left filled excessively.)

3a. If the puzzle becomes invalid, then replace last cell removed and return to (2).
3b. If the puzzle becomes too difficult, then replace last cell removed and return to (2).
3c. If the puzzle is too easy, then return to (2).

4. Done.
_________________
Agent Allen (seriously paraphrased!)
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Mar 23, 2006 12:16 am    Post subject: Reply with quote

jdport wrote:
I read one post that suggested that starting with a full grid was better for a brute force solver, and starting with an empty grid was better for a logic based solver. Why is that? Why does it matter?

I will first answer this question.

When you start with an empty grid, a brute force solver has to fill all those empty cells before deciding there are multiple solutions. A logical solver will stop when there is no more logic to apply, which is very quick on an almost empty grid.

When the grid is almost filled (i.e. when you remove clues from a completed solution) brute force has only a few cells to complete, and it will only find 2 solutions at the point you want to end. A logical solver has to check all the filled cells for each technique, which takes a lot more time.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
jdport

Joined: 19 Oct 2005
Posts: 13
:

Items
PostPosted: Thu Mar 23, 2006 3:07 am    Post subject: Reply with quote

I found a great article about DLX that others in the same position as me might find helpful in trying to understand how to use DLX with Sudoku.

http://www.osix.net/modules/article/?id=785

He gives a brief introduction to DLX, not going into it completely (referring you to Knuth's papers for a full explanation) but giving a pretty good description and then goes on to relate it to Sudoku and even shows some code (not sure if he posts an entire DLX processor or just parts, i haven't read it all yet) ... it looks like he used c# and since that's a .net language I could probably use his code in my application to implement this and be done with it (i'm using vb.net) but ... since the whole purpose of writing the code is to learn some things and improve my programming skills i want to write it myself. This looks like a nice article though to learn from, thought others might be interested.

-Jeff
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting 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