Shuffling a 3x3 matrix

[magnum7]

Hello,

I've been trying to solve a problem for quite a few hours.
There's a 3x3 matrix with the digits 1-9 randomly placed. The task is to palce the digits in a particular order so that every number formed on a column or roll or diagonal can be devided by 3. The only way to shuffle is to swap positions of digits that are next to each other.
Example:

1 2 3
4 5 6
7 8 9

1 can be swapped with 2, 2 with 3, 4 with 7 but not 1 with 5.
What i want is to shuffle the matrix by all possible ways and save the shortest one. My code is getting stuck right after the 2nd move. Here it is:

#include <iostream> 
using namespace std;
int sp[9][4]=
{

    { 1, 3,-1,-1 }, //0
    { 0, 2, 4,-1 }, //1        
    { 1, 5,-1,-1 }, //2       0 1 2
    { 0, 4, 6,-1 }, //3       3 4 5
    { 2, 3, 5, 7 }, //4       6 7 8
    { 2, 4, 8,-1 }, //5
    { 3, 7,-1,-1 }, //6
    { 4, 6, 8,-1 }, //7
    { 5, 7,-1,-1 }  //8
};
int c[8],sum=2000000000;
void rec(int a, int b, int tsum)
{
    int temp,i,j,k;
    if(sum>1)
    {
        if(((c[0]*100+c[4]*10+c[8])%3+(c[0]*100+c[1]*10+c[2])%3+(c[2]*100+c[4]*10+c[6])%3+
        (c[0]*100+c[3]*10+c[6])%3+(c[1]*100+c[4]*10+c[7])%3+(c[2]*100+c[5]*10+c[8])%3+
        (c[3]*100+c[4]*10+c[5])%3+(c[6]*100+c[7]*10+c[8])%3)==0)
        {
            if(sum>tsum) sum=tsum;
        }
        else
        {
            for(j=0;j<=8;j++)
                for(i=0;i<=8;i++)
                    if((sp[i][j]>-1) && !((i==a || i==b) && (sp[i][j]==a || sp[i][j]==b)))
                    {
                        tsum+=1;
                        cout<<i<<" "<<sp[i][j]<<" "<<endl;
                        system("pause");
                        temp=c[i];
                        c[i]=c[sp[i][j]];
                        c[sp[i][j]]=temp;
                        rec(i,sp[i][j],tsum);
                    }
        }        
    }           
}
int main()
{
    int i;
    bool san=false;
    for(i=0;i<=8;i++)
        cin>>c[i];
    rec(-1,-1, 0);
    cout<<sum<<endl;
    cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<endl;
    cout<<c[3]<<" "<<c[4]<<" "<<c[5]<<endl;
    cout<<c[6]<<" "<<c[7]<<" "<<c[8]<<endl;
    system("pause");
    return 0;
}

The 1st global array indicates which positions can be swapped. -1 means none.
Please excuse me for the bad english. Help will be much apriciated.

[shasha821110]

kind of couldn't understand you??

[VernonDozier]

First nail down the algorithm. I can't comment on the code, really, because it's not clear to me what the algorithm to solve this is in your case. I understand the objective. I guess this is a brute-force "dumb" method (the word "dumb" here intended as descriptive rather than pejorative). You simply go through every possible shuffle till you get one that works? If that's so, then I guess maybe I DO understand the algorithm. That big nested for-loop shuffles, I imagine, but I think you need to throw in some comments and explanation of what variables stand for what for this to be readable.

[magnum7]

First nail down the algorithm. I can't comment on the code, really, because it's not clear to me what the algorithm to solve this is in your case. I understand the objective. I guess this is a brute-force "dumb" method (the word "dumb" here intended as descriptive rather than pejorative). You simply go through every possible shuffle till you get one that works? If that's so, then I guess maybe I DO understand the algorithm. That big nested for-loop shuffles, I imagine, but I think you need to throw in some comments and explanation of what variables stand for what for this to be readable.

You've understood correctly. Indeed it's a brute-froce method. The problem has no time limit. Thats why i thought it would be easyer like this. Please reply with your idea!

The code itself works. All i need is the algorithm. I'll try to comment it.

[StuXYZ]

Let us see what we can do if we think about the algorithm.

Let us start with a brute force algorithm. There are 9! ways to rearrange that 3x3 matrix (362880). BUT there are an infinite number of paths to go between any two matrix configurations.

So the SIMPLISTIC brute force method says that you create all possible patterns, and calculate their connecting graphs (those that can be obtained with one move.) and then find a route from your current position to the new position(s)!

[Sorry, I understood that you have one starting position (unknow at compile time) and a end condition that allows many end positions. I may well have mis-understood you.]

I don't think I like that algorithm !!! It is horrific. The only thing going for it is that you have so many possibilities to make a move that the average exchange.

Ok, can we come up with another SIMPLE method. There are some other possible ways. You can use a routine that I recall as the A* (a-star) route finding algorithm.

I haven't looked it up, it was in a 6502 assembler book I read when I was a teenager. [oh I am that old :( ]. Anyway the method is as follows:

