Number Swapping Game


The Initial Board Setup:

enter image description here


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:

enter image description here

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

enter image description here


The Object of the Game:

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

enter image description here

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)

  • 3
    I have been mentioned, thanks! – RE60K May 9 '15 at 8:08
  • @ADG haha it took me all day to get that comment! lol – JLee May 10 '15 at 0:16
  • Where is the link to the program you used? – EKons Aug 23 '16 at 14:47
up vote 8 down vote accepted

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;
}
  • I tried doing something like this (although in C) for almost two hours with no luck. The ~10 seconds this took to run definitely isn't slow compared to how long mine would have taken if I finished. I must be learning how to code the wrong way. – Quark May 9 '15 at 5:30
  • @Quark I could have used int for the states but string just made it simpler for swapping the digits. Int would have made it run a lot faster :) – LeppyR64 May 9 '15 at 15:39

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.

  • This doesn't quite work because a move can be made diagonally as in the first example, so each move could potentially change the disorder by 4. – OpiesDad Jun 12 '15 at 16:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.