in this program i use the Breadth-first algorithms to solve transposition Puzzle Games, each node has four derection to move, and in the path[], i record each of the state,when the aim matrix has been found, get out of the program, but found that process into the cycle of loop and did not get out: (
some error with the red part in my program????/
Code:
#include<iostream>
using namespace std;
const int N = 3;
#define blank 0
//record every matrix in the transform path step by step to the aim
struct node {
int nodesun[N][N];
int pre;
int x, y;//record the blank's place
} path[4000];
int zx[4] = { -1, 0, 1, 0 };
int zy[4] = { 0, -1, 0, 1 };
int front, rear;
int desti[N][N];//the aim matrix
//check the state of the one in the path array
int detect(struct node *p) {
int i, j;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
if (p->nodesun[i][j] != desti[i][j])
return 0;
return 1;
}
//print the change state
void printlj() {
int tempt;
int i, j;
tempt = rear;
while (tempt != 0) {
for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
cout << path[tempt].nodesun[i][j] << " ";
if (j == N - 1)
cout << endl;
}
tempt = path[tempt].pre;
cout << endl;
}
}
int main() {
int i, j, m, n, f;
int ii,jj;
int temp, find = 0;
front = rear = 1;
path[1].pre = 0;
path[1].y = 2;
path[1].x = 2;
//initialize the two matrix
/*
the begin matrix is like:
5 8 7
1 2 4
3 6
the aim matrix is like:
1 2 3
4 5 6
7 8
*/
int index = 0;
int a[9] = { 5, 8, 7, 1, 2, 4, 3, 6, 0 };
for (i = 0; i < N; i++)
for (j = 0; j < N; j++) {
path[1].nodesun[i][j] = a[index++];
desti[i][j] = index;
}
desti[2][2] = blank;
path[1].nodesun[2][2] = blank;
while (front <= rear && !find) {
m = path[front].x;
n = path[front].y;
for (f = 0; f < 4; f++) {
ii = m + zx[f];
jj = n + zy[f];
if (ii >= 0 && ii < N && jj >= 0 && jj < N) {
rear++;
//path[rear] = path[front];
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
path[rear].nodesun[i][j] = path[front].nodesun[i][j];
path[rear].nodesun[m][n] = path[front].nodesun[ii][jj];
path[rear].nodesun[ii][jj] = blank;
path[rear].pre = front;
path[rear].x = ii;
path[rear].y = jj;
if (detect(&path[rear])) {
cout<<"find"<<endl;
printlj();
find = 1;
break;
}
}
}
front++;
}
cout<<"end OK"<<endl;
return 0;
}