8 Puzzle problem (Bài toán Ta canh)


#include <iostream>
using namespace std;
#define MAX 3

// the result state must be
int Final_State[MAX][MAX] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 0}
};

// initialize
int Current_State[MAX][MAX] = {
{0, 1, 3},
{4, 2, 5},
{7, 8, 6}
};

// moving step (0,-1) that means (i, j-1) => Move left
// moving step (-1,0) that means (i-1, j) => Move up
// moving step (0,+1) that means (i, j+1) => Move right
// moving step (+1,0) that means (i+1, j) => Move down
int di[4] = {0, -1, 0, +1};
int dj[4] = {-1, 0, +1, 0};

int DD[13][MAX][MAX];
int nDD = 0;
int step = 0;

void Swapper(int &a, int &b){ a = a^b; b = a^b; a = a^b; }

// find index of an element in matrix
int FindIndex(int a[MAX][MAX], int row, int column, int &rowIndex, int &columnIndex, int x){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(a[i][j] == x){
rowIndex = i;
columnIndex = j;
return 1;
}
}
}
return -1;
}

int TotalMoving(int T[MAX][MAX]){
int total = 0;
int rowIndex, columnIndex;
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T[i][j] != 0){
FindIndex(Final_State, MAX, MAX, rowIndex, columnIndex, T[i][j]);
total += (abs(rowIndex-i) + abs(columnIndex-j));
}
}
}
return total;
}

void ArrayCopy(int a[MAX][MAX], int b[MAX][MAX], int na, int nb){
for(int i=0; i<na; i++){
for(int j=0; j<nb; j++){
b[i][j] = a[i][j];
}
}
}

void PrintArray(int a[MAX][MAX], int row, int column){
for(int i=0; i<row; i++){
for(int j=0; j<column; j++){
cout << a[i][j] << " ";
}
cout << endl;
}
}

bool IsDuplicate(int T1[MAX][MAX], int T2[MAX][MAX]){
for(int i=0; i<MAX; i++){
for(int j=0; j<MAX; j++){
if(T1[i][j] != T2[i][j]){
return false;
}
}
}
return true;
}

bool IsVisited(int T[MAX][MAX]){
for(int i=0; i<nDD; i++){
if(IsDuplicate(T, DD[i])){
return true;
}
}
return false;
}

int Solve(){
int i0, j0;

int minSum;
int T[MAX][MAX];
int temp[MAX][MAX];

while(1){
cout <<"\nstep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
// param 0: find index of zero
FindIndex(Current_State, MAX, MAX, i0, j0, 0);

minSum = 100;
for(int count=0; count<4; count++){
int lci = i0 + di[count];
int lcj = j0 + dj[count];
if(lci >= 0 && lci < MAX && lcj >= 0 && lcj < MAX){
ArrayCopy(Current_State, temp, MAX, MAX);
Swapper(temp[i0][j0], temp[lci][lcj]);
int sum = TotalMoving(temp);
if(sum < minSum && IsVisited(temp) == false){
minSum = sum;
ArrayCopy(temp, T, MAX, MAX);
}
}
}
ArrayCopy(T, Current_State, MAX, MAX);
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
step++;
if(minSum == 0){
return 1;
}
if(step == 13){
return 0;
}
}
return 0;
}

int main()
{
ArrayCopy(Current_State, DD[nDD++], MAX, MAX);
if(Solve() == 0){
cout << "Failed !";
}
else{
cout << "\nStep " << step + 1 << ":" << endl;
PrintArray(Current_State, MAX, MAX);
cout << "\nSuccess!" << endl;
}
return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s