6*6 puzzle algorithm

Question

I have a 6*6 puzzle with 35 numbers(1~35) in a random sequence. Use the blank one as a 'register' and move the numbers one by one to let them be in order. I can deal with a 3*3 puzzle, but how to deal with a 6*6 one? Could you give me some hints?

Answer 1

The idea is the same, represent the problem as a states graph, and run shortest path algorithm.

If the efficiency of the algorithm is important, you might want an informed algorithm -such as A* algorithm, which is expected to be pretty fast (relative to the alternatives) with a good admissible heuristic function.
A slower though simpler solution can be running a BFS.

Both algorithms (A*, BFS) are both complete (always finds a solutuion, if one exists) and optimal (finds shortest path).

Also note, you can use macros to learn "good" series of moves, to get the algorithm faster. Ignore this improvement until you implement a working (though slow) solution.

---

EDIT: Coding guidelines:
Look at the problem as a graph: The graph will be G=(V,E) where V = { all possible states} and E = { (u,v) | can move from state u to state v within a single step }

Now, with this graph - you have a starting position (the source, which is given as input) and a target (a sorted puzzle). Start a BFS or A* (have a look at the pseudo code of these in the attached wikipedia links), to find a path from the source to the destination. You should start with BFS - it is simpler.
The path returned by the shortest path algorithm is identical to the series of moves you will have to do in order to get from the starting board to the target.

Note: You do not need to create the actual graph! you just need a to hold the starting node (source) - and create its vertex, and have a successors:V->2^V function, that gives you the successors for each vertex (formally: successors(v) = { (v,u) | (v,u) is in E } ). This way, you can build the relevant part of the graph on the fly.

Answer 2

I've studied this same problem/puzzle when I was in college and its a very interesting problem that involves AI and heuristic techniques and graph-theory. As stated by amit, you is strongly recommended to check A*, BFS and heuristics.

Here is my contribution: when trying to solve this, you can try a divide to conquer strategy. You can think that this 6x6 grid is just four 3x3 grids coupled close each other, and try to solve each one as separated cases in a given order.

For instance, you can try the following algorithm:

1. arrange your pieces in a manner that the left-upper grid contains all of its pieces, except one (that will be used as working space);
2. solve the left-upper grid;
3. arrange the right-upper grid in a manner that it contais all of its pieces, except the botttom-right one (that will be used as working space);
4. solve the right-upper grid;
5. ... and so on, independetly of the number of grids!

The final issue to say is that you must pay attention on which corner you gonna left as working space as you can't let the upper-right corner of the upper-right grid be your working space "missing pieces" because it will be not possible to put a piece there in future;

Ps1: working space is the position that you temporary let the piece missed, to be able to have a free space to maneuver pieces;

Ps2: in this context, grid is a combination of NxN pieces, that haves all the correct pieces, not necessarily in order.

Hope that I've helped in some way. :-)