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   

Genetic Algorithms to Generate Valid Sudoku Puzzles

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

Joined: 20 Apr 2006
Posts: 6
:

Items
PostPosted: Thu Apr 20, 2006 10:58 pm    Post subject: Genetic Algorithms to Generate Valid Sudoku Puzzles Reply with quote

Hi folks,

I'm going to make a program that will generate valid sudoku puzzles (that has only one solution) with genetic algorithms but I still couldn't exactly determine how to do it. There are some ideas in my head, but I'm not quite sure which approach to use. I thought it would be useful to make a brain-storming with people in this forum.

This thread will exactly serve this purpose, discussion about generating (not solving) sudoku puzzles with genetic algorithms. The important problems that may be addressed here are:

- How to represent Sudoku boards as chromosomes
- How to make the mutation on these chromosomes
- How to make the cross-over, which type of cross-over to use
- The Fitness function, how to determine the fitness value of individuals.


Here is some portion of what is in my mind: The chromosomes would be made up of 81 integers, but is there a way to represent a random board of sudoku with bits ? Fitness function would check to see how many solutions does an individual random Sudoku board has and determine a value accordingly. Can we make the work of genetic algorithms easier by using an intelligent technique, like using appropriately filled Sudoku boards (solutions) as a guide?
Back to top
View user's profile Send private message
The Ostrich

Joined: 20 Apr 2006
Posts: 49
:

Items
PostPosted: Sun Apr 23, 2006 1:22 am    Post subject: Reply with quote

Just a little word of caution... You are going to end up with a useless dog of a generator. The reason for this is quite simple. In general, a simple contradition check on a potential new given is sufficient to determine whether that given will be valid or not.

Postulate 1: The only efficient way of evaluating fitness is to estimate the number of solutions.

Postulate 2: The number of solutions cannot be efficiently estimated with less work than that required to produce two solutions for an arbitrary input.

Now... Assuming these are correct, my new hacky and not-well-tuned generator produces sudokus with an average of 23 givens, doing an average of 133 solves per puzzle. So this corresponds to a theoretical efficiency of N = 17.3%, where 100% would mean never placing a given which wasn't in the final puzzle. So your genetic algorithm would require fewer than 1 in 5 errors over the entire process of producing the puzzle to beat a simple generator hacked together in less than an hour. I wouldn't have thought this was possible, even if you have the nous to pull off the re-writing of the problem in terms of GA.

Furthermore, if after placing some random givens, I used the solution results to place the remaining ones, I could probably double this efficiency... Of course I plan to do this in the future, at it will take me about 30 minutes, in contrast to a GA-based program, which will take you weeks...
Back to top
View user's profile Send private message
Frost_Byte

Joined: 20 Apr 2006
Posts: 6
:

Items
PostPosted: Mon Apr 24, 2006 3:02 pm    Post subject: Reply with quote

I see your point. I also don't think it will be much efficient to generate puzzles with Genetic Algorithms. But I want to experiment. Right now I'm working on the solver. Soon I may be able to finish the first executable and try it. I hope it will not take too much time to generate some output... Sad

But one of the most important reasons that I've opened this thread is to see if people have some ideas to make it work easier... Question
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Wed Apr 26, 2006 6:21 pm    Post subject: Reply with quote

As I've said before, I don't know if genetic algorithms can illuminate much on puzzle generation, but they may well be the key to finding better algorithms to gauge difficulty. What we have right now is an intuitive idea based on our own subjective approaches, and that leads to two common subjective measures: 1) scoring techniques based on subjective difficulty and finding the path of least resistance to a solution (usually not by recursion but by always applying the "easiest" technique, so this might be improvable), or 2) finding which particular techniques exist in the puzzle along the path of least resistance, and how many times each is encountered.

That some techniques are easier than others is obvious, but which ones are easiest in general is an unanswered question. The answer, if there is one, is probably a compromise of the many different viewpoints involved. But while that's of key importance to any difficulty metric, we still don't know what balance of methods 1 and 2 is best, or if perhaps still more methods exist for determining difficulty.
Back to top
View user's profile Send private message
The Ostrich

Joined: 20 Apr 2006
Posts: 49
:

Items
PostPosted: Sat Apr 29, 2006 10:38 pm    Post subject: Reply with quote

