I want to make a program that will solve the Rotation puzzle that you can find on Nokia cellphones. For those of you who do not know it, it''s a 9x9 board with numbers 1-9 and you can rotate each 2x2 square. You need to arrange the board so that the numbers are in the correct order. It seems easy enough to use A* to do it, but for that I need a heuristic. That is, I need to know how close I am to the solution. I tried many things but it''s quite diffcult finding a mathmatical way to evaluate this, since the board changes quite drastically every move. Is there a way to make a heuristic or is it all trial-and-error? Thanks, Kalugny

One obvious heuristic is to use the amount of pieces that are already on their correct places. At least it should be better than no heuristic at all

Well, of course.
But that''s no good.
Look at this:

2 5 3
1 4 6
7 8 9

You can solve this in one move: rotate the top-left 2x2 square clockwise. But there are 4 numbers not in place.
Here:

1 2 3
5 4 6
7 8 9

There are only 2 out of place but you can''t solve this in a few easy steps.

As long as a heuristic does not overestimate it is ok, however a heuristic that is closer to the actual value (number of steps etc.) will (i think it''s proved) work better.
Number of numbers out of place is not a very good (and possibly invalid) heuristic because it does not neccessarily have a direct relation to the number of ''moves'' that will be required to solve the puzzle. A better heuristic would be along the lines of number of rotations required to solve the puzzle. You coould try using the minimum number of rotations to get each number into place (vaguely similar to using manhattan distance in nxn puzzle), you would need to come up with a heuristic that could, to some extent, take into account that multiple numbers can move at once. If you wanted to try something very simple though, the simplest heuristic i can think of right now, is
for each number, the sum of the minimum number of rotations to get that number into place divided by 4.
So, for your first example, with 4 numbers out of place, each number out of place is a single roatation from it''s correct position, so the sum of rotations = 4, divided by 4 your heuristic would give the value 1. (yay)
for your second example, you would get 0.5 (round up to 1 because you have to perform a full rotation) which isn''t anywhere near as nice a value, but hey, i did say it was a simple heuristic a more complex heuristic might take into account that those two numbers would require an opposite rotation and adjust itself.
Oh, and importantly, if all the numbers are in the right place, it will require 0 rotations, and 0 / 4 is 0.
Hope that helps at least a little

Thanks, that is something to start with, but it won''t do.
Even in the second example it ends up as a 1. One rotation to get 4 to it''s proper place and 3 to get 5 to it''s proper place (all rotations are clockwise). But why divide by 4? Let''s take the maximum number of rotations for any one piece. If we do, then the first example get''s a 1, and the second get''s a 3.

But here are a number of other interesting states to look at:

2 6 4
1 3 5 Notice that this one can be solved by 3 rotations.
7 8 9

Using this method, this get''s a score of 3 as well (due to the 4) even though it''s a lot easier than the second example posted before.

Kal,

I think he meant take all the numbers, and how many rotations it''ll take to get them in their proper place. So, in example #1 of yours, it''ss take 1 rotation to get 1 to the proper place, 1 rotation for 2, 1 rotation for 4 and 1 rotation for 5. 1+1+1+1 = 4/4 = 1

Yeah, sure, I got that.
It''s a nice idea I haven''t thought of before, bu it doesn''t solve the problem. Besides, I don''t see the point in deviding by 4.

But I return to the question I asked before: Is it all really just trial and error? Is there no way to construct a heuristic logically?

The point of dividing by 4 was this:
During a rotation, you move 4 numbers at a time, therefore it is possible (as noted in your first example) for 4 numbers to be out of place, and then, after a single rotation thos 4 numbers will be in the correct place. So with 4 numbers moving at a time, rather than 1, this must be taken into account in the heuristic because the heurisitic will not work as efficiently if it overestimates. It''s easy to see that in example 1 4 would be an overestimate , so it is neccessary to divide by 4 so that in no case will the heurisitic overestimate.

The fact that you can only move clockwise is an important piece of the puzzle you didn''t mention before

You can construct a heuristic logically according to "AI: A Modern Approach", it suggests using the relaxed problem approach, which means removing some of the rules governing the puzzle to make the problem easier. For instance you might remove the rule the numbers have to rotate, instead you could ''replace'' that with ''move the 4 numbers in a 2x2 square to anywhere else on the board''. Then you can just use a heuristic basically the same as the first AP, where you just use the number of pieces that are out of place (divided by 4). Without making the heurisitc a lot more complicated, i really can''t think of a way to get around using the divide by 4, because you really must make sure the heuristic doesn''t overestimate to be effective (solve the puzzle in the minimum number of steps). There is also a suggestion that you can come up with a number of equally good heuristics, and just use max(h1, h2,...hn) as the current heuristic.
It''s not trial and error coming up with a heuristic...it might be trial and error coming up with a really good, or best, heuristic. Try using the relaxed problem approach to create a few heuristics.

I have not seen the particular puzzle you are talking about as I do not own a Nokia phone... however, it basically sounds like the 8-puzzle... assuming that it IS the 8-puzzle, there are two widely accepted and well known heuristics for this problem.

Heuristic 1: The number of tiles NOT currently in their correct position. Since each tile not in its correct position will have to move at least 1 square then this heuristic is guaranteed never to overestimate the actual distance to be moved;

and,

Heuristic 2: The Manhattan Distance , which is the sum of horizontal and vertical movements required to move the piece from its current position to its correct position (assuming no other pieces on the board to block it). So, for example, the number 4 is in the position of number 8, so there is 1 horizontal and 1 vertical move required to move it to the number 4 position, so the heuristic cost for that node in the search tree is 4.

Cheers,

Timkin

[edited by - Timkin on May 1, 2002 11:44:42 PM]

It might help to read the post Timkin
The puzzle as stated above is to get all the numbers into the right place by a series of clockwise rotations of 4 numbers (in a 2x2 square) at a time.
Now get back to work on your PhD