بازی معمای هشت ( ۸-puzzle ) یکی از بازی های فکری است که احتمالا در دوران بچگی همه ی ما با آن خود را سرگرم می کردیم.
در شکل زیر بازی معمای هشت را می بینید:
همین طور که می بینید ما یک صفحه ی ۳ در ۳ داریم که با ۸ کاشی با شماره های یک تا هشت پر شده اند. در این بازی شما می توانید کاشی های مجاور خانه ی خالی را هول دهید و به جای خانه ی خالی بیاورید مثالا فرض کنید کاشی شماره ی شش را به پایین هول دهیم. شکل زیر ظاهر می شود:
با این کار ما می توانیم جای کاشی ها رو عوض کنیم.
هدف از این بازی این است که کاشی ها را با جابه جایی به شکل زیر برسانیم و مسیری را که منتهی به جواب می شود را بدست بیاوریم:
ما این سوال را با استفاده از روش عقبگرد ( Back Tracking) که نوعی روش جست و جو است حل می کنیم.
برای اینکه بتوانیم از روش عقبگرد استفاده باید با درخت حالات استفاده کنیم.
فرض کنید به ما این پازل را داده اند حل کنیم:
ما اینجا در این وضعیت سه کار می توانیم بکنیم:
یک :
شش را به پایین حل بدهیم :
دو:
یا ۵ را به چپ حل بدهیم:
سه :
یا هفت را به راست هول بدهیم:
خوب الان تمام سه حالت ممکن را برای آن حالت تولید کردیم.حالا فرض کنید که برای این سه حالت جدید به دست آمده تمام حالتاشونو تولید کنیم ، درخت زیر به دست می آید که به آن گراف حالات می گویند.(با کلیک روی آن آن را در اندازه ی واقعی ببینید)
حالا ما با جست و جوی درخت بالا می توانیم به جواب برسیم
جست و جوی عقبگرد درخت را به صورت عمقی جست و جو می کند.یعنی از ریشه ی درخت شروع می کنیم و به پایین می رویم اگر به جواب رسیدیم جست و جو را متوقف می کنیم در غیر این صورت به پایین می رویم تا به برگ های درخت (نود هایی که بچه ندارند برسیم) بعد از اینکه به برگ رسیدیم دوباره از مسیری که پایین آمدیم بالا می رویم تا به نودی در مسیر برسیم که امکان پایین رفتن را به ما بدهد ،وقتی به آن نود رسیدیم دوباره شروع می کنیم به پایین رفتن از درخت . این کار را تا زمانی که به جواب برسیم دونبال می کنیم.
در شکل بالا گره ها شماره گذاری شده است ، جست و جو به روش عقبگرد در دخت بالا به شکل زیر است:
۱ ,۲ ,۵,۱۰,۲۰
به ته درخت رسیدیم آن قدر بالا می رویم تا به نودی برسیم که بتوانیم از آن پایین بیاییم که اگر از مسیری که آمده ایم به عقب برگردیم اولین نودی که می توانیم از آن پایین برویم گره ی ۵ است که اگر از آن پایین برویم به مسیر زیر به دست می آید:
۱,۲,۵,۱۱,۲۱
به جواب نرسیدیم دوباره کار قبل را تکرار می کنیم تا به جواب برسیم مسیر های زیر مسیرهایی است که تارسیدن به جواب تولید می شود
۱,۲,۵,۱۱,۲۲
۱,۲,۵,۱۱,۲۳
۱,۳,۶,۱۲,۲۴
۱,۳,۶,۱۳,۲۵
۱,۳,۷,۱۴,۲۶,۲۷
مسیر (۱,۳,۷,۱۴,۲۶,۲۷) به حل سوال منتهی می شود پس به جواب رسیده ایم و جست و جوی درخت را متوقف می کنیم.مسیر به دست آمده با خط پر رنگ در شکل مشخص شده است.
آیا قبل از حل مساله باید درخت حالات را تولید کرد و بعد در آن جست و جو کنیم؟
خیر ، اگر بخواهیم کل درخت را بسازیم و بعد در آن جست و جو کنیم حافظه خیلی زیادی را باید مصرف کنیم ، بهمین خاطر در حین حل مسیله درخت را می سازیم.
شاید یک سوال برای شما پیش آمده باشد و آن این است که چرا ما درخت حالت را تا عمق خاصی ساخته ایم در حالی که تا بی نهایت ممکن است عمق درخ ادامه داشته باشد؟
خوب دلیلش این است که حافظه ی کامپیوتر محدود است و ما نمی توانیم از یک عمقی به بعد را در نظر بگیریم و به همین دلیل درخت حالات را تا یک عمق مشخص پیمایش می کنیم
حالا بریم سراغ کد برنامه :
تابع مقایسه ی دو آرایه ی دو بعدی :
a و b دو آرایه ای هستند که قرار است مقایسه شوند و به صورت اشاره گر به تابع فرستاده شده اند.
n هم طول و عرض آرایه است.
خروجی به صورت bool است که یا مقدار True را دارد یا False.
bool compareToArray(int **a, int **b, int n)
{
bool equality = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i][j] != b[i][j])
{
equality = false;
}
}
}
return equality;
}
تابع حل سوال n puzzle :
این تابع n را می گیرد و مشخص می کند پازل شما چند در چند است و فقط مختص به هشت پازل نیست مثالا ما اگر بخواهیم هشت پازل را حل کنیم پازل را در یک آرایه ی سه در سه می ریزیم بنابر این n برابر سه می شود.
این تابع به صورت بازگشتی است.
int **current_status : آرایه ی دو بعدی است که حالتی از پازل است که باید آن را حل کنیم
int **goal_status : آرایه ای دو بعدی است که هدف بازی است و باید به آن برسیم
در آریه ی پازل خانه ی خالی را با صفر نمایش می دهیم.
vector <int> *path : وکتوری از جنس اعداد صحیح است که مسیری را طی کرده ایم در آن قرار دارد که اعداد در آن به شرح زیر است:
۰: یعنی خانه ی خالی در پازل را به سمت بالا برده ایم
۱: یعنی خانه ی خالی در پازل را به سمت چپ برده ایم
۲: یعنی خانه ی خالی در پازل را به سمت پایین برده ایم
۳: یعنی خانه ی خالی در پازل را به سمت راست برده ایم
int deep: حداکثر عمق درختی است که ما می توانیم به در درخت پیش برویم. اولین بار هنگام فراخوانی به deep مقدار ۱- را می دهیم.
int i_zeroPoint : مختصات i کاشی خالی است.
int j_zeroPoint : مختصات j کاشی خالی است.
int lastMove: حرکت قبلیمان در آن است تا دوباره آن را تکرار نکنیم و به مرحله ی قبل برویم. چون اگر به مرحله قبل برویم ممکن است توی حلقه ی هایی بی افتیم که مدت حل سوال را زیاد می کند. البته از vector <int> *path هم می توانستیم جای lastMove استفاده کنیم!
این تابع بازگشتی است و درخت را در خودش می سازد.
تابع حل مسیله ی puzzle , Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square , هشت پازل , شانزده پازل , پازل , n پازل ، معمای هشت
bool eightPuzzle(int **current_status, int **goal_status, vector <int> *path, int n, int deep, int i_zeroPoint, int j_zeroPoint, int lastMove)
{
if (compareToArray(current_status, goal_status, n))
{
return true;
}
if (deep > 20)
{
path->pop_back();
return false;
}
for (int i = 0; i < 4; i++)
{
if ((lastMove == 0 && i == 2) || (lastMove == 2 && i == 0))
{
continue;
}
if ((lastMove == 1 && i == 3) || (lastMove == 3 && i == 1))
{
continue;
}
switch (i)
{
case 0:
{
//Up
if (i_zeroPoint - 1 >= 0 )
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint - 1][j_zeroPoint];
current_status[i_zeroPoint - 1][j_zeroPoint] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint - 1, j_zeroPoint, i))
{
current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
case 1:
{
//Left
if (j_zeroPoint - 1 >= 0)
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint - 1];
current_status[i_zeroPoint][j_zeroPoint - 1] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint - 1, i))
{
current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
case 2:
{
//Down
if (i_zeroPoint + 1 < n)
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint + 1][j_zeroPoint];
current_status[i_zeroPoint + 1][j_zeroPoint] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint + 1, j_zeroPoint, i))
{
current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
case 3:
{
//Right
if (j_zeroPoint + 1 < n)
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint + 1];
current_status[i_zeroPoint][j_zeroPoint + 1] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint + 1, i))
{
current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
default:
break;
}
}
path->pop_back();
return false;
}
تابع showPath :
این تابع حرکاتی را که باید روی خانه ی خالی انجام دهیم را که در وکتور vector <int>* path قرار دارد روی حالت اولیه انجام می دهد و قدم به قدم پازل حل شده را نمایش می دهد.
void showPath(int **current_status, int **goal_status, vector <int> *path, int n,int i_zeroPoint, int j_zeroPoint)
{
int lasti;
int lastj;
std::cout << "goal state:" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (goal_status[i][j] == 0)
{
std::cout << " " << " ";
continue;
}
std::cout << goal_status[i][j] << " ";
}
std::cout << endl;
}
std::cout << endl;
std::cout << "start state:" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (current_status[i][j] == 0)
{
std::cout << " " << " ";
continue;
}
std::cout << current_status[i][j] << " ";
}
std::cout << endl;
}
std::cout << endl;
int **temp = new int*[3];
for (int i = 0; i < 3; i++)
{
temp[i] = new int[3];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
temp[i][j] = current_status[i][j];
if (temp[i][j] == 0)
{
lasti = i;
lastj = j;
}
}
}
std::cout << "Number of total Step " << path->size() << "." << endl << endl;
for (int i = 0; i < path->size(); i++)
{
std::cout << "Step " << i + 1 << ":"<< endl;
switch (path->at(i))
{
case 0:
{
temp[lasti][lastj] = temp[lasti - 1][lastj];
temp[lasti - 1][lastj] = 0;
lasti = lasti - 1;
break;
}
case 1:
{
temp[lasti][lastj] = temp[lasti][lastj - 1];
temp[lasti][lastj - 1] = 0;
lastj = lastj - 1;
break;
}
case 2:
{
temp[lasti][lastj] = temp[lasti + 1][lastj];
temp[lasti + 1][lastj] = 0;
lasti = lasti + 1;
break;
}
case 3:
{
temp[lasti][lastj] = temp[lasti][lastj + 1];
temp[lasti][lastj + 1] = 0;
lastj = lastj + 1;
break;
}
default:
break;
}
//
for (int p = 0; p < n; p++)
{
for (int q = 0; q < n; q++)
{
if (temp[p][q] == 0)
{
std::cout << " " << " ";
continue;
}
std::cout << temp[p][q] << " ";
}
std::cout << endl;
}
std::cout << endl;
//
}
std::cout << endl;
}
در زیر کد کلی برنامه هشت پازل (معمای هشت) را با سی پلاس پلاس می بینید که در Main آن یک مثال به به تابع فرستاده شده:
(قبل از نوشتن کد یک عکس از خروجی را قرار داده ام)
// 8-puzzle-back tracking.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
bool compareToArray(int **a, int **b, int n)
{
bool equality = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (a[i][j] != b[i][j])
{
equality = false;
}
}
}
return equality;
}
bool eightPuzzle(int **current_status, int **goal_status, vector <int> *path, int n, int deep, int i_zeroPoint, int j_zeroPoint, int lastMove)
{
if (compareToArray(current_status, goal_status, n))
{
return true;
}
if (deep > 20)
{
path->pop_back();
return false;
}
for (int i = 0; i < 4; i++)
{
if ((lastMove == 0 && i == 2) || (lastMove == 2 && i == 0))
{
continue;
}
if ((lastMove == 1 && i == 3) || (lastMove == 3 && i == 1))
{
continue;
}
switch (i)
{
case 0:
{
//Up
if (i_zeroPoint - 1 >= 0 )
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint - 1][j_zeroPoint];
current_status[i_zeroPoint - 1][j_zeroPoint] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint - 1, j_zeroPoint, i))
{
current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint - 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
case 1:
{
//Left
if (j_zeroPoint - 1 >= 0)
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint - 1];
current_status[i_zeroPoint][j_zeroPoint - 1] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint - 1, i))
{
current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint][j_zeroPoint - 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
case 2:
{
//Down
if (i_zeroPoint + 1 < n)
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint + 1][j_zeroPoint];
current_status[i_zeroPoint + 1][j_zeroPoint] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint + 1, j_zeroPoint, i))
{
current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint + 1][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
case 3:
{
//Right
if (j_zeroPoint + 1 < n)
{
current_status[i_zeroPoint][j_zeroPoint] = current_status[i_zeroPoint][j_zeroPoint + 1];
current_status[i_zeroPoint][j_zeroPoint + 1] = 0;
path->push_back(i);
if (eightPuzzle(current_status, goal_status, path, n, deep + 1, i_zeroPoint, j_zeroPoint + 1, i))
{
current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
return true;
}
current_status[i_zeroPoint][j_zeroPoint + 1] = current_status[i_zeroPoint][j_zeroPoint];
current_status[i_zeroPoint][j_zeroPoint] = 0;
}
break;
}
default:
break;
}
}
path->pop_back();
return false;
}
void showPath(int **current_status, int **goal_status, vector <int> *path, int n,int i_zeroPoint, int j_zeroPoint)
{
int lasti;
int lastj;
std::cout << "goal state:" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (goal_status[i][j] == 0)
{
std::cout << " " << " ";
continue;
}
std::cout << goal_status[i][j] << " ";
}
std::cout << endl;
}
std::cout << endl;
std::cout << "start state:" << endl;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (current_status[i][j] == 0)
{
std::cout << " " << " ";
continue;
}
std::cout << current_status[i][j] << " ";
}
std::cout << endl;
}
std::cout << endl;
int **temp = new int*[3];
for (int i = 0; i < 3; i++)
{
temp[i] = new int[3];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
temp[i][j] = current_status[i][j];
if (temp[i][j] == 0)
{
lasti = i;
lastj = j;
}
}
}
std::cout << "Number of total Step " << path->size() << "." << endl << endl;
for (int i = 0; i < path->size(); i++)
{
std::cout << "Step " << i + 1 << ":"<< endl;
switch (path->at(i))
{
case 0:
{
temp[lasti][lastj] = temp[lasti - 1][lastj];
temp[lasti - 1][lastj] = 0;
lasti = lasti - 1;
break;
}
case 1:
{
temp[lasti][lastj] = temp[lasti][lastj - 1];
temp[lasti][lastj - 1] = 0;
lastj = lastj - 1;
break;
}
case 2:
{
temp[lasti][lastj] = temp[lasti + 1][lastj];
temp[lasti + 1][lastj] = 0;
lasti = lasti + 1;
break;
}
case 3:
{
temp[lasti][lastj] = temp[lasti][lastj + 1];
temp[lasti][lastj + 1] = 0;
lastj = lastj + 1;
break;
}
default:
break;
}
//
for (int p = 0; p < n; p++)
{
for (int q = 0; q < n; q++)
{
if (temp[p][q] == 0)
{
std::cout << " " << " ";
continue;
}
std::cout << temp[p][q] << " ";
}
std::cout << endl;
}
std::cout << endl;
//open-mind.ir
}
std::cout << endl;
}
int main()
{
vector<int> *path = new vector<int>;
int **current_status = new int*[3];
for (int i = 0; i < 3; i++)
{
current_status[i] = new int[3];
}
int **goal_status = new int*[3];
for (int i = 0; i < 3; i++)
{
goal_status[i] = new int[3];
}
current_status[0][0] = 2;
current_status[0][1] = 8;
current_status[0][2] = 3;
current_status[1][0] = 1;
current_status[1][1] = 6;
current_status[1][2] = 4;
current_status[2][0] = 7;
current_status[2][1] = 0;
current_status[2][2] = 5;
goal_status[0][0] = 1;
goal_status[0][1] = 2;
goal_status[0][2] = 3;
goal_status[1][0] = 8;
goal_status[1][1] = 0;
goal_status[1][2] = 4;
goal_status[2][0] = 7;
goal_status[2][1] = 6;
goal_status[2][2] = 5;
eightPuzzle(current_status, goal_status, path, 3,0, 2, 1,-1);
showPath(current_status, goal_status, path, 3, 2,1);
return 0;
}
