• Advertisement
Sign in to follow this  

How to use GA to slove the 8 - puzzle?

This topic is 4611 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How to use GA to slove the 8 - puzzle? Please offer your wisdom.

Share this post


Link to post
Share on other sites
Advertisement
First offer yours. What is the 8-puzzle? What have you discovered so far?

Greetz,

Illco

Share this post


Link to post
Share on other sites
A GA is probably not the best choice for the 8-puzzle. In fact, it may be a poor choice. You could compose your chromosome as a series of moves (left, right, up, down), but this will very likely get stuck in cycles (left, right, left, right, left, ...) and will need measures to prevent such cycles.

Why have you chosen GAs? Some insight on your decision would be helpful.

-Kirk

Share this post


Link to post
Share on other sites

I have an application with solves an 8-puzzle with Genetic Algorithms. Must be said, this is definately not the most effective or efficient way, but I just did it for fun.

If you want to solve the 8-puzzle (efficiently), you might want to look into A* (or even standard Backtracking will do). The way I coded it with a GA:

- You have a pool of chromosomes (30-50)
- Each chomosome has a number of genes (maximum number of moves you want to search).
- Each gene is a 2-bit value (1 0 for left, 0 1 for right etc...).

You either penalize chromosomes which contains illegal moves, or just ignore them. If you implement it the right way, it could be fast and would not get stuck in endless loops.

But then again, GA is not the optimal tool for this problem.

Edo

Share this post


Link to post
Share on other sites
If you are looking for efficient solutions to the n-queens problem, you may want to look into constraint satisfaction problems (CSP).

Share this post


Link to post
Share on other sites
Thanks all for answer my question, if you all said that GA is not the optimal tool to slove the 8-puzzle, I agree with it. But I only want to make some thing interesting to show the GA. Do you have some wanderful advice?

Share this post


Link to post
Share on other sites
The bin packing problem is usually a good start, or also known as the knapsack problem.

Given: You have a bag of a fixed volume or size and n items each with a specific volume/size and a value.

Problem: Which items would you put in the bag from the n items available tus to optimize the total value.

Solution: Binary coded GA

Share this post


Link to post
Share on other sites
If it is just for learning purposes and for an interesting demo, edtorpedo's advice is likely your best option. IMHO

-Kirk

Share this post


Link to post
Share on other sites
Are there any interesting question like TSP sloved by AG will very efficiency?

Share this post


Link to post
Share on other sites

Quote:

Are there any interesting question like TSP sloved by AG will very efficiency?


Ehmmm... what?

The thing with GA is: you can not guarantee that a solution given by a GA is the optimal solution or even the most efficient. I think you should look into the workings of Genetic Algorithms a bit further and just start experimenting with a few simple problems.

Found a nice example once:
You have a rectangular area filled with random circles, all with different diameters.
Question: what is the largest circle (ie a circle having the largest radius) you can fit in to that area without overlapping other circles?

Start your Algorithms!

Edo

Share this post


Link to post
Share on other sites
IF you Google for "traveling salesman problem genetic algorithm" you will find a long list of descriptions and demos.

-Kirk

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Question: what is the largest circle (ie a circle having the largest radius) you can fit in to that area without overlapping other circles?

that was a very wonderful question isn't it?
but what's the name of this question ?

Share this post


Link to post
Share on other sites
Question: what is the largest circle (ie a circle having the largest radius) you can fit in to that area without overlapping other circles?

that was a very wonderful question isn't it?
but what's the name of this question ?

Share this post


Link to post
Share on other sites

Quote:

that was a very wonderful question isn't it?
but what's the name of this question ?


I'm having trouble following you tczyp... It was actually a typical 'GA-problem'. Do you want the name of this problem? I don't think it has one...

Like to help you, but I don't quite understand what exactly you're asking for..

Cheers,

Edo

Share this post


Link to post
Share on other sites
I'm sorry to trouble you, My English is so poor, so that I can't express my mind(my thinking) correctly, But fortunately you catch it. If there no name of the question, are there some introduce to this question?(how to implement it...)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement