Genetic Algorithm and Sudoku

I actually tried doing this about 2 months ago. As you mentioned, there doesn't seem to be a good crossover operator available. In my opinion even if you found a crossover operator that produced valid solutions, it would do little good anyway as it would likely just be effectively macro-mutation (and macro-mutation is highly unlikely to increase fitness).

I chose to just use mutation instead and focused on figuring out some good mutation operators instead. I implemented a substitution mutation and a swap mutation (swapped two random boxes in the grid).

Unfortunately my conclusion was that GA's are not well suited to this problem. The reason is that Suduko requires a perfect solution, wheras the evolutionary process is best suited for problems where near-perfect solutions are acceptable. In Sudoku near-perfect solutions are just wrong solutions.

Using a GA to solve suduko you can easily reach a local maximum where you have just two numbers in the wrong order, but it would take a long series of downhill mutations to reach the global optimum.

Unless you hybridise the algorithm with some sort of domain knowledge (which is kind of cheating) then you may have to leave your machine running for days to find the solution.

I chose to cheat instead. I found that suduko can actually be solved using a sequence of logical steps. In answer to your question about how the difficulty of Suduko puzzles is based, no it is not soley based on the number of missing spaces. There is a sequence of steps you can use to solve a suduko puzzle and more difficult puzzles will require more steps.

The first step I used was to store a list of possible values for each box in the grid. Then the program removes values from this list that cannot go in the box (ie if there is a 5 in the same row, or column as the box then 5 cannot go into the box, so remove 5 is removed from the list of possible values for that box).

After ruling out values for all the boxes in the grid, the next step is to find boxes with only one possible value left. You then obviously assign that value to the box, and then because the grid has changed, you redo step 1 above.

These steps alone can complete the easier Suduko puzzles, but with moderately hard puzzles you reach a stage where there are boxes not yet filled in, but they all have more than one possible value.

The next step is to look at each 3x3 subgrid seperately. You know the rule that a subgrid must contain the numbers 1 to 9. Take the numbers 1 to 9 in turn and check to see if they can only go in one box in the subgrid. If so then fill in that box, and redo from the first step.

The above steps will solve most moderate puzzles, and some hard. But some puzzles are even harder and I got stuck on that stage. My brain wasn't good enough to figure out the next logical step (I have no idea if there are more barriers after that).

Instead I just brute forced the rest, by treating it like a combination lock, and exiting early if a combination broke the suduko constraints. The above steps reduced the combinations enough so that it could be solved instantaneously.

I fully agree with RunningInt. Sudoku is not a puzzle that will be solved very well at all with a genetic algorithm. The fact that there are strategies and various logical steps necessary says it all. The best way to implement any AI to solve Sudoku is to program it to use the same techniques a human player would use in solving the puzzle. You can easily find these anywhere and in fact using them creates for a very fast puzzle solver ( as opposed to brute force... ).

Sudoku is a prime example of a class of problems known as Constraint Satisfaction Problems. The formal definition of a CSP is as follows (taken from my AI professors website):

A CSP is a triplet {V, D, C}, where V is a finite number of variables, V={V1, V2, ..., Vn}.

Each variable may be assigned a value from a domain D.

Each member of C is a pair: the first element of the pair is a set of variables, and the second element is the set of legal values for those sets. (Note that C is usually represented with a function, rather than explicitly).

The method to solve such a problem is depth first search with constraint propogation (detailed in the website I cited earlier). The basic idea is for each variable, determine the set of all possible values for it. You perform a depth first search, where every time you try setting a variable, you check that variable with all of the constraints, eliminating illegal values from other variables. You then propogate these changes recursively, doing a similar check for each variable possible set that you changed. If you ever prune a set to the empty set, then you end that branch of the search and backtrack.

In practice, the constraint propogation "pre-processing" will sometimes solve the problem with no search at all. If it doesn't, it usually doesn't take many iterations of the search to find a solution.

Have the last 3 posters all missed the fact that the original poster asked to "generate the puzzles" which is not the same as "solving the puzzles"?

LOL yes. whoops. I guess generating one follows a similar method though. First you have to effectively solve one, and then get rid of some of the answers.

Quote:

Original post by Kylotan Have the last 3 posters all missed the fact that the original poster asked to "generate the puzzles" which is not the same as "solving the puzzles"?

Quote:

Since there doesn't seem to be a way that would help determine a possible solution except by randomly copying numbers from one or the other.

