number rotation game :)

[gregorynoob]

okay, i don't have a problem coding the game... that part would be easy. but the problem is to output the lease number of rotations needed to complete the game, so for example...
123 => 413
456 => 526
789 => 789
(rotation of the top left corner)
that's what it should look like after rotations.
now, i did some study, spent some time figuring the facts, and if i'm correct, the number of possible layouts of a 3*3 square is 9 factorial... which is uhmm... 362880. so even if i tried doing all the possible layouts, i wouldn't get the good result cause i have tho have the right sequence of operations... so, as i know nothing about the np-completeness.. (btw. is it?)i figured i better ask here as i really have no idea..

[Sky Diploma]

Whats your game all about? Please Explain?

[gregorynoob]

it's about having a board with 9 numbers, 1-9 obviously. they are organized in a 3*3 matrix.
the solved problem looks like:
123
456
789
the problem is, you are given a scrambled matrix, and you have to fix it using 4 possible moves, rotate top left 2*2, top right, bottom left, bottom right 2*2 square (for example in a solved board top left would be
12
45
).
you rotate them clockwise. so you gotta find the minimum sequence of operations to get the matrix in order.

[VernonDozier]

it's about having a board with 9 numbers, 1-9 obviously. they are organized in a 3*3 matrix.
the solved problem looks like:
123
456
789
the problem is, you are given a scrambled matrix, and you have to fix it using 4 possible moves, rotate top left 2*2, top right, bottom left, bottom right 2*2 square (for example in a solved board top left would be
12
45
).
you rotate them clockwise. so you gotta find the minimum sequence of operations to get the matrix in order.

Not a trivial problem at all, and a very interesting one. I'd say you could take at least two approaches. One, you can doodle around on paper with it and see if you can figure out the actual puzzle and an algorithm for it. I played around with it that way, but haven't solved it yet. If you actually find that you can solve this puzzle, see whether you can write down an algorithm of how you did it. Depending on that, try to program it.

Second option. Start with the solved puzzle.

1 2 3
4 5 6
7 8 9

You have four possible puzzles that are one step away from that:

4 1 3
5 2 6
7 8 9

1 5 2
4 6 3
7 8 9

1 2 3
7 4 6
8 5 9

1 2 3
4 8 5
7 9 6

Mark them as "solved" and mark the next move to make "solve" them (i.e. the proper rotation to make to solve them, represented perhaps as an integer from 1 to 4). So this is the set that can solved in one move. Then for each of these four orderings that can be solved in one move, make each of the four possible rotations. This is the set of orderings that can be solved in two moves. Mark them solved and save which rotation produced them. Then take all of those orderings and do each of four rotations. THOSE are now solved, so mark them solved and keep track of what rotation produced them. And so on. For each ordering that's just been solved, do each of the four rotations and get the new set of orderings that are solvable. You'll soon get rotations that have already been solved in fewer moves, so if something's already been solved, don't mark the new "solution", keep the old solution since that is fewer moves or the same number of moves.

Basically you are solving for ALL the combinations when you use this approach, not a single one, so it takes a long time, bu it only has to be done once. After that single run, save it to a file or a database. Then when you run it and enter a 3 x3 grid, it's much quicker because it's just looking the answer up. No calculation. It'll be pretty memory and space intensive and it's a brute force method, but with a 3 x3 grid, that's still small enough. If you start generalizing to 4 x 4 grids and 5 x 5 grids, the time and memory involved is going to get really big really quick, so you'd need a better method, but 3 x 3 should be small enough to be doable this way.

But again, it's a brute force approach. You may be able to find a non-brute-force mathematical algorithm to solve it.

[WaltP]

It's called a depth-first search since you know the maximum number of moves.

Start with the unsolved starting point
3 5 2
8 7 1
4 6 9
Then generate the first possibilities with upper-left
1)
832
751
469
saving this solution
Then rotate again,
2)
782
351
469
and again,
3)
372
581
469
and again,
4)
532
871
469
You are now at 4 moves with no solution.
Back up one move (to 3) and try the upper right corner, followed by the UpperLeft again.

IOW, you cycle through UL, UR, LR, LL each time you back up. And each time you back up, start again with the UL. Kind of like trying to solve a maze.

[gregorynoob]

@WaltP
umm, dfs? how do you mean dfs, what you mentioned seems like trying all possibilities...

[Sky Diploma]

Well Because You Are Trying All the possible nodes in order to get to the solution.

As You do when you are trying to find the shortest path.

It just needs you to find all possibilities on rotating the 2x2 matrix in order to get to the result.

And then look on what is the shortest way or the only way of finding the solution.

[gregorynoob]

hmm, but is there a way to shorten it, i got the concept of doing it recursively, but all i need is a limit for the number so i don't overflow the stack, also, is there a way to cut it on time by killing the constant factor of actually swapping all the 4 numbers in the matrix?

[Sky Diploma]

Well then you can go for vernon's second option. Though it prettymuch works in the same way as the first one. It might save time

[peterfosterfca]

where can i get the game?

[AmerJamil]

create your own logic and build it on C++ :)

[frogboy77]

it can be found on some very old nokia phones.