Number swapping game

Question

Number Swapping Game

---

The Initial Board Setup:

---

The Rules:

1. A move is made by selecting one of the 9 cells.
2. When a cell is selected, the number in that cell swaps places with the largest number in any adjacent cell (horizontally, vertically, or diagonally), but only if that number is larger than the number in the selected cell.
3. The letters do not move. They are labels for the cells, so that you can easily represent a list of moves.
4. A list of moves is made by simply putting the letters together, in order from left to right. For example, ADG

Note: Not all moves will change the board (such as the move I on move #1), so it's wise to not make those types of moves.

For example, after the move A is made on the initial board, the board looks like this:

Taking this example further, after another move is made, F, the board looks like this:

---

The Object of the Game:

Reverse the order of the numbers so that the board looks like this:

The answer that uses the fewest number of moves wins. I thought up this little puzzle today and created a simple program so that I could mess around with it, and after about an hour of trial and error, the shortest solution I ended up finding was 16 moves long. I have no idea if that is optimal.

So, if you find a solution that is 16 or less moves, I will upvote your answer.

To get marked as the accepted answer, you must prove that a certain number (16 or less) is optimal, whether by using brute force and sharing your code, or by some elegant proof (which is worded, as much as possible, so that most people can understand)

Answer 1

The minimum number of moves is 12 moves. A possible solution is:

123 A 523 B 563 D 563 E 563 F 563 H 563 E 563 G 563 C 567 B 587 E 587 A 987 
456   416   412   812   892   829   824   894   874   834   634   694   654 
789   789   789   749   741   741   791   721   921   921   921   321   321 

I solved this using a breadth first seach solution. The number of possible states is 9! = 362880 which makes a breadth first search possible.

Here is my incredibly slow code. I wanted to aim for corectness more than speed.

#include <iostream>
#include <queue>
#include <map>
using namespace std;

queue<string> Q;
map<string, int> D;
map<string, string> P;
map<string, string> M;

string next_state(string u, int x) {
    int r = x / 3;
    int c = x % 3;
    int mx = u[r * 3 + c], mr = r, mc = c;
    for(int i = r - 1; i <= r + 1; i++)
        for(int j = c - 1; j <= c + 1; j++) 
            if(i >= 0 && i < 3 && j >= 0 && j < 3) 
                if(u[i * 3 + j] > mx) {
                    mx = u[i * 3 + j];
                    mr = i;
                    mc = j;
                }

    char z = u[r * 3 + c];
    u[r * 3 + c] = u[mr * 3 + mc];
    u[mr * 3 + mc] = z;
    return u;
}

void bfs() {
    string u = "123456789", v;
    P[u] = u;
    D[u] = 1;
    Q.push(u);
    while(!Q.empty()) {
        u = Q.front();
        Q.pop();
        for(int i = 0; i < 9; i++) {
            v = next_state(u, i);
            if(D[v] == 0) {
                D[v] = D[u] + 1;
                P[v] = u;
                M[v] = i + 'A';
                Q.push(v);
            }
        }
    }   
}


int main() {
    bfs();

    string a, b, c, u = "987654321";
    a = b = c = "";
    while(P[u] != u) {
        a = M[u] + " " + u.substr(0,3) + " " + a;
        b = "  " + u.substr(3,3) + " " + b;
        c = "  " + u.substr(6,3) + " " + c;
        u = P[u];
    }
    cout << "123 " + a << endl << "456 " + b << endl << "789 " + c << endl;
}

Answer 2

Edit: I misread the question; this answer is incorrect as it overlooks diagonal movement.

LeppyR64 has brute forced the answer. There is, however, a simple proof that 12 moves is the minimum:

Define the disorder of an arrangement to be the sum of each square's distance, both horizontally and vertically, from its starting position. The disorder is initially 0, and that of the desired state can be easily calculated to be 24 (4 per corner, 2 per side, 0 for centre). Since each move shifts 2 pieces by 1 square each, the largest possible change in disorder from each move is 2. We therefore need at least 12 moves to reach the desired state.