His post was kind of confusing. He said he wanted to make puzzles, but he also said he was having difficulty getting the computer to solve them. I was answering the latter question.

Additionally, as RunningInt touched on, making a puzzle is essentially solving a puzzle with no constraints, and then replacing some of the squares with blanks. By randomizing which node you expand in the depth first search part of constraint propogation, you can create random solutions. The problem is then reduced to finding a strategy of covering squares given a certain difficulty, checking to make sure the end result is solvable.

Why do you care about cross-over? Is random 'mutation' not enough?

Will

Quote:

Original post by RPGeezus Why do you care about cross-over? Is random 'mutation' not enough? Will

Well, some believe that crossover is the only thing needed in GAs, while others believe that the whole crossover concept is worthless.

In this case, due to the high level of dependency among the values in the candidate solution, crossover may not be exactly possible.

As for generating a problem, I think using a GA may not be the best idea for directly generating a problem. However, you could use a GA to generate an end result, then use a reverse solver to start plucking out values.

I was planning on making a little Sudoku game, and the method for generating the puzzles I thought up is as follows.

Basically the there are two phases:

Phase one: Fill the board.

To fill the board you use a simple iterative search. For each box you determine the valid locations for the current number and then place it in a random spot. Then move to the next box. This repeated until the current number is placed in all boxes, then you move to the next number and repeat. Eventually you will have a completed Sudoku.

Phase two: determine values to show:

Once you have a completed board you create a play board by determining the number values to show based on the difficulty level and then show that many random values and you are done.

I apologise for the confusing first post.

As KevMo correctly stated, generating a sudoku board is near enough the same as solving a sudoku board. The main difference is that 'solving' one has a head start where the initial values on the board is 'correct' and will lead to a solution.

I've always though that the mutator in a GA provides the random element, whilst the crossover provides the process to move the population towards some possible solution. If the whole breeding process is totally random, then it seems like it is just wildly searching for the solution.
As some of you mention, this means that GA is possibly not suitable for what I am trying to accomplished.

Quote:

Original post by TechnoGoth Phase one: Fill the board. To fill the board you use a simple iterative search. For each box you determine the valid locations for the current number and then place it in a random spot. Then move to the next box. This repeated until the current number is placed in all boxes, then you move to the next number and repeat. Eventually you will have a completed Sudoku.

Does this need some form of backtracking - will it always give a solution and you wont get stuck half way filling the board?

Thanks all for answering, this has been very enlightening.

http://en.wikipedia.org/wiki/Sudoku
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

Quote:

Original post by Chrominium Does this need some form of backtracking - will it always give a solution and you wont get stuck half way filling the board?

When solving an already generated Sudoku puzzle using constraint propogation, I do not think you would need backtracking. However, when generating a puzzle from scratch using DFS+constraint propogration, you will, because I think it is possible to choose a value for a node that turns out later to be impossible.

Quote:

Original post by Chrominium I've always though that the mutator in a GA provides the random element, whilst the crossover provides the process to move the population towards some possible solution. If the whole breeding process is totally random, then it seems like it is just wildly searching for the solution. As some of you mention, this means that GA is possibly not suitable for what I am trying to accomplished.

Crossover and mutation are not so separate. Usually both involve a random factor, but traditionally crossover combines part of one solution with another (in the hope that good parts from each will be combined) while mutation makes small changes to a solution (in the hope that a small but significant improvement can be made). I like to think of crossover as coming up with ideas and mutation as refining them.

I think GAs would be a decent solution to this problem but I expect there is a more rigorous mathematical approach that would work better.

27 equations. Cij where C00 is the upper left corner, i is the row , j is the column. Probably this CSP thingy but I'm not a mathematician.

C00 + C01 + C02 + ... + C08 = 45 and similarly for all rows, all columns and all 3 by 3 grids...

Solve the matrix. It's an interesting idea to do it with a genetic algorithm but it follows in the vein of using neural nets for everything. Certain techniques should be used in specific cases but quite often the popular techniques get applied instead. However if you're doing it just for fun then enjoy :-) Seems interesting enough!

Quote:

Original post by Metorical 27 equations. Cij where C00 is the upper left corner, i is the row , j is the column. Probably this CSP thingy but I'm not a mathematician. C00 + C01 + C02 + ... + C08 = 45 and similarly for all rows, all columns and all 3 by 3 grids... Solve the matrix. It's an interesting idea to do it with a genetic algorithm but it follows in the vein of using neural nets for everything. Certain techniques should be used in specific cases but quite often the popular techniques get applied instead. However if you're doing it just for fun then enjoy :-) Seems interesting enough!