(a) score the current position relative to the win metric.
(b) Make all possible moves and score them.
(c) If a move increases the score keep the best (repeat from (a))
(d) if not back track one move and find the second best etc.

Ok, that isn't 100% robust, it has a few problems, it mostly works for highly connected maps (your is). After you have a route (any)
you can then do refinement of sub sections, to find the best route.

That should be "relatively" easy to code.

Comments by all welcome. I am 99.99% sure there are other better algorithms, both simpler to code and quicker/robust etc.

I almost think this thread should be in algorithms -- then moved to here after code is written.

[VernonDozier]

Hello,
My code is getting stuck right after the 2nd move.

The code itself works. All i need is the algorithm.

This is a contradiction, isn't it? Does the code work or does the code not work? Does the code work and you need a better algorithm or do you like the algorithm, but want to change the code, or do you like neither and want to change to a non-brute-force algorithm and change the code as well? The code has to change if the algorithm changes, obviously.

[magnum7]

#include <iostream> 
using namespace std;
int sp[9][4]=
{

    { 1, 3,-1,-1 }, //0    Positions that can be swaped 
    { 0, 2, 4,-1 }, //1        
    { 1, 5,-1,-1 }, //2       0 1 2
    { 0, 4, 6,-1 }, //3       3 4 5
    { 2, 3, 5, 7 }, //4       6 7 8
    { 2, 4, 8,-1 }, //5
    { 3, 7,-1,-1 }, //6
    { 4, 6, 8,-1 }, //7
    { 5, 7,-1,-1 }  //8
};
int c[8],sum=2000000000; // c- actual values on positions; sum- number of minimal swaps.
void rec(int a, b, int tsum) // a,b- positions previously swaped, tsum - temporary sum of swaps
{
    int temp,i,j,k;
    if(sum>1) // if sum=0 or sum=1 that means there can't be any better ways to solve it
    {
        if(((c[0]*100+c[4]*10+c[8])%3+(c[0]*100+c[1]*10+c[2])%3+(c[2]*100+c[4]*10+c[6])%3+
        (c[0]*100+c[3]*10+c[6])%3+(c[1]*100+c[4]*10+c[7])%3+(c[2]*100+c[5]*10+c[8])%3+
        (c[3]*100+c[4]*10+c[5])%3+(c[6]*100+c[7]*10+c[8])%3)==0) //check if the columns, diagonals and rolls can be devided by 3
        {
            if(sum>tsum) sum=tsum; //then take the tsum in case its smaller than the current one
        }
        else
        {
            for(i=p;i<=8;i++) // THIS PART I NEED HELP WITH
                for(j=0;j<=8;j++)
                    if((sp[i][j]>-1) && !((i==a || i==b) && (sp[i][j]==a || sp[i][j]==b))) // if swap is possible and haven't been done last time
                    {
                        tsum+=1;
                        temp=c[i]; //swap
                        c[i]=c[sp[i][j]];
                        c[sp[i][j]]=temp;
                        rec(i,sp[i][j],tsum);
                    }
        }        
    }           
}
int main()
{
    int i;
    bool san=false;
    for(i=0;i<=8;i++)
        cin>>c[i];
    rec(-1,-1, 0);// -1,-1 means that there haven't been a swap before. tsum is 0 in the beginning.
    cout<<sum<<endl;
    cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<endl;
    cout<<c[3]<<" "<<c[4]<<" "<<c[5]<<endl;
    cout<<c[6]<<" "<<c[7]<<" "<<c[8]<<endl;
    system("pause");
    return 0;
}

Hope this makes it clearer.

[StuXYZ]

I wish to comment again, since I now have understood what you are doing!!!! -- Well at least the problem, the code that is a different problem.

Let me see you want to get a position were the columns/ rows AND diagonals all sum up to numbers as a factor 3.

Now let us do this on a piece of paper. Then you will see that you really don't need much computer code.

First question should be given 9 random numbers CAN it be done.
Let us consider the problem: There are three rows, three columns and two diagonals. To get all of them to add up correctly, you need
to change the problem to a matrix of remainders. It doesn't matter if the number is 983231 or 2 both have the same remainder on division by 3.

Convert the numbers to 0,1,2 (or I prefer -1,0,1 but it is unimportant).
Now you add everything up, if the sum is not 0,9 or18 then you can't do the problem.

Next you have to find a solution:
You are aided by the fact that the contributions are
4 points (2 times) [outside middles]
4 points (3 times) [corners]
1 point (4 times) [centre]

The solution has to be symmetric, and the solutions (with the multiplication for occurance must again be a factor of 3).

There are a small set of symmetric graphs and it is quick to find how to transform yours. You only have a maximium of 6 moves I think.

[VernonDozier]

To get all of them to add up correctly, you need
to change the problem to a matrix of remainders. It doesn't matter if the number is 983231 or 2 both have the same remainder on division by 3.

Convert the numbers to 0,1,2 (or I prefer -1,0,1 but it is unimportant).

Nice reduction of the problem to something more manageable. This should simplify both the algorithm and the coding.