Genetic Algorithm and Sudoku

AndyTang · 2005-12-07T12:59:00

I've recently been interested in Sudoku puzzles and I'm trying to figure out a way to generate the puzzles. At first I thought I could use a genetic algorithm to generate a puzzle through generation iterations as I heard a few people have already tried. Here lies the first stumbling block. I have a decent fitness method and I can choose two puzzles from the population (randomly generated grid filled with numbers) but I cannot figure out a way to cross breed these two grids. 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. Any suggestions? BTW, does any one knows what determines the difficulty of a sudoku problem? Is it just the number of missing spaces.

Artificial Intelligence Programming

Started by AndyTang November 04, 2005 11:22 AM

63 comments, last by Rockoon1 18 years, 5 months ago

AndyTang

122

Author

November 10, 2005 07:17 AM

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.

Martin Proud

124

November 11, 2005 06:35 AM

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

kevmo

205

November 13, 2005 01:04 AM

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.

Kylotan

10,512

November 14, 2005 08:59 AM

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.

Metorical

580

November 14, 2005 10:38 AM

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!

kevmo

205

November 14, 2005 11:14 PM

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.

Timkin

864

November 15, 2005 07:44 AM

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.

RPGeezus

216

November 15, 2005 12:38 PM

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.

------------------http://www.nentari.com

RunningInt

133

November 15, 2005 05:32 PM

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.

Timkin

864

November 15, 2005 07:17 PM

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

Genetic Algorithm and Sudoku

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Genetic Algorithm and Sudoku

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines