Problem Description:
There is a 3 * 3 chessboard, which is 0-89 numbers, 0 represents spaces, and other numbers can be exchanged with the 0. Seeking initial state
1 2 3
4 5 6
7 8 0
Solution to the minimum number of target status steps.
Input method:
E.g:
INPUT: from the keyboard:
1 2 3 7 4 5 8 0 6
OUTPUT:
Step: 1
1 2 3
4 5 6
7 8 0
Step: 2
1 2 3
4 5 0
7 8 6
Step: 3
1 2 3
4 0 5
7 8 6
Step: 4
1 2 3
0 4 5
7 8 6
Step: 5
1 2 3
7 4 5
0 8 6
STEP: 6
1 2 3
7 4 5
8 0 6
My program:
#include
#include
#include
Struct BSM
{
Int S [9];
INT preip, POS;
} AR1 [1000], AR2 [1000];
INT H1, R1, H2, R2, STEP
Struct BSM P;
INT PD (INT K)
{
INT I, J, B1, B2;
B1 = 1;
P.S [P.POS K] = P.s [P.POS] P.s [P.POS K];
P.S [p.pos] = p.s [p.pos k] -p.s [p.pos];
P.S [P.POS K] = P.s [P.POS K] -p.s [p.pos];
P.POS = P.pos K;
For (i = 0; i <= r1; i )
{
B2 = 0;
For (j = 0; j <9; j )
IF (! (AR1 [i] .S [j] == p.s [j])) b2 = 1;
B1 = b1 * b2;
}
Return (B1);
}
INT PD0 (INT K)
{
INT I, J, B1, B2;
B1 = 1;
P.S [P.POS K] = P.s [P.POS] P.s [P.POS K];
P.S [p.pos] = p.s [p.pos k] -p.s [p.pos];
P.S [P.POS K] = P.s [P.POS K] -p.s [p.pos];
P.POS = P.pos K;
For (i = 0; i <= r2; i )
{
B2 = 0;
For (j = 0; j <9; j )
IF (! (AR2 [i] .s [j] == p.s [j])) b2 = 1;
B1 = b1 * b2;
}
Return (B1);
}
INT PD1 ()
{
INT I, J, B1, B2;
B1 = 0;
For (i = H2; i <= r2; i )
{
B2 = 0;
For (j = 0; j <9; j )
IF (! (AR2 [i] .s [j] == p.s [j])) b2 = 1;
IF (0 == b2)
{
R2 = i;
B1 = 1;
}
}
Return (B1);
}
INT PD2 ()
{
INT I, J, B1, B2;
B1 = 0;
For (i = H1; i <= r1; i )
{
B2 = 0;
For (j = 0; j <9; j )
IF (! (AR1 [i] .S [j] == p.s [j])) b2 = 1; if (0 == b2)
{
R1 = i;
B1 = 1;
}
}
Return (B1);
}
Void OUT1 (Struct BSM M)
{
INT I, J;
Step ;
Printf ("Step:% D", STEP);
For (i = 0; i <9; i )
{
IF (0 == i% 3) Printf ("/ n");
Printf ("% d", m.s [i]);
}
While (! kbhit ());
i = getCH ();
Printf ("/ n");
}
void out ()
{
INT I, J, K;
Int Arr [1000];
J = -1;
While (r1> 0)
{
J = J 1;
Arr [J] = R1;
R1 = Ar1 [r1] .prep;
}
J = J 1;
Arr [J] = R1;
For (i = j; i> -1; i -)
{
OUT1 (AR1 [Arr [I]]);
}
While (R2> 0)
{
OUT1 (Ar2 [Ar2 [R2] .prep]);
R2 = ar2 [r2] .prep;
}
}
void main ()
{
INT I, J;
Step = 0;
For (i = 0; i <9; i )
{
Ar1 [0] .S [i] = (i 1)% 9;
Scanf ("% d", & ar2 [0] .s [i]);
IF (0 == Ar2 [0] .S [i]) Ar2 [0] .pos = i;
}
AR1 [0] .pos = 8;
AR1 [0] .prep = -1;
Ar2 [0] .prep = -1;
H1 = 0; R1 = 0; H2 = 0; R2 = 0;
While ((((h1 <= r1) && (R1 <999)) || ((H2 <= R2) && (R2 <999)))))
{
IF ((h1 <= r1) && (R1 <999))
{
P = Ar1 [h1];
IF (p.pos> 2)
{
IF (1 == PD (-3))
{
p.PREP = H1;
R1 ;
AR1 [R1] = P;
IF (1 == PD1 ())
{
OUT (); RETURN;
}
}
}
P = Ar1 [h1];
IF (p.pos% 3> 0)
{
IF (1 == Pd (-1)))
{
p.PREP = H1;
R1 ;
AR1 [R1] = P;
IF (1 == PD1 ())
{
OUT (); RETURN;
}
}
}
P = Ar1 [h1];
IF (P.POS <6)
{
IF (1 == Pd (3))
{
p.PREP = H1;
R1 ;
AR1 [R1] = P;
IF (1 == PD1 ())
{
OUT (); RETURN;
}
}
}
P = Ar1 [h1];
IF (p.pos% 3 <2)
{
IF (1 == Pd (1))
{
p.PREP = H1;
R1 ;
AR1 [R1] = P;
IF (1 == PD1 ())
{
OUT (); RETURN;
}
}
}
H1 ;
}
IF ((H2 <= R2) && (R2 <999))
{
P = Ar2 [H2];
IF (p.pos> 2)
{
IF (1 == PD0 (-3))
{
P.PREP = H2;
R2 ;
Ar2 [R2] = P;
IF (1 == PD2 ())
{
OUT (); RETURN;
}
}
}
P = Ar2 [H2];
IF (p.pos% 3> 0)
{
IF (1 == PD0 (-1))
{
P.PREP = H2;
R2 ;
Ar2 [R2] = P;
IF (1 == PD2 ())
{
OUT (); RETURN;
}
}
}
P = Ar2 [H2];
IF (P.POS <6)
{
IF (1 == PD0 (3))
{
P.PREP = H2;
R2 ;
Ar2 [R2] = P;
IF (1 == PD2 ())
{
OUT (); RETURN;
}
}
}
P = Ar2 [H2];
IF (p.pos% 3 <2)
{
IF (1 == PD0 (1))
{
P.PREP = H2;
R2 ;
Ar2 [R2] = P;
IF (1 == PD2 ())
{
OUT (); RETURN;
}
}
}
H2 ;
}
}
IF (Step == 0) Printf ("i cannot find the answer!");
}