I think that, if you really want an accurate way of gauging difficulty, you would want to focus more closely on people, and less closely on algorithms. Difficulty relates to two things, as far as people are concerned, time and solvability. If you don't know a required technique, and aren't smart enough to work it out, you can't solve a puzzle. Thus the less easy a technique is to DERIVE, the harder its use should be graded.

If we assume that a solver IS going to be able to solve the puzzle, we must then look at the time its going to take them. So, is it harder to spot an X-wing or an XY-wing (I'd say its pretty obviously a no-brainer that X-wings are way easier). In fact, anything relying on a combination of multiple digits is pretty certain to be harder than a single-digit pattern. For this reason, I often find myself using single-colouring and x-wings on puzzles that don't need them, because they're faster than finding the aligned pair exclusion or hidden triple that my generator assumed I would find.

I'd say the problem that we have, then, is that a technique that is easy to derive for yourself isn't necessarily a technique that's easy to apply, and therefore any rating of difficulty that embraces one method will exclude the other to some degree. Like most of life, its a trade-off. To advanced players of the sort we have on this forum, whom we can assume have coded and therefore know just about all techniques, it would be pretty stupid to advance the solvability component at the expense of the time-to-find component. But against joe public, that might well be necessary, if you don't want people to leave wondering why they were able to solve easy puzzles 1-3 in 5 minutes, and easy puzzle 4 not at all.
Back to top
View user's profile Send private message
Frost_Byte

Joined: 20 Apr 2006
Posts: 6
:

Items
PostPosted: Mon May 01, 2006 1:39 am    Post subject: Reply with quote

I'm not much into difficulty issue yet. I've finished my solver, though it does not incorporate advanced techniques, it can find solutions by basic techniques and guessing. And it can also find the "number of solutions" to an inappropriate puzzle board, which my genetic algorithm puzzle generator will possibly make use of.

Now, I'm curious if I'm gonna get some puzzle outputs easily (without much waiting) after devising a fitness function. I'm gonna learn this soon... Smile
Back to top
View user's profile Send private message
constablebrew

Joined: 08 Mar 2007
Posts: 1
:

Items
PostPosted: Thu Mar 08, 2007 10:26 pm    Post subject: Re: Genetic Algorithms to Generate Valid Sudoku Puzzles Reply with quote

This sounds like a fun project. I've not programmed a GA before but have wanted to for some time.

Evolving sudoku sets as the agent doesn't seem like it would be a viable system. Evolution is a sloppy process and requires an amount of error. If the sudoku set is the agent then some agents would have to be invalid (multiple solutions, no solutions, or even duplicate numbers) for a healthy genetic pool. Such a system would spend lots of time evolving through sudoku-invalid space and would be difficult to create a fitness function for.

Evolving sudoku-set generators would probably be a more useful process. Each agent would receive a pre-generated, solved sudoku set. The agent will process the set and remove numbers. The final output of the agent will then be evaluated for it's complexity. More difficult puzzles will award the agent with a higher fitness score.

Agent's genetic code is comprised of a set of instructions that allow for the analyasis and editing of a given sudoku set. In effect, each agent is a virtual cpu and the DNA is the programming code.

The scoring of each agent is highly dependent on how difficulty is gauged. Determining a proper score for puzzle difficulty is still under debate. As has been stated earlier, the emphasis of one technique as being more difficult than another will lead to puzzles that tend to be similar. Co-evolution of a difficulty evaluator and puzzle generators might lead to some interesting techniques of puzzle evaluation and generation while avoiding skewed results.

The population of evaluation agents will all score the output of the generating agents. The average score of all the evaluation agents for each puzzle output will be the fitness score of the generating agent. Agents that solve puzzles faster will have a higher fitness than the slower agents.

Thus we will have two populations. Puzzle generating agents that all compete to generate the most difficult puzzles and evaluation agents that all compete to solve puzzles faster.
Back to top
View user's profile Send private message
dmkAlex

Joined: 02 Jun 2007
Posts: 11
:
Location: USA

Items
PostPosted: Sat Jun 02, 2007 2:14 am    Post subject: Reply with quote

observation: symetric position of numbers in the cells
Back to top
View user's profile Send private message
atkman

Joined: 04 Jan 2008
Posts: 4
:

Items
PostPosted: Fri Jan 04, 2008 6:41 pm    Post subject: Reply with quote

You need to add some sought of intelligence to a solver otherwise to go through the combinations of numbers will take a very long time and cpu power. but it may be a trade off of difficulty
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