# How to use GA to slove the 8 - puzzle?

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

## Recommended Posts

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

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

Greetz,

Illco

##### 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 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 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 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 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 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 on other sites
Are there any interesting question like TSP sloved by AG will very efficiency?

##### 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?

Edo

1. 1
Rutin
38
2. 2
3. 3
4. 4
5. 5

• 11
• 10
• 13
• 104
• 11
• ### Forum Statistics

• Total Topics
632977
• Total Posts
3009677
• ### Who's Online (See full list)

There are no registered users currently online

×