These equations aren't enough. A valid Sudoku puzzle is solveable without guessing, so you would need to be able to get an exact answer with the given square values. There are 81 squares on a Sudoku puzzle, but if you only used 27 equations, then you could only solve for 27 unknowns. This means you would need to cover up >50 squares for a solvable puzzle. Howevever, it is possible to make a Sudoku puzzle with only 20 or so givens, which would be 60 unknowns.

The thing missing in your equations is that you need restrictions on the variables to make them in the range of 1-9. You can't really make that restriction if you were to solve your equations by matrix inversion.

This is where the constraint satisfaction part comes in. You augment your given (but modified) constraints with the constraint that each square comes from the set of 1 through 9.

Quote:

Original post by Chrominium If the whole breeding process is totally random, then it seems like it is just wildly searching for the solution.

Take a look at simulated annealing ;) (not for this project, you just may find it interesting) It's an algorithm in the class of minimization/maximization (along with genetic algorithms and hill climbing/gradient descent). It is kind of similar to genetic algorithms with only mutation.

Quote:

Original post by Kylotan I like to think of crossover as coming up with ideas and mutation as refining them.

They are really both just methods of hypothesis generation by analogy. Remember that the selection operator is responsible for choosing good hypotheses. Crossover attempts to alter the selected hypotheses by switching substates on a submanifold of the state space determined by the crossover site, while mutation essentially nudges a point in the state space a small distance. Crossover has a predominant affect on the convergence rate of the population, however it is also responsible for the asymptotic performance of GAs.

Quote:

Original post by Timkin Quote: Original post by Kylotan I like to think of crossover as coming up with ideas and mutation as refining them. They are really both just methods of hypothesis generation by analogy. Remember that the selection operator is responsible for choosing good hypotheses. Crossover attempts to alter the selected hypotheses by switching substates on a submanifold of the state space determined by the crossover site, while mutation essentially nudges a point in the state space a small distance. Crossover has a predominant affect on the convergence rate of the population, however it is also responsible for the asymptotic performance of GAs.

I'd like to add something to that. :)

Population management can radically affect the usefulness of crossover or mutation.

As an example:
The top scoring member moves on to the next generation AND a copy of this member (mutated or crossed with another member). Same for the second best, etc.. until we have 10 members for the next generation. No monte-carlo selection, we always take the fittest.

In this case, after the population matures a bit, cross-over will become little different from mutation. The members in the population will be nearly identical. A cross-over is more likely to break the member, since the changes tend to be more dramatic, and as the population is mature, it has likely evolved some internal structure that may not take kindly to big changes.

The last few times I've used EP for a problem I've had the program record the number of times a mutation improved fitness, and the number of times cross-over improved fitness. I realize that this is very subjective to the problem being addressed, and may fly in the face of conventional wisdom, but I found that in less than 5% of improvements cross-over was the contributing factor.

I wouldnt be too surprised if it were possible to show, mathmatically, that mutation and cross-over are equivilant under certain constraints.

Quote:

Original post by WeirdoFu Well, some believe that crossover is the only thing needed in GAs, while others believe that the whole crossover concept is worthless.

I think it's worthless. But im not an expert. Do you happen to know if the worth of crossover is contested in acedemia? Just to clarify - I realise crossover is useful in some model situations. But almost all of the problems i've tried GA's on I have never seen how crossover is anything more than a large mutation.

I sometimes get the impression that all the rage for crossover in GA's is simply because crossover exists in nature. Although I realise I might be spouting ignorant foolishness here.

Quote:

Original post by RunningInt I realise crossover is useful in some model situations. But almost all of the problems i've tried GA's on I have never seen how crossover is anything more than a large mutation.

That's suggestive of trying to apply GAs to a search problem where they simply aren't appropriate... or of a bad encoding scheme (usually the latter).

Quote:

I sometimes get the impression that all the rage for crossover in GA's is simply because crossover exists in nature. Although I realise I might be spouting ignorant foolishness here.

If you remove crossover from a GA, then you are left merely with random-walk-hillclimbing...certainly an inefficient search method, but one that is easily applied to many domains (and almost any encoding).

The skill in efficient and successful application of a GA is getting the encoding scheme correct.

I really should re-publish an old thesis of mine on the analysis of GA operators and algorithmic performance... maybe over my xmas downtime...