
View previous topic :: View next topic 
Author 
Message 
 Frost_Byte
 Joined: 20 Apr 2006  Posts: 6  :   Items 

Posted: Thu Apr 20, 2006 10:58 pm Post subject: Genetic Algorithms to Generate Valid Sudoku Puzzles 


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 brainstorming 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 crossover, which type of crossover 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 


 The Ostrich
 Joined: 20 Apr 2006  Posts: 49  :   Items 

Posted: Sun Apr 23, 2006 1:22 am Post subject: 


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 notwelltuned 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 rewriting 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 GAbased program, which will take you weeks... 

Back to top 


 Frost_Byte
 Joined: 20 Apr 2006  Posts: 6  :   Items 

Posted: Mon Apr 24, 2006 3:02 pm Post subject: 


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

Back to top 


 Lummox JR
 Joined: 07 Sep 2005  Posts: 202  :   Items 

Posted: Wed Apr 26, 2006 6:21 pm Post subject: 


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 


 The Ostrich
 Joined: 20 Apr 2006  Posts: 49  :   Items 

Posted: Sat Apr 29, 2006 10:38 pm Post subject: 


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 Xwing or an XYwing (I'd say its pretty obviously a nobrainer that Xwings are way easier). In fact, anything relying on a combination of multiple digits is pretty certain to be harder than a singledigit pattern. For this reason, I often find myself using singlecolouring and xwings 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 tradeoff. 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 timetofind 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 13 in 5 minutes, and easy puzzle 4 not at all. 

Back to top 


 Frost_Byte
 Joined: 20 Apr 2006  Posts: 6  :   Items 

Posted: Mon May 01, 2006 1:39 am Post subject: 


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

Back to top 


 constablebrew
 Joined: 08 Mar 2007  Posts: 1  :   Items 

Posted: Thu Mar 08, 2007 10:26 pm Post subject: Re: Genetic Algorithms to Generate Valid Sudoku Puzzles 


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 sudokuinvalid space and would be difficult to create a fitness function for.
Evolving sudokuset generators would probably be a more useful process. Each agent would receive a pregenerated, 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. Coevolution 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 


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

Posted: Sat Jun 02, 2007 2:14 am Post subject: 


observation: symetric position of numbers in the cells 

Back to top 


 atkman
 Joined: 04 Jan 2008  Posts: 4  :   Items 

Posted: Fri Jan 04, 2008 6:41 pm Post subject: 


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 




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

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
