Genetic Algorithms to Generate Valid Sudoku Puzzles

Frost_Byte

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?

The Ostrich · 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 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...

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

Lummox JR · 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.

The Ostrich · 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 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.

Frost_Byte · 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... Smile

constablebrew

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.

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

observation: symetric position of numbers in the cells

atkman · 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