0

